PHP.SU

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


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

> Описание: Комбинаторика, алгоритмы и прочее - в программном коде
SAD
Отправлено: 28 Декабря, 2012 - 23:05:37
Post Id



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


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


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




да, задачка, над которой нужно задуматься... Вы уже придумали решение?)
 
 Top
EuGen Администратор
Отправлено: 28 Декабря, 2012 - 23:07:03
Post Id


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


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


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




Если честно - нет. Подозреваю, что это будет некоторый анализ с математической точки зрения, а так же динамическое программирование.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
SAD
Отправлено: 03 Января, 2013 - 21:37:04
Post Id



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


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


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




Подниму тему. Довольно интересная задачка. Сам пока решения не придумал.

http://forum.php.su/topic.php?fo...18013#1356718013
 
 Top
EuGen Администратор
Отправлено: 10 Января, 2013 - 22:26:05
Post Id


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


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


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




(Сообщения не по теме удалены)
По поводу задачи - я не уверен, что она - задача - не является NP-полной. Помимо алгоритма построения, у меня нет сейчас идей. Но хотелось бы что-либо более изящное.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 16 Мая, 2013 - 00:41:26
Post Id



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


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


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




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

Приведу примеры (система - десятичная):
Дан набор чисел (4, 1, 5, 2, 0)
Тогда непрерывно достижимыми в этом наборе будут только числа 0, 1 и 2.
не пойму как была получена 1 из 0?
что именно означает фраза "число и весь ряд до него могут быть записаны из чисел данного набора" можно развернутый пример?
 
 Top
EuGen Администратор
Отправлено: 16 Мая, 2013 - 09:14:03
Post Id


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


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


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




Непрерывно записаны в десятичной записи. То есть записано число и все числа натурального ряда до него - но это не означает, что "записаны все сразу", а означает следующее: берём 0, проверям, непрерывно ли он достижим. Так как до нуля нет ничего, то это равносильно тому, что 0 может быть записан из чисел исходного набора, то есть, попросту, принадлежит ли 0 исходному набору. Нет? Конец алгоритма, ответ: "нет". Да? Продолжаем, проверяем, достижим ли непрерывно 1. Так как мы уже знаем, что 0 непрерывно достижим, то достаточно проверить, можно ли записать 1 из чисел исходного набора. Нет? Конец алгоритма, ответ "нет". Да? Идём далее .. Берём N, проверяем, достижимо ли оно непрерывно. Так как мы знаем к этому шагу, что все числа 0..N-1 непрерывно достижимы, то достаточно, чтобы само N можно было записать в числах исходного набора. Нет? Конец алгоритма, ответ: "нет". Да? Конец алгоритма, ответ: "да".

Это было краткое описание алгоритма построения, а не математическое определение. Описание алгоритма я дал как развёрнутый пример для понимания того, что я подразумевал под "непрерывной достижимостью".
В примере выше 1 достижимо просто потому, что в наборе есть 0 и само 1, то есть достижим 0 и достижимо 1.
Можно сформулировать более строго (рекуррентно):
Пусть дан набор чисел U = {U0, U1, ... , Us} - тогда натуральное число N считается непрерывно достижимым в наборе U для M-ичной системы счисления, если оно может быть записано в M-ичной записи из чисел данного набора U0, U1, ... , Us без повторений членов набора, а так же натуральное число N-1 непрерывно достижимо в данном наборе. Если N = 0, то непрерывная достижимость равносильна тому, что 0 E U


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 16 Мая, 2013 - 09:43:25
Post Id



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


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


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




то есть если уйти от заумных фраз
то получается что это такая последовательность чисел у которой для любого числа есть число -1?
и для набора (4, 1, 5, 2, 0 ) 4 и 5 не канают так как нет 3?
 
 Top
EuGen Администратор
Отправлено: 16 Мая, 2013 - 09:48:55
Post Id


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


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


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




DlTA пишет:
для набора (4, 1, 5, 2, 0 )

Верно, для данного набора, очевидно, непрерывно достижимы числа 0, 1, 2 - и всё. На тройке непрерывная достижимость закончится. Само слово "непрерывная" в "достижимости" это и означает - что в контексте натурального ряда достижимость нигде не прерывается.
Однако в общем случае в наборе могут быть любые числа, не обязательно от 0 до 9. И то, какие числа будут непрерывно достижимы, в общем случае неочевидно. Рассмотрите пример, который я уже приводил:
EuGen пишет:
Дан набор чисел (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11)
- Тогда числа от 0 до 21 включительно будут непрерывно достижимыми в этом наборе.


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



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


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


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




EuGen пишет:
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11)
а если бы в этом наборе было число 22 то запнулись бы на 32?
 
 Top
EuGen Администратор
Отправлено: 16 Мая, 2013 - 09:57:11
Post Id


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


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


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




DlTA пишет:
а если бы в этом наборе было число 22 то запнулись бы на 32?

EuGen пишет:
если оно может быть записано в M-ичной записи из чисел данного набора U0, U1, ... , Us без повторений членов набора

- да, тогда не удалось бы записать 33, поскольку нет двух троек или самого 33. Обратите внимание, что U0..Us не подчинены требованию уникальности, значит, к примеру, на 33 алгоритм может "не споткнуться" либо если есть две и более тройки в наборе (например, (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 3) - две тройки), либо есть само 33 - ну или, разумеется, если есть и то, и другое (то есть более 1-й тройки и само 33 впридачу).


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 16 Мая, 2013 - 11:09:57
Post Id



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


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


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




EuGen пишет:
например, (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 3)

версия 0.9 (Отобразить)



в теории возможно создать такую последовательность при которой это дело выдаст меньшее значение чем должно быть на самом деле, но надо гонять
(Добавление)
кстати вот вот последовательность
var_dump(getMaxAchievable(array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 3, 33, 44,55,66,77,88,99,100,10,21,1)));
сказало что 200 может быть
НО 0 есть только 1, а 00 приводится к 0, это правильно?
(Добавление)
0.10 (Отобразить)
 
 Top
EuGen Администратор
Отправлено: 16 Мая, 2013 - 11:36:49
Post Id


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


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


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




Нет, каждое число набора может быть использовано однажды. То есть, например, требуется записать "3000". Это достигается в наборах {30, 0, 0} или {300,0}, но не достигается в наборе {3, 0, 0}


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
DlTA
Отправлено: 16 Мая, 2013 - 11:38:40
Post Id



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


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


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




версия 0.10
(Добавление)
вообще версия 1.0 должна быть на порядок сложнее, и уметь перебирать больше вариантов комбинаций, но это надо посидеть.
(Добавление)
да и вообще задача похожа на попытку заполнить жесткий диск с минимальной фрагментацией файла
 
 Top
EuGen Администратор
Отправлено: 16 Мая, 2013 - 12:06:04
Post Id


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


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


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




На самом деле, это решение " в лоб". У меня было аналогичное решение, только я шёл по строке слева, а не справа (просто мне так удобнее, разницы никакой):
PHP:
скопировать код в буфер обмена
  1. function isAchievable($mNumber, $rgNumbers)
  2. {
  3.    if(in_array((string)$mNumber, $rgNumbers=array_map('strval', $rgNumbers), true))
  4.    {
  5.       return true;
  6.    }
  7.    for($i=1; $i<=strlen((string)$mNumber); $i++)
  8.    {
  9.       if(($iKey = array_search(substr((string)$mNumber, 0, $i), $rgNumbers, true))!==false)
  10.       {
  11.          unset($rgNumbers[$iKey]);
  12.          if(isAchievable(substr((string)$mNumber, $i), $rgNumbers))
  13.          {
  14.             return true;
  15.          }
  16.       }
  17.    }
  18.    return false;
  19. }
  20.  
  21. function getMaxAchievable($rgNumbers)
  22. {
  23.    $mResult = null;
  24.    while(isAchievable((int)$mResult, $rgNumbers))
  25.    {
  26.       $mResult++;
  27.    }
  28.    return --$mResult; // --null is null while ++null is 1? fail! useful here, anyway
  29. }
  30.  
  31. $rgNumbers = array(0,1,2,2,3,4,5,6,7,8,9,11,33);
  32. var_dump(getMaxAchievable($rgNumbers));//43

Однако идея была в том, что, возможно, существуют способы нахождения искомого числа без полного построения.


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



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


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


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




EuGen пишет:
У меня было аналогичное решение
работает так же не корректно как и мое 0,9
(Добавление)
EuGen пишет:
Однако идея была в том, что, возможно, существуют способы нахождения искомого числа без полного построения.
но это же задача иного раздела, для математиков
(Добавление)
кстати если отсюда вообще выбростиь понятия число, получается интересней
 
 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