Thon Условные



бет22/38
Дата23.02.2020
өлшемі2,05 Mb.
#58878
1   ...   18   19   20   21   22   23   24   25   ...   38
Байланысты:
8-3 python


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

Алгоритм Евклида позволяет найти наибольший общий делитель (НОД) двух натуральных чисел.



Алгоритм Евклида для натуральных чисел: заменять бóльшее из двух заданных чисел на их разность до тех пор, пока они не станут равны. Полученное число и есть их НОД.

Этот вариант алгоритма работает довольно медленно, если одно из чисел значительно меньше другого, например, для па-ры чисел 2 и 2020. Значительно быстрее выполняется улучшен-ный (модифицированный) алгоритм Евклида.



Модифицированный алгоритм Евклида для натуральных чисел: заменять бóльшее из двух заданных чисел на остаток от деления бóльшего на меньшее, пока этот остаток не станет ра-вен нулю. Тогда второе число и есть их НОД.

Мы видим, что здесь тоже нужно выполнять некоторые операции несколько раз, причём сколько раз заранее неиз-вестно. Но нас выручит цикл с условием, ведь мы знаем, когда нужно остановиться когда какое-нибудь из двух чисел станет равно нулю.


57 http://kpolyakov.spb.ru

05.04.2019 Информатика, 8 класс К.Ю. Поляков, Е.А. Еремин

Запишите условие, которое означает «одно из значений переменных a или b равно нулю». После этого запишите обратное условие.

Теперь мы готовы записать цикл:

while a != 0 and b != 0:

if a > b:

a = a % b else:

b = b % a

Остаётся вывести результат ненулевое значение пере-менной a или b.



Запишите условный оператор, который выводит результат, проверяя одну из переменных на равенство нулю.

Из двух переменных, a и b, одна (неизвестно какая) равна нулю, а вторая не ноль. Запишите арифметическое выражение, которое всегда равно второй (ненулевой) переменной.

Количество итераций такого цикла заранее неизвестно и зависит от исходных данных. Дополним программу так, чтобы она считала ещё и количество сделанных итераций. Для этого нужно ввести переменную-счётчик целого типа. Перед началом цикла счётчик обнуляется него записывается ноль), и после каждой итерации значение счётчика увеличивается на едини-цу:

count = 0

while a != 0 and b != 0:

...

count += 1 print( a + b )

print( "Шагов:", count )

Вместо многоточия нужно вставить условный оператор, как и в предыдущем варианте программы. Обратите внимание, что


58 http://kpolyakov.spb.ru

05.04.2019 Информатика, 8 класс К.Ю. Поляков, Е.А. Еремин

оператор, увеличивающий значение счётчика, записывается с отступом он находится в теле цикла.



Достарыңызбен бөлісу:
1   ...   18   19   20   21   22   23   24   25   ...   38




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет