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
http://forum.php.su/topic.php?fo...18013#1356718013
34. EuGen - 10 Января, 2013 - 22:26:05 - перейти к сообщению
(Сообщения не по теме удалены)
По поводу задачи - я не уверен, что она - задача - не является NP-полной. Помимо алгоритма построения, у меня нет сейчас идей. Но хотелось бы что-либо более изящное.
По поводу задачи - я не уверен, что она - задача - не является NP-полной. Помимо алгоритма построения, у меня нет сейчас идей. Но хотелось бы что-либо более изящное.
35. DlTA - 16 Мая, 2013 - 00:41:26 - перейти к сообщению
EuGen пишет:
не пойму как была получена 1 из 0?Назовем число непрерывно достижимым в N-ичной системе для некоторого набора чисел, если это число и весь натуральный ряд до него могут быть записаны из чисел данного набора, при том, что каждый член из набора не может быть использован более 1 раза при построении очередного числа. Старт происходит с 0.
Приведу примеры (система - десятичная):
Дан набор чисел (4, 1, 5, 2, 0)
Тогда непрерывно достижимыми в этом наборе будут только числа 0, 1 и 2.
Приведу примеры (система - десятичная):
Дан набор чисел (4, 1, 5, 2, 0)
Тогда непрерывно достижимыми в этом наборе будут только числа 0, 1 и 2.
что именно означает фраза "число и весь ряд до него могут быть записаны из чисел данного набора" можно развернутый пример?
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
Это было краткое описание алгоритма построения, а не математическое определение. Описание алгоритма я дал как развёрнутый пример для понимания того, что я подразумевал под "непрерывной достижимостью".
В примере выше 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?
то получается что это такая последовательность чисел у которой для любого числа есть число -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 включительно будут непрерывно достижимыми в этом наборе.
- Тогда числа от 0 до 21 включительно будут непрерывно достижимыми в этом наборе.
39. DlTA - 16 Мая, 2013 - 09:52:30 - перейти к сообщению
EuGen пишет:
а если бы в этом наборе было число 22 то запнулись бы на 32?
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11)
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 - перейти к сообщению
в теории возможно создать такую последовательность при которой это дело выдаст меньшее значение чем должно быть на самом деле, но надо гонять
(Добавление)
кстати вот вот последовательность
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 (Отобразить)