Найти закономерность между числами?

Question

[plr]

Есть исходные числа, 5 штук, на их основании формируется шестое число. Других переменных, кроме 5 чисел — нет, но могут быть константы.


Действия между 5 числами не известны, алгоритм не доступен. Действия могут быть любого характера, не только математические, а, например, по-битный сдвиг, что-то еще хитрее и т.п.


Примеров 5 и результирующим чисел имеем больше кол-во. Т.е. алгоритм может их выдавать до бесконечности.


Можно ли без реверс-инжиниринга существующего кода определить алгоритм, зависимости?


Хотя бы в теории хочу понять, возможно ли решение этой задачи?

Answer 1

[LeoCcoder]

невозможно решить в вашей постановки задачи.

Вы говорите, что есть 5 чисел, то есть нам известены x1, x2, x3, x4, x5. Есть незвестная произвольная функция F, которая вычисляет x6 = F(x1, x2, x3, x4, x5).

Задача: Угадайте F и значение x6.

xDDD

Comments

[plr]

X6, как и X1-X5 известны изначально

[LeoCcoder]

приведите пример, что дано, что надо найти и правильный ответ — тогда будет понятней.

складывается впечатление что нужно задачу решать перебором, генерировать разные функции F и смотреть подходят ли они или нет. Перебор ясен пень надо сделать умным, а не просто так перебирать все возможные варианты F. Виды функций F можно ограничить несколькими шаблончиками…

в общем случае задачу не решить… например, то что у вас в ряду миллион единичек, не гарантирует, что миллион первый член тоже будет единичкой, так как внутри F может быть все что угодно… поэтому правильно ли вы подобрали F вы никогда не узнаете.

Answer 2

[sergeypid]

Это задача для генетического алгоритма. Описано и есть исходный код в книге «Программируем коллективный разум», поищите. Краткая суть алгоритма: математические операции представляются в виде дерева. Например, А + Б это дерево в корне операция сложения, два листа дерева А и Б. Операция А * 2 + Б это дерево в корне +, слева (левый операнд) — Умножение, справа Б. Узел «умножение» опять делится на две ветви — слева А справа 2. Ну в общем вы поняли. Генерируем случайным образом популяцию и запускаем генетический алгоритм. Виды мутаций — копирование и перестановка поддеревьев. Функция выживаемости — насколько полученное математическое выражение правильно находит шестой член для каждой из ваших обучающих последовательностей.

Я пробовал этот исходный код на простых примерах, типа угадать формулы такого вида «А*4 + Б*9» — довольно быстро находится решение на обучающих выборках по 100 примеров. Если у вас достаточное количество обучающих примеров, есть шанс, что найдет решение в вашем случае. Напишите пож. результаты если сделаете.

Answer 3

[Андрей]

Может быть вам поможет аппроксимация?
Правда перед перестановками цифр в результатирующем числе она бессильна))

Answer 4

[ixSci]

Ну в теории всё возможно. У вас есть хорошая база: источник — результат. Поэтому вооружившись криптоаналитиком эту задачу можно решить, в теории. На практике же можно придумать очень сложный алгоритм, который врядли можно будет разрешить или можно, но с привлечением таких средств, что задача того не стоит.

К тому же, если функция для вас черный ящик с чего Вы взяли, что там не используется x7 равный фазе Юпитера в данный, конкретный, момент времени.

Такие задачи, всё же, проще решать реверсом, если, конечно там не угадывается некий шаблон сразу же.

Comments

[plr]

В алгоритме может использоваться х7 равный фазе Юпитера, если это константа. Т.е. в алгоритме не используются более никакие переменные, кроме х1… х6

[ixSci]

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

[plr]

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

Answer 5

[Вячеслав Голованов]

Ну если бы ещё задачу сформулировать попонятнее.
«Других переменных, кроме 5 чисел — нет, но могут быть константы.» — а константы не являются числами?

«Действия могут быть любого характера, не только математические» — я не представляю себе не-математические действия над числами. Число — это математическая абстракция. Побитный сдвиг — это умножение на степень 2, к примеру,…

Разве что, как в той детской задачке, нематематические действия над числами — это когда восьмёрка соответствует двойке, потому что в восьмёрке два кружочка. Но если это такой алгоритм, тогда конечно вряд ли его можно подобрать…

Если вы из головы задачу придумали, нужно её сформулировать строже.

Comments

[plr]

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

Побитный сдвиг — умножение на степень 2 — я не знал, я многого не знаю, посыпаю голову пеплом.

Два кружочка — я не знаю, может быть и используется в алгоритме подобные действия или, например, меняется порядок цифр в результирующем числе.

Я готов сформулировать строже, чего не хватает?

И если принять условие, что действия только математические — можно решить такую задачу?

[Вячеслав Голованов]

Смена цифр — это тоже математическое действие. Поймите, над цифрами нельзя производить нематематических действий, это оксюморон Ж:) Это как производить немузыкальные действия над нотами.

В общем случае решить такую задачу, пожалуй, нельзя.
Например, вот вам такая функция — перемножить все числа, взять от результата синус, и взять у синуса цифру после запятой, стояющую на позиции N, где N — сумма этих 5 чисел.
Естественно, до этого догадаться невозможно никак.
То есть, если не определён набор действий, которые можно над числами производить — это абсурд, этих действий тысячи.

Если ограничить действия арифметическими, к примеру (сложение, умножение, вычитание, деление ) — тогда хоть можно перебором…

Answer 6

[mr_idiot]

Можно попытаться угадать. Точно определить невозможно.

Answer 7

[0leGG]

Ну как минимум для любых x1..x5 можно строить для любого возможного x6 полином 5-ой степени, проходящий через все эти точки, так что предсказать что-либо без дополнительных данных тут не представляется возможным.

Comments

[plr]

Какие нужны дополнительные данные?

Answer 8

[FanKiLL]

Вы можете предоставить хотябы 1 ряд чисел, а лучше ряда 3, в теории можно, если 6'ое число не рендомно, а выполнено по какому то алгоритму, то его можно в теории вычислить.

Ещё эти 5 чисел вы можете задавать сами? Или они выдаются вместе с уже 6 числом?

Answer 9

[nickme]

Как мне кажется, к заданным пяти числам можно добавить любое шестое — обязательно найдется закономерность (и не одна, а бесконечно много)… Например, рассмотрим числа 1, 2, 3, 4, 5:

• x₆=1, т. к. 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, ...
• x₆=2, т. к. 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, ...
• x₆=3, т. к. 1, 2, 3, 4, 5, 3, 4, 5, 6, 7, 5, 6, 7, 8, 9, ...
• x₆=4, т. к. 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3...
• x₆=5, т. к. 1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, ...

Ну и т.д. Другими словами, знание первых n членов числовой последовательности не определяет всех ее остальных членов.

Другое дело, если речь идет о стандратных последовательностях. Например, есть такой онлайн словарь последовательностей, где можно ввести первых несколько чисел и система выдаст какие из известных последовательностей начинаются с таких чисел.

Comments

[nickme]

Примеров 5 и результирующим чисел имеем больше кол-во. Т.е. алгоритм может их выдавать до бесконечности

Плохо прочитал, извиняюсь… Правда, математически это ничего не меняет. Дело в том, что после любой итерации (задали пять чисел, получили шестое), у нас будет конечное число точек, в которых мы знаем значение неизвестной функции f(x1, x2, x3, x4, x5), область определения которой бесконечна. Поэтому, вся эта полученная нами информация не определяет функции. При условии, что мы не знаем априори никаких свойств этой функции…

Answer 10

[GavriKos]

Без известных вариантов действий между числами — нет. Но если можно ограничить их количество — можно попробовать подобрать функцию ген. алгоритмом. Т.е. задача вида «даны 5 чисел, расставте между ними арифметические операции так, чтобы получилось шестое число» ген. алгоритмом разрешима вполне легко.

Answer 11

[Vampiro]

Если результатом является число, и разброс этих пяти входящих достаточно мал, я бы строил для начала таблицы такого вида:

0+0-0+0-0=0
1+0-0+0-0=1
2+0-0+0-0=2
.....
0+1-0+0-0=1
.....
0+0-1+0-0=-1
.......

Понятно, что арифметические операции вам неведомы, но сама такая таблица, в которой будут итоговые результаты при вариации одного параметра, оставляя другие неизменными сможет вас натолкнуть на мысли. Без таких данных я слабо представляю что можно делать кроме аппроксимации полиномами, да и то придется набирать приличное количество точек.

Answer 12

[Petrify]

При бесконечной выдаче алгоритмом наборов 5:1 можно свести задачу к 1:1, т.е. найти много наборов, где изменяется только одна переменная, остальные являются константами. По сути получаем F(x)=y, где х и у известны. обратную функцию можно получить разложением в ряд. Естественно функцию можно восстановить только с определенной точностью.
Имхо задача в теории решаемая.