![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Новости с Эйлерного фронта
Nov. 9th, 2011 02:13 amЧто-то часто я стал на эту тему писать, но вот нравится решать алгоритмические задачки, и все тут! Даже интереснейшую книжку Маркова "Рождение Сложности" про происхождение жизни и эволюцию в свете новейших достижений молекулярной биологии забросил. Но к ней я еще вернусь, а пока несколько красивых или познавательных задач.
8-я задача (максимальная сумма пяти подряд цифр длинного-длинного числа). The power of Scala:
55-я -- поиск чисел Лишрела. Это такие натуральные числа, которые, если их бесконечно переворачивать и складывать сами с собой, никогда не превратятся в палиндромы. Оказывается, большинство чисел "сходятся" к палиндромам очень быстро, буквально за 1-2-3 итерации. Трудно поверить, но это так, я проверял :) Однако, есть такие, которые не сходятся никогда. И хотя до сих пор математически доказать этот факт никто не смог, но эксперименты показали, что если за несколько десятков итераций последовательность не сходится, то она никогда не сойдется. Пример из экспериментальной математики.
Программа так же чрезвычайно проста. Функция, проверяющая числа на лишреловость занимает две строчки.
93-я задача оказалась технически немного сложнее, и в красивые пару строчек не укладывается. Здесь требуется искать натуральные числа, составленные из разных наборов 4х фиксированных цифр, арифметических операций и скобок. Например, (1+2)*3+4. Оказывается, что с таким ограниченным набором можно получить несколько десятков разных чисел, и требуется найти заветную четверку цифр, которая бы дала максимально длинный последовательный ряд выразимых через них чисел, начиная от 1, т.е. 1,2,3,4. Задача опять на комбинаторный перебор, и вся суть, как обычно, в том, чтобы этот перебор сделать максимально просто и эффективно. Чтобы избежать скобок и проще вычислять выражения, я взял обратную польскую запись, и, конечно, решил сэкономить. 4 цифры и три операции можно в обратной польской записи расположить 5-ю разными способами, а именно.
1. XXXX+++
2. XXX+X++
3. XXX++X+
4. XX+XX++
5. XX+X+X+
(здесь 'X' обозначена любая цифра, а '+' -- операция)
Интуитивно мне показалось, что все пять пробовать -- это много, а одного мало. Я не прогадал, в итоге оказалось, что 1й и 4й вполне достаточны для правильного ответа, но интересно было бы строго доказать, что 2й, 3й и 5й варианты не могут дать результата, невыразимого через 1й и 4й, учитывая, что мы можем произвольно переставлять цифры. Что-то простое сходу в голову не приходит, а технически выписывать и сводить одно к другому неохота.
Следующие намеченные задачи -- 100я или 256я. В 100й получается интересное диофантово уравнение, а 256я -- топологическая, к моделированию которой я пока даже не придумал, как подступиться. И это бодрит.
Update: 100я решена. Не могу не отметить грамотность условия, которое сильно облегчает решение. Программирования тут две строчки, остальное -- элементарная математика.
8-я задача (максимальная сумма пяти подряд цифр длинного-длинного числа). The power of Scala:
(s sliding 5) map (_ map (_.toInt-48) product) max
55-я -- поиск чисел Лишрела. Это такие натуральные числа, которые, если их бесконечно переворачивать и складывать сами с собой, никогда не превратятся в палиндромы. Оказывается, большинство чисел "сходятся" к палиндромам очень быстро, буквально за 1-2-3 итерации. Трудно поверить, но это так, я проверял :) Однако, есть такие, которые не сходятся никогда. И хотя до сих пор математически доказать этот факт никто не смог, но эксперименты показали, что если за несколько десятков итераций последовательность не сходится, то она никогда не сойдется. Пример из экспериментальной математики.
Программа так же чрезвычайно проста. Функция, проверяющая числа на лишреловость занимает две строчки.
93-я задача оказалась технически немного сложнее, и в красивые пару строчек не укладывается. Здесь требуется искать натуральные числа, составленные из разных наборов 4х фиксированных цифр, арифметических операций и скобок. Например, (1+2)*3+4. Оказывается, что с таким ограниченным набором можно получить несколько десятков разных чисел, и требуется найти заветную четверку цифр, которая бы дала максимально длинный последовательный ряд выразимых через них чисел, начиная от 1, т.е. 1,2,3,4. Задача опять на комбинаторный перебор, и вся суть, как обычно, в том, чтобы этот перебор сделать максимально просто и эффективно. Чтобы избежать скобок и проще вычислять выражения, я взял обратную польскую запись, и, конечно, решил сэкономить. 4 цифры и три операции можно в обратной польской записи расположить 5-ю разными способами, а именно.
1. XXXX+++
2. XXX+X++
3. XXX++X+
4. XX+XX++
5. XX+X+X+
(здесь 'X' обозначена любая цифра, а '+' -- операция)
Интуитивно мне показалось, что все пять пробовать -- это много, а одного мало. Я не прогадал, в итоге оказалось, что 1й и 4й вполне достаточны для правильного ответа, но интересно было бы строго доказать, что 2й, 3й и 5й варианты не могут дать результата, невыразимого через 1й и 4й, учитывая, что мы можем произвольно переставлять цифры. Что-то простое сходу в голову не приходит, а технически выписывать и сводить одно к другому неохота.
Следующие намеченные задачи -- 100я или 256я. В 100й получается интересное диофантово уравнение, а 256я -- топологическая, к моделированию которой я пока даже не придумал, как подступиться. И это бодрит.
Update: 100я решена. Не могу не отметить грамотность условия, которое сильно облегчает решение. Программирования тут две строчки, остальное -- элементарная математика.
