Последовательности (рекурсивный алгоритм)

Задача та же, что в пункте 1.1. Опишем рекурсивную процедуру Generate(k), предъявляющую все последовательности длины N из чисел 1,...,M, у которых фиксировано начало X[1],X[2],...,X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. При k<N будем сводить задачу к k+1:

procedure Generate(k:byte); var i,j:byte; begin if k=N then begin for i:=1 to N do write(X[i]);writeln end else for j:=1 to M do begin X[k+1]:=j; Generate(k+1) end

end;

Основная программа теперь выглядит очень просто:

program SequencesRecursion; type Sequence=array [byte] of byte; var M,N:byte; X:Sequence; procedure Generate(k:byte);............ begin write('M,N=');readln(M,N); Generate(0) end.

Перестановки (рекурсивный алгоритм)

Задача та же, что в пункте 1.2. Опишем рекурсивную процедуру Generate(k), предъявляющую все перестановки чисел 1,...,N, у которых фиксировано начало X[1],X[2],...,X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k=N мы снова имеем только тривиальное решение - саму перестановку. При k<N будем сводить задачу к k+1:

procedure Generate(k:byte); var i,j:byte; procedure Swap(var a,b:byte); var c:byte; begin c:=a;a:=b;b:=c end; begin if k=N then begin for i:=1 to N do write(X[i]);writeln end else for j:=k+1 to N do begin Swap(X[k+1],X[j]); Generate(k+1); Swap(X[k+1],X[j]) end

end;

Основная программа:

program PerestanovkiRecursion; type Pere=array [byte] of byte; var N,i,j:byte; X:Pere; procedure Generate(k:byte);............... begin write('N=');readln(N); for i:=1 to N do X[i]:=i; Generate(0) end.

Чтобы до конца разобраться в этой непростой программе, советуем выполнить ее на бумаге при N=3. Обратите внимание, что порядок вывода перестановок не будет лексикографическим!

Перебор с отходом назад

Как вы уже поняли, перебор комбинаторных объектов - задача весьма трудоемкая даже для компьютера. Hапример, перестановок из восьми чисел будет 8! = 40320 - число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕHИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i]-i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7,... рассматривать не нужно! Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма

|X[1]-1| + |X[2]-2| +... + |X[k]-k|

уже больше 8, то рассматривать все перестановки, начинающиеся на X[1],...,X[k] уже не нужно - следует вернуться к X[k] и изменить его значение ("отойти назад" - отсюда название метода).

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

X[1],...,X[N],

где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1],...,X[k] (k<N) и хотим продолжить его до решения.

Предположим также, что у нас есть некоторый простой метод P(X[1],...,X[k]), который позволяет получить ответ на вопрос: можно продолжить X[1],...,X[k] до решения (true) или нет (false). Заметим, что значение true еще HЕ ГАРАHТИРУЕТ существование такого продолжения, но зато значение false ГАРАHТИРУЕТ непродолжаемость ("не стоит дальше и пробовать"). Получаем простую рекурсивную процедуру ПЕРЕБОРА С ОТХОДОМ HАЗАД:

procedure Backtracking(k); begin for (y in A[k]) do if P(X[1],...,X[k-1],y) then begin X[k]:=y; if k=N then {X[1],...,X[N] -решение} Backtracking(k+1) end end;

ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ ЗАДАЧИ И РЕШЕНИЯ

ЧАСТЬ 2

Простые задачи.

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

Задача 1.1

Проверить, поместится ли на диске компьютера музыкальная композиция, которая длится m минут и n секунд, если свободное дисковое пространство 6 мегабайт, а для записи одной секунды звука необходимо 16 килобайт.

Задача 1.2

Координаты двух полей шахматной доски заданы в виде двух пар чисел x₁, y₁ и x₂, y₂. На первом поле стоит ферзь, на втором - конь. Определить, бьет ферзь коня, конь - ферзя, или фигуры не угрожают друг другу.

Задача 1.3

Для нормального разведения золотых рыбок необходимо, чтобы на каждую рыбку в аквариуме приходилось не менее 3-х литров воды. По известным объему аквариума и количеству рыбок, в нем содержащихся, определить, является ли аквариум "перенаселенным" или нет, и указать количество рыбок, которых в случае перенаселенности необходимо поместить в другой аквариум.

Задача 1.4

По данным статистического исследования, производительность птицефермы такова, что каждые полторы курицы за полтора дня сносят полтора яйца. Написать программу, которая позволяет рассчитать, сколько яиц (без десятых долей) снесут N кур за d дней (N и d - целые числа).

Задача 1.5

Показать, что любую сумму, большую 7 копеек, можно выплатить, используя только 3-х и 5-ти копеечные монеты. (То есть, для любого целого N>7 найти такие целые числа x и y, что 3x+5y=N).

Задача 1.6

Написать программу, которая переводит величину, заданную в метрах и сантиметрах, в футы и дюймы. 1 фут = 30,48 см; 1 дюйм = 2,54 см. Если величина не переводится нацело, округлить число дюймов до ближайшего целого. Учесть, что 1 фут равен 12 дюймам.

Задача 1.7

Диаметр колеса автомобиля 80 см. Колесо потребует замены через 200 000 оборотов. Определить, доедет ли колесо от города Саратова до города N-ска, если расстояние между ними x километров.

Задача 1.8

Количество цветов, которые может воспроизводить видеоадаптер, определяется количеством бит, отводимых в видеопамяти ПК для описания одной точки. Например, 2 бита позволяют воспроизводить 4 цвета, 4 бита - 16 цветов и т.д. Видеопамять содержит информацию о цвете каждой точки экрана. Определить, может ли картинка на экране монитора с разрешающей способностью видеоадаптера 800x600 содержать 2048 цвета, если видеопамять ПК - 4 мегабайта.

Задача 1.9

Известна цена монитора Samsung SyncMaster в январе 2000 г. и январе 2001 г. Ответьте на вопрос: "Произошло ли удешевление или нет? На сколько процентов изменилась цена изделия?"

Задача 1.10

В совпадающих по типу переменных a и b хранятся некоторые числовые значения. Поменять местами значения этих переменных, не используя третьей дополнительной переменной.