6. Комбинаторные задачи
6. Комбинаторные задачи
Головоломка 28.
Действительно ли вам что-то еще нужно сообщать? Тогда я немного уточню способ поддержания части от 1 до р в порядке неубывания. Исходим ив упорядоченного по неубыванию вектора a1, a2, …, ар. Вы последовательно заменяете элемент ар элементами аi, где i направлен по убыванию. Вы последовательно получите
a1, a2, …, ар-1, ар,
a1, a2, …, ар, ар-1,
a1, a2, …, ар-3, ар-1, ар, ар-2.
По индукции, предположим, что в некоторый момент вы получили
a1, …, аi-1, аi+1, …, ар, аi
после перемены мест элементов с номерами i, р.
На следующем ходе вы поменяете местами аi-1 и последний член, который равен аi. Эта форма остается неизменной, и первая часть, от 1 до р ? 1, остается отсортированной в неубывающем порядке. В конце вы получите
a2, a3, …, ар, a1.
Чтобы восстановить исходный порядок, вы располагаете последний элемент на запасном поле, поднимаете все остальные элементы на одну ступень, а затем размещаете содержимое запасного поля на первом месте.
Это вы делаете только в случае необходимости. Незачем восстанавливать порядок, когда все закончено.
Процедура работает достаточно быстро для того, чтобы в случае неудачи иметь возможность испытать наличие решения для n ? 1, а затем для n + 1. Таким образом, по прошествии 45 с для каждого кандидата мы получаем в качестве результата
— решение, если оно существует,
— приближение о точностью до единицы, если это возможно.
Эта программа терпит неудачу крайне редко.
В выпуске от 8 марта 1984 года следующий розыгрыш не был найден ни кандидатами, ни Бертраном, ни кем- либо из присутствующих:
50 10 10 5 4 2 n = 767.
На моем микрокомпьютере нужно 18 с, чтобы обнаружить, что эта задача не имеет решения, а затем еще 5 с, чтобы получить
50 ? 10 = 40 , 40 * 5 = 200, 10 ? 2 = 8,
200 ? 8 = 192, 192 * 4 = 768.
Для задачи
9 7 6 4 3 1 n = 795 через 6 с получается
4 * 9 = 36, 36 + 1 = 37, 37 * 7 = 259,
259 + 6 = 265, 265 * 3 = 795.
Наконец,
100 50 8 5 4 2 n = 631.
За менее чем 2 с получаем
50 ? 4 = 46 , 46 * 2 = 92, 92 * 8 = 736,
100 + 5 = 105 , 736 ? 105 = 631.
Я уже предлагал вам следующий пример:
100 75 50 25 10 10.
Для n = 370 особой трудности нет, потому что это — кратное десяти.
Компьютер сообщает мне
75/25 = 3,
50 ? 3 = 47,
47 * 10 = 470,
470 ? 100 = 370.
Это уже интересно, потому что это — совершенно не то решение, которое я собирался искать.
Чтобы найти 369, нужно образовать число, не кратное 5, — чего нельзя сделать с помощью какой-либо из трех операций +, ?, *, сохраняющих кратность пяти. Следовательно, нужно использовать деление. Вот решение:
50/10 = 5,
5 * 75 = 375,
375 ? 10 = 365,
100/25 = 4,
365 + 4 = 369.
Обе представленные здесь программы не позволяют получить это решение. Действительно, оно записывается в виде
(50/10) * 75 + 100/25 ? 10.
А число 368? Вы нашли для него решение? Я не сумел. Но Жак Бейгбеде сообщил мне, что он получил его делением на 25…
10 * 100= 1000,
1000 ? 75 = 925,
925 * 10 = 9250,
9250 ? 50 = 9200,
9200/25 = 368.