Thon Условные

жүктеу/скачать 2,05 Mb.

бет	22/38
Дата	23.02.2020
өлшемі	2,05 Mb.
	#58878

1 ... 18 19 20 21 22 23 24 25 ... 38

Байланысты:
8-3 python
Резюме

Модифициро в анн ый
"Шагов:", count

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

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

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

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

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

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

57 http://kpolyakov.spb.ru

^05.04^.²⁰¹⁹Информатика, 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^.²⁰¹⁹Информатика, 8 класс К.Ю. Поляков, Е.А. Еремин

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

жүктеу/скачать 2,05 Mb.

Достарыңызбен бөлісу:

1 ... 18 19 20 21 22 23 24 25 ... 38