PHP.SU

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


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

> Описание: Комбинаторика, алгоритмы и прочее - в программном коде
EuGen Администратор
Отправлено: 28 Сентября, 2010 - 14:42:46
Post Id


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


Покинул форум
Сообщений всего: 9098
Дата рег-ции: Июнь 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). Направление движения, которое разрешено - любое (вверх, вниз, влево, вправо, по диагонали нельзя). Задача та же - набрать максимальное число в сумме (суммируются все посещенные элементы, повторения элементов не допускаются).
Решением обеих задач можно назвать информацию о пройденном пути в любом виде (например, в виде последовательного списка посещенных элементов с координатами каждого из них. Или, к примеру, графическое представление).

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


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



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


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


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




Решение задачи №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. ?>
 
 Top
EuGen Администратор
Отправлено: 28 Сентября, 2010 - 17:49:21
Post Id


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


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


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




Насколько я понял, этот скрипт реализует "жадный алгоритм" - просто из двух направлений выбирается то, где соседний элемент больше. Это не приведет к правильному решению. Например:
1 0 9 9
2 0 0 9
0 0 0 9
- на такой матрице скрипт первым ходом пойдет вниз (2>0) но очевидно что правильный выбор - это 0 - за ним девятки.


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



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


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


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




Очень согласен. Спасибо. Будет время - буду пытаться отточить алгоритм. Но главное - начало.
 
 Top
EuGen Администратор
Отправлено: 29 Сентября, 2010 - 14:07:38
Post Id


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


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


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




Подскажу, что в решении этих задач поможет алгоритм динамического программирования:
http://ru[dot]wikipedia[dot]org/wiki/%D0[dot][dot][dot]0%BD%D0%B8%D0%B5


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
ALEN Модератор
Отправлено: 30 Сентября, 2010 - 19:09:24
Post Id



Участник


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


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




Ссылка битая у тебя: http://ru[dot]wikipedia[dot]org/wiki/ Динамическое_программирование - напишите вместо символов

(Отредактировано автором: 30 Сентября, 2010 - 19:10:04)

 
 Top
EuGen Администратор
Отправлено: 01 Октября, 2010 - 09:25:42
Post Id


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


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


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




Скорее, это вопрос к движку форума. Соответственно фидбэк в тему о багах.
В спойлер я поместил ссылку на решение имеющихся задач.

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


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


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


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


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




Топик, конечно, устарел, но тем не менее - встретилась одна задача, которая может быть полезна на практике.

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

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


Ваши идеи?


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



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


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


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




EuGen пишет:
Ваши идеи?
на строй версии php при копировании объекта копировались и все данные объекта, достаточно было бы всего лишь посмотреть разницу в свободном месте в памяти, а вот на 5.3 (кажись) при копировании объекта происходит копирование по ссылке, так что надо думать
 
 Top
Panoptik
Отправлено: 06 Марта, 2012 - 15:48:41
Post Id



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


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


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




EuGen пишет:
@mVar mixed
то есть типы ресурс и объект?


-----
Just do it
 
 Top
EuGen Администратор
Отправлено: 06 Марта, 2012 - 15:53:15
Post Id


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


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


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




Panoptik
Разумеется. Более того, это может быть, скажем, многомерный массив, в измерениях которого записаны ресурсы, объекты, что угодно. Или объект с атрибутами - массивами произвольного содержимого и т.п.
И, таким образом, на вариант DlTA (насколько я понял это memory_get_usage + копирование переменной + memory_get_usage + расчет разницы) может попросту не хватить памяти (например, переменная имеет размер 25Mb а лимит памяти равен 30Mb). Поскольку неизвестен размер переменной, он может быть любым - несколько гигабайт, например, так что копирование может привести вдобавок и к отказу исполнения скрипта по причине лимита времени (даже если памяти хватает)
Поэтому такой вариант я не рассматривал.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Bio man
Отправлено: 06 Марта, 2012 - 18:05:45
Post Id


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


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


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




может как то так?
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
 
 Top
DlTA
Отправлено: 06 Марта, 2012 - 22:40:56
Post Id



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


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


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




Bio man пишет:
в данном случае погрешность составляет 224 байта
метод мало чем отличается от предложенного мной више(

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


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


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


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




Цитата:
разница до удаления и после и должно быть размером субъекта

это если сборщик мусора сработает


-----
Open Source учетная система http://zippy[dot]com[dot]ua/
 
 Top
DlTA
Отправлено: 08 Марта, 2012 - 00:16:51
Post Id



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


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


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




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


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

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

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