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
Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737 Форумы портала PHP.SU :: Вопрос к программистам [3]
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
(Сообщения не по теме удалены)
По поводу задачи - я не уверен, что она - задача - не является NP-полной. Помимо алгоритма построения, у меня нет сейчас идей. Но хотелось бы что-либо более изящное.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 00:41:26
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
EuGen пишет:
Назовем число непрерывно достижимым в N-ичной системе для некоторого набора чисел, если это число и весь натуральный ряд до него могут быть записаны из чисел данного набора, при том, что каждый член из набора не может быть использован более 1 раза при построении очередного числа. Старт происходит с 0.
Приведу примеры (система - десятичная):
Дан набор чисел (4, 1, 5, 2, 0)
Тогда непрерывно достижимыми в этом наборе будут только числа 0, 1 и 2.
не пойму как была получена 1 из 0?
что именно означает фраза "число и весь ряд до него могут быть записаны из чисел данного набора" можно развернутый пример?
EuGen
Отправлено: 16 Мая, 2013 - 09:14:03
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 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
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 09:43:25
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
то есть если уйти от заумных фраз
то получается что это такая последовательность чисел у которой для любого числа есть число -1?
и для набора (4, 1, 5, 2, 0 ) 4 и 5 не канают так как нет 3?
EuGen
Отправлено: 16 Мая, 2013 - 09:48:55
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 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 включительно будут непрерывно достижимыми в этом наборе.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 09:52:30
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
EuGen пишет:
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11)
а если бы в этом наборе было число 22 то запнулись бы на 32?
EuGen
Отправлено: 16 Мая, 2013 - 09:57:11
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 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 впридачу).
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 11:09:57
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
в теории возможно создать такую последовательность при которой это дело выдаст меньшее значение чем должно быть на самом деле, но надо гонять (Добавление)
кстати вот вот последовательность
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, это правильно? (Добавление)
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Нет, каждое число набора может быть использовано однажды. То есть, например, требуется записать "3000". Это достигается в наборах {30, 0, 0} или {300,0}, но не достигается в наборе {3, 0, 0}
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 11:38:40
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
версия 0.10 (Добавление)
вообще версия 1.0 должна быть на порядок сложнее, и уметь перебирать больше вариантов комбинаций, но это надо посидеть. (Добавление)
да и вообще задача похожа на попытку заполнить жесткий диск с минимальной фрагментацией файла
EuGen
Отправлено: 16 Мая, 2013 - 12:06:04
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
На самом деле, это решение " в лоб". У меня было аналогичное решение, только я шёл по строке слева, а не справа (просто мне так удобнее, разницы никакой):
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.