PHP.SU

Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (9): « 1 2 3 [4] 5 6 7 8 9 »   

> Описание: Комбинаторика, алгоритмы и прочее - в программном коде
EuGen Администратор
Отправлено: 16 Мая, 2013 - 12:23:28
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




DlTA пишет:
работает так же не корректно

Но по другой причине, хотя и схожей. А именно - желание сделать функцию работоспособной независимо от типа (строка/число). Сейчас это было устранено добавлением приведения типа массива.
DlTA пишет:
но это же задача иного раздела, для математиков

Как раз потому задача и решается сначала математически, а затем воплощается в программный код. Потому всякая задача по программированию для начала решается математически.

И, кстати, я тоже решил проверить работу Вашей функции, и обнаружил, что у Вас есть ошибка в логике. Например,
PHP:
скопировать код в буфер обмена
  1.     function checkCollection($list, $number){
  2.             //print_r('num:'.$number.PHP_EOL);
  3.             //print_r($list);
  4.            
  5.             if(array_search($number, $list, true)!==false){
  6.                     //print_r('ok: '.$number.PHP_EOL);
  7.                     return true;
  8.             }
  9.                    
  10.             //print_r('-no: '.$number.PHP_EOL);
  11.            
  12.             $strNum = strval($number);
  13.            
  14.             for($len = strlen($strNum)-1; $len>0; $len--){        
  15.                     $checkNum = substr($strNum, 0, $len);
  16.                     //print_r($len.' c:'.$checkNum.PHP_EOL);
  17.                     $keyVal = array_search($checkNum, $list);
  18.                     if($keyVal!==false){
  19.                             unset($list[$keyVal]);
  20.                             return checkCollection($list, substr($strNum, $len));
  21.                     }
  22.                     //print_r('next'.PHP_EOL);
  23.             }
  24.             //echo 'fail'.PHP_EOL;
  25.             return false;
  26.     }
  27. $rgNumbers = array(11,2);
  28. var_dump(checkCollection($rgNumbers, 211));//why false?

- предлагаю Вам самостоятельно её найти, она легко исправляется.

Проблема же решения в лоб состоит в том, что оно будет очень долго работать на примере даже обозримых наборов. Например, набор из 10 нулей, 10 единиц ... 10 девяток. Создать его легко, но вот время исполнения будет очень большим
PHP:
скопировать код в буфер обмена
  1. $rgNumbers = array();
  2. $iMax      = 10;
  3. $iNum      = 10;
  4. for($i=0; $i<$iMax; $i++)
  5. {
  6.    $rgNumbers=array_merge($rgNumbers, array_fill(0, $iNum, $i));
  7. }
  8.  
  9. //var_dump(getMaxAchievable($rgNumbers));


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 16 Мая, 2013 - 14:20:31
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2914
Дата рег-ции: Окт. 2010  


Помог: 53 раз(а)




EuGen пишет:
обнаружил, что у Вас есть ошибка
на какой последовательности?
(Добавление)
EuGen пишет:
10 единиц ... 10 девяток.
суть понятна, НО с учетом разрядности это уже космические значения, для чего такие задачи?
 
 Top
EuGen Администратор
Отправлено: 16 Мая, 2013 - 14:34:25
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




DlTA пишет:
на какой последовательности?

EuGen пишет:
$rgNumbers = array(11,2);
var_dump(checkCollection($rgNumbers, 211));//why false?

DlTA пишет:
НО с учетом разрядности это уже космические значения

Почему же - 100 элементов всего, но ведь не ищется 100-разрядное число, ищется то, которое максимально достижимо непрерывно. Это сам алгоритм такой выбран, что его сложность высока по времени, но это не означает, что не существует других, более быстрых, алгоритмов.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 16 Мая, 2013 - 15:21:39
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2914
Дата рег-ции: Окт. 2010  


Помог: 53 раз(а)




Спойлер (Отобразить)


не по тому ответил, пытаюсь понять суть ошибки

(Отредактировано автором: 16 Мая, 2013 - 15:29:36)

 
 Top
EuGen Администратор
Отправлено: 16 Мая, 2013 - 15:32:58
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Нет, функция не делает того, для чего предназначена - то есть она не проверяет правильно, можно ли составить из членов набора число. В простом примере выше это, очевидно, возможно, но функция вернёт false - речь ведь не о вычислении максимального достижимого, а об определении составляемости числа из членов последовательности.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 16 Мая, 2013 - 15:39:59
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2914
Дата рег-ции: Окт. 2010  


Помог: 53 раз(а)




ошибка заключалась в том что массив подаваемый параметром в функцию имевший значения числовые но тип ячеек при этом был строковый почему то преобразовывался к числовому, странно конечно

Спойлер (Отобразить)
 
 Top
EuGen Администратор
Отправлено: 21 Июня, 2013 - 13:19:36
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Предлагаю задачу с очень простой формулировкой. Как известно, в PHP легко можно присваивать необъявленные свойства объекту, даже если они не были объявлены в классе:
PHP:
скопировать код в буфер обмена
  1. class Foo
  2. {
  3. }
  4. $rObj = new Foo;
  5. $rObj->bar = 'baz';
  6. //var_dump($rObj->bar);

