Программирование. Программирование на языке Python (Полякова К.Ю.). Общие сведения о языке Python История

• Название: Общие сведения о языке Python История
• Анкор: Программирование
• Дата: 27.02.2023
• Размер: 5.72 Mb.
• Имя файла: Программирование на языке Python (Полякова К.Ю.).ppt
• Тип: Документы; #956875
• страница: 18 из 18

Быстрая сортировка

Случайный выбор элемента-разделителя:


from random import randint
def qSort ( A, nStart, nEnd ):
...
X = A[randint(L,R)]
...


X = A[randint(L,R)]


или так:


from random import choice
def qSort ( A, nStart, nEnd ):
...
X = choice ( A[L:R+1] )
...


X = choice ( A[L:R+1] )

Быстрая сортировка

В стиле Python:


from random import choice
def qSort ( A ):
if len(A) <= 1: return A
X = random.choice(A)
B1 = [ b for b in A  if b < X ]
BX = [ b for b in A  if b == X ]
B2 = [ b for b in A  if b > X ]
return qSort(B1) + BX + qSort(B2)


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


Что плохо?


?


окончание рекурсии


Asort = qSort( A )

Быстрая сортировка

N	метод пузырька	метод выбора	быстрая сортировка
1000	0,09 с	0,05 с	0,002 с
5000	2,4 с	1,2 с	0,014 с
15000	22 с	11 с	0,046 с

Сортировка массива случайных значений:

Сортировка в Python

B = sorted( A )


алгоритм Timsort


По возрастанию:


B = sorted( A, reverse = True )


По убыванию:


reverse = True


По последней цифре:


def lastDigit ( n ):
return n % 10
B = sorted( A, key = lastDigit )


key = lastDigit


или так:


B = sorted( A, key = lambda x: x % 10  )


lambda x: x % 10


«лямбда»-функция
(функция без имени)

Сортировка в Python – на месте

A.sort()


По возрастанию:


A.sort ( reverse = True )


По убыванию:


reverse = True


По последней цифре:


def lastDigit ( n ):
return n % 10
A.sort ( key = lastDigit )


key = lastDigit


или так:


A.sort( key = lambda x: x % 10  )


lambda x: x % 10

Задачи

«A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1

Задачи

«B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 5

Задачи

«C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.


«D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки c с выбором среднего элемента показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

РАБОТА С ФАЙЛАМИ

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


Формирование полного пути к файлу в любой ОС


начиная с версии 2.6


"r" – открыть на чтение,
"w" – открыть на запись,
"a" – открыть на добавление.


Если нужно прочитать несколько данных в одной строке, разделённых пробелами, используют метод split. Этот метод разбивает строку по пробелам и строит список из соответствующих «слов»:
Fin = open ( "input.txt" )
s = Fin.readline().split()
Если в прочитанной строке файла были записаны числа 1 и 2, список s будет выглядеть так:
["1", "2"]


Убираем ненужные символы


f=open('e:/0/qqq.top','r')
1) while True:
s=f.readline()
print s
if not s:
break
2) for i in f:
print i
f.close()


3) for s in open ('e:/0/qqq.top','r'):
print (s)

Генерация таблицы умножения

f=open('e:/0/qqq.txt','w')
a= [[i*j for j in range(1,10)] for i in range(1,10)]
for i in range(9):
s=str(a[i])+'\n'
f.write(s)
f.close()


Процедуры

Что такое процедура?

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


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

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

print ( "Ошибка программы" )


много раз!


def Error():
print( "Ошибка программы" )


n = int ( input() )
if n < 0:
Error()


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


Процедура:


define определить

Процедура с параметрами

Задача. Вывести на экран запись целого числа (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-битном двоичном коде.


Решение:


k = 128
while k > 0:
print ( n // k,
end = "" )
n = n % k
k = k // 2

n	k	вывод
178	128	1
50	64	0
50	32	1
18	16	1
2	8	0
2	4	0
2	2	1
0	1	0
0	0

178





10110010


Результат зависит от n!


!

Процедура с параметрами

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 )


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

Локальные и глобальные переменные

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»: Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из N символов '–'.
Пример:
Введите N:
10
----------
«B»: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой.
Пример:
Введите натуральное число:
1234
1
2
3
4


Функции

Что такое функция?

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


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


Алгоритм:


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

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

# основная программа
print ( sumDigits(12345) )


def sumDigits( n ):
sum = 0
while n!= 0:
sum += n % 10
n = n // 10
return sum


return sum


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

Использование функций

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

Задачи

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

Задачи

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

Как вернуть несколько значений?

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)


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

Задачи

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

Задачи

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

Логические функции

Задача. Найти все простые числа в диапазоне от 2 до 100.


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


i - простое


isPrime(i)


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

Функция: простое число или нет?

Какой алгоритм?


?


def isPrime ( n ):
k = 2
while k*k <= n and n % k != 0:
k += 1
return (k*k > n)


return (k*k > n)


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

Логические функции: использование

n = int ( input() )
while isPrime(n):
print ( n, "– простое число" )
n = int ( input() )


Функция, возвращающая логическое значение, может использоваться везде, где и логическая величина!


!

Задачи

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

Задачи

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