Глава 5. АЛГОРИТМЫ
Глава 5. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ
5.1. Олимпиада - 89
r89_1 Задача о ханойских башнях "кочует" по учебникам информатики, не миновала она и кировские олимпиады. Суть решения явно просматривается из текста программы.
Вычислим число f(n) ходов, необходимых для проведения игры с n кольцами. Число ходов f(n) получается в результате переноса башни из (n-1)-го кольца с иглы 1 на иглу 2, затем один ход на перенос n-го кольца с 1 иглы на 3 и переноса башни из (n-1)-го кольца с иглы 2 на иглу 3. Следовательно, f(n)=2*f(n-1)+1. Введем функцию g(n)=f(n)+1=2*f(n-1)+2=2*(f(n-1)+1)=2*g(n-1). Имеем: f(0)=0, g(0)=f(0)+1, f(1)=1, g(1)=f(1)+1=2. По индукции g(n)=2n, и, наконец, f(n)=2n-1. Для игры с 30 дисками требуется 230-1 ходов. Но 210 равно 1024, или порядка 103. Следовательно, 230 порядка 109. Предположим, что компьютер за одну секунду выполняет 106 ходов. Потребуется порядка 0.27 часа для решения задачи.
r89_2 Ограничение на представление слова и текста в виде массива символов дано "под
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
