Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 32
Зачем у вас логика на исключениях?
1) унарный минус надо таки учитывать, например для решения 001101
2) какой процент нерешаемых задач? А если разрешить степень и факториал?
2) какой процент нерешаемых задач? А если разрешить степень и факториал?
1) В классическом варианте, вроде как, унарного минуса, степеней и факториалов нет. Как бы то ни было, если разрешить унарный минус, можно выбросить операцию вычитания.
2) Понятия не имею, честно говоря. Код слишком медленный, чтобы пропустить его миллион раз. Я попробую его переписать без исключений в варианте «есть/нет решений» и отпишусь.
С дополнительными операциями, скорее всего, решений будет больше, но всё равно не все комбинации будут решаемы.
001101
001101
(0*0)-(1-101)
(0*0)-1+101
0+0-(1-101)
0+0-1+101
0-(0+1)+101
0-(0+1-101)
0-0-(1-101)
0-0-1+101
2) Понятия не имею, честно говоря. Код слишком медленный, чтобы пропустить его миллион раз. Я попробую его переписать без исключений в варианте «есть/нет решений» и отпишусь.
С дополнительными операциями, скорее всего, решений будет больше, но всё равно не все комбинации будут решаемы.
Нерешаемых задач, если разрешить дробное деление, получилось 93901.
Оптимизация ещё в процессе, сей подсчёт занял около 40 минут, что уже гораздо лучше прошлого раза (оставил на ночь, к утру так и не закончилось).
Оптимизация ещё в процессе, сей подсчёт занял около 40 минут, что уже гораздо лучше прошлого раза (оставил на ночь, к утру так и не закончилось).
Solved 906099 out of 1000000; 90.6099%
С дробями, но без унарного минуса у меня получилось всего 93265 плохих билетов. Вот их список (надеюсь, что он откроется). Есть ли какой-нибудь плохой номер, не попавший в него?
Особенно интересно было бы разрешить кратные факториалы. Типа 3!!-620+00 для 362000.
Унарный минус (в арифметическом варианте) достаточно применять ко всему выражению, т.е. задача сводится к тому, чтобы получить 100 или --100.
А кроме степени и факториала имеет смысл добавить квадратный корень (в более продвинутом варианте есть ещё десятичная точка и периодические дроби — но для 6-значных номеров это перебор). И получаются варианты вроде:
4436: 100=sqrt(sqrt(sqrt(4^(4!))+36
22838: 100=sqrt(2)*((sqrt(2)+sqrt(8))^3-8
не так-то просто их искать автоматически.
А кроме степени и факториала имеет смысл добавить квадратный корень (в более продвинутом варианте есть ещё десятичная точка и периодические дроби — но для 6-значных номеров это перебор). И получаются варианты вроде:
4436: 100=sqrt(sqrt(sqrt(4^(4!))+36
22838: 100=sqrt(2)*((sqrt(2)+sqrt(8))^3-8
не так-то просто их искать автоматически.
1) 0*0-1+101
2) Нерешаемых задач, по моим подсчётам, 101893 из миллиона, т.е. чуть больше 10%. На перебор миллиона номеров ушло примерно 170 секунд.
2) Нерешаемых задач, по моим подсчётам, 101893 из миллиона, т.е. чуть больше 10%. На перебор миллиона номеров ушло примерно 170 секунд.
Интересно, что 101 из 6-значного номера получается уже только в 82% случаев. А получить 10000 из восьмизначного номера — довольно редкий вариант (особенно, если первая и последняя цифры нечётны). Правда, всех номеров я не перебирал.
Бывает так, что ну никак не удаётся найти решение, и конкретная задачка не отпускает весь оставшийся день.
Эта задача вообще выполнима для любого шестизначного числа?
А как обрабатывается деление с остатком?
я реализовывал такую задачу с помощью обратной польской записи. хотя суть та же. только варианты перебираются с помощью добавление новых символов к строке.
А можно поподробнее?
Если я правильно помню, "(222-22)/2" в ОПЗ записывается как «222 22 — 2 /». Если просто добавлять символы в конец строки, такого не получить; если вставлять и в середину — плохо представляю себе реализацию.
Если я правильно помню, "(222-22)/2" в ОПЗ записывается как «222 22 — 2 /». Если просто добавлять символы в конец строки, такого не получить; если вставлять и в середину — плохо представляю себе реализацию.
Составляется набор всех допустимых последовательностей операций. В последовательности 11=6+5 мест для операций, в каждом месте может стоять одна из 5 операций (4 арифметических+загрузка очередной цифры). Фактически набор операций — программа для стековой машины. Затем каждая программа прогоняется на интерпретаторе (тоже нужно написать) для данного набора цифр в билете.
Вставлять после каждого числа и знака. Было (2 + 3) * 4, в ОПЗ будет 23+4*. Хотим добавить все варианты деления на 5 — ставим 5/ после всех знаков и чисел. получаем следующее:
25/3+4* -> (2 / 5 + 3) * 4
25/3+4*
25/3+4*
25/3+4*
25/3+4* -> (2 / 5 + 3) * 4
25/3+4*
25/3+4*
25/3+4*
Вставлять после каждого числа и знака. Было (2 + 3) * 4, в ОПЗ будет 23+4*. Хотим добавить все варианты деления на 5 — ставим 5/ после всех знаков и чисел. получаем следующее:
25/3+4* -> (2 / 5 + 3) * 4
235/+4* -> (2 + 3 / 5) * 4
23+5/4* -> (2 + 3) / 5 * 4
23+45/* -> (2 + 3) * (4 / 5)
23+45*/ -> (2 + 3) / (4 * 5)
25/3+4* -> (2 / 5 + 3) * 4
235/+4* -> (2 + 3 / 5) * 4
23+5/4* -> (2 + 3) / 5 * 4
23+45/* -> (2 + 3) * (4 / 5)
23+45*/ -> (2 + 3) / (4 * 5)
Мсье, try-catch, ну как же так.
Эта задача хорошо решается кодогенерацией.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Автобусный билетик