XI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
РЕШЕНИЕ ЗАДАЧ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ PYTHON (ПАЙТОН)
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
В данной работе представлен материал о высокоуровневом языке программирования Python (Пайтон). Тема достаточно актуальная и представляет повышенный интерес для учащихся профильных классов.
Цель данной работы заключается в том, чтобы получить дополнительные знания по этой теме.
Задача состоит в том, чтобы подобрать соответствующий материал с последующей систематизацией, обобщением и иллюстрацией текста.
Работа состоит из двух частей: теоретической (даны история языка, описание типов и структур данных, возможности, стандартная библиотека) и практической (приведён пример разработки алгоритма и двух вариантов программы (скрипта) с последующей обработкой данных на компьютере).
Основная часть
Общие сведения о языке программирования Python (Пайтон)
§ 1. История языка Пайтон
Р азработка языка Python (Пайтон) была начата в конце 1980-х годов сотрудником голландского института CWI Гвидо ванн Россумом. Гвидо начал писать Python на досуге, позаимствовав некоторые наработки для языка ABC (Гвидо участвовал в разработке этого языка, ориентированного на обучение программированию). В феврале 1991 года Гвидо опубликовал исходный текст.
Наличие дружелюбного, отзывчивого сообщества пользователей считается, наряду с дизайнерской интуицией Гвидо, одним из факторов успеха Python. Развитие языка происходит согласно чётко регламентированному процессу создания, обсуждения, отбора и реализации документов PEP (англ. Python Enhancement Proposal) — предложений по развитию Python.
3 декабря 2008 года после длительного тестирования, вышла первая версия Python 3000 (или Python 3.0, также используется сокращение Py3k). В Python 3000 устранены многие недостатки архитектуры с максимально возможным (но не полным) сохранением совместимости со старыми версиями Python. На сегодня поддерживается одна ветка развития (Python 3.x), поддержка ветки Python 2.x закончилась в апреле 2020 года [1].
§ 2. Типы и структура данных
Python поддерживает динамическую типизацию, то есть тип переменной определяется только во время исполнения. Поэтому вместо “присваивания значения переменной” лучше говорить о “связывании значения с некоторым именем”. В Python имеются встроенные типы: булевый, строка, Unicode-строка, целое число произвольной точности, число с плавающей запятой, комплексное число и некоторые другие. Из коллекций в Python встроены: список, кортеж (неизменяемый список), словарь, множество и другие. Все значения являются объектами, в том числе функции, методы, модули, классы.
Добавить новый тип можно либо написав класс (class), либо определив новый тип в модуле расширения (например, написанном на языке C). Система классов поддерживает наследование (одиночное и множественное) и метапрограммирование. Возможно наследование от большинства встроенных типов и типов расширений.
Все объекты делятся на изменяемые и неизменяемые: списки, словари и множества являются изменяемыми, а все остальные — неизменяемыми (например, при изменении строки фактически создаётся новая, а при изменении списка — только меняются ссылки в нём). Кортеж в Python является, по сути, неизменяемым списком. Во многих случаях кортежи работают быстрее списков, поэтому если вы не планируете изменять последовательность, то лучше использовать именно их. Неизменяемые объекты (и все объекты в них, если это, например, кортеж) могут быть ключами словаря (должны иметь метод hash) [1].
§ 3. Возможности для объектно-ориентированного программирования
Дизайн языка Python построен вокруг объектно-ориентированной модели программирования. Реализация ООП в Python является элегантной, мощной и хорошо продуманной, но вместе с тем достаточно специфической по сравнению с другими объектно-ориентированными языками [1].
§ 4. Стандартная библиотека
Богатая стандартная библиотека является одной из привлекательных сторон Python. Здесь имеются средства для работы со многими сетевыми и форматами Интернета, например, модули для написания HTTP-серверов и клиентов, для разбора и создания почтовых сообщений, для работы с XML и т. п. Набор модулей для работы с операционной системой позволяет писать кросс-платформенные приложения. Существуют модули для работы с регулярными выражениями, текстовыми кодировками, мультимедийными форматами, криптографическими протоколами, архивами, сериализации данных, поддержка юнит-тестирования и др [1].
Практическая часть
Разработка программ с использованием управляющих конструкций (ветвление, цикл) на примере сортировки Джона фон Неймана (процедура слияния двух отсортированных массивов)
§ 1. Словесное описание алгоритма
Для более быстрой сортировки массивов в 1945 году Джон фон Нейман предложил алгоритм, основанный на процедуре слияния двух заранее отсортированных массивов. Предположим, что есть два отсортированных массива A и B, размеры которых соответственно Na и Nb и мы хотим объединить их элементы в один отсортированный массив C размером Na + Nb. Для этого будем на каждом шаге сравнивать два первых (ещё не использованных) элемента массивов A и B, добавляя в конец массива C наименьший из них. Так продолжается до тех пор, пока один из массивов не закончиться, тогда оставшийся “хвост” второго массива просто добавляется в конец массива C (он ведь уже отсортирован!). Пример такого слияния показан на рис. 1.
|
A |
B |
C |
|||||||||||||||
|
6 |
34 |
67 |
82 |
98 |
44 |
55 |
78 |
6 |
|||||||||
|
34 |
67 |
82 |
98 |
44 |
55 |
78 |
6 |
34 |
|||||||||
|
67 |
82 |
98 |
44 |
55 |
78 |
6 |
34 |
44 |
|||||||||
|
67 |
82 |
98 |
55 |
78 |
6 |
34 |
44 |
55 |
|||||||||
|
67 |
82 |
98 |
78 |
6 |
34 |
44 |
55 |
67 |
|||||||||
|
82 |
98 |
78 |
6 |
34 |
44 |
55 |
67 |
78 |
|||||||||
|
82 |
98 |
6 |
34 |
44 |
55 |
67 |
78 |
82 |
98 |
||||||||
Рис.1. Сортировка слиянием
Фоном выделены элементы, которые добавляются в массив C на очередном шаге. Шаги 1-6 – это добавление в массив C наименьшего из первых двух элементов массивов A и B, а шаг 7 – дописывание в конец массива C с “хвоста” массива A (ведь массив B уже добавлен в массив C) [2].
§ 2. Составление программы (скрипта)
Рассмотрим два варианта решения данной задачи:
1. Количество элементов одного массива не соответствует количеству элементов второго массива (N = 5, M = 3); заполнить массивы с клавиатуры;
2. Количество элементов одного массива соответствует количеству элементов второго массива (N = 8); заполнить массивы случайными числами из отрезка [100, 150] с использованием функции randint, которая импортируется из модуля random.
1. Исходный модуль программы:
#Сортировка Джона фон Неймана (процедура слияния)
#Количество элементов исходных массивов N и M
#Заполнение массивов с клавиатуры
print(" Заполнить два целочисленных массива, отсортировать их по возрастанию,")
print("сформировать третий массив с последующей его сортировкой по возрастанию")
print()
print("Введите количество элементов для массива A:")
N = int(input())
print("Введите количество элементов для массива B:")
M = int(input())
print("Заполнение массива(списка) A целыми числами")
A = [int(input()) for i inrange(N)]
print("Заполнение массива(списка) B целыми числами")
B = [int(input()) for i inrange(M)]
#Сортировка массива A (Метод Подстановки)
for i inrange(N):
for j inrange(N-1):
if A[i] < A[j]: #условиесортировки
A[i], A[j] = A[j], A[i] #поменятьэлементы
print("Отсортированныймассив A:")
for i inrange(N):
print(A[i], "", end = "") #построчныйвыводмассива A
print()
#Сортировка массива B (Метод Подстановки)
for i inrange(M):
for j inrange(M-1):
if B[i] < B[j]: #условие сортировки
B[i], B[j] = B[j], B[i] #поменять элементы
print("Отсортированныймассив B:")
for i inrange(M):
print(B[i], "", end = "") #построчный вывод массива B
C = [] #объявить маcсив C
i = j = 0 #инициализация параметров циклаprint()
#формирование и сортировка массива C слиянием
while ((i < N) and (j < M)):
if A[i] <= B[j]: #условие отбора
C.append(A[i]) #запись в конец массива C
i += 1
else:
C.append(B[j]) #запись в конец массива C
j += 1
C = C + A[i:] #добавить в массив C оставшуюся часть A
i = 0 #инициализация параметра цикла i
print("Отсортированный массив C:")
for i inrange(N+M):
print(C[i], "", end = "") #построчный вывод массива C
print()
print("Программа завершена")
2. Исходный модуль программы:
#Сортировка Джона фон Неймана
#(процедура слияния двух отсортированных массивов)
from random import randint
print(" Заполнить два целочисленных массива, отсортировать их по возрастанию,")
print("сформироваить третий массив с последующей его сортировкой по возрастанию")
print()
print("Введите количество элементов для каждого массива:")
N = int(input())
print("Заполнение массива(списка) A целыми числами")
A = [ randint(100, 150) for x inrange(N)]
print(A) #вывод на экран выбранных элементов массива A
print("Заполнение массива(списка) B целыми числами")
B = [ randint(100, 150) for x inrange(N)]
print(B) #вывод на экран выбранных элементов массива B
#Сортировка массива A (Метод Подстановки)
for i inrange(N):
for j inrange(N-1):
if A[i] < A[j]: #условиесортировки
A[i], A[j] = A[j], A[i] #поменятьэлементы
print("Отсортированныймассив A:")
for i inrange(N):
print(A[i], "", end = "") #построчныйвыводмассива A
print()
#Сортировка массива B (Метод Подстановки)
for i inrange(N):
for j inrange(N-1):
if B[i] < B[j]: #условие сортировки
B[i], B[j] = B[j], B[i] #поменять элементы
print("Отсортированныймассив B:")
for i inrange(N):
print(B[i], "", end = "") #построчный вывод массива B
C = [] #объявить маcсив C
i = j = 0 #инициализация параметров цикла while
print()
#формирование и сортировка массива C
#слиянием массива A и массива B
while ((i < N) and (j < N)):
if A[i] <= B[j]: #условие отбора
C.append(A[i]) #запись в конец массива C
i += 1
else:
C.append(B[j]) #запись в конец массива C
j += 1
C = C + A[i:] #добавить в массив C оставшуюся часть A
i = 0 #инициализация параметра цикла i
print("Отсортированный массив C:")
for i inrange(N*2):
print(C[i], "", end = "") #построчный вывод массива C
print()
print("Программа завершена")
§ 3. Подготовка тестовых примеров
Тестовый пример №1:
|
Количество элементов для массива A |
5 |
|
Количество элементов для массива B |
3 |
|
Числовые значения элементов массива A |
6 34 67 82 98 |
|
Числовые значения элементов массива B |
78 44 55 |
|
Отсортированный массив A |
|
|
6 34 67 82 98 |
|
|
Отсортированный массив B |
|
|
44 55 78 |
|
|
Сформированный и отсортированный массив C |
|
|
6 34 44 55 67 78 82 98 |
|
Тестовый пример №2:
Количество элементов каждого из двух массивов равно 8.
§ 4. Компьютерный эксперимент
Войти в программную среду Пайтон, выполнив команды File – New File.
В текстовом редакторе набрать исходный модуль программы (§ 2).
Запустить программу на выполнение, выполнив команды: Run – Run Module (F5).
В появившемся окне сохранить модуль, указав имя программы и место сохранения:
Ввести исходные данные и получить результат (§ 3).
Выполнение программы по тесту №1:
Выполнение программы по тесту № 2:
§ 5. Анализ выполнения программы
Сортировка слиянием использует следующие этапы:
Задача разбивается на несколько подзадач меньшего размера.
Эти подзадачи решаются с помощью рекурсивных вызовов того же (или другого) алгоритма.
Решения подзадач объединяются, и получается решение исходной задачи.
Сортировка слиянием применима для данных с последовательным доступом. Этот алгоритм можно использовать в системах с параллельными процессорами с общей памятью, которые работают одновременно и делят работу между собой.
Главный недостаток состоит в том, что нужен дополнительный массив того же размера, что и исходный (массив C) [2] .
З аключение
Язык Python (Пайтон) – это профессиональный язык программирования, который активно используется в таких компаниях, как Яндекс и Google. На нём разрабатываются сайты и веб-сервисы, он применяется для составления небольших программ, расширяющих возможности других программ [2].
Python (Пайтон) – современный развивающийся язык, изучение которого начинается в профильных классах общеобразовательных учреждений на примере использования его основных конструкций, что достаточно наглядно показано в данной работе.
Список использованных источников и литературы
Python - Википедия - https://ru.wikipedia.org/wiki/Python
Информатика. Базовый и углублённый уровни: учебник для 10 класса, часть 2 / К.Ю. Поляков, Е.А. Еремин. – М.: БИНОМ. Лаборатория знаний, 2019.
Программное обеспечение
Операционная система Windows
Текстовый процессор MS Word
Среда программирования Python – 3.8.0