Математика и информатика. Филимонова Л.В - 93 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

Составители: 

Рубрика: 

93
Э. Дийкстр (известный математик) в своей структурной теореме ска-
зал: "Алгоритм любой сложности можно реализовать, используя триаду
"следование" - "повторение (циклы)" - "выбор (развилки)".
Пример 11.6.11 Алгоритм Евклида нахождения наибольшего общего де-
лителя (НОД) неотрицательных целых чисел основан на следующих свой-
ствах этой величины. Пусть m и n одновременно не равные нулю целые
неотрицательные числа и пусть m≥n. Тогда, если n=0, то НОД(n,m)=m, а
если n≠0, то для чисел m, n и r, где r - остаток от деления m на n, выполня-
ется равенство НОД(m,n)=
НОД(n,r). Например, НОД(15,6) = НОД(6,3) =
НОД(3,0) =3
НОД(24,8) = НОД(8,16) = НОД(8,8) = 8
НОД(56,24) = НОД(24,32) = НОД(24,8) =
НОД(8,16) = НОД(8,8) = 8
Даны натуральные числа n, m. Исполь-
зуя алгоритм Евклида, найти наибольший
общий делитель n и m.
10 REM “Алгоритм Евклида”
20 INPUT M, N
30 IF M<>N THEN 40 ELSE 60
40 IF M>N THEN M=M-N ELSE N=N-M
50 GOTO 30
60 PRINT “НОД=”; M
70 END
Пример 11.6.12
Задано n
троек чисел a, b, c. Определить,
сколько из предложенных троек
можно использовать для построе-
ния треугольника, если
a, b, c – длины его сторон.
10 REM “Треугольник”
20 INPUT N
30 FOR I=1 TO N
40 INPUT “A=”;A
50 INPUT “B=”;B
60 INPUT “C=”;C
70 IF A>C+B AND B>A+C AND
C>A+B THEN K=K+1
80 NEXT I
90 PRINT “Пригодно троек”; K
100 END
M;N
M>N
начало
M≠N
да
нет
M
конец
M:=M-N N:=N-M
да нет
начало
N
K:=0
I=1, N; 1
A, B, C
A>C+B
B>A+C
C>A+B
K:=K+1
K
конец
Да Нет 
                                     93

      Э. Дийкстр (известный математик) в своей структурной теореме ска-
зал: "Алгоритм любой сложности можно реализовать, используя триаду
"следование" - "повторение (циклы)" - "выбор (развилки)".
Пример 11.6.11 Алгоритм Евклида нахождения наибольшего общего де-
лителя (НОД) неотрицательных целых чисел основан на следующих свой-
ствах этой величины. Пусть m и n одновременно не равные нулю целые
неотрицательные числа и пусть m≥n. Тогда, если n=0, то НОД(n,m)=m, а
если n≠0, то для чисел m, n и r, где r - остаток от деления m на n, выполня-
ется равенство НОД(m,n)=НОД(n,r). Например, НОД(15,6) = НОД(6,3) =
НОД(3,0) =3
НОД(24,8) = НОД(8,16) = НОД(8,8) = 8                             начало
НОД(56,24) = НОД(24,32) = НОД(24,8) =
НОД(8,16) = НОД(8,8) = 8                                           M;N
      Даны натуральные числа n, m. Исполь-
зуя алгоритм Евклида, найти наибольший                      да          нет
общий делитель n и m.                                             M≠N
10 REM “Алгоритм Евклида”                           да            нет
20 INPUT M, N                                             M>N
30 IF M<>N THEN 40 ELSE 60
40 IF M>N THEN M=M-N ELSE N=N-M                    M:=M-N        N:=N-M
50 GOTO 30
60 PRINT “НОД=”; M
70 END
                                                                  M
                начало
                                                              конец
                   N
                                                 Пример 11.6.12 Задано n
                K:=0                      троек чисел a, b, c. Определить,
                                          сколько из предложенных троек
                I=1, N; 1                 можно использовать для построе-
                 A, B, C                  ния         треугольника,   если
                                          a, b, c – длины его сторон.

       Да       A>C+B        Нет          10 REM “Треугольник”
                B>A+C                     20 INPUT N
    K:=K+1      C>A+B
                                          30 FOR I=1 TO N
                                          40 INPUT “A=”;A
                                          50 INPUT “B=”;B
                                          60 INPUT “C=”;C
                                          70 IF A>C+B AND B>A+C AND
                   K                         C>A+B THEN K=K+1
                                          80 NEXT I
                конец                     90 PRINT “Пригодно троек”; K
                                          100 END

Страницы