Razdel_13_Osn_alg_i_i_progr_ya_11_05_10

Часть 13. Основы алгоритмизации и программирования

N, i, j : Integer;

{-------------------------------------}

Procedure InputOutput; {описание процедуры ввода-

вывода матрицы} Begin ClrScr;

Write(’Количество строк и столбцов – ’);

ReadLn(N);

For i := 1 to N do

For j := 1 to N do

begin Write(’A[’ , i , ’, ’ , j , ’] = ’);

ReadLn(A[i, j]) end; ClrScr;

WriteLn(’ Исходная матрица :’); WriteLn;

For i := 1 to N do begin

For j := 1 to N do Write(A[i, j] : 5 : 1); WriteLn

end; WriteLn

End; { of InputOutput } {-------------------------------------------}

201

Часть 13. Основы алгоритмизации и программирования

первого отрицательного}

If A[i, j]<0 then Flag:=TRUE else

For j := 1 to N do A[i, j] := 0 {отрицательные

элементы }

End; {-------------------------------------------}

Procedure OutRes; {описание процедуры вывода матрицы-

результата}

Begin

WriteLn(’ Матрица-результат :’); WriteLn; For i := 1 to N do

begin

For j := 1 to N do Write(A[i, j]:5:1);

WriteLn

end; ReadLn End; { of OutRes }

{-------------------------------------------} BEGIN

InputOutput; {вызов процедуры ввода-вывода матрицы}

202

Часть 13. Основы алгоритмизации и программирования

For i := 1 to N do Line(i);{циклический вызов про-

цедуры обработки строк}

OutRes; {вызов процедуры вывода матрицы-

результата}

END.

QBasic

CLS : INPUT "Количество строк и столбцов - ", N DIM A(N, N)

FOR i = 1 TO N ’ввод матрицы

FOR j = 1 TO N

PRINT "A(" ; i ; ", " ; j ; ") = " ;

INPUT A(i, j)

NEXT j

NEXT i : CLS

PRINT "Исходная матрица :" : PRINT

FOR i = 1 TO N ’вывод матрицы

FOR j = 1 TO N

PRINT A(i, j) ;

NEXT j

PRINT

NEXT i : PRINT

FOR i = 1 TO N ’цикл по строкам матрицы j = 1 : Flag=0

WHILE (j <= N) AND (Flag = 0) ’цикл до первого от-

рицательного

IF A(i, j) < 0 THEN Flag = 1 ELSE j = j + 1 ’эле-

мента строки

WEND

203

Часть 13. Основы алгоритмизации и программирования

NEXT j : PRINT

NEXT i

END

204

Часть 13. Основы алгоритмизации и программирования

10Алгоритм Евклида

Древнегреческие математики называли этот алгоритм словом

ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. Евклид описал его в Началах дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X

книге для нахождения наибольшей общей меры двух величин.

Историками математики было выдвинуто предположение, что имен-

но с помощью алгоритма Евклида впервые было установлено существова-

ние несоизмеримых величин. Впрочем, это предположение не имеет доста-

точных документальных подтверждений.

Алгоритм Евклида для целых чисел

Этот алгоритм был изложен в Началах Евклида (ок. 300 до н.э.). С

его помощью вычисляется наибольший общий делитель двух целых чисел.

Для случая положительных чисел он формулируется в виде процедурного правила: «Разделите большее из двух данных чисел на меньшее. Затем раз-

делите делитель на остаток от деления и продолжайте действовать так же,

пока последний делитель не разделится нацело на последний остаток. По-

следний из делителей и будет наибольшим общим делителем двух данных чисел».

В качестве числового примера рассмотрим два целых числа 3132 и 7200. Алгоритм в этом случае сводится к следующим действиям:

Наибольший общий делитель совпадает с последним делителем – числом 36. Объяснение просто. В нашем примере мы видим из последней строки, что число 36 делит число 288. Из предпоследней строки следует,

