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
Форумы портала PHP.SU :: Версия для печати :: Вопрос к программистам [3]
Форумы портала PHP.SU » Разное » Прочее » Вопрос к программистам

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

31. SAD - 28 Декабря, 2012 - 23:05:37 - перейти к сообщению
да, задачка, над которой нужно задуматься... Вы уже придумали решение?)
32. EuGen - 28 Декабря, 2012 - 23:07:03 - перейти к сообщению
Если честно - нет. Подозреваю, что это будет некоторый анализ с математической точки зрения, а так же динамическое программирование.
33. SAD - 03 Января, 2013 - 21:37:04 - перейти к сообщению
Подниму тему. Довольно интересная задачка. Сам пока решения не придумал.

http://forum.php.su/topic.php?fo...18013#1356718013
34. EuGen - 10 Января, 2013 - 22:26:05 - перейти к сообщению
(Сообщения не по теме удалены)
По поводу задачи - я не уверен, что она - задача - не является NP-полной. Помимо алгоритма построения, у меня нет сейчас идей. Но хотелось бы что-либо более изящное.
35. DlTA - 16 Мая, 2013 - 00:41:26 - перейти к сообщению
EuGen пишет:
Назовем число непрерывно достижимым в N-ичной системе для некоторого набора чисел, если это число и весь натуральный ряд до него могут быть записаны из чисел данного набора, при том, что каждый член из набора не может быть использован более 1 раза при построении очередного числа. Старт происходит с 0.

Приведу примеры (система - десятичная):
Дан набор чисел (4, 1, 5, 2, 0)
Тогда непрерывно достижимыми в этом наборе будут только числа 0, 1 и 2.
не пойму как была получена 1 из 0?
что именно означает фраза "число и весь ряд до него могут быть записаны из чисел данного набора" можно развернутый пример?
36. EuGen - 16 Мая, 2013 - 09:14:03 - перейти к сообщению
Непрерывно записаны в десятичной записи. То есть записано число и все числа натурального ряда до него - но это не означает, что "записаны все сразу", а означает следующее: берём 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
37. DlTA - 16 Мая, 2013 - 09:43:25 - перейти к сообщению
то есть если уйти от заумных фраз
то получается что это такая последовательность чисел у которой для любого числа есть число -1?
и для набора (4, 1, 5, 2, 0 ) 4 и 5 не канают так как нет 3?
38. EuGen - 16 Мая, 2013 - 09:48:55 - перейти к сообщению
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 включительно будут непрерывно достижимыми в этом наборе.
39. DlTA - 16 Мая, 2013 - 09:52:30 - перейти к сообщению
EuGen пишет:
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11)
а если бы в этом наборе было число 22 то запнулись бы на 32?
40. EuGen - 16 Мая, 2013 - 09:57:11 - перейти к сообщению
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 впридачу).
41. DlTA - 16 Мая, 2013 - 11:09:57 - перейти к сообщению
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 (Отобразить)
42. EuGen - 16 Мая, 2013 - 11:36:49 - перейти к сообщению
Нет, каждое число набора может быть использовано однажды. То есть, например, требуется записать "3000". Это достигается в наборах {30, 0, 0} или {300,0}, но не достигается в наборе {3, 0, 0}
43. DlTA - 16 Мая, 2013 - 11:38:40 - перейти к сообщению
версия 0.10
(Добавление)
вообще версия 1.0 должна быть на порядок сложнее, и уметь перебирать больше вариантов комбинаций, но это надо посидеть.
(Добавление)
да и вообще задача похожа на попытку заполнить жесткий диск с минимальной фрагментацией файла
44. EuGen - 16 Мая, 2013 - 12:06:04 - перейти к сообщению
На самом деле, это решение " в лоб". У меня было аналогичное решение, только я шёл по строке слева, а не справа (просто мне так удобнее, разницы никакой):
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

Однако идея была в том, что, возможно, существуют способы нахождения искомого числа без полного построения.
45. DlTA - 16 Мая, 2013 - 12:12:26 - перейти к сообщению
EuGen пишет:
У меня было аналогичное решение
работает так же не корректно как и мое 0,9
(Добавление)
EuGen пишет:
Однако идея была в том, что, возможно, существуют способы нахождения искомого числа без полного построения.
но это же задача иного раздела, для математиков
(Добавление)
кстати если отсюда вообще выбростиь понятия число, получается интересней

 

Powered by ExBB FM 1.0 RC1