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 :: Вопрос к программистам
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Здесь предлагаю публиковать задачи по программированию - те из них, что наиболее интересны, или же требуют применения определенных парадигм (к слову, "Hello World" не тот случай) - по аналогии с темой о математических задачах.
Пока что в разделе "Прочее", но если материал будет интересным, подумаю о перемещении темы и в "Уроки".
Решения - предпочтительно на PHP или на другом языке серверного программирования (у нас же есть раздел о Perl, Python и других). Если задача затрагивает вопросы web - тем ценнее она будет для читателей.
Заранее благодарю всех авторов.
Первой задачей опубликую классическую вещь:
Дана матрица N*M размерности. Заполнена случайными числами от 0 до 9. Например:
4 9 2 0
7 3 3 1
6 9 2 5
Нужно пройтись из левого верхнего угла в нижний правый так, чтобы набрать максимальное число суммируемых элементов матрицы. Движение разрешается только или вправо или вниз. Один и тот же элемент нельзя посещать дважды
Вторая задача - модификация первой. Дана все та же матрица, но числа в ее элементах могут быть любыми (например, от -100000 до 100000). Направление движения, которое разрешено - любое (вверх, вниз, влево, вправо, по диагонали нельзя). Задача та же - набрать максимальное число в сумме (суммируются все посещенные элементы, повторения элементов не допускаются).
Решением обеих задач можно назвать информацию о пройденном пути в любом виде (например, в виде последовательного списка посещенных элементов с координатами каждого из них. Или, к примеру, графическое представление).
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Насколько я понял, этот скрипт реализует "жадный алгоритм" - просто из двух направлений выбирается то, где соседний элемент больше. Это не приведет к правильному решению. Например:
1 0 9 9
2 0 0 9
0 0 0 9
- на такой матрице скрипт первым ходом пойдет вниз (2>0) но очевидно что правильный выбор - это 0 - за ним девятки.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
garvey
Отправлено: 28 Сентября, 2010 - 17:52:06
Частый посетитель
Покинул форум
Сообщений всего: 528
Дата рег-ции: Май 2010 Откуда: Minsk
Помог: 3 раз(а)
Очень согласен. Спасибо. Будет время - буду пытаться отточить алгоритм. Но главное - начало.
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Скорее, это вопрос к движку форума. Соответственно фидбэк в тему о багах.
В спойлер я поместил ссылку на решение имеющихся задач.
Что же, видимо я сразу начал с непростых задач.
Попробую опубликовать не менее классическую, но более простую вещь:
Даны два числа, записанные в виде строк. Требуется вычислить
1. Их сумму
2. Их произведение
Чилса даны в десятичной системе счисления, длина строк, представляющих 2 входных числа, не ограничена (для определенности, скажем, не более 100000 символов).
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
EuGen
Отправлено: 06 Марта, 2012 - 15:29:26
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Топик, конечно, устарел, но тем не менее - встретилась одна задача, которая может быть полезна на практике.
Язык - php (версия произвольна, ориентировочно 5.3)
Дано - некоторая переменная.
Задача - найти её размер в байтах оптимальным способом.
Формализовано - задача состоит в написании некоторой функции или, возможно, класса (хотя первое проще и логичнее):
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 06 Марта, 2012 - 15:48:37
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
EuGen пишет:
Ваши идеи?
на строй версии php при копировании объекта копировались и все данные объекта, достаточно было бы всего лишь посмотреть разницу в свободном месте в памяти, а вот на 5.3 (кажись) при копировании объекта происходит копирование по ссылке, так что надо думать
Panoptik
Отправлено: 06 Марта, 2012 - 15:48:41
Постоянный участник
Покинул форум
Сообщений всего: 2493
Дата рег-ции: Нояб. 2011 Откуда: Одесса, Украина
Помог: 131 раз(а)
EuGen пишет:
@mVar mixed
то есть типы ресурс и объект?
----- Just do it
EuGen
Отправлено: 06 Марта, 2012 - 15:53:15
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Panoptik
Разумеется. Более того, это может быть, скажем, многомерный массив, в измерениях которого записаны ресурсы, объекты, что угодно. Или объект с атрибутами - массивами произвольного содержимого и т.п.
И, таким образом, на вариант DlTA (насколько я понял это memory_get_usage + копирование переменной + memory_get_usage + расчет разницы) может попросту не хватить памяти (например, переменная имеет размер 25Mb а лимит памяти равен 30Mb). Поскольку неизвестен размер переменной, он может быть любым - несколько гигабайт, например, так что копирование может привести вдобавок и к отказу исполнения скрипта по причине лимита времени (даже если памяти хватает)
Поэтому такой вариант я не рассматривал.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Bio man
Отправлено: 06 Марта, 2012 - 18:05:45
Постоянный участник
Покинул форум
Сообщений всего: 2751
Дата рег-ции: Июль 2010 Откуда: Даугавпилс, Латвия
в данном случае погрешность составляет 224 байта (Добавление)
размер переменной 20480 байт. выводит 20704
DlTA
Отправлено: 06 Марта, 2012 - 22:40:56
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
Bio man пишет:
в данном случае погрешность составляет 224 байта
метод мало чем отличается от предложенного мной више(
вариант 2:
1) замеряем объем свободного места
2) берем субъект, серилизуем его в файл, и удаляем
3) замеряем, объем свободного места
4) востанавливаем субъект из файла
разница до удаления и после и должно быть размером субъекта
caballero
Отправлено: 06 Марта, 2012 - 23:55:55
Активный участник
Покинул форум
Сообщений всего: 5998
Дата рег-ции: Сент. 2011 Откуда: Харьков
Помог: 126 раз(а)
Цитата:
разница до удаления и после и должно быть размером субъекта
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
EuGen пишет:
Первой задачей опубликую классическую вещь:
Дана матрица N*M размерности. Заполнена случайными числами от 0 до 9. Например:
4 9 2 0
7 3 3 1
6 9 2 5
Нужно пройтись из левого верхнего угла в нижний правый так, чтобы набрать максимальное число суммируемых элементов матрицы. Движение разрешается только или вправо или вниз. Один и тот же элемент нельзя посещать дважды
----- Табличка------
4 9 2 0
7 9 3 1
6 9 2 5
-----------------------
Максимальная сумма: 38
-------путь----------
array
0 =>
object(SPoint)[2]
public 'x' => int 0
public 'y' => int 0
1 =>
object(SPoint)[3]
public 'x' => int 1
public 'y' => int 0
2 =>
object(SPoint)[7]
public 'x' => int 1
public 'y' => int 1
3 =>
object(SPoint)[10]
public 'x' => int 1
public 'y' => int 2
4 =>
object(SPoint)[5]
public 'x' => int 2
public 'y' => int 2
5 =>
object(SPoint)[14]
public 'x' => int 3
public 'y' => int 2
(Добавление)
Описание решения, рекурсивно строятся все возможные пути, и при этом считаетcя сумма каждого, в результат выводится максимальная сумма и путь для достижения этой суммы
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.