Презентация по теме "Запись вспомогательных алгоритмов на языке Python" (9 класс)

Слайд #1

ЗАПИСЬ ВСПОМОГАТЕЛЬНЫХ АЛГОРИТМОВ НА ЯЗЫКЕ PYTHON
АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ
учитель: Сойникова Екатерина Дмитриевна.
МКОУ «Новоспасская СОШ» Золотухинского района Курской области

Слайд #2

Ключевые слова
подпрограмма
процедура
функция
рекурсивная функция

Слайд #3

Подпрограммы
Запись вспомогательных алгоритмов в языках программирования осуществляется с помощью подпрограмм.
В Python различают два вида подпрограмм
Процедура
Функция
Подпрограмма

Слайд #4

Процедуры
Процедура – это подпрограмма, выполняющая некоторые действия; она может иметь произвольное количество заданных параметров.
Описание процедуры имеет вид:
def <имя процедуры> ():
<операторы>

Слайд #5

Процедуры Python
Процедура начинается со служебного слова def (от англ. define – определитель). После этого записывается имя процедуры, скобки и двоеточие.
Операторы, которые входят в тело процедуры записываются отступом. Так мы показываем, какие команды входят в процедуру.
Для того, чтобы процедура заработала, ее необходимо вызвать по имени; причем таких вызовов может быть сколько угодно.
Процедура должна быть определена к моменту ее вызова, т.е., должна быть выполнена команда def, которая создает объект-процедуру в памяти. Если процедура вызывается из основной программы, то нужно поместить определение процедуры раньше точки ее вызова.

Слайд #6

Процедуры Python
def digit():
print(1111111)
print(‘Четыре строки из семи единиц’)
digit()
digit()
digit()
digit()
Пример. Предположим, что требуется вывести четыре строки, каждая из которых состоит из семи единиц. Для этого создадим процедуру, которая выполнит вывод одной строки из семи единиц, и вызовем ее четыре раза.

Слайд #7

Процедуры Python
print(‘1’ * n)
Предположим, что требуется вывести четыре строки, состоящие из семи, восьми, девяти и десяти единиц соответственно.
Для этого создадим процедуру с параметром, определяющим длину строки.
Чтобы вывести единицу n раз, воспользуемся командой:
Чтобы использовать эту команду в процедуре, укажем в скобках переменную (параметр), значение которой и будет определять длину строки.
def digit(n):
print(‘1’ * n)

Слайд #8

Процедуры Python
Чтобы вывести строку требуемой длины, нужно вызвать процедуру, указав в скобках значение параметра n, т.е., количество символов ‘1’:
def digit(n):
print(‘1’ * n)
digit(7) #выводит 7 единиц: 1111111
digit(8) #выводит 8 единиц: 11111111
digit(9) #выводит 9 единиц: 111111111
digit(10) #выводит 10 единиц: 1111111111

Слайд #9

Процедуры Python
Процедура может зависеть от нескольких параметров. Давайте немного улучшим процедуру digit(d,n): сделаем так, чтобы можно было изменять не только длину строки, но и цифры, из которых она строится. Для этого введем процедуру еще один параметр, который назовем d:
def digit(d,n):
print(d * n)

Слайд #10

Процедуры Python
def digit(d,n):
print(d * n)
x = (input(‘Введите цифру: ’))
y = (input(‘Введите длину строки: ’))
digit(x, y)
Обозначим переменных, значения которых мы вводим с клавиатуры, не обязательно должно совпадать с обозначением параметров процедуры. Мы могли назвать их любыми другими именами, например:

Слайд #11

Процедуры Python
Переменные d и n – это локальные переменные; они определены и используются только внутри процедуры digit(). Обращаться к ним все этой процедуры нельзя. Как только работа процедуры будет закончена, все ее локальные переменные удалятся из памяти.
В тех случаях, когда значение переменной, полученное в подпрограмме, должно быть использовано в основной программе, эту переменную следует объявить как глобальную.

Слайд #12

Процедуры Python
Пример. Хорошо известный алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел в виде процедуры можно описать так:
Модифицированный алгоритм Евклида для натуральных чисел: заменять бóльшее из двух заданных чисел на остаток от деления бóльшего на меньшее, пока этот остаток не станет равен нулю. Тогда второе число и есть их НОД.
def nod (a,b):
global x
while a!=b:
if a > b:
a = a – b
else:
b = b - a
x = a

Слайд #13

