Алгоритм подбора чисел для определенного правила

[schmidt]

Добрый день,

В общем виде ситуация выглядит следующим образом:

Есть начальный набор чисел (заранее известно только их кол-во, но не конкретные значения):

Цитата:

#1 #2 #3 #4 #5 #6

Есть число $R$, изначально равное 0. Над числами 1-6 по порядку выполняется следующая операция:

R = R*7 + N

где $N$ - число из исходного набора.

После завершения обработки всех чисел проверяется собственно "корректность правила": $R$ должно равняться конкретному (заранее заданному в правиле) числу. Есть ли какие-то посильные/оптимальные методы решения подобных задач?.. Мне пока что ничего, кроме метода прямого подбора, тыкая "пальцем в небо" в голову не приходит. Поделитесь идеями, пожалуйста, если они у вас есть.

Deggial: формулы и код поправил. Код оформляйте тегом code, формулы - $\TeX$ом, иначе тема будет перемещена в Карантин.

[Cash]

Вообще непонятно. Что искать-то нужно???

-- Пт июн 21, 2013 12:50:38 --

По заданному числу подобрать набор?
Ограничения на числа в наборе есть? Неотрицательные, ограничены сверху, может еще что-то?
Нужно найти хотя бы один или все наборы?

[schmidt]

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

Сама задача прямиком из программного обеспечения: есть строка символов (ключ) и процедура его проверки, которая исполняется в соответствии с вышеописанным правилом. Сижу и размышляю над обратной задачей - как на основе этого правила написать генератор ключей. Я так предполагаю, что алгоритм генератора в упрощенном виде должен выглядеть так:

1. Сгенерировать первое случайное число (символ)
2. Подобрать остальные числа в набор так, чтобы правило выполнялось.

Сложность этого подхода заключается в том, что он "слишком неопределен". Иными словами это все равно, что пытаться отыскать набор из N чисел, сумма которых равняется точному числу. С 2мя числами все просто: 1е по рандому, а второе - разность результата и 1го. А вот с 3 и более - это все равно, что слепому звезды считать. Я как-то уже писал такой генератор и работал он очень медленно и без всякой гарантии на успех.

[Sonic86]

schmidt в сообщении #739181 писал(а):

Сама задача прямиком из программного обеспечения: есть строка символов (ключ) и процедура его проверки, которая исполняется в соответствии с вышеописанным правилом. Сижу и размышляю над обратной задачей - как на основе этого правила написать генератор ключей. Я так предполагаю, что алгоритм генератора в упрощенном виде должен выглядеть так:

У Вас получается дана строка символов $a_1,...,a_n$ (ключ), а $R=a_1q^{n-1}+a_2q^{n-2}+a_{n-1}q+a_n$ ($q=7$, $N$ похоже на число в семиричной системе счисления с цифрами $a_1,...,a_n$). Вы ASCII-коды символов складываете? Я как бы буковки складывать не умею Ну т.е. умею, но не в $\mathbb{Z}$, но это не то...
Еще вопрос: у Вас $R$ - произвольное натуральное число или тип целого числа ($R$ по модулю $2^{A}$).
Ну в принципе в любом случае Вы должны осознавать, что решений будет очень много - порядка $O(a^n)$. Т.е. ключи и хэши как бы не дураки придумали

-- Пт июн 21, 2013 16:04:34 --

schmidt в сообщении #739181 писал(а):

Иными словами это все равно, что пытаться отыскать набор из N чисел, сумма которых равняется точному числу.

Число способов разбить число $R$ на $n$ слагаемых равна $\binom{R+n-1}{R}$ (вроде, пойду проверю... главное - много очень)

[Joker_vD]

$(q^{n-1},q^{n-2},\dots,q,1)=1$, поэтому обобщенный алгоритм Евклида вас спасет... если у вас нету ограничений на диапазон значений $a_i$. Иначе все плохо.

[Cash]

Если задача - найти все наборы из положительных чисел без прочих ограничений, то перебор видится следующим:
Формируем начальный набор, удовлетворяющий равенству
$R=a_nq^{n-1}+a_{n-1}q^{n-2}+a_{2}q+a_1$

1. $i\leftarrow 1$
2. $a_i \leftarrow R \mod q$
3. $R \leftarrow \lfloor R/q \rfloor$
4. $i \leftarrow i+1$
5. Если $i<n$ перейти к п.2
6. $a_n \leftarrow R$

Этот набор можно представить следующим образом: у нас есть $n$ ячеек, в первой (крайней левой) ячейке находится $M= \lfloor R/q^{n-1} \rfloor-1$ кубиков, прочие пусты. Перемещая вправо один кубик из ячейки i в ячейку j, мы $a_i$ уменьшаем на 1, $a_j$ увеличиваем на $q^{i-j}$. Рекурсией мы можем получить все размещения $M$ кубиков по $n$ ячейкам. Общее число способов очень похоже на то, что указал Sonic86, тоже боюсь напутать, но что-то вроде $A^n_{M+n}$. Как-то так...

-- Сб июн 22, 2013 08:59:26 --

ТС рекомендую почитать про системы счисления, только не Вики (там ужас-ужас), а в популярной литературе для школьников, ее предостаточно.

[DredFeel]

Здравствуйте,
А можно ли использовать данную модель не только для нахождения численных значений,но и буквенных значений?