Форумы портала PHP.SU » Разное » Прочее » Вопрос к программистам

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

1. EuGen - 28 Сентября, 2010 - 14:42:46 - перейти к сообщению
Здесь предлагаю публиковать задачи по программированию - те из них, что наиболее интересны, или же требуют применения определенных парадигм (к слову, "Hello World" не тот случай) - по аналогии с темой о математических задачах.
Пока что в разделе "Прочее", но если материал будет интересным, подумаю о перемещении темы и в "Уроки".
Решения - предпочтительно на PHP или на другом языке серверного программирования (у нас же есть раздел о Perl, Python и других). Если задача затрагивает вопросы web - тем ценнее она будет для читателей.
Заранее благодарю всех авторов.

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

Спойлер (Отобразить)
2. garvey - 28 Сентября, 2010 - 17:17:10 - перейти к сообщению
Решение задачи №1. Возможно есть лучше алгоритм.
PHP:
скопировать код в буфер обмена
  1. <?PHP
  2. function createMatrix($m, $n) {
  3.     echo '<table>';
  4.     for ($i = 0; $i < $m; $i++) {
  5.         echo '<tr>';
  6.         for ($j = 0; $j < $n; $j++) {
  7.            $matrix[$i][$j] = rand(0,9);
  8.            echo '<td>' . $matrix[$i][$j] . '</td>';
  9.         }
  10.         echo '</tr>';
  11.     }
  12.     echo "</table>";
  13.     return $matrix;
  14. }
  15.  
  16. function runByMatrix($matrix, $i = 0, $j = 0) {
  17.     $result = $matrix[$i][$j];
  18.     echo $result.'('.$i.','.$j.')<br>';
  19.     if (isset($matrix[$i + 1][$j]) && isset($matrix[$i][$j + 1])) {
  20.         if ($matrix[$i + 1][$j] > $matrix[$i][$j + 1]) {
  21.             $ii = $i + 1;
  22.             $jj = $j;
  23.         }
  24.         else {
  25.             $ii = $i;
  26.             $jj = $j + 1;
  27.         }
  28.         $result += runByMatrix($matrix, $ii, $jj);
  29.     }
  30.     else {
  31.         if (!isset($matrix[$i + 1][$j]) && isset($matrix[$i][$j + 1])) {
  32.             $ii = $i;
  33.             $jj = $j + 1;
  34.             $result += runByMatrix($matrix, $ii, $jj);
  35.         }
  36.         elseif (isset($matrix[$i + 1][$j]) && !isset($matrix[$i][$j + 1])) {
  37.             $ii = $i + 1;
  38.             $jj = $j;
  39.             $result += runByMatrix($matrix, $ii, $jj);
  40.         }
  41.     }
  42.     return $result;
  43. }
  44.  
  45. $matrix = createMatrix(5, 5);
  46. echo runByMatrix($matrix);
  47. ?>
3. EuGen - 28 Сентября, 2010 - 17:49:21 - перейти к сообщению
Насколько я понял, этот скрипт реализует "жадный алгоритм" - просто из двух направлений выбирается то, где соседний элемент больше. Это не приведет к правильному решению. Например:
1 0 9 9
2 0 0 9
0 0 0 9
- на такой матрице скрипт первым ходом пойдет вниз (2>0) но очевидно что правильный выбор - это 0 - за ним девятки.
4. garvey - 28 Сентября, 2010 - 17:52:06 - перейти к сообщению
Очень согласен. Спасибо. Будет время - буду пытаться отточить алгоритм. Но главное - начало.
5. EuGen - 29 Сентября, 2010 - 14:07:38 - перейти к сообщению
Подскажу, что в решении этих задач поможет алгоритм динамического программирования:
http://ru[dot]wikipedia[dot]org/wiki/%D0[dot][dot][dot]0%BD%D0%B8%D0%B5
6. ALEN - 30 Сентября, 2010 - 19:09:24 - перейти к сообщению
Ссылка битая у тебя: http://ru[dot]wikipedia[dot]org/wiki/ Динамическое_программирование - напишите вместо символов
7. EuGen - 01 Октября, 2010 - 09:25:42 - перейти к сообщению
Скорее, это вопрос к движку форума. Соответственно фидбэк в тему о багах.
В спойлер я поместил ссылку на решение имеющихся задач.

