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]
Я учитывал что все числа в матрице больше ноля.
При желании, если не нравится ноль, можно изменить тип проверки. (Добавление)
continue; в 25-ой строке не нужен, атавизм от тестов остался (Добавление)
EuGen пишет:
Это не приведет к правильному решению. Например:
1 0 9 9
2 0 0 9
0 0 0 9
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
точное решение подобных задач можно получить только полным перелопачиванием вариантов, это же графы
решать такие задачи в цикле, это равносильно обходу дерева в цикле, один жуткий костыль, надо делать через рекурсию, единственное место где можно поиграться это в объемах необходимый для обхода (Добавление)
SAD пишет:
теорию о задаче о коммивояжере
это та в которой:
"для того чтоб обойти все узлы пройдя по каждому пути только 1 раз, надо чтоб узлы имели четное количество связей"?
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Пока что не удалось найти нормального решения для определения размеров переменной в памяти.
Но эта задача породила другую, а именно - узнать, как называется переменная. Ведь если у нас есть
то второй пример пусть и не намного, но займет больше в памяти.
В PHP размер строки в памяти выравнивается по 4 байта. То есть, строки длиной 0-4 символов будут занимать X байт, длиной 5-8 будут занимать X+4 байт, ну и для произвольного N размер значения (значения, не указателей) будет X+(int)(N/4)*4 - вот мне и стало интересно, как обстоит дело с собственно самим именем переменной. Здесь X - то количество байт, которое выделится на строку при её "создании" (объявлении). Точного значения здесь не найти, так как, очевидно, PHP оптимизирует память, и, в зависимости от обстоятельств, это значение может варьироваться.
Сразу оговорюсь, что корректного способа определения имени переменной мне не удалось найти. Вот мой вариант:
- сразу очевиден его серьезнейший недостаток - копирование переменной. Но пока что, другого способа найти не удалось.
В явном виде зависимость байтового размера ссылки (то есть) от ее длины в написании в документации я не нашел, но вот какую интересную вещь мне удалось обнаружить:
0. Предположим, что Y - размер в байтах, выделяемый "по-умолчанию", при объявлении переменной
1. Тогда получается, что при длине имени переменной в интервале [1,8] размер будет Y
2. При длине имени переменной в интервале (8, 12] размер будет Y+28
3. При длине имени переменной в интервале (12, ∞) размер будет Y+28+ceil((N-12)/4)*4 где N - длина имени переменной (для её определения я и использовал функцию выше) - то есть очевидно, что применяется обычное правило выравнивания по 4 байта.
Собственно, функция для определения имени переменной - плоха в таком варианте. Но, может, кто-нибудь предложит более оптимальный вариант?
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Саныч
Отправлено: 28 Апреля, 2012 - 20:15:13
Участник
Покинул форум
Сообщений всего: 1365
Дата рег-ции: Июль 2010 Откуда: Украина, Запорожье
Помог: 62 раз(а)
EuGen пишет:
Дана матрица N*M размерности. Заполнена случайными числами от 0 до 9. Например:
4 9 2 0
7 3 3 1
6 9 2 5
Нужно пройтись из левого верхнего угла в нижний правый так, чтобы набрать максимальное число суммируемых элементов матрицы. Движение разрешается только или вправо или вниз. Один и тот же элемент нельзя посещать дважды
На написание убил полтора часа... Сама функция, которая и вычисляет "путь" всего 10 строк
На выходе получаем такую табличку Прикреплено изображение (Нажмите для увеличения)
----- Все возражают против того, что я гений, хотя никто еще так меня не назвал. - Орсон Уэллс
EuGen
Отправлено: 28 Апреля, 2012 - 23:06:28
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Саныч
Ваш алгоритм, насколько я понимаю, реализует перебор (построение + подсчет суммы) всех возможных путей прохода и затем выбирает тот из них, который имеет максимальную сумму.
В случае N и M порядка 1e6 это будет иметь очень большую продолжительность по времени. Задача решается другим способом.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Саныч
Отправлено: 28 Апреля, 2012 - 23:28:31
Участник
Покинул форум
Сообщений всего: 1365
Дата рег-ции: Июль 2010 Откуда: Украина, Запорожье
Помог: 62 раз(а)
EuGen, да, здесь именно перебор.
EuGen пишет:
Задача решается другим способом.
Хм... Тогда у меня 2 вопроса:
- какой этот другой способ? Я так понимаю это задачка из области математики, а именно комбинаторики?
- какое практическое преминение всего этого дела?
----- Все возражают против того, что я гений, хотя никто еще так меня не назвал. - Орсон Уэллс
DlTA
Отправлено: 02 Ноября, 2012 - 00:38:44
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
задачка, расчет числа Фибоначчи без рекурсии:
вариант с рекурсией:
Покинул форум
Сообщений всего: 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 не может быть непрерывно достигнут.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
SAD
Отправлено: 28 Декабря, 2012 - 22:05:00
Постоянный участник
Покинул форум
Сообщений всего: 2508
Дата рег-ции: Май 2009 Откуда: Днепропетровск, Украина
Помог: 75 раз(а)
EuGen пишет:
при том, что каждый член из набора не может быть использован более 1 раза
во втором примере, имхо, для 10 уже используются 0 и 1, хотя они были заюзаны.
EuGen
Отправлено: 28 Декабря, 2012 - 23:04:01
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
SAD пишет:
во втором примере, имхо, для 10 уже используются 0 и 1, хотя они были заюзаны.
Имелось ввиду - 1 раз при построении конкретного числа, а не вообще всех чисел. По этой причине во втором примере достижимы 12,13 и т.п. до 21.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.