Разделы презентаций


Программирование на языке Python

Содержание

Программа, вывод и комментарии# Это пустая программакомментарии после # не обрабатываются# -*- coding: utf-8 -*-# Это пустая программакодировка utf-8 по умолчанию)Windows: cp1251""" Это тоже комментарий"""

Слайды и текст этой презентации

Слайд 1Программирование на языке Python

Программирование на языке Python

Слайд 2Программа, вывод и комментарии
# Это пустая программа
комментарии после # не

обрабатываются
# -*- coding: utf-8 -*-
# Это пустая программа
кодировка utf-8 по

умолчанию)

Windows: cp1251

"""
Это тоже комментарий
"""

Программа, вывод и комментарии# Это пустая программакомментарии после #  не обрабатываются# -*- coding: utf-8 -*-# Это

Слайд 3Вывод на экран
print ( "2+2=?" )
print ( "Ответ: 4" )


Протокол:
2+2=?
Ответ: 4
автоматический переход на новую строку
print ( '2+2=?'

)
print ( 'Ответ: 4' )
Вывод на экранprint (

Слайд 4Задания
«B»: Вывести на экран текст «лесенкой»
Вася

пошел
гулять
«C»: Вывести

на экран рисунок из букв
Ж
ЖЖЖ
ЖЖЖЖЖ
ЖЖЖЖЖЖЖ
HH HH
ZZZZZ
Задания«B»: Вывести на экран текст «лесенкой»	 Вася     пошел

Слайд 5Ввод двух значений в одной строке
a, b = map (

int, input().split() )
input()
ввести строку с клавиатуры
21 33
input().split()
21
33
разделить

строку на части по пробелам

map ( int, input().split() )

21

33

целые

применить

эту операцию

a, b = map ( int, input().split() )

Ввод двух значений в одной строкеa, b = map ( int, input().split() )input()ввести строку с клавиатуры21 33

Слайд 6Изменение значений переменной
a = 5
b = a + 2
a =

(a + 2)*(b – 3)
b = b + 1
a
5
b
=5+2
7
28
=(5+2)*(7-3)
=7+1
8

Изменение значений переменнойa = 5b = a + 2a = (a + 2)*(b – 3)b = b

Слайд 7Вывод данных
print ( a )
значение переменной
print ( "Ответ: ", a

)
значение и текст
print ( "Ответ: ", a+b )
вычисление выражения
print (

a, "+", b, "=", c )

2 + 3 = 5

через пробелы

print ( a, "+", b, "=", c, sep = "" )

2+3=5

sep = ""

убрать разделители

Вывод данныхprint ( a )значение переменнойprint (

Слайд 8Форматный вывод
a = 123
print ( "{:5d}".format(a) )
a = 123
print (

"{:5d}{:5d}{:5d}".format

(a, a*a, a*a*a) )

целое

Форматный выводa = 123print (

Слайд 9Случайные числа
Случайно…
встретить друга на улице
разбить тарелку
найти 10 рублей
выиграть в лотерею
Случайный

выбор:
жеребьевка на соревнованиях
выигравшие номера в лотерее
Как получить случайность?

Случайные числаСлучайно…встретить друга на улицеразбить тарелкунайти 10 рублейвыиграть в лотереюСлучайный выбор:жеребьевка на  соревнованияхвыигравшие номера  в

Слайд 10Случайные числа на компьютере
Электронный генератор
нужно специальное устройство
нельзя воспроизвести результаты
318458191041
564321
209938992481
458191
938992
малый период

(последовательность повторяется через 106 чисел)
Метод середины квадрата (Дж. фон Нейман)
в

квадрате

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

зерно

Случайные числа на компьютереЭлектронный генераторнужно специальное устройствонельзя воспроизвести результаты318458191041564321209938992481458191938992малый период  (последовательность повторяется через 106 чисел)Метод середины

Слайд 11Генератор случайных чисел
Генератор на [0,1):
X = random(); # псевдослучайное

число
Y = random() # это уже другое число!
англ. random –

случайный

Целые числа на отрезке [a,b]:

X = randint(a, b) # псевдослучайное число
Y = randint(a, b) # это уже другое число!

import random

Генератор случайных чиселГенератор на [0,1): X = random(); # псевдослучайное числоY = random() # это уже другое

Слайд 12Задачи
«A»: Ввести с клавиатуры три целых числа, найти их сумму,

произведение и среднее арифметическое.
Пример:
Введите три целых числа:
5 7 8
5+7+8=20
5*7*8=280
(5+7+8)/3=6.667
«B»:

Ввести с клавиатуры координаты двух точек (A и B) на плоскости (вещественные числа). Вычислить длину отрезка AB.
Пример:
Введите координаты точки A:
5.5 3.5
Введите координаты точки B:
1.5 2
Длина отрезка AB = 4.272
Задачи«A»: Ввести с клавиатуры три целых числа, найти их сумму, произведение и среднее арифметическое. Пример:Введите три целых

Слайд 13Задачи
«C»: Получить случайное трехзначное число и вывести через запятую его

отдельные цифры.
Пример:
Получено число 123.
Его цифры 1, 2, 3.

Задачи«C»: Получить случайное трехзначное число и вывести через запятую его отдельные цифры. Пример:Получено число 123.Его цифры 1,

Слайд 14Программирование на языке Python
Ветвления

Программирование на языке PythonВетвления

Слайд 15Условный оператор
Задача: изменить порядок действий в зависимости от выполнения некоторого

условия.
полная форма ветвления
if a > b:
M = a


else:
M = b
Условный операторЗадача: изменить порядок действий в зависимости от выполнения некоторого условия.полная форма ветвленияif a > b: M

Слайд 16Условный оператор: неполная форма
неполная форма ветвления
M = a
if

b > a:
M = b
M = max(a, b)
Решение

в стиле Python:

M = a if a > b else b

Условный оператор: неполная форманеполная форма ветвленияM = a  if b > a:  M = bM

Слайд 17Условный оператор
if a > b:
с = a


a = b
b = c
4
6
?
4
6
4
a
b
3
2
1
c
a, b =

b, a

Решение в стиле Python:

Условный операторif a > b:  с = a   a = b b = c

Слайд 18Знаки отношений
>
=

Знаки отношений>=

Слайд 19Вложенные условные операторы
if a > b:
print("Андрей старше")
else:




if

a == b:
print("Одного возраста")
else:
print("Борис старше")
вложенный условный оператор
Задача:

в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше?
Вложенные условные операторыif a > b: print(

Слайд 20Каскадное ветвление
if a > b:
print("Андрей старше")
elif a ==

b:
print("Одного возраста")
else:
print("Борис старше")

Каскадное ветвлениеif a > b: print(

Слайд 21Каскадное ветвление
cost = 1500
if cost < 1000:
print (

"Скидок нет." )
elif cost < 2000:
print ( "Скидка

2%." )
elif cost < 5000:
print ( "Скидка 5%." )
else:
print ( "Скидка 10%." )

первое сработавшее условие

Скидка 2%.

Каскадное ветвлениеcost = 1500 if cost < 1000: print (

Слайд 22Задачи

Задачи

Слайд 23Программирование на языке Python
Циклические алгоритмы

Программирование на языке PythonЦиклические алгоритмы

Слайд 24Что такое цикл?
Цикл – это многократное выполнение одинаковых действий.
Два вида

циклов:
цикл с известным числом шагов (сделать 10 раз)
цикл с неизвестным

числом шагов (делать, пока не надоест)

Задача. Вывести на экран 10 раз слово «Привет».

Что такое цикл?Цикл – это многократное выполнение одинаковых действий.Два вида циклов:цикл с известным числом шагов (сделать 10

Слайд 25Повторения в программе
print("Привет“)
print("Привет")
...
print("Привет")

Повторения в программеprint(

Слайд 26Блок-схема цикла
начало
конец
да
нет
тело цикла

Блок-схема цикланачалоконецданеттело цикла

Слайд 27Как организовать цикл?
счётчик = 0
пока счётчик < 10:
print("Привет“)
увеличить

счётчик на 1
счётчик = 10
пока счётчик > 0:
print("Привет")

уменьшить счётчик на 1


результат операции автоматически сравнивается с нулём!


Слайд 28Цикл с условием
count = 0;
while :





n = n // 10
count += 1

тело цикла
начальное значение

счётчика

n > 0

условие продолжения

заголовок цикла

Цикл с условиемcount = 0;while    :   n = n // 10count +=

Слайд 29Цикл с условием
k = 0
while k < 10:
print

( "привет" )
k += 1
При известном количестве шагов:
k =

0
while k < 10:
print ( "привет" )

Зацикливание:

Цикл с условиемk = 0while k < 10:  print (

Слайд 30Цикл с постусловием
while True:


if n > 0: break
условие выхода
print (

"Введите положительное число:" )
n = int ( input() )
тело цикла
при

входе в цикл условие не проверяется
цикл всегда выполняется хотя бы один раз

Задача. Обеспечить ввод положительного числа в переменную n.

бесконечный цикл

прервать цикл

Цикл с постусловиемwhile True:if n > 0: breakусловие выходаprint (

Слайд 31Цикл с переменной
Задача. Вывести 10 раз слово «Привет!».
 
while

:
print("Привет!")
 
i = 0
i < 10
i += 1
for

:
print("Привет!")

i in range(10)

в диапазоне [0,10)

Цикл с переменной:

range(10)  0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Цикл с переменнойЗадача. Вывести 10 раз слово «Привет!». while    : print(

Слайд 32Цикл с переменной
Задача. Вывести все степени двойки от 21 до

210.
 
while :
print ( 2**k )
 
k =

1

k <= 10

k += 1

for :
print ( 2**k )

k in range(1,11)

в диапазоне [1,11)

Цикл с переменной:

range(1,11)  1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Цикл с переменнойЗадача. Вывести все степени двойки от 21 до 210. while    : print (

Слайд 33Цикл с переменной: другой шаг
100
81
64
49
36
25
16
9
4
1
1
9
25
49
81
for

:
print ( k**2 )
k in

range(1,11,2)

for :
print ( k**2 )

k in range(10,0,-1)

шаг

10,9,8,7,6,5,4,3,2,1

1,3,5,7,9

Цикл с переменной: другой шаг10081644936251694119254981for          : print (

Слайд 34Задачи
i=1
m=32000
while i

m=a
otv=i
i+=1
print("Номер минимального числа otv=",otv)
«A»: Нахождение номера

минимального значения в последовательности вводимых чисел

i=1
m=0
while i<10:
a=float(input("Введите число a="))
if (m>a or m==0):
m=a
otv=i
i+=1
print("Номер минимального числа otv=",otv)

Задачиi=1m=32000while i

Слайд 35Вложенные циклы
Задача. Вывести все простые числа в диапазоне от 2 до

1000.
сделать для n от 2 до 1000
если число

n простое то
вывод n

число n простое

нет делителей [2.. n-1]: проверка в цикле!

for n in range(2, 10001):
if число n простое:
print( n )

Вложенные циклыЗадача. Вывести все простые числа в диапазоне от 2 до 1000.сделать для n от 2 до

Слайд 36Вложенные циклы
for n in range(2, 10001):
count = 0;



if count == 0:
print( n )
for k in

range(2,n):
if n % k == 0:
count += 1

вложенный цикл

Вложенные циклыfor n in range(2, 10001):  count = 0; if count == 0:  print( n

Слайд 37Вложенные циклы
for i in range(1,45):
for k in range(1,i+1):

print( i, k )
1 1
2 1
2 2
3 1
3 2
3 3
4

1
4 2
4 3
4 4
Вложенные циклыfor i in range(1,45): for k in range(1,i+1):  print( i, k )1 12 12 23

Слайд 38Поиск простых чисел – как улучшить?
count = 0
k =

2
while :
if n %

k == 0:
count += 1
k += 1

while k <= math.sqrt(n):

while k*k <= n:
if n % k == 0: break
k += 1
if k*k > n:
print ( n )

k*k <= n

выйти из цикла

если вышли по условию

Поиск простых чисел – как улучшить? count = 0k = 2while     :

Слайд 39Задачи
«А»: В магазине продается мастика в ящиках по 15 кг,

17 кг, 21 кг. Как купить ровно 185 кг мастики,

не вскрывая ящики? Сколькими способами можно это сделать?

count = 0
for i in range(13):
for j in range(11):
for k in range(9):
if 185 == i*15+j*17+k*21:
count += 1
print(i,j,k)
print('Всего способов - ', count)

Задачи«А»: В магазине продается мастика в ящиках по 15 кг,  17 кг, 21 кг. Как купить

Слайд 40Задачи
«С на дом»: Напишите программу, которая получает натуральные числа a

и b(a меньше b) и выводит все простые числа в

интервале от a до b
Пример:
Введите границы диапазона: 10 20 11 13 15 17 19


a = int(input("Введите нижнюю границу a="))
b = int(input("Введите верхнюю границу b="))

for n in range (a, b):
for a in range (2, n):
if (n % a) == 0:
break
else:
print (n)
break

Задачи«С на дом»: Напишите программу, которая получает натуральные числа a и b(a меньше b) и выводит все

Слайд 41Программирование на языке Python
Процедуры

Программирование на языке PythonПроцедуры

Слайд 42Зачем нужны процедуры?
print ( "Ошибка программы" )
много раз!
def Error():
print(

"Ошибка программы" )
n = int ( input() )
if n

0:
Error()

вызов процедуры

Процедура:

define определить

Зачем нужны процедуры?print (

Слайд 43Что такое процедура?
Процедура – вспомогательный алгоритм, который выполняет некоторые действия.
текст

(расшифровка) процедуры записывается до её вызова в основной программе
в программе

может быть много процедур
чтобы процедура заработала, нужно вызвать её по имени из основной программы или из другой процедуры
Что такое процедура?Процедура – вспомогательный алгоритм, который выполняет некоторые действия.текст (расшифровка) процедуры записывается  до её вызова

Слайд 44Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255)

в 8-битном двоичном коде.
много раз!
Алгоритм:
178

101100102
7 6 5 4 3

2 1 0

1 0 1 1 0 0 1 02

разряды

n:=

n // 128

n % 128

n1 // 64

Процедура с параметрамиЗадача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде. много раз!Алгоритм:1781011001027 6

Слайд 45Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255)

в 8-битном двоичном коде.
Решение:
k = 128
while k > 0:

print ( n // k,
end = "" )
n = n % k
k = k // 2

178


10110010

Процедура с параметрамиЗадача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде. Решение:k = 128while

Слайд 46Процедура с параметрами
printBin ( 99 )
значение параметра (аргумент)
def printBin( n

):
k = 128
while k > 0:
print

( n // k, end = "" )
n = n % k;
k = k // 2

Параметры – данные, изменяющие работу процедуры.

локальная переменная

def printSred( a, b ):
print ( (a + b)/2 )

Несколько параметров:

Процедура с параметрамиprintBin ( 99 )значение параметра (аргумент)def printBin( n ): k = 128 while k >

Слайд 47Локальные и глобальные переменные
a = 5
def qq():
a = 1

print ( a )
qq()
print ( a )
глобальная переменная
локальная переменная
1
5
a =

5
def qq():
print ( a )
qq()

5

a = 5
def qq():
global a
a = 1
qq()
print ( a )

1

global a

работаем с
глобальной переменной

Локальные и глобальные переменныеa = 5def qq(): a = 1 print ( a )qq()print ( a )глобальная

Слайд 48Задачи
«A»: Напишите процедуру, которая принимает параметр – натуральное число N

– и выводит на экран линию из N символов '–'.


Пример:
Введите N:
10
----------
«B»: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой.
Пример:
Введите натуральное число:
1234
1
2
3
4

def printChar(s):
print('-'*int(s))

n = input('введите число n=')
printChar(n)

Задачи«A»: Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из

Слайд 49Программирование на языке Python
§ 60. Функции

Программирование на языке Python§ 60. Функции

Слайд 50Что такое функция?
Функция – это вспомогательный алгоритм, который возвращает значение-результат

(число, символ или объект другого типа).
Задача. Написать функцию, которая вычисляет

сумму цифр числа.

Алгоритм:

сумма = 0
пока n != 0:
сумма += n % 10
n = n // 10

Что такое функция?Функция – это вспомогательный алгоритм, который возвращает значение-результат (число, символ или объект другого типа).Задача. Написать

Слайд 51Сумма цифр числа
# основная программа
print ( sumDigits(12345) )
def sumDigits( n

):
sum = 0
while n!= 0:
sum +=

n % 10
n = n // 10
return sum

return sum

передача результата

Сумма цифр числа# основная программаprint ( sumDigits(12345) )def sumDigits( n ): sum = 0 while n!= 0:

Слайд 52Использование функций
x = 2*sumDigits(n+5)
z = sumDigits(k) + sumDigits(m)
if sumDigits(n) %

2 == 0:
print ( "Сумма цифр чётная" )
print

( "Она равна", sumDigits(n) )

Одна функция вызывает другую:

def middle ( a, b, c ):
mi = min ( a, b, c )
ma = max ( a, b, c )
return a + b + c - mi - ma

вызываются min и max

Использование функцийx = 2*sumDigits(n+5)z = sumDigits(k) + sumDigits(m)if sumDigits(n) % 2 == 0: print (

Слайд 53Задачи
«A»: Напишите функцию, которая находит наибольший общий делитель двух натуральных

чисел.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574) = 1234.
«B»: Напишите функцию,

которая определяет сумму цифр переданного ей числа.
Пример:
Введите натуральное число:
123
Сумма цифр числа 123 равна 6.

Задачи«A»: Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел. Пример:Введите два натуральных числа:7006652 112307574НОД(7006652,112307574) =

Слайд 54Задачи
«C»: Напишите функцию, которая «переворачивает» число, то есть возвращает число,

в котором цифры стоят в обратном порядке.
Пример:
Введите натуральное число:
1234
После

переворота: 4321.
Задачи«C»: Напишите функцию, которая «переворачивает» число, то есть возвращает число, в котором цифры стоят в обратном порядке.

Слайд 55Как вернуть несколько значений?
def divmod ( x, y ):
d

= x // y
m = x % y
return

d, m

d – частное,
m – остаток

a, b = divmod ( 7, 3 )
print ( a, b ) # 2 1

q = divmod ( 7, 3 )
print ( q ) # (2, 1)

(2, 1)

кортеж – набор элементов

Как вернуть несколько значений?def divmod ( x, y ): d = x // y m = x

Слайд 56Задачи
«A»: Напишите функцию, которая переставляет три переданные ей числа в

порядке возрастания.
Пример:
Введите три натуральных числа:
10 15 5
5 10 15
«B»:

Напишите функцию, которая сокращает дробь вида M/N.
Пример:
Введите числитель и знаменатель дроби:
25 15
После сокращения: 5/3

Задачи«A»: Напишите функцию, которая переставляет три переданные ей числа в порядке возрастания. Пример:Введите три натуральных числа:10 15

Слайд 57Задачи
«C»: Напишите функцию, которая вычисляет наибольший общий делитель и наименьшее

общее кратное двух натуральных чисел.
Пример:
Введите два натуральных числа:
10 15
НОД(10,15)=5
НОК(10,15)=30

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

Слайд 58Логические функции
Задача. Найти все простые числа в диапазоне от 2

до 100.
for i in range(2,1001):
if  i - простое  :

print ( i )

i - простое

isPrime(i)

функция, возвращающая логическое значение (True/False)

Логические функцииЗадача. Найти все простые числа в диапазоне  от 2 до 100. for i in range(2,1001):

Слайд 59Функция: простое число или нет?
def isPrime ( n ):
k

= 2
while k*k

!= 0:
k += 1
return (k*k > n)

return (k*k > n)

if k*k > n:
return True
else:
return False

Функция: простое число или нет?def isPrime ( n ): k = 2 while k*k n)return (k*k >

Слайд 60Логические функции: использование
n = int ( input() )
while isPrime(n):
print

( n, "– простое число" )
n = int

( input() )
Логические функции: использованиеn = int ( input() )while isPrime(n): print ( n,

Слайд 61Задачи
«A»: Напишите логическую функцию, которая определяет, является ли переданное ей

число совершенным, то есть, равно ли оно сумме своих делителей,

меньших его самого.
Пример:
Введите натуральное число:
28
Число 28 совершенное.
Пример:
Введите натуральное число:
29
Число 29 не совершенное.
Задачи«A»: Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным, то есть, равно ли оно

Слайд 62Задачи
«B»: Напишите логическую функцию, которая определяет, являются ли два переданные

ей числа взаимно простыми, то есть, не имеющими общих делителей,

кроме 1.
Пример:
Введите два натуральных числа:
28 15
Числа 28 и 15 взаимно простые.
Пример:
Введите два натуральных числа:
28 16
Числа 28 и 16 не взаимно простые.
Задачи«B»: Напишите логическую функцию, которая определяет, являются ли два переданные ей числа взаимно простыми, то есть, не

Слайд 63Задачи
«С»: Простое число называется гиперпростым, если любое число, получающееся из

него откидыванием нескольких цифр, тоже является простым. Например, число 733

– гиперпростое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что переданное ей число – гиперпростое. Используйте уже готовую функцию isPrime, которая приведена в учебнике.
Пример:
Введите натуральное число:
733
Число 733 гиперпростое.
Пример:
Введите натуральное число:
19
Число 19 не гиперпростое.
Задачи«С»: Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких цифр, тоже является простым.

Слайд 64Программирование на языке Python
§ 61. Рекурсия

Программирование на языке Python§ 61. Рекурсия

Слайд 65Что такое рекурсия?
У попа была собака, он её любил, Она съела

кусок мяса, он её убил, В землю закопал, Надпись написал:
У попа была

собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:

Что такое рекурсия?У попа была собака, он её любил, Она съела кусок мяса, он её убил, В

Слайд 66Что такое рекурсия?
Натуральные числа:
индуктивное определение
Рекурсия — это способ определения множества

объектов через само это множество на основе заданных простых базовых

случаев.

Числа Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, …

Что такое рекурсия?Натуральные числа:индуктивное определениеРекурсия — это способ определения множества объектов через само это множество на основе

Слайд 67Фракталы
Фракталы – геометрические фигуры, обладающие самоподобием.
Треугольник Серпинского:

ФракталыФракталы – геометрические фигуры, обладающие самоподобием. Треугольник Серпинского:

Слайд 68Ханойские башни
за один раз переносится один диск
класть только меньший диск

на больший
третий стержень вспомогательный
перенести (n-1, 1, 2)
1 -> 3
перенести (n-1,

2, 3)

перенести (n, 1, 3)

Ханойские башниза один раз переносится один дисккласть только меньший диск на большийтретий стержень вспомогательныйперенести (n-1, 1, 2)1

Слайд 69Ханойские башни – процедура
def Hanoi ( n, k, m

):
p = 6 - k - m
Hanoi (

n-1, k, p )
print ( k, "->", m )
Hanoi ( n-1, p, m )

номер вспомогательного стержня (1+2+3=6!)

сколько

откуда

куда

рекурсия

рекурсия


Слайд 70Ханойские башни – процедура
Рекурсивная процедура (функция) — это процедура

(функция), которая вызывает сама себя напрямую или через другие процедуры

и функции.

def Hanoi ( n, k, m ):

p = 6 - k - m
Hanoi ( n-1, k, p )
print ( k, "->", m )
Hanoi ( n-1, p, m )

if n == 0: return

условие выхода из рекурсии

# основная программа
Hanoi( 4, 1, 3 )


Слайд 71Вывод двоичного кода числа
def printBin ( n ):
if n

== 0: return
printBin ( n // 2 )
print

( n % 2, end = "" )

условие выхода из рекурсии

напечатать все цифры, кроме последней

вывести последнюю цифру

10011

printBin( 19 )

printBin( 9 )

printBin( 4 )

printBin( 2 )

printBin( 1 )

printBin( 0 )

Вывод двоичного кода числаdef printBin ( n ): if n == 0: return printBin ( n //

Слайд 72Вычисление суммы цифр числа
def sumDig ( n ):
sum =

n % 10
if n >= 10:
sum +=

sumDig ( n // 10 )
return sum

рекурсивный вызов

sumDig( 1234 )

4 + sumDig( 123 )

4 + 3 + sumDig( 12 )

4 + 3 + 2 + sumDig( 1 )

4 + 3 + 2 + 1

последняя цифра

Вычисление суммы цифр числаdef sumDig ( n ): sum = n % 10 if n >= 10:

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

вычитать из большего числа меньшее до тех пор, пока меньшее

не станет равно нулю. Тогда второе число и есть НОД исходных чисел.

def NOD ( a, b ):
if a == 0 or b == 0:

if a > b:
return NOD( a - b, b )
else:
return NOD( a, b – a )

return a + b;

рекурсивные вызовы

условие окончания рекурсии

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

Слайд 74Задачи
«A»: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел,

используя модифицированный алгоритм Евклида.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574)=1234.
«B»: Напишите

рекурсивную функцию, которая раскладывает число на простые сомножители.
Пример:
Введите натуральное число:
378
378 = 2*3*3*3*7

Задачи«A»: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида. Пример:Введите два натуральных

Слайд 75Задачи
«C»: Дано натуральное число N. Требуется получить и вывести на

экран количество всех возможных различных способов представления этого числа в

виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры.
Пример:
Введите натуральное число:
4
Количество разложений: 4.
Задачи«C»: Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления

Слайд 76Как работает рекурсия?
def Fact(N):
print ( "->", N )
if

N

N * Fact ( N – 1 )
print ( "<-", N )
return F

-> N = 3
-> N = 2
-> N = 1
<- N = 1
<- N = 2
<- N = 3

Факториал:


Слайд 77Стек
Стек – область памяти, в которой хранятся локальные переменные и

адреса возврата.
Fact(3)
Fact(2)
Fact(1)
значение параметра
адрес возврата
локальная переменная

СтекСтек – область памяти, в которой хранятся локальные переменные и адреса возврата.Fact(3)Fact(2)Fact(1)значение параметраадрес возвраталокальная переменная

Слайд 78Рекурсия – «за» и «против»
с каждым новым вызовом расходуется память

в стеке (возможно переполнение стека)
затраты на выполнение служебных операций при

рекурсивном вызове

программа становится более короткой и понятной

возможно переполнение стека
замедление работы

def Fact ( n ):
f = 1
for i in range(2,n+1):
f *= i
return f

итерационный алгоритм

Рекурсия – «за» и «против»с каждым новым вызовом расходуется память в стеке (возможно переполнение стека)затраты на выполнение

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика