Глава 3. Задание по программированию Программирование алгоритма дискретной математики
Задание:
Общие положения. При выполнении задания необходимо
1. Подробно описать алгоритм.
2. Подробно описать программу, реализующую алгоритм: типы и структуры данных, блок-схему программы и т.п.
3. Привести листинг программы.
4. Привести результаты решения не мене трех тестовых примеров с различными исходными данными.
Индивидуальное задание(вариант 2):
Черепашка. На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.
Описание программы:
Данная программа была написана на языке Pascal, при помощи оболочки Turbo Pascal.
Так как необходимо обрабатывать элементы квадратной доски, используется двумерный массив, заполняемый пользователем вручную после определения его размера. Одно из условий заключается в том, что на доске расставлены целые, неотрицательные числа, поэтому используем массив типа Integer, при этом сравниваем каждый введенный элемент с нулем. В случае, если a[i, j]<0,
выводится сообщение об ошибке.
Переменная n хранит размер двумерного массива(nxn), переменные i, j используются для определения элементов массива и обращения к ним.
Для реализации алгоритма, в программе есть две подпрограммы (функции), осуществляющие обработку данных.
Первая функция - function maxim(a, b: integer): integer;
Реализует алгоритм определения большего из двух значений, передаваемых функции в качестве параметров a и b.
Вторая функция - function f(x, y: integer): integer;
По условию задачи принимает в качестве параметров индексы первого элемента двумерного массива(левый верхний угол квадратной доски).
Данная функция выполняется до тех пор, пока индексы текущего элемента не совпадут с индексами последнего элемента массива(правый нижний угол квадратной доски).
В случае, если оба индекса первого элемента равны индексам последнего, то функция возвращает значение равное значению первого элемента массива - f := a[x, y].
Если только индекс строки элемента равен индексу последнего элемента, то функция вызывается рекурсивно, принимая в качестве параметров индексы элемента следующего в этой же строке. Тогда значение функции равно - f := f(x, y + 1) + a[x, y].
В случае, когда индекс столбца элемента равен индексу последнего элемента, то аналогично предыдущей ситуации, функция вызывается рекурсивно, принимая в качестве параметров индексы следующего элемента в том же столбце. Значение функции равно - f := f(x + 1, y) + a[x, y].
Последняя возможная ситуация, когда ни один из индексов текущего элемента не равен индексам последнего элемента. В таком случае, при вычислении значения функции f(x,y) вызывается функция maxim(a,b), которой в качестве параметров передаются значения функции f, а именно, параметр a = f(x + 1, y), а параметр b = f(x, y + 1). В данной ситуации значение функции равно - f := maxim(f(x + 1, y), f(x, y + 1)) + a[x, y];
Выполнение программы(после определения функций и переменных):
Теперь опишем работу части кода программы, осуществляющую взаимодействие с пользователем, заключенную между операторами begin - end. Пользователю выводится сообщение, о том, что необходимо ввести размер двумерного массива в формате nxn, т.к. по условию доска квадратная. Введенное пользователем значение присваивается переменной n, после чего пользователь вводит n2 элементов массива(осуществляется при помощи вложенных циклов for). Если пользователь вводит отрицательный элемент массива, то выдается предупреждение, о том, что значение элемента будет изменено на положительное.
После того, как массив заполнен, производится вызов функции f(1,1) и вывод полученного значения на экран вместе с введенной пользователем матрицей.
Блок-схема программы(определение функций вынесено в отдельные блок-схемы)
Блок-схема подпрограммы1(функция maxim(a,b))
Блок-схема подпрограммы2(функция f(x, y))
Блок-схема основной части программы:
Листинг программы:
Uses crt;
Var
n, i, j : integer;
a: array[0..100, 0..100] of integer;
function maxim(a,b: integer): integer;
begin
if a > b then
maxim := a
else
maxim := b;
end;
function f(x, y: integer):integer;
begin
if (x = n) and (y = n) then
f := a[x, y]
else
if (x = n) then
f := f(x, y + 1) + a[x,y]
else
if (y = n) then
f := f(x + 1, y) + a[x,y]
else
f := maxim(f(x+1,y), f(x, y+1)) + a[x,y];
end;
begin
clrscr;
write('Vvedite razmer polya (n x n), n = ');
readln(n);
writeln('vvedite elementi massiva');
for i := 1 to n do
begin
for j := 1 to n do
begin
read(a[i,j]);
if (a[i,j] < 0) then
begin
writeln('Vveden element < 0, a = |a|');
a[i,j] := -a[i,j];
end
else
readln;
end;
end;
writeln;
writeln('matrix:');
for i := 1 to n do
begin
for j := 1 to n do
begin
write(a[i,j]);
write(' ');
end;
writeln;
end;
write('max dlina puti = ');
writeln(f(1,1));
readln;
end.