»нформатика на п€ть ќ нас
 ƒобавить в избранное
5byte.ru
 “еори€
 Х8 класс
 Х9 класс
 Х10 класс
 Х11 класс
«адани€
 Х8 класс
 Х9 класс
 Х10 класс
 Х11 класс
 ниги
“есты
≈√Ё
Turbo Pascal 7
 Хќписание
 Х«адачи
HTML
–ефераты

јлгоритм ≈вклида

Ќаибольший общий делитель

–ассмотрим следующую задачу: требуетс€ составить программу определени€ наибольшего общего делител€ (Ќќƒ) двух натуральных чисел.

¬спомним математику. Ќаибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они дел€тс€ нацело. Ќапример, у чисел 12 и 18 имеютс€ общие делители: 2, 3, 6. Ќаибольшим общим делителем €вл€етс€ число 6. Ёто записываетс€ так:

Ќќƒ(12, 18) = 6.

ќбозначим исходные данные как ћ u N. ѕостановка задачи выгл€дит следующим образом:
ƒано: ћ, N
Ќайти: Ќќƒ(ћ, N).

¬ данном случае какой-то дополнительной математической формализации не требуетс€. —ама постановка задачи носит формальный математический характер. Ќе существует формулы дл€ вычислени€ Ќќƒ(ћ, N) по значени€м ћ и N. Ќо зато достаточно давно, задолго до по€влени€ Ё¬ћ, был известен алгоритмический способ решени€ этой задачи. Ќазываетс€ он алгоритмом ≈вклида.

»де€ алгоритма ≈вклида

»де€ этого алгоритма основана на том свойстве, что если M>N, то

Ќќƒ(ћ, N) = Ќќƒ(ћ - N, N).

»наче говор€, Ќќƒ двух натуральных чисел равен Ќќƒ их положительной разности (модул€ их разности) и меньшего числа.

Ћегко доказать это свойство. ѕусть   - общий делитель ћ u N (M> N). Ёто значит, что ћ = m , N = n , где m, n - натуральные числа, причем m > n. “огда ћ - N =  (m - n), откуда следует, что   - делитель числа ћ - N. «начит, все общие делители чисел ћ и N €вл€ютс€ делител€ми их разности ћ - N, в том числе и наибольший общий делитель.

¬торое очевидное свойство:

Ќќƒ(ћ, ћ) = ћ.

ƒл€ "ручного" счета алгоритм ≈вклида выгл€дит так:

1) если числа равны, то вз€ть любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;

2) заменить большее число разностью большего и меньшего из чисел;

3) вернутьс€ к выполнению п. 1.

–ассмотрим этот алгоритм на примере ћ=32, N=24:



ѕолучили: Ќќƒ(32, 24) =Ќќƒ(8, 8) = 8, что верно.

ќписание алгоритма ≈вклида блок-схемой

Ќа рис. 3.12 приведена блок-схема алгоритма ≈вклида.

–ис. 3.12. Ѕлок-схема алгоритма ≈вклида


—труктура алгоритма - цикл-пока с вложенным ветвлением. ÷икл повтор€етс€, пока значени€ ћ и N не равны друг другу. ¬ ветвлении большее из двух значений замен€етс€ на их разность.

ј теперь посмотрите на трассировочную таблицу алгоритма дл€ исходных значений ћ = 32, N = 24.

Ўаг ќпераци€ M N ”словие
1 ввод ћ 32    
2 ввод N   24  
3 M ¹ N     32 ¹ 24, да
4 M>N     32>24, да
5 M:=M-N 8    
6 M ¹ N     8 ¹ 24, да
7 M>N     8>24, нет
8 N:=N-M   16  
9 M ¹ N     8 ¹ 16, да
10 M>N     8>16, нет
11 N:=N-M   8  
12 M ¹ N     8 ¹ 8, нет
13 вывод M 8    
14 конец      

¬ итоге получилс€ верный результат.

ѕрограмма на јя и на ѕаскале

«апишем алгоритм на јя и программу на ѕаскале.

алг ≈вклид
цел ћ, N
нач
     вывод " ¬ведите ћ и N" ввод ћ, N
     пока ћ N, повтор€ть
     нц
          если M>N
          то M:=M-N
          иначе N:=N-M
          кв
     кц
     вывод "Ќќƒ=",ћ
кон
Program Evklid;
var M, N: integer;
begin
     writeln('¬ведите ћ и N');
     readln(M, N);
     while M<>N do
          begin
               if M>N
               then M:=M-N
               else N:=N-M
     end;
     write('Ќ0ƒ=',ћ)
end.


¬опросы и задани€

1. ¬ыполните на компьютере программу Evklid. ѕротестируйте ее на значени€х ћ= 32, N = 24; ћ = 696, N = 234.

2. —оставьте программу нахождени€ наибольшего общего делител€ трех чисел, использу€ следующую формулу:

Ќќƒ(ј, B, —) = Ќќƒ(Ќќƒ(ј, ¬), —).

3. —оставьте программу нахождени€ наименьшего общего кратного (Ќќ ) двух чисел, использу€ формулу:

ј × ¬ = Ќќƒ(ј, ¬) × Ќќ (ј, ¬).




–Ш–љ–і–Є–≤–Є–і—Г–∞–ї–Ї–∞ –Ш—А–Є–љ–∞ https://ram.sibirki.org/id_9817.html —А–∞–є–Њ–љ –Є –Љ–µ—В—А–Њ - sibirki.org
 ” ¬ас есть материал пишите нам
 
    Copyright © 2008    
  Top.Mail.Ru