Процедуры Python
Протестируйте программу на последовательности из шести чисел: 16, 32, 40, 64, 80 и 128.
Задача поиска НОД для последовательности натуральных чисел, количества членов которой k вводится с клавиатуры, может быть решена с помощью следующей программы:
Подпрограмма
k = int(input(‘k=’))
x = int(input())
for i in range (1,k):
y = int(input())
nod(x,y)
print(‘НОД=’,x)
Основная программа
def nod (a,b):
global x
while a!=b:
if a > b:
a = a – b
else:
b = b - a
x = a

Слайд #14

Примеры основной программы
m = [16, 32, 40, 64, 80, 128]
x = m[0]
for i in range (1, 6):
y = m[i]
nod(x,y)
print (‘НОД=‘,x)
Измените программу так, чтобы с ее помощью можно было найти:
а) наибольший общий делитель для следующих пяти чисел: 12, 24, 30, 48 и 51;
б) наибольший общий делитель произвольных десяти целых двузначных чисел.
С помощью массива

Слайд #15

Напишем программу
а) наибольший общий делитель для следующих пяти чисел: 12, 24, 30, 48 и 51;
def nod (a,b):
global x
while a!=b:
if a> b:
a = a-b
else:
b = b-a
x = a
m = [12, 24, 30, 48, 51]
x = m[0]
for i in range (1, 5):
y = m[i]
nod(x,y)
print ('НОД=',x)

Слайд #16

Напишем программу
б) наибольший общий делитель произвольных десяти целых двузначных чисел.
def nod (a,b):
global x
while a!=b:
if a> b:
a = a-b
else:
b = b-a
x = a
N=10
A=[0]*N
from random import randint
for i in range (N):
A[i]=randint(0,99)
for i in range(N):
print('A = [',i,'] = ',A[i])
x = A[0]
for i in range (1, 10):
y = A[i]
nod(x,y)
print ('НОД=',x)

Слайд #17

Рассмотрим программу, которая выводит все простые
множители произвольного натурального числа a > 1
(если число простое, то выводится оно само)
Процедуры Python
Подпрограмма
a = int(input(‘a = ‘))
while a > 1:
ppd(a)
a = a / d
Основная программа
def ppd (n):
global d
d = 2
while n % d > 0:
d = d + 1
print(d)
Протестируйте программу на числах 121, 135 и 847. В результате ее выполнения вы должны получить соответствующие наборы чисел, записанных в столбик: 11, 11; 3, 3, 3, 7, 11, 11.

Слайд #18

Разработанная блок-схема на основе данного алгоритма
Процедуры Python
Начало
n
d := 1
Конец
d
да
n mod d > 0
нет
d := d+1
Здесь n – натуральное число, большее 1. Его первый простой
делитель d находится перебором всех возможных делителей, начиная с 2 – наименьшего простого числа. Если само n окажется простым числом, то d будет присвоено значение n
Алгоритм нахождения первого простого делителя

Слайд #19

Процедуры Python
Вспомогательный алгоритм при решении задачи разложения натурального числа на простые множители
Начало
n
Конец
да
n mod d > 0
нет
ppd (a, p)
a := a/p
Вспомогательный алгоритм нахождения первого простого делителя для некоторого числа мы назвали ppd. Его формальными параметрами являются переменные n, d; фактическими – a, p.

Слайд #20

Схема вызова вспомогательного алгоритма
Основной алгоритм






…
Имя вспомогательного
алгоритма (список
фактических параметров)

Вспомогательный алгоритм

Формальные аргументы
Формальные аргументы
…

Слайд #21

1. Для чего используют подпрограммы?
Вопросы и задания
2. Дан текст процедуры на языке Python:
def f (n):
if n > 1:
f(n // 2)
print(‘**’)
Определите, сколько звездочек будет выделено в результате вызова f(7). Вычисления фиксируйте в таблице:

Слайд #22

3. Напишите процедуру с параметрами n (целое число) и
a (символ), которая выводит на экран n строк, каждая из
Которых содержит n символов a.
Вопросы и задания
def f(n,a):
for i in range(n):
print(a*n)
f(12,'А')

Слайд #23

Вопросы и задания
def f(h,w,a):
for i in range(h):
print(a*w)
f(12,6,'А')
4. Напишите процедуру с параметрами w (ширина), h (высота), a (символ), которая выводит на экран «прямоугольник» из символов a, ширина которого равна w, а высота – h.

Слайд #24

Функции
Функция – подпрограмма, имеющая единственный результат, записываемый в ячейку памяти.
Функция начинается со служебного слова def. После этого записывается имя функции, скобки и двоеточие. Операторы, которые входят в тело функции, записывается с отступом. После оператора return записывается результат, который возвращает функции.
В языке Python есть встроенная функция max, вычисляющая максимальное значение.
В отличие от процедуры, функция не только выполняет какие-то команды, но возвращает результат в виде числа, символьной строки или др.
Описание функции имеет вид:
def <имя функции> ():
<операторы>
return <результат>

Слайд #25

Функции
В языке Python есть встроенная функция max, вычисляющая максимальное значение.
def max(a, b):
if a > b:
m = a
else:
m = b
return m
Результат функции можно сразу вывести на экран:
print (max(6,8))
Также мы можем присвоить результат работы функции любой глобальной переменной:
x = max(6,8)
Одна функция может вызвать другую.

Слайд #26

Функции
Запишем программу нахождения максимального из четырех целых чисел, использующую функцию поиска максимального из двух чисел.
def max(a, b):
if a > b:
m = a
else:
m = b
return m
a, b, c, d = map(int,input().split())
f = max(max(a, b),max(c, d))
print(‘f = ’,f)
Измените программу так, чтобы с ее помощью можно было найти:
а) максимальное из чисел a, b, c;
б) максимальное из чисел b, c, d;
в) минимальное из четырех чисел;
г) разность максимального и минимального из четырех чисел.
a, b, c, d = map(int,input().split()) – ввод строковых величин, разделенных пробелом

Слайд #27

Напишем программу
Измените программу так, чтобы с ее помощью можно было найти:
а) максимальное из чисел a, b, c
def max(a, b):
if a > b:
m = a
else:
m = b
return m
a, b, c = map(int,input().split())
f = max(max(a, b),c)
print('f = ',f)
б) максимальное из чисел b, c, d;
def max(a, b):
if a > b:
m = a
else:
m = b
return m
b, c, d = map(int,input().split())
f = max(max(b,c),d)
print('f = ',f)

Слайд #28

Напишем программу
в) минимальное из четырех чисел;
def min(a, b):
if a < b:
m = a
else:
m = b
return m
a, b, c, d = map(int,input().split())
f = min(min(a,b),min(c,d))
print('f = ',f)

Слайд #29

Напишем программу
г) разность максимального и минимального из четырех чисел.
def max(a, b):
if a > b:
m = a
else:
m = b
return m
def min(a, b):
if a < b:
m = a
else:
m = b
return m
a, b, c, d = map(int,input().split())
f = max(max(a, b),max(c, d))- min(min(a,b),min(c,d))
print('f = ',f)

Слайд #30

Функция
5. В чем основное различие процедур и функций?
6. Напишите функцию KDN(), которая вычисляет количество цифр вводимого целого числа.
def KDN(a):
cnt=0
while a > 0:
a=a//10
cnt+=1
return cnt
n = int(input('Введите число '))
print('Количество цифр в числе ',KDN(n))
Напишем программу

Слайд #31

Функция
7. Напишите функцию KBDN(), которая вычисляет количество в двоичной записи вводимого десятичного числа.
def KBDN(a):
b=''
while a>0:
b=str(a%2)+b
a=a//2
b=int(b)
print('Двоичная система счисления: ',b)
cnt=0
while b > 0:
b=b//10
cnt+=1
return cnt
a = int(input('Введите число '))
print('Количество цифр в числе ',KBDN(a))
Напишем программу

Слайд #32

Функция
8. Напишите программу вычисления наименьшего общего кратного следующих четырех чисел: 36, 54, 18 и 15. Используйте процедуру вычисления наибольшего общего делителя
Напишем программу
def NOK (x,y):
global c
if x>y:
g=x
else:
g=y
while True:
if((g%x==0) and (g%y==0)):
c=g
break
g+=1
A=[36,54,24,20]
c=A[0]
for i in range(1,4):
y=A[i]
NOK(c,y)
print(c)

Слайд #33

Функция
9. Напишите программу перестановки значений переменных a, b, с в порядке возрастания, т. е. так, чтобы a < b < c. Используйте процедуру swap.
def swap (a, b, c):
if a > b:
a, b = b, a
…

Исходные данные вводятся с клавиатуры.

Слайд #34

Напишем программу
a, b, c = map(int,input().split())
def swap(a,b,c):
if a > b:
a,b = b,a
if b > c:
b,c = c,b
if a > b:
a,b = b,c
print(a,b,c)
swap(a,b,c)

Слайд #35

Функция
10. Видоизмените программу сортировки массива выбором так, чтобы в ней использовалась процедура выбора наибольшего элемента массива.
N=10
A=[0]*10
for i in range(N):
A[i]=int(input())
for i in range(N):
print('A [ ',i,'] = ',A[i])
def sort(array):
n = len(array)
for i in range(n):
for j in range(0,n-i-1):
if array[j] > array[j+1]:
array[j],array[j+1]=array[j+1],array[j]
sort(A)
print(A)