- и это нормальное поведение. То есть динамически создавать свойства класса легко. Теперь, собственно, условие: динамически создать статическое свойство класса. То есть, для примера выше:
PHP:
скопировать код в буфер обмена
  1. class Foo
  2. {
  3. }
  4. $rObj0 = new Foo;
  5. //var_dump($rObj0::$bar); //fatal error
  6. /*
  7. some code, which adding static ::$bar to Foo
  8. */
  9. $rObj1 = new Foo;
  10. var_dump($rObj0::$bar); //baz
  11. var_dump($rObj1::$bar); //baz

- в общем случае можно сформулировать так - создать функцию:
PHP:
скопировать код в буфер обмена
  1. function createStaticProperty($mClassOrObject, $sPropertyName, $mDefaultValue=null)
  2. {
  3.    // ?
  4. }

- которая добавит в класс $mClassOrObject (если параметр - строка, то соответствующему классу, если объект - то тому классу, которому принадлежит объект) статическое свойство $sPropertyName со значением $mDefaultValue

hint (Отобразить)


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
vanicon
Отправлено: 21 Июня, 2013 - 15:37:09
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 808
Дата рег-ции: Янв. 2010  
Откуда: Самара


Помог: 17 раз(а)




Не знаю точно получиться или нет, ибо расширение устанавливать лень.
Через runkit_class_adopt и eval, но даже если и получиться то это уж точно не элегантное решение)), хотелось бы взглянуть на него.
Так как статическое свойство должно быть обязательно объявлено, то тут думаю тока наследованием...

(Отредактировано автором: 21 Июня, 2013 - 15:37:33)



-----
Так было, так есть и так будет
 
 Top
EuGen Администратор
Отправлено: 02 Июля, 2013 - 09:13:06
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Классическая задача заливки.
0. Общий вариант задачи
Дан массив из отрезков. Каждый отрезок задаётся двумя своими точками - начало (from) и окончание (till). Начало и окончание отрезка есть точки на плоскости и задаются своими координатами x и y. Отрезков в массиве может быть сколько угодно (на деле ограничим это число, например, 1E6). Пример структуры:
PHP:
скопировать код в буфер обмена
  1. $rgLines = array(
  2.    array('from' => array('x' =>  0, 'y' => 4), 'till' => array('x' => -8, 'y' =>3)),
  3.    array('from' => array('x' =>  5, 'y' => 6), 'till' => array('x' =>  0, 'y' =>9)),
  4.    array('from' => array('x' => -4, 'y' => 0), 'till' => array('x' =>  7, 'y' =>-2))
  5. );

Даны также две точки - начальная (start) и проверочная (test). Они также задаются своими координатами x и y.
На плоскости проводятся все отрезки, данные в первом массиве - возможно, они образуют разичные замкнутые фигуры (а возможно, и нет).
В начальной точке start происходит заливка плоскости цветом. Заливка - это окрашивание плоскости в цвет. Заливка не может преодолеть линии на плоскости, если те ограничивают замкнутые области (как изнутри, так и снаружи, то есть, если заливка происходила из замкнутой области, то она не проникнет дальше неё, и, аналогично, если есть замкнутая область, которой не принадлежит точка start, то вся эта область не будет окрашена). Хорошая иллюстрация заливки - то, как это происходит в небезызвестной mspaint.
Для простоты будем считать, что точки start и test не лежат ни на одном из отрезков, данных в первом массиве. Требуется определить, будет ли заливкой затронута проверочная точка test.

1. Упрощённый вариант задачи
Вводится дополнительное ограничение на отрезки в певоначальном массиве: все они либо параллельны оси абсцисс, либо параллельны оси ординат, а также не могут лежать друг на друге полностью или частично (но пересекаться, разумеется, могут) - то есть, отрезки имеют не более одной общей точки попарно друг с другом.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
EuGen Администратор
Отправлено: 11 Июля, 2013 - 14:47:46
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




К сожалению, до этого времени я не увидел вариантов решения задачи о заливке. На самом деле она достаточно интересная - но, вместе с тем, нетривиальная. Ниже я приведу решение, на которое у меня ушло около 3-х дней (не полных, но всё же). Возможно, существует не конструктивное решение, однако моё - именно конструктивное, то есть основано на построении.
Само решение выглядит, конечно, очень просто:
'app.php' (Отобразить)

- задачу выполняет LineSet_2D, работающий с полигональной моделью. Для решения задачи строятся все полигоны, которые образуются при пересечении отрезков. Полигон - это по сути невыпуклый (или слабовыпуклый, частный случай чего - сильная выпуклость) многоугольник, без самопересечений (замкнутость подразумевается).
В моём решении считается, что две точки могут быть залиты, если они принадлежат одному и тому же множеству полигонов. Если это множество пусто, то точки также могут быть залиты.
Собственно, сам класс построения:
class LineSet_2D (Отобразить)

