Питон хард. 8-3py_Хард. 17. Введение 18. Линейные программы 19. Ветвления 20. Программирование циклических алгоритмов

• Название: 17. Введение 18. Линейные программы 19. Ветвления 20. Программирование циклических алгоритмов
• Анкор: Питон хард
• Дата: 15.04.2023
• Размер: 5.26 Mb.
• Имя файла: 8-3py_Хард.ppt
• Тип: Документы; #1063848
• страница: 12 из 18

Задачи

«C»: Напишите программу, которая получает с клавиатуры натуральное число и находит наибольшую цифру в его десятичной записи.
Пример:
Введите число: 311
Наибольшая цифра: 3
«D»: Напишите программу, которая получает с клавиатуры натуральное число и определяет, есть ли в его десятичной записи одинаковые цифры, стоящие рядом.
Пример:
Введите число: 553 Введите число: 535
Ответ: да. Ответ: нет.

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

Задача. Найти наибольший общий делитель (НОД) двух натуральных чисел.


Евклид
(365-300 до. н. э.)


НОД(a,b)= НОД(a-b, b)
= НОД(a, b-a)


Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.


НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)


НОД (1998, 2) = НОД (1996, 2) = … = 2


Пример:


много шагов при большой разнице чисел:


= НОД (7, 7) = 7

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

a = b?


да


нет


a > b?


да


a=a-b


нет


b=b-a


начало


конец

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

while a != b:
if a > b:
a = a - b
else:
b = b - a


Где будет НОД? Как его вывести?


?


Как вывести НОД в формате НОД(14,21) = 7?


?


А без дополнительных переменных?


?


a -= b


b -= a


как заменить?

Модифицированный алгоритм Евклида

НОД(a,b)= НОД(a % b, b)
= НОД(a, b % a)


Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД.


НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7


Пример:

Модифицированный алгоритм

while a != 0 and b != 0:
if a > b:
a = a % b
else:
b = b % a


Где будет НОД? Как его вывести?


?


if a != 0:
print(a)
else:
print(b)


print( ??? )


a+b

В стиле Python

while b!=0:   a, b = b, a % b print(a)


Почему работает?


?


заменить a на b и b на (a % b)

a	b
21	14
14	7
7	0

a	b
14	21
21	14
14	7
7	0

a > b!


!





С++:


while (a!=0 && b!=0)
{
if (a > b)
a = a % b;
else
b = b % a;
}


Паскаль:


while (a<>0) and
(b<>0) do
if a>b then
a:= a mod b
else
b:= b mod a;