8класс_Python. Что такое алгоритм

• Название: Что такое алгоритм
• Дата: 27.02.2023
• Размер: 3.34 Mb.
• Имя файла: 8класс_Python.ppt
• Тип: Документы; #957577
• страница: 9 из 11

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

Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока они не станут равны. Это число и есть НОД исходных чисел.


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


пока a != b:
если a > b:
a -= b # a = a - b
иначе:
b -= a # b = b - a


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


НОД(1998,2) =


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

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

Модифицированный алгоритм Евклида. Заменять большее число на остаток от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Другое (ненулевое) число и есть НОД чисел.


НОД(1998,2) = НОД(0,2) = 2


пока ???:
если a > b:
a = a % b
иначе:
b = b % a


Какое условие?


?


a!=0 and b!=0:


Как вывести результат?


?


если a != 0:
вывести a
иначе:
вывести b

Задачи

«3»: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью алгоритма Евклида.
Пример:
Введите два числа:
21 14
НОД(21,14)=7


«4»: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью модифицированного алгоритма Евклида. Заполните таблицу:

a	64168	358853	6365133	17905514	549868978
b	82678	691042	11494962	23108855	298294835
НОД(a,b)

Задачи

«5»: Ввести с клавиатуры два натуральных числа и сравнить количество шагов цикла для вычисления их НОД с помощью обычного и модифицированного алгоритмов Евклида.
Пример:__Введите_число:_Введите_число:__1010100_abcd10__Да._Нет.___Задачи'>Пример:__Введите_число:__1010100__Нулей:_4__Единиц:_3____«4»'>Пример:
Введите два числа:
1998 2
НОД(1998,2)=2
Обычный алгоритм: 998
Модифицированный: 1

Обработка строк в цикле

Задача. Ввести строку и определить, сколько в ней цифр.


счётчик = 0
для каждого символа строки:
если символ – цифра:
счётчик += 1


s = input()
k = 0
for c in s:
if c.isdigit():
k += 1


for c in s:


для всех символов в строке


если c – это цифра

Проверка символов

if c.isalpha():
print("Буква")


if c.islower():
print("Строчная буква")


if c.isupper():
print("Заглавная буква")


if c.isdigit():
print("Цифра")


if c in ["а","б"]:
print("Это а или б")

Задачи

«3»: Ввести с клавиатуры число в двоичной системе счисления. Определить, сколько в его записи единиц и сколько нулей.
Пример:
Введите число:
1010100
Нулей: 4
Единиц: 3


«4»: Ввести с клавиатуры символьную строку. Если это правильная запись двоичного числа, вывести сообщение «Да», иначе вывести сообщение «Нет».
Пример:
Введите число: Введите число:
1010100 abcd10
Да. Нет.

Задачи

«5»: Ввести с клавиатуры символьную строку и составить новую строку, удалив из исходной все пробелы.
Пример:
Введите строку:
Вася пошел гулять.
Васяпошелгулять.