Что же, видимо я сразу начал с непростых задач.
Попробую опубликовать не менее классическую, но более простую вещь:
Даны два числа, записанные в виде строк. Требуется вычислить
1. Их сумму
2. Их произведение
Чилса даны в десятичной системе счисления, длина строк, представляющих 2 входных числа, не ограничена (для определенности, скажем, не более 100000 символов).
8. EuGen - 06 Марта, 2012 - 15:29:26 - перейти к сообщению
Топик, конечно, устарел, но тем не менее - встретилась одна задача, которая может быть полезна на практике.

Язык - php (версия произвольна, ориентировочно 5.3)
Дано - некоторая переменная.
Задача - найти её размер в байтах оптимальным способом.

Формализовано - задача состоит в написании некоторой функции или, возможно, класса (хотя первое проще и логичнее):
PHP:
скопировать код в буфер обмена
  1. /*
  2. * @mVar mixed
  3. * return integer
  4. */
  5. function get_size_of_var($mVar)


Ваши идеи?
9. DlTA - 06 Марта, 2012 - 15:48:37 - перейти к сообщению
EuGen пишет:
Ваши идеи?
на строй версии php при копировании объекта копировались и все данные объекта, достаточно было бы всего лишь посмотреть разницу в свободном месте в памяти, а вот на 5.3 (кажись) при копировании объекта происходит копирование по ссылке, так что надо думать
10. Panoptik - 06 Марта, 2012 - 15:48:41 - перейти к сообщению
EuGen пишет:
@mVar mixed
то есть типы ресурс и объект?
11. EuGen - 06 Марта, 2012 - 15:53:15 - перейти к сообщению
Panoptik
Разумеется. Более того, это может быть, скажем, многомерный массив, в измерениях которого записаны ресурсы, объекты, что угодно. Или объект с атрибутами - массивами произвольного содержимого и т.п.
И, таким образом, на вариант DlTA (насколько я понял это memory_get_usage + копирование переменной + memory_get_usage + расчет разницы) может попросту не хватить памяти (например, переменная имеет размер 25Mb а лимит памяти равен 30Mb). Поскольку неизвестен размер переменной, он может быть любым - несколько гигабайт, например, так что копирование может привести вдобавок и к отказу исполнения скрипта по причине лимита времени (даже если памяти хватает)
Поэтому такой вариант я не рассматривал.
12. Bio man - 06 Марта, 2012 - 18:05:45 - перейти к сообщению
может как то так?
PHP:
скопировать код в буфер обмена
  1. class VarMemory{
  2.         private $_start;
  3.         function __construct(){
  4.                 $this->_start = memory_get_usage();
  5.         }
  6.         function getSizeOfVar($mVar){
  7.                 return memory_get_usage()-$this->_start;
  8.         }
  9.         function getStartMemoryUsage(){
  10.                 return $this->_start;
  11.         }
  12. }
  13. $rMemUse = new VarMemory();
  14. echo 'Before '.$rMemUse->getStartMemoryUsage().' bytes<br>';
  15. echo 'Var size '.$rMemUse->getSizeOfVar(str_repeat('Hello', 4096)).' bytes<br>';

в данном случае погрешность составляет 224 байта
(Добавление)
размер переменной 20480 байт. выводит 20704
13. DlTA - 06 Марта, 2012 - 22:40:56 - перейти к сообщению
Bio man пишет:
в данном случае погрешность составляет 224 байта
метод мало чем отличается от предложенного мной више(

вариант 2:
1) замеряем объем свободного места
2) берем субъект, серилизуем его в файл, и удаляем
3) замеряем, объем свободного места
4) востанавливаем субъект из файла
разница до удаления и после и должно быть размером субъекта
14. caballero - 06 Марта, 2012 - 23:55:55 - перейти к сообщению
Цитата:
разница до удаления и после и должно быть размером субъекта

это если сборщик мусора сработает
15. DlTA - 08 Марта, 2012 - 00:16:51 - перейти к сообщению
EuGen пишет:
Первой задачей опубликую классическую вещь:
Дана матрица N*M размерности. Заполнена случайными числами от 0 до 9. Например:
4 9 2 0
7 3 3 1
6 9 2 5
Нужно пройтись из левого верхнего угла в нижний правый так, чтобы набрать максимальное число суммируемых элементов матрицы. Движение разрешается только или вправо или вниз. Один и тот же элемент нельзя посещать дважды


Решение: (Отобразить)

Результат: (Отобразить)

(Добавление)
Описание решения, рекурсивно строятся все возможные пути, и при этом считаетcя сумма каждого, в результат выводится максимальная сумма и путь для достижения этой суммы

 

Powered by ExBB FM 1.0 RC1