Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737
Форумы портала PHP.SU :: Вопрос к программистам [2]

 PHP.SU

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


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

> Описание: Комбинаторика, алгоритмы и прочее - в программном коде
Поиск в теме | Версия для печати
DeepVarvar Супермодератор
Отправлено: 08 Марта, 2012 - 00:52:15
Post Id



Активный участник


Покинул форум
Сообщений всего: 10377
Дата рег-ции: Дек. 2008  
Откуда: Альфа Центавра


Помог: 353 раз(а)
DlTA:
PHP:
скопировать код в буфер обмена
  1. $tab = array(
  2.   array(4,9,2,0),
  3.   array(7,9,3,1),
  4.   array(6,9,2,5)
  5. );
  6.  
  7. $posx = 0;
  8. $posy = 0;
  9.  
  10. $sum = 0;
  11. $path = array("[x:0,y:0]");
  12.  
  13. while (true) {  
  14.  
  15.   $sum += $tab[$posy][$posx];
  16.   $right = (isset($tab[$posy][$posx+1])) ? $tab[$posy][$posx+1] : 0;
  17.   $bottom = (isset($tab[$posy+1][$posx])) ? $tab[$posy+1][$posx] : 0;
  18.  
  19.   if ($right == 0 and $bottom == 0) break;
  20.  
  21.   if ($bottom > $right) $posy++;
  22.   else $posx++;
  23.  
  24.   array_push($path,"[x:$posx,y:$posy]");
  25.   continue;
  26.  
  27. }
  28.  
  29.  
  30. echo "Сумма: $sum <br /> Путь:<br />";
  31. foreach ($path as $step) echo "$step<br />";

Вывод:

Сумма: 38
Путь:
[x:0,y:0]
[x:1,y:0]
[x:1,y:1]
[x:1,y:2]
[x:2,y:2]
[x:3,y:2]

Я учитывал что все числа в матрице больше ноля.
При желании, если не нравится ноль, можно изменить тип проверки.
(Добавление)
continue; в 25-ой строке не нужен, атавизм от тестов остался Закатив глазки
(Добавление)
EuGen пишет:
Это не приведет к правильному решению. Например:
1 0 9 9
2 0 0 9
0 0 0 9

Покурим еще Закатив глазки
 
 Top
SAD
Отправлено: 08 Марта, 2012 - 01:21:19
Post Id



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


Покинул форум
Сообщений всего: 2508
Дата рег-ции: Май 2009  
Откуда: Днепропетровск, Украина


Помог: 75 раз(а)
нужно применить теорию о задаче коммивояжере

(Отредактировано автором: 08 Марта, 2012 - 01:23:42)

 
 Top
DlTA
Отправлено: 08 Марта, 2012 - 01:22:20
Post Id



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


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


Помог: 53 раз(а)
точное решение подобных задач можно получить только полным перелопачиванием вариантов, это же графы

решать такие задачи в цикле, это равносильно обходу дерева в цикле, один жуткий костыль, надо делать через рекурсию, единственное место где можно поиграться это в объемах необходимый для обхода
(Добавление)
SAD пишет:
теорию о задаче о коммивояжере
это та в которой:
"для того чтоб обойти все узлы пройдя по каждому пути только 1 раз, надо чтоб узлы имели четное количество связей"?

(Отредактировано автором: 08 Марта, 2012 - 01:26:12)

 
 Top
DeepVarvar Супермодератор
Отправлено: 08 Марта, 2012 - 12:46:30
Post Id



Активный участник


Покинул форум
Сообщений всего: 10377
Дата рег-ции: Дек. 2008  
Откуда: Альфа Центавра


Помог: 353 раз(а)
Добил скрипт, выложил и нашел косяк.. Закатив глазки выложу как исправлю..

(Отредактировано автором: 08 Марта, 2012 - 12:56:51)

 
 Top
EuGen Администратор
Отправлено: 12 Марта, 2012 - 15:51:54
Post Id


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


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


Помог: 707 раз(а)
Пока что не удалось найти нормального решения для определения размеров переменной в памяти.
Но эта задача породила другую, а именно - узнать, как называется переменная. Ведь если у нас есть
PHP:
скопировать код в буфер обмена
  1. $a=1;

и
PHP:
скопировать код в буфер обмена
  1. $thisIsAnotherAndVeryVeryLongNameForVariable=1

