Как вычислить неизвестную формулу, если известны входные параметры и результат?

Question

[Мимокрокодил]

Есть таблица из большого количества записей числа-результат. Неизвестная формула принимает от трёх до 15 целочисленных переменных (точное число ещё не установлено) и выдаёт целочисленный результат. Какие есть способы вычисления этой формулы?

Answer 1

[LoliDeveloper]

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

Comments

[Денис Загаевский]

Лагранж это самый простой и самый плохой вариант. Смотреть интерполяцию сплайнами.

[LoliDeveloper]

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

Answer 2

[Griboks]

Хочу дополнить Иван Шумов. Действительно, функцию можно только угадать. В таких ситуациях обычно берут несколько гипотез о функциях (например, линейная регрессия) и вычисляют некие критерии правдоподобности (например, критерий Пирсона). А затем выбирают наиболее подходящие функции на каждом участке или сразу на всей области определения.

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

Comments

[Иван Шумов]

А также алкоголь, табак и различные запрещённые вещества)

Answer 3

[Сергей]

Это целый раздел математики. Называется он аппроксимация и интерполяция.
Вам туда.
В общем случае вы можете лишь приблизится к табличных путем интерполяции. А если вы примерно знаете формулу, но вам нужно узнать какие-то коэффициенты в формуле, которая дает результат -- то это уже аппроксимация.

Answer 4

[Иван Шумов]

Никаких. Вообще ноль шансов вычислить гарантированно. Есть некоторый шанс догадаться при наличии данных на большой выборке, но только при очень простой логике

Comments

[LoliDeveloper]

Да, но можно приблизить её, чтобы в пределе (при кол-ве выборки стремящейся к +беск) получалась нужная функция.

[Иван Шумов]

LoliDeveloper, если ее сложность - одна простая арифметическая операция. Ну максимум 2. На третьей точно пока

[LoliDeveloper]

Иван Шумов, не вижу причин так думать. Использование компьютера в разы всё облегчает.

[U235U235]

Есть 15 чисел. Они преобразуются в строки, строки объединяются в одну. Вычисляется md5 хэш этой строки.
Как зная 15 чисел и хэш (число) определить что производились именно такие манипуляции? Никак.
Полиномиальная регрессия хороша, если функция дифференцируема, а если нет?

[LoliDeveloper]

U235U235, так нам ни к чему знать конкретные манипуляции. Главное чтобы приближённый результат при использовании этой функции нас устраивал.

[Иван Шумов]

LoliDeveloper, автор просит именно внутреннюю формулу. Про примерно это ты сам додумал

[LoliDeveloper]

Иван Шумов, в первом комментарии к вашему ответу я сказал именно про приближённое вычисление.

[Иван Шумов]

LoliDeveloper, но автор просил другое

[U235U235]

Если функция - что-то типа генератора псевдослучайного числа, то никакое приближенное значение не пойдет.

[LoliDeveloper]

U235U235 подойдёт вообще-то

[Иван Шумов]

LoliDeveloper, давай я сделаю функцию, которая всегда прибавляет к входному значению единицу, но 29 февраля будет делить на 3. А в бой курантов травить байки про Штирлица.

[LoliDeveloper]

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

[Иван Шумов]

LoliDeveloper, послушай ты в миллионный раз. Ты придумал себе это статистическое попадание и действительно можешь его добиться, пожалуйста. Автор вопроса просто хочет не этого. Так что твоя статистика бесполезна. Совсем. В контексте данного вопроса

[LoliDeveloper]

Иван Шумов, удобно наверное ссылаться из любого контекста на то что хочет автор вопроса.
Я человеку про псевдорандом отвечал.

[Иван Шумов]

LoliDeveloper, ты отвечаешь в комментарии к моему ответ, в вопросе про другое. И даже до появления U235U235 это все утверждал

Answer 5

[Сергей Соколов]

Полиномиальной регрессией.

Answer 6

[Александр Скуснов]

Обучите нейронную сеть. Утверждают, что она аппроксимирует любую функцию. (сама формула останется неизвестной, но ведь главное - результат предсказания?)