РЕШЕНИЕ ЗАДАЧ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ PYTHON (ПАЙТОН)

XI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

РЕШЕНИЕ ЗАДАЧ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ PYTHON (ПАЙТОН)

Ватьков А.С. 1
1Муниципальное общеобразовательное учреждение “Тверской лицей”
Наумова А.И. 1
1Муниципальное общеобразовательное учреждение “Тверской лицей”

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате 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. Компьютерный эксперимент

Войти в программную среду Пайтон, выполнив команды FileNew File.

В текстовом редакторе набрать исходный модуль программы (§ 2).

Запустить программу на выполнение, выполнив команды: RunRun 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

Просмотров работы: 275