то второй пример пусть и не намного, но займет больше в памяти.
В PHP размер строки в памяти выравнивается по 4 байта. То есть, строки длиной 0-4 символов будут занимать X байт, длиной 5-8 будут занимать X+4 байт, ну и для произвольного N размер значения (значения, не указателей) будет X+(int)(N/4)*4 - вот мне и стало интересно, как обстоит дело с собственно самим именем переменной. Здесь X - то количество байт, которое выделится на строку при её "создании" (объявлении). Точного значения здесь не найти, так как, очевидно, PHP оптимизирует память, и, в зависимости от обстоятельств, это значение может варьироваться.
Сразу оговорюсь, что корректного способа определения имени переменной мне не удалось найти. Вот мой вариант:
PHP:
скопировать код в буфер обмена
  1. function get_var_name(&$mVar, $rgScope=null)
  2. {
  3.     $mOld = $mVar;        
  4.     if(($mResult = array_search($mVar = uniqid(), !isset($rgScope)?$GLOBALS:$rgScope)) && $mVar=$mOld)
  5.     {
  6.         return $mResult;
  7.     }
  8.     return null;
  9. }

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

0. Предположим, что Y - размер в байтах, выделяемый "по-умолчанию", при объявлении переменной
1. Тогда получается, что при длине имени переменной в интервале [1,8] размер будет Y
2. При длине имени переменной в интервале (8, 12] размер будет Y+28
3. При длине имени переменной в интервале (12, ∞) размер будет Y+28+ceil((N-12)/4)*4 где N - длина имени переменной (для её определения я и использовал функцию выше) - то есть очевидно, что применяется обычное правило выравнивания по 4 байта.

Собственно, функция для определения имени переменной - плоха в таком варианте. Но, может, кто-нибудь предложит более оптимальный вариант?


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Саныч
Отправлено: 28 Апреля, 2012 - 20:15:13
Post Id



Участник


Покинул форум
Сообщений всего: 1365
Дата рег-ции: Июль 2010  
Откуда: Украина, Запорожье


Помог: 62 раз(а)
EuGen пишет:
Дана матрица N*M размерности. Заполнена случайными числами от 0 до 9. Например:
4 9 2 0
7 3 3 1
6 9 2 5
Нужно пройтись из левого верхнего угла в нижний правый так, чтобы набрать максимальное число суммируемых элементов матрицы. Движение разрешается только или вправо или вниз. Один и тот же элемент нельзя посещать дважды

Делать нечего было, решил мозг подразмять немного Улыбка
PHP:
скопировать код в буфер обмена
  1. <?PHP
  2. /*
  3. $tab = [
  4.         [4, 9, 2, 0],
  5.         [7, 3, 3, 1],
  6.         [6, 9, 2, 5]
  7. ];
  8. */
  9. $tab = [];
  10. for ($y = 0; $y < 10; $y++)
  11.         for ($x = 0; $x < 10; $x++)
  12.                 $tab[$y][$x] = mt_rand(0, 100);
  13. //=================
  14. $xLen = count($tab[0]);
  15. $yLen = count($tab);
  16. $res = [];
  17.  
  18. function line($x = 0, $y = 0, $key = '', $sum = 0) {
  19.         global $xLen, $yLen, $res, $tab;
  20.         for (; $x < $xLen; $x++) {
  21.                 $sum += $tab[$y][$x];
  22.                 $key .= ($key ? '=>' : '') . $x . '-' . $y;
  23.                 if ($y + 1 < $yLen)
  24.                         line($x, $y + 1, $key, $sum);
  25.                 else if ($x + 1 == $xLen)
  26.                         $res[$key] = $sum;
  27.         }
  28. }
  29. line();
  30.  
  31. $maxSum = max($res);
  32. $maxSumEls = array_search($maxSum, $res);
  33.  
  34. echo 'Максимальная сумма: ', $maxSum, '<table>';
  35. foreach ($tab as $y => $xEls) {
  36.         echo '<tr>';
  37.         foreach ($xEls as $x => $num)
  38.                 echo strpos($maxSumEls, $x . '-' . $y) === false ? '<td>' . $num . '<td>' : '<th bgcolor="#ccc">' . $num . '<th>';
  39.         echo '</tr>';
  40. }
  41. echo '</table>';
  42. ?>

На написание убил полтора часа... Сама функция, которая и вычисляет "путь" всего 10 строк Радость
На выходе получаем такую табличку
Прикреплено изображение (Нажмите для увеличения)
Снимок12.JPG

(Отредактировано автором: 28 Апреля, 2012 - 20:18:10)



-----
Все возражают против того, что я гений, хотя никто еще так меня не назвал. - Орсон Уэллс
 
 Top
Саныч
Отправлено: 28 Апреля, 2012 - 20:26:44
Post Id



Участник


Покинул форум
Сообщений всего: 1365
Дата рег-ции: Июль 2010  
Откуда: Украина, Запорожье


Помог: 62 раз(а)
З.ы. вторая задача, по-моему безсмысленна, т.к. наибольшее значение всегда будет при движении змейкой
Прикреплено изображение
Снимок122.JPG


-----
Все возражают против того, что я гений, хотя никто еще так меня не назвал. - Орсон Уэллс
 
 Top
EuGen Администратор
Отправлено: 28 Апреля, 2012 - 21:44:59
Post Id


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


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