- этот класс опирается на различные модели 2D - фигур. Приведу их по-порядку:
0. Класс для 2D-точки:
class Point_2D (Отобразить)

1. Класс для 2D-линии. Важное пояснение - линия это сущность, которая может быть как прямой, так и отрезком и содержит методы работы для обоих случаев.
class Line_2D (Отобразить)

2. Класс для 2D-полигона
class Polygon_2D (Отобразить)

3. Класс для 2D-угла
class Angle_2D (Отобразить)

4. Класс для 2D-окружности (для решения задачи он не требуется, однако в методах классов выше он имеется, поэтому для полноты приводится):
class Circle_2D (Отобразить)

5. Базовый класс для 2D-фигур:
class Entity_2D (Отобразить)

6. Класс для операций над вещественными числами:
class Float_Operations (Отобразить)

7. Класс для операций с массивами:
class Array_Operations (Отобразить)

8. Класс для решения уравнений (в "Пользовательских функциях" я приводил его ранее, при решении этой задачи он пригодился):
class Float_Equation (Отобразить)


Теперь об оценках.
Понял, что ошибся в расчётах, не учитывая время обхода направленного графа. Корректная оценка затруднительна, однако, в силу NP-полноты задачи о поиске наиболее длинного пути эта задача также как минимум NP-полна
При решении этой задачи я решил множество сопутствующих, полезных задач, и теперь думаю, что созданный код вполне пригоден для того, чтобы стать библиотекой для геометрических вычислений (тот же Circle_2D написан впоследствии для этого). Возможно, я дополню его версией для 3D и создам библиотеку.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Panoptik
Отправлено: 11 Июля, 2013 - 15:06:41
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2496
Дата рег-ции: Нояб. 2011  
Откуда: Одесса, Украина


Помог: 131 раз(а)




интересная задачка.
без освеженных знаний по геометрии сложновато оперировать координатами
и с визуализацией было бы понятней, но это довольно емко и может быть не резонно
может библиотеку опубликовать на гитхабе!


-----
Just do it
 
 Top
EuGen Администратор
Отправлено: 11 Июля, 2013 - 15:12:24
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




У меня визуализацией была, как и всегда, бумага - множество листов которой пришлось потратить.
Суть в том, что нет гарантии, что отрезки не будут вложенными/накладывающимися и т.п. Поэтому решались многие общие задачи, при этом стало ясно, что намного проще оперировать 2D-объектами, чем координатами (собственно, суть ООП-подхода). В процессе удалось решить задачи:
* Принадлежности точки многоугольнику
* Построения замкнутой области по заданному множеству отрезков
* Определению пересечения двух окружностей
и т.п.
Наверное, эта задача относится к классу таких задач, решение которых не очень полезно само по себе, однако в процессе попыток её "расколоть" рождаются многие другие - действительно полезные задачи, решая которые, пишется полезный код.

Кстати, любопытно, что в то время, когда я впервые встретил эту задачу на олимпиаде ACM, решена командой соперников она была очень изящно - они действительно подключили графический модуль, нарисовали все отрезки, инициировали процесс заливки в начальной точке и давали ответ, беря пробу цвета в конечной точке (если цвет совпадал с цветом заливки - то ответ положителен). Стоит отметить, что там давался упрощённый вариант задачи, который, очевидно, решается иным способом (иначе было бы невозможно уложиться в лимит 5 сек. с соблюдением допустимого размера набора отрезков). В последствии правила локальных ACM были приведены в соответствие с глобальными, что привело к запрету подключения сторонних библиотек, asm-вставок и всего подобного.
Насчёт гитхаба - возможно, так и поступлю, после того, как определю круг полезных 3D (и, возможно, 2D) задач и реализую их.
А пока что, подумаю над следующей задачей, которую здесь опубликую. Возможно, стоит вводить вознаграждение за их решение? Просто ради стимула. Хотя тогда возникает трудность с проверкой корректности (например, решение выше проверить полностью очень трудно) - и авторства решения


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 11 Июля, 2013 - 17:21:33
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2914
Дата рег-ции: Окт. 2010  


Помог: 53 раз(а)




EuGen пишет:
озможно, стоит вводить вознаграждение за их решение? Просто ради стимула. Хотя тогда возникает трудость с проверкой корректности (например, решение выше проверить полностью очень трудно) - и авторства решения
может какой то информер забацать для подобных тем, а то я например не знал о новых задачках до сегодня
 
 Top
EuGen Администратор
Отправлено: 11 Июля, 2013 - 17:25:48
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




DlTA
Вы можете подписаться на новые сообщения в этой теме. Соответствующая ссылка доступна в последнем комментарии.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 11 Июля, 2013 - 17:33:28
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2914
Дата рег-ции: Окт. 2010  


Помог: 53 раз(а)





было бы не плохо ее в начале продублироать

(Добавление)
а есть такая
 
 Top
Страниц (9): « 1 2 3 [4] 5 6 7 8 9 »
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0)
« Прочее »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB