Расстановка знаков операций в N-значном числе (С++) - Помощь студентам

Aspirisha · 12.11.2012, 15:41

Здравствуйте. Недавно попалась довольно интересная задачка на лабораторной, и как ее нормально решить я пока не понял.

Условия:
На вход подается 2 числа. Первое не более чем 100-значное, второе влезает в int.

1. Необходимо получить второе число вставив знаки операций между цифрами первого числа.
2. Скобки ставить не надо - то есть только + - * / или ничего (если ничего, то цифры склеиваются в число - понятно).

Очевидно, простой перебор в худшем случае переживет нашу вселенную. Не говоря уже о том что становятся к тому же дорогими вычисления - нужна длинная арифметика.
Я написал рекурсивную функцию, которая работает для чисел до 10^12. При увеличении разрядности она конечно выпадает в осадок.
Есть ли идеи как оптимизировать перебор до ~ 10^8 операций? При необходимости могу сюда вставить код текущей функции.

Есть идея оптимизировать отсекая заведомо паршивые ветки рекурсии - то есть такие где текущее число например настолько маленькое, что его не увеличить до нужного даже используя все оставшиеся справа цифры как одно число. Но мне кажется, это тоже не сильно поможет делу.

Abstraction · 12.11.2012, 15:55

"Скобки ставить не надо" - читай, "скобки ставить нельзя"?
Действительно, интересная задача. Навскидку, я бы попытался опереться на то, что предоставленная нам свобода избыточна - т.е. с высокой вероятностью можно получить произвольное число из ~20 значного. Тогда остальные цифры можно превратить в случайное выражение и перенести его на другую сторону. Также, возможно, хорошей идеей будет перенос с приближением к 0 - простейший жадный алгоритм вырывает из большого числа слагаемые, по возможности уменьшающие по модулю остаток; 20-30 случайных цифр не должно быть проблемой преобразовать в заданное двузначное число.

Aspirisha · 12.11.2012, 16:20

Да, скобки ставить нельзя.
Насчет избыточной свободы - хорошая идея. Даже очень! Я ее почему то откинул еще на стадии обдумывания (дескать, если есть 2 50-значных равных числа в записи первого и надо получить 1, то может статься что 1 никак не получить кроме как делением). Сейчас попробую реализовать. Если не получится, попробую приближать к 0.

Aspirisha · 12.11.2012, 16:37

Работать стало быстро, и если надо построить маленькое число оно находит последовательность действий почти всегда. Для 6-7 разрядных чисел уже не всегда. Разумеется, это логично, большое число получить сложнее, но дело в том, что никак не проверить, его нельзя получить действительно или это ошибка программы. Черт, тяжело решать задачу не зная решения.
Вернее нет, работает увы неверно. проверить можно сделав так например

6778630834736463746378436347043
646374
По идее 2 зеленых нуля убивают все лишнее и мы способны точно получить второе число из первого. Увы пока никак.

Abstraction · 12.11.2012, 17:20

Достаточно безопасно предполагать, что решение есть, на самом деле.

$6778630834736463746378436347043 (646374)
677863$0834736463746378436347043 (-31489)
677863-083*473$6463746378436347043 (7770)
677863-083*473+6463$746378436347043 (1307)
677863-083*473+6463+746$378436347043 (561)
677863-083*473+6463+746+378$436347043 (183)
677863-083*473+6463+746+378+4*36$347043 (39)
677863-083*473+6463+746+378+4*36+34$7043 (5)
Из 7043 5 не получается, шаг назад:
677863-083*473+6463+746+378+4*36$347043 (39)
677863-083*473+6463+746+378+4*36-34/7+043 (0)

Aspirisha · 13.11.2012, 00:51

Abstraction, спасибо за совет. Особенно с уменьшением остатка - ты прав, это действенный способ.

Aspirisha · 17.11.2012, 15:54

Если кому либо когда либо еще понадобится - используйте поиск с возвратом. То есть полный перебор рекурсивно с умными ограничениями - например, не брать в рассмотрение число если оно меньше чем 1% от искомого или больше чем 100 искомых. Если ответ не находится - увеличивайте точность (ослабляйте условия выхода). Написал так, пока что не смог найти контрпример, работающий дольше 4 секунд.

12.11.2012, 15:41	#1
Aspirisha Пользователь Регистрация: 12.11.2012 Сообщений: 20	Расстановка знаков операций в N-значном числе (С++) Здравствуйте. Недавно попалась довольно интересная задачка на лабораторной, и как ее нормально решить я пока не понял. Условия: На вход подается 2 числа. Первое не более чем 100-значное, второе влезает в int. 1. Необходимо получить второе число вставив знаки операций между цифрами первого числа. 2. Скобки ставить не надо - то есть только + - * / или ничего (если ничего, то цифры склеиваются в число - понятно). Очевидно, простой перебор в худшем случае переживет нашу вселенную. Не говоря уже о том что становятся к тому же дорогими вычисления - нужна длинная арифметика. Я написал рекурсивную функцию, которая работает для чисел до 10^12. При увеличении разрядности она конечно выпадает в осадок. Есть ли идеи как оптимизировать перебор до ~ 10^8 операций? При необходимости могу сюда вставить код текущей функции. Есть идея оптимизировать отсекая заведомо паршивые ветки рекурсии - то есть такие где текущее число например настолько маленькое, что его не увеличить до нужного даже используя все оставшиеся справа цифры как одно число. Но мне кажется, это тоже не сильно поможет делу.

12.11.2012, 16:37	#4
Aspirisha Пользователь Регистрация: 12.11.2012 Сообщений: 20	Работать стало быстро, и если надо построить маленькое число оно находит последовательность действий почти всегда. Для 6-7 разрядных чисел уже не всегда. Разумеется, это логично, большое число получить сложнее, но дело в том, что никак не проверить, его нельзя получить действительно или это ошибка программы. Черт, тяжело решать задачу не зная решения. Вернее нет, работает увы неверно. проверить можно сделав так например 6778630834736463746378436347043 646374 По идее 2 зеленых нуля убивают все лишнее и мы способны точно получить второе число из первого. Увы пока никак. Последний раз редактировалось Aspirisha; 12.11.2012 в 16:40.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Найдите наибольшее произведение пяти последовательных цифр в 1000-значном числе.	RealBig	Помощь студентам	4	30.06.2011 15:10
Определить сколько знаков в числе, вычислить сумму цифр и определить старшую цифру	Blombox	Помощь студентам	5	25.04.2011 15:52
Счёт кол-во знаков в числе (Pascal)	_fynjy_	Помощь студентам	6	06.12.2010 20:19
(+,-,*,/)Расстановка знаков	МаксимNEWProgramm	Паскаль, Turbo Pascal, PascalABC.NET	5	17.04.2008 17:04

12.11.2012, 15:55	#2
Abstraction Старожил Регистрация: 25.10.2011 Сообщений: 3,178	"Скобки ставить не надо" - читай, "скобки ставить нельзя"? Действительно, интересная задача. Навскидку, я бы попытался опереться на то, что предоставленная нам свобода избыточна - т.е. с высокой вероятностью можно получить произвольное число из ~20 значного. Тогда остальные цифры можно превратить в случайное выражение и перенести его на другую сторону. Также, возможно, хорошей идеей будет перенос с приближением к 0 - простейший жадный алгоритм вырывает из большого числа слагаемые, по возможности уменьшающие по модулю остаток; 20-30 случайных цифр не должно быть проблемой преобразовать в заданное двузначное число.

12.11.2012, 16:20	#3
Aspirisha Пользователь Регистрация: 12.11.2012 Сообщений: 20	Да, скобки ставить нельзя. Насчет избыточной свободы - хорошая идея. Даже очень! Я ее почему то откинул еще на стадии обдумывания (дескать, если есть 2 50-значных равных числа в записи первого и надо получить 1, то может статься что 1 никак не получить кроме как делением). Сейчас попробую реализовать. Если не получится, попробую приближать к 0.

12.11.2012, 17:20	#5
Abstraction Старожил Регистрация: 25.10.2011 Сообщений: 3,178	Достаточно безопасно предполагать, что решение есть, на самом деле. $6778630834736463746378436347043 (646374) 677863$0834736463746378436347043 (-31489) 677863-083473$6463746378436347043 (7770) 677863-083473+6463$746378436347043 (1307) 677863-083473+6463+746$378436347043 (561) 677863-083473+6463+746+378$436347043 (183) 677863-083473+6463+746+378+436$347043 (39) 677863-083473+6463+746+378+436+34$7043 (5) Из 7043 5 не получается, шаг назад: 677863-083473+6463+746+378+436$347043 (39) 677863-083473+6463+746+378+436-34/7+043 (0)

13.11.2012, 00:51	#6
Aspirisha Пользователь Регистрация: 12.11.2012 Сообщений: 20	Abstraction, спасибо за совет. Особенно с уменьшением остатка - ты прав, это действенный способ.

17.11.2012, 15:54	#7
Aspirisha Пользователь Регистрация: 12.11.2012 Сообщений: 20	Если кому либо когда либо еще понадобится - используйте поиск с возвратом. То есть полный перебор рекурсивно с умными ограничениями - например, не брать в рассмотрение число если оно меньше чем 1% от искомого или больше чем 100 искомых. Если ответ не находится - увеличивайте точность (ослабляйте условия выхода). Написал так, пока что не смог найти контрпример, работающий дольше 4 секунд.