Задача о фамилии Тьюринга

Мы посвящаем следующую задачу Алану Тьюрингу (1912–1954) – английскому математику и криптографу, который, помимо других замечательных достижений, сыграл ведущую роль в развитии теоретической информатики.

Задача о фамилии Тьюринга

Эта задача – четвёртый эпизод нашего сериала головоломок. После описания задачи идёт ответ на вчерашнюю головоломку об острове хамелеонов.

Задача о фамилии Тьюринга

Условие. Если мы сгенерируем список всех «слов», составленных из букв G, I, N, R, T и U в лексикографическом порядке, начиная с GINRTU и заканчивая UTRNIG, какую позицию в списке займёт TURING?

Альтернативный подход 🌟. Если вы не знаете, как подступиться к задаче аналитически, но можете решить программно, предложите в комментариях вариант решения общего случая с помощью кода. На входе – строка фамилии, на выходе – её номер в списке «слов», составленных из букв фамилии.

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

Ответ и решение – завтра в 14:00.

***

Решение задачи об острове хамелеонов

В комментариях на сайте Библиотеки программиста пользователь matuseho первым дал правильный ответ и описал разгадку. Нам остаётся только процитировать:

После каждого обмена между двумя хамелеонами, количество хамелеонов соответствующих цветов изменяется следующим образом: -1, -1, +2. То есть остатки при делении кол-ва хамелеонов на 3 меняются одинаково. Исходный набор {10, 14, 15} соответствует набору остатков {1, 2, 0}, а желаемый финальный набор {0, 0, 39} (в любом порядке) соответствует набору остатков {0, 0, 0}. Из набора разных остатков мы не можем получить набор одинаковых, так что вывод: нет, нельзя добиться единого цвета для всех.

proglib.io

Добавить комментарий

Ваш e-mail не будет опубликован.

12 + 16 =