2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Алгоритм подбора чисел для определенного правила
Сообщение21.06.2013, 09:57 


21/06/13
11
Добрый день,

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

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

Цитата:
#1 #2 #3 #4 #5 #6


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

Код:
R = R*7 + N


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

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

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

 Профиль  
                  
 
 Re: Алгоритм подбора чисел для определенного правила
Сообщение21.06.2013, 11:28 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Алгоритм подбора чисел для определенного правила
Сообщение21.06.2013, 18:22 


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

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

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

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

 Профиль  
                  
 
 Re: Алгоритм подбора чисел для определенного правила
Сообщение21.06.2013, 19:02 
Заслуженный участник


08/04/08
8460
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}$ (вроде, пойду проверю... главное - много очень)

 Профиль  
                  
 
 Re: Алгоритм подбора чисел для определенного правила
Сообщение21.06.2013, 19:51 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Алгоритм подбора чисел для определенного правила
Сообщение22.06.2013, 07:51 
Заслуженный участник


12/09/10
1527
Если задача - найти все наборы из положительных чисел без прочих ограничений, то перебор видится следующим:
Формируем начальный набор, удовлетворяющий равенству
$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 --

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

 Профиль  
                  
 
 Re: Алгоритм подбора чисел для определенного правила
Сообщение07.04.2018, 20:35 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group