Слайд #36

Функция
 
n=int(input())
def f(n):
s=0
for i in range(1,n+1):
cnt=1
f=1
while cnt<=i:
f*=cnt
cnt+=1
s+=f
return s
print('s = ',f(n))

Слайд #37

Функция
def func(x,n):
res=1
for i in range(n):
res*=x
return res
x = int(input('Введите x '))
n = int(input('Введите n '))
print('s = ',func(x,3)+func(x,5)+func(x,n))
12. Напишите программу вычисления выражения:
s = x3 + x5 + xn,
где x и n вводятся с клавиатуры.
Используйте функцию вычисления степени.

Слайд #38

Функция
13. Напишите функцию, вычисляющую длину отрезка по координатам его концов. С помощью этой функции напишите программу, вычисляющую периметр треугольника по координатам его вершин.
from math import*
def p(xa,ya,xb,yb):
res=abs(sqrt((xb-xa)**2 + (yb-ya)**2))
return res
xa=int(input('xa = '))
ya=int(input('ya = '))
xb=int(input('xb = '))
yb=int(input('yb = '))
xc=int(input('xc = '))
yc=int(input('yc = '))
P=p(xa,ya,xb,yb)+p(xa,ya,xc,yc)+p(xc,yc,xb,yb)
print('P = ',P)

Слайд #39

Функция
14. Напишите функцию, вычисляющую площадь треугольника по целочисленным координатам его вершин.
С помощью этой функции вычислите площадь четырёхугольника по координатам его вершин.
 
 

Слайд #40

Напишем программу
from math import*
def s(xa,ya,xb,yb,xc,yc):
res=abs(xa*(yb-yc)+xb*(yb-ya)+xc*(ya-yb))/2
return res
xa=int(input('xa = '))
ya=int(input('ya = '))
xb=int(input('xb = '))
yb=int(input('yb = '))
xc=int(input('xc = '))
yc=int(input('yc = '))

print('S = ',s(xa,ya,xb,yb,xc,yc))

Слайд #41

Последовательность Фибоначчи
В январе Саше подарили пару новорождённых кроликов. Через два месяца они дали первый приплод - новую пару кроликов, а затем давали приплод по паре кроликов каждый месяц.
Каждая новая пара также даёт первый приплод (пару кроликов) через два месяца, а затем - по паре кроликов каждый месяц. Сколько пар кроликов будет у Саши в декабре?
Числа 1, 1, 2, 3, 5, 8, … образуют так называемую последовательность Фибоначчи, названную в честь итальянского математика, впервые решившего соответствующую задачу ещё в начале XIII века.

Слайд #42

Математическая модель
Пусть f(n) количество пар кроликов в месяце с номером n.
По условию задачи:
f(1) = 1,
f(2) = 1,
f(3) = 2.
 

Слайд #43

Рекурсия
Полученная функция рекурсивная - в ней реализован способ вычисления очередного значения функции через вычисление её предшествующих значений.
Оформим в виде функции вычисление члена последовательности Фибоначчи.
def f(n):
if n == 1 or n == 2:
rez =1
else:
rez = f(n – 1) + f(n – 2)
return(rez)
Напишите программу, вычисляющую и выводящую 12 первых членов последовательности Фибоначчи.

Слайд #44

Напишем программу
def f(n):
if n==0:
return 0
elif n==1:
return 1
else:
return f(n-1)+f(n-2)
for i in range(13):
print(f(i))

Слайд #45

Напишем программу на языке Python для задачи «Ханойские башни»
def S(n):
if n == 1:
return 1
if n>0:
return 2*S(n-1)+1
print(S(7))

Слайд #46

Самое главное
Запись вспомогательных алгоритмов в языках программирования осуществляется с помощью подпрограмм. В Паскале различают два вида подпрограмм: процедуры и функции.
Процедура - подпрограмма, имеющая произвольное количество входных и выходных данных.
Функция - подпрограмма, имеющая единственный результат, записываемый в ячейку памяти, имя которой совпадает с именем функции.

Слайд #47

Опорный конспект
Запись вспомогательных алгоритмов в языках программирования осуществляется с помощью подпрограмм.
Подпрограмма, имеющая произвольное количество входных и выходных данных.
Подпрограмма, имеющая единственный результат, записываемый в ячейку памяти, имя которой совпадает с именем функции.
Процедура
Функция
Подпрограмма