Конец примера
1.
В приведенном примере вариантом
решения являлась переменная i, используемая
как счетчик цикла. Не трудно представить
себе, задачу, где такое невозможно. Например,
вариант может не быть целым числом. В
этом случае переменная счетчик цикла
выступает как номер варианта, а в цикле
требуется совершить еще одно действие:
по номеру определить этот самый вариант.
То есть вместо схемы:
Перебираем варианты
и проверяем, удовлетворяют ли они условию
будем иметь схему
Перебираем номера
вариантов, по номеру вычисляем вариант
решения, проверяем
Пример
2. Найти минимумы функции
с точностью до 0.001 на отрезке от –5 до
5.
Для поиска минимума будем перебирать
все числа от –5 до 5 с шагом 0.001. Условием
нахождения минимума будем считать то,
что значение функции
меньше, чем в соседних точках. А именно:
. Данный алгоритм можно реализовать с
помощью программы:
Step:=0.001;
MinX:=-5;
MaxX:=5;
VarNumber:=trunc((MaxX – MinX)/Step)+1; {Вычисляем
количество
перебираемых вариантов решения}
for i:=1 to VarNumber do
begin
x:=MinX + (i-1)*step; {Вычисляем вариант,
соответствующий номеру i}
if (sqr(sqr(x))–sqr(x) < sqr(sqr(x-step))–sqr(x-step))
and
(sqr(sqr(x))–sqr(x) < sqr(sqr(x+step)) then
writeln(x);
end; |
Кроме перебора вариантов здесь
в начале программы использован еще один
важный прием, называемыйпараметризацией.
Такие характеристики как точность и диапазон
поиска были записаны в отдельные переменные,
а затем вместо чисел использовались имена
этих переменных. Такой подход позволяет
легче модифицировать программу, если
параметры задачи изменятся, программа
становится более универсальной. Кроме
того, программа становится более понятной,
особенно если имена переменных выбраны
так, чтобы соответствовать смыслу, хранимого
в них параметра (MinX – минимальное значение
переменной x и т.п.)
Каждый следующий проверяемый
вариант можно также вычислять не по номеру
а по предыдущему значению
Очевидно, это ничем не хуже.
Пример
3. Пусть двумя числами
(H и V) задано положение коня на шахматной
доске. Найдите координаты всех клеток,
куда конь может пойти следующим ходом
(других фигур на доске нет).
В данном примере, вариантами
решения являются координаты клеток, то
есть каждый вариант это не одно число,
а два. Необходимо придумать способ вычисления
варианта (в данном случае номеров горизонтали
и
вертикали) по его номеру.
Всего клеток 64. Пронумеруем
клетки, как показано на рисунке. Теперь,
если мы будем перебирать в цикле номера
клеток N, необходимо
уметь по этим номерам определять номер
горизонтали X и вертикали Y. Нетрудно видеть, что
номер горизонтали определяется тем сколько
раз по 8 клеток надо взять, пока мы не доберемся
до числа N:
(N - 1) потому что важно
сколько горизонталей заполняют
клетки лежащие до N-й, а их как
раз N - 1.
Остаток после удаления целого
числа раз по 8 клеток позволит вычислить
номер вертикали:
Теперь, когда мы умеем перебирать
варианты, необходимо записать условие
того, что данный вариант является решением
задачи. Известно, что конь ходит буквой
Г, смещаясь на две клетки в одном направлении
и на одну в другом. Например, на рисунке
показан ход, когда перемещение коня состоит
из сдвига на две клетки по вертикали и
на одну по горизонтали.
Пусть проверяется клетка с координатами
(x, y). Тогда условие
сдвига по горизонтали на 2 будет выглядеть
так:
Взятие модуля необходимо, чтобы
учесть возможность сдвига как вправо,
так и влево. Аналогично условие сдвига
на одну клетку, например, по вертикали:
Полное условие возможности
пойти на клетку конем будет выглядеть
как:
((abs(X-H) = 2)and(abs(Y-V) = 1)) or ((abs(Y-V) =
2)and(abs(X-H) = 1)) |
То есть либо сначала по горизонтали
на две клетки, а потом на одну по вертикали
либо на две по вертикали, потом на одну
по горизонтали.
Теперь, когда ясно как перебирать
клетки и как проверять возможность хода,
можно написать требуемую программу:
readln(H, V); {запрашиваем расположение
коня}
for n:=1 to 64 do
begin
X := n div 8 + 1;
Y := n mod 8;
if ((abs(X-H) = 2)and(abs(Y-V) = 1)) or ((abs(Y-V)
= 2)and(abs(X-H) = 1)) then
writeln(X, Y);
end; |
В случае, когда как в приведенном
примере, каждый вариант задается не одним
числом, а несколькими, удобно для перебора
использовать вложенные циклы. В данном
случае номера вертикали и горизонтали
являются целым числами от 1 до 8, поэтому
для перебора их значений можно использовать
счетчики циклов:
readln(H, V);
for X:=1 to 8 do
for Y:=1 to 8 do
if ((abs(X-H) = 2)and(abs(Y-V) = 1)) or ((abs(Y-V)
= 2)and(abs(X-H) = 1)) then
writeln(X, Y); |
Рассмотрим еще один пример,
где вариант задается несколькими числами.
Пример
4. Составить программу-генератор
пифагоровых троек. Пифагоровой тройкой
называют такие целые числа a, b и c, которые
удовлетворяют условию a2+b2=c2. Известно, что существует
прямоугольный треугольник с такими длинами
сторон. Найдем все пифагоровы тройки
для c <
5.
Тройное вложение циклов позволит
перебрать все возможные комбинации значений
трех чисел a, b и c и вывести те из них, которые
удовлетворяют заданному равенству.
MaxC:=25; {Снова используем параметризацию}
MaxAB:=trunc(sqrt(MaxC));
for a:=1 to MaxAB do
for b:=1 to MaxAB do
for c:=1 to MaxC do
if a*a+b*b = c*c then
begin
write(a, ' ', b, ' ', c);
writeln;
end; |
Как всегда при решении задачи
методом перебора, следует задуматься,
можем ли мы сократить число перебираемых
вариантов. Оказывается, можно ограничиться
только перебором a и b, а c вычислять по
теореме Пифагора
. Вычисленное таким образом c может оказаться
нецелым, поэтому условие задачи для него
проверять все равно необходимо.
MaxC:=25; {Используем параметризацию}
MaxAB:=trunc(sqrt(MaxC));
for a:=1 to MaxAB do
begin
for b:=1 to MaxAB do
begin
c:=round(sqrt(a*a+b*b));
if a*a+b*b = c*c then
begin
write(a, ' ', b, ' ', c);
writeln;
end;
end;
end; |
Задание 6. Задачи на перебор
вариантов
1. Для заданного целого
числа проверьте, является ли
оно кубом другого целого числа.
2. Задача Ал-Хорезми (ок. 780-850).
Разложить число 10 на 2 слагаемых, сумма
квадратов которых равна 58.
3. Задача Л.Эйлера. Некий
чиновник купил лошадей и быков
на сумму 1770 талеров. За каждую
лошадь он уплатил по 31 талеру,
а за каждого быка по 21 талеру.
Сколько лошадей и быков купил
чиновник? Используйте прием параметризации,
чтобы легче было модифицировать
программу при изменении рыночных
цен и финансовых возможностей
чиновника.
4. Теорема Ферма утверждает,
что не существует решения
в целых положительных числах
уравнения
при
. Напишите программу, которая проверяла
бы это утверждение при заданном n для всех x, y и z меньших 100.
5. Найдите все трехзначные
числа, сумма цифр которых равна
произведению цифр.
6. Решите следующие числовые
ребусы:
УДАР + УДАР = ДРАКА
БУЛОК + БЫЛО = МНОГО
КОКА + КОЛА = ВОДА
ПОДАЙ — ВОДЫ = ПАША
ТРИ + ТРИ + ТРИ = ДЫРА, причем (Ы + Ы) : Ы = Ы
Здесь каждая буква взаимнооднозначно
соответствует какой-нибудь цифре. Первая
цифра числа не может быть нулем.
7.1. Переменные-флаги:
теория
Флаг – это полотнище правильной
(как правило, прямоугольной) формы прикрепленное
к древку или поднимаемое на специальной
мачте (флагштоке). Исторически флаги появились
для передачи простых сигналов на поле
боя. Например: подняли флаг, и конница
понеслась в атаку! Как-то так. В простейшем
случае с помощью флага передается информация
объемом 1 бит (одно из двух: флаг поднят
или нет).
Переменная флаг – это, как правило,
переменная логического типа, значение
которой сигнализирует о состоянии вычислительного
процесса. Приведем несколько примеров,
когда результат может характеризоваться
всего одной логической переменной:
1) Подводится баланс коммерческого
предприятия. Дальнейшие действия
могут зависеть от того, будет
он положительным или отрицательным.
Если отрицательный, надо просить
кредит, положительный – планировать
отдых на Багамах. В общем, самая
существенная информация может
быть передана одним битом.
2) Решаем квадратное уравнение.
Если дискриминант не отрицательный
– ищем корни. Для хода вычислительного
важен факт не отрицательности,
который также содержит 1 бит информации
и может, таким образом, быть сохранен
с помощью логической переменной.
3) Детям на уроке физкультуры
велено построиться по росту.
Если они построились не по
росту, надо на них наорать. Опять
действия учителя зависят от
информации объемом 1 бит.
Но кто и кому может передавать
информацию в ходе выполнения программы?
Дело в том, что при разработке больших
программ происходит разделение задачи
на более мелкие подзадачи (блоки), каждая
из которых решается отдельно и, может
быть даже, разными людьми. В этом случае
один блок, закончив свою работу должен
передать ее результат другому блоку.
Здесь и могут пригодиться флаги.
Пример
1. Решение квадратного
уравнения.
Предположим, что программу
решения квадратного уравнения пишут
два человека (ну, можно же). Пусть первый
умеет решать квадратные уравнения, но
не знает, как вывести результат (не ходил
на лекции). Второй знает, как вывести результат,
но про квадратные уравнения слышит первый
раз в жизни. Попробуем представить, какую
программу они напишут.
var
a, b, c: real; {Коэффициенты уравнения
}
d: real; {Дискриминант}
x1, x2: real; {Корни}
RootsExist: boolean; {Переменая-флаг}
begin
{Блок, написанный первым
программистом}
readln(a, b, c);
d := sqr(b)-4*a*c;
RootsExist := (d>=0); {Флаг служит
для хранения
информации о наличии корней}
if RootsExist then
begin
x1:=(-b+sqrt(d))/(2*a);
x2:=(-b-sqrt(d))/(2*a);
end;
{Блок, написанный вторым
программистом}
if RootsExist then
writeln(x1, x2)
else
writeln('Roots don’t exist');
end. |
Переменная-флаг передает информацию
о наличии корней. С ее помощью первый
блок сигнализирует второму блоку. Вы
скажете, почему бы второму программисту
вместо строчки
не написать
Зачем использовать еще одну
переменную? Давайте вспомним, что второй
программист ничего не знает о квадратных
уравнениях и в частности не в курсе, что
наличие корней определяется знаком дискриминанта.
Не вдаваясь в тонкости чужой задачи, он
просто просит первого программиста передать
существенную информацию, через переменную-флаг.
На таком простом примере, как
решение квадратного уравнения трудно
проникнутся ощущением полезности флагов.
Я, пожалуй, соглашусь, что в данном случае
флаг это лишнее. Однако, нетрудно представить
себе более сложную задачу, где такой подход
окажется полезным.
Представьте себе, что вам требуется
написать программу размером несколько
тысяч строк (это сравнительно небольшая
программа). Есть единственный способ
создавать программы такого размера –
это разбиение решаемой задачи на подзадачи
и написание отдельных блоков программы,
решающих каждый свою подзадачу. Чтобы
можно было сосредоточиться на решении
отдельной подзадачи надо сделать их решение
по возможности максимально независимым
друг от друга. Для этого от одного блока
к другому должно передаваться как можно
меньше информации. Так что даже если программу
пишет всего один человек, флаги облегчат
его работу.
Как уже отмечалось, флаги минимизируют
информацию, передаваемую между блоками.
Так в примере с квадратным уравнением
использование флага позволило передавать
всего 1 бит вместо 8-ми байт, которые пришлось
бы потратить на значение дискриминанта.
Общий принцип здесь такой – чем меньше
информации, тем труднее допустить ошибку.
При разработке сложных программ поиск
ошибок занимает больше времени, чем собственно
их написание и любая возможность уменьшить
вероятность их появления должна приветствоваться.
В дополнение еще один пример.
Пример
2. Проверка упорядоченности
последовательности.
Пользователь вводит 10 чисел.
Требуется проверить, упорядочены ли они
по возрастанию, и передать эту информацию
с помощью переменной флага.
Решение:
Growing:=true; {Переменная флаг}
readln(x);
for i:=2 to 10 do
begin
x2:=x;
readln(x);
Growing:=Growing and (x > x2);
end; |
Если очередное введенное число
(x) будет меньше предыдущего (x2), то флаг
примет значение false и сохранит это значение
до конца цикла.
Блоки, передающие друг другу
информацию с помощью флагов, не обязательно
должны идти последовательно друг за другом.
Можно представить себе ситуацию, когда
один блок является составной частью другого.
Например:
Пример
3: Найти все простые
числа от 1 до N.