205

Часть 13. Основы алгоритмизации и программирования

что число 36 делит 324. Так, двигаясь от строки к строке вверх, мы убеж-

даемся в том, что число 36 делит 936, 3132 и 7200. Мы утверждаем теперь,

что число 36 есть общий делитель чисел 3132 и 7200. Пусть g – наиболь-

ший общий делитель чисел 3132 и 7200. Так как g делит 3132 и 7200, из первой строки следует, что g делит 936. Из второй строки мы заключаем,

что g делит 324. Так, спускаясь от строки к строке, мы убеждаемся в том,

что g делит 288 и 36. А так как 36 – общий делитель чисел 3132 и 7200 и

делится на наибольший общий их делитель, мы заключаем, что 36 и есть этот наибольший общий делитель.

Наибольшим общим делителем (НОД) двух целых чисел называет-

ся такое наибольшее по модулю число, которое делит эти два числа. По определению НОД(0,0) = 0.

Данный алгоритм вычисления НОД двух целых чисел a и b состоит в следующем: если хотя бы одно из чисел равно нулю, то НОД(a,b) = |a+b|, в

других случаях последовательно находятся остатки ri от делений: a на b-a = bq1 +r1 ,

b на r1 -b = r1 q2 +r2 , r1 на r2 -r1 = r2 q3 +r3 ,

......

и т.д., пока rn+1 не станет равно нулю.

Тогда НОД(a,b) = НОД(b,r1 ) = НОД(r1 ,r2 ) = ... = НОД(rn-1 ,rn ) =

rn .

206

Часть 13. Основы алгоритмизации и программирования

Рисунок. Блок-схема определения НОД

unit gcdunit; interface

uses Math, Ap, Sysutils;

function GCD(A : Integer; B : Integer):Integer;

implementation

(***********************************************************

Функция ищет наибольший общий делитель двух чисел алгоритмом Евклида.

***********************************************************)

207

Часть 13. Основы алгоритмизации и программирования

function GCD(A : Integer; B : Integer):Integer; begin

A := AbsInt(A);

B := AbsInt(B);

if (a=0) or (b=0) then begin

Result := a+b;

Exit;

end;

while a<>b do begin

if a>b then begin

a:= a-b;

end else begin

b:= b-a;

end;

end;

Result := b; end;

end.

208

Часть 13. Основы алгоритмизации и программирования

11 Тестовые задания для самостоятельной подготовки

«Основы алгоритмизации и программирования. Часть 1.»

1. В результате выполнения фрагмента программного кода вычисляется

S:=0;

for i:=1 to n do

if A[i]<0 then S:=S+A[i];

количество положительных элементов в массиве А количество отрицательных элементов в массиве А сумма положительных элементов массива А сумма отрицательных элементов массива А

2. В результате выполнения фрагмента программного кода вычисляется

m:=0;

for i:=1 to n do

if A[i]>0 then m:=m+1;

количество положительных элементов в массиве А количество отрицательных элементов в массиве А сумма положительных элементов массива А сумма отрицательных элементов массива А

3. В результате выполнения фрагмента программного кода вычисляется

209

Часть 13. Основы алгоритмизации и программирования

m:=0;

for i:=1 to n do

if A[i]<0 then m:=m+1;

количество положительных элементов в массиве А количество отрицательных элементов в массиве А сумма положительных элементов массива А сумма отрицательных элементов массива А

4. В результате выполнения фрагмента программного кода вычисляется

S:=0;

for i:=1 to n do

if A[i]>0 then S:=S+A[i];

количество положительных элементов в массиве А количество отрицательных элементов в массиве А сумма положительных элементов массива А сумма отрицательных элементов массива А

5. В результате выполнения фрагмента программного кода определяется

S:=A[1];

for i:=2 to n do

if A[i]>S then S:=A[i];

номер минимального элемента в массиве А номер максимального элемента в массиве А

210