Помог: 707 раз(а)
Нет. Не стоит забывать, что числа могут быть отрицательными.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Саныч
Отправлено: 28 Апреля, 2012 - 22:07:54
Post Id



Участник


Покинул форум
Сообщений всего: 1365
Дата рег-ции: Июль 2010  
Откуда: Украина, Запорожье


Помог: 62 раз(а)
да, точно, забыл про отрицательные... Ну при условии 0+ - змейка с небольшими вычислениями при четном количестве столбцов.

А вот с отрицательными числами нужно думать. В следующий раз, как появятся пара ненужных часов, подумаю над второй частью Подмигивание

з.ы. а что скажете про реализацию первой части? Возможно что-то улучшить (уменьшить)?

(Отредактировано автором: 28 Апреля, 2012 - 22:09:47)



-----
Все возражают против того, что я гений, хотя никто еще так меня не назвал. - Орсон Уэллс
 
 Top
EuGen Администратор
Отправлено: 28 Апреля, 2012 - 23:06:28
Post Id


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


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


Помог: 707 раз(а)
Саныч
Ваш алгоритм, насколько я понимаю, реализует перебор (построение + подсчет суммы) всех возможных путей прохода и затем выбирает тот из них, который имеет максимальную сумму.
В случае N и M порядка 1e6 это будет иметь очень большую продолжительность по времени. Задача решается другим способом.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Саныч
Отправлено: 28 Апреля, 2012 - 23:28:31
Post Id



Участник


Покинул форум
Сообщений всего: 1365
Дата рег-ции: Июль 2010  
Откуда: Украина, Запорожье


Помог: 62 раз(а)
EuGen, да, здесь именно перебор.
EuGen пишет:
Задача решается другим способом.
Хм... Тогда у меня 2 вопроса:
- какой этот другой способ? Улыбка Я так понимаю это задачка из области математики, а именно комбинаторики?
- какое практическое преминение всего этого дела?


-----
Все возражают против того, что я гений, хотя никто еще так меня не назвал. - Орсон Уэллс
 
 Top
DlTA
Отправлено: 02 Ноября, 2012 - 00:38:44
Post Id



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


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


Помог: 53 раз(а)
задачка, расчет числа Фибоначчи без рекурсии:
вариант с рекурсией:
PHP:
скопировать код в буфер обмена
  1. function fibonacci($n) {
  2.         if ($n < 2)
  3.         return 1;
  4.         else
  5.         return fibonacci($n-2) + fibonacci($n-1);
  6. }

а для усложнения чтоб еще и с минимизацией телодвижений.
мои варианты (не подглядывать)):
1 (Отобразить)

2 (Отобразить)
 
 Top
EuGen Администратор
Отправлено: 28 Декабря, 2012 - 20:06:53
Post Id


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


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


Помог: 707 раз(а)
Придумал задачу по пути домой. Итак:

Назовем число непрерывно достижимым в N-ичной системе для некоторого набора чисел, если это число и весь натуральный ряд до него могут быть записаны из чисел данного набора, при том, что каждый член из набора не может быть использован более 1 раза при построении очередного числа. Старт происходит с 0.

Приведу примеры (система - десятичная):
Дан набор чисел (4, 1, 5, 2, 0)
Тогда непрерывно достижимыми в этом наборе будут только числа 0, 1 и 2.

Дан набор чисел (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11)
- Тогда числа от 0 до 21 включительно будут непрерывно достижимыми в этом наборе.

Очевидно, что если в наборе отсутствует 0, то ни одно число в нём не может быть непрерывно достигнуто.

Итак, дан массив целых неотрицательных чисел, записанных в десятичной системе счисления. Задача - найти максимальное непрерывно достижимое число для данного массива значений.
Результат следует оформить в виде функции getMaxAchievable, принимающей единственный параметр - массив значений, и возвращающей единственное целое значение, либо null, если даже 0 не может быть непрерывно достигнут.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
SAD
Отправлено: 28 Декабря, 2012 - 22:05:00
Post Id



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


Покинул форум
Сообщений всего: 2508
Дата рег-ции: Май 2009  
Откуда: Днепропетровск, Украина


Помог: 75 раз(а)
EuGen пишет:
при том, что каждый член из набора не может быть использован более 1 раза


во втором примере, имхо, для 10 уже используются 0 и 1, хотя они были заюзаны.
 
 Top
EuGen Администратор
Отправлено: 28 Декабря, 2012 - 23:04:01
Post Id


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


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


Помог: 707 раз(а)
SAD пишет:
во втором примере, имхо, для 10 уже используются 0 и 1, хотя они были заюзаны.

Имелось ввиду - 1 раз при построении конкретного числа, а не вообще всех чисел. По этой причине во втором примере достижимы 12,13 и т.п. до 21.


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


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



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

 
Powered by ExBB FM 1.0 RC1. InvisionExBB