Открытый урок; Циклы в Python; план-конспект урока по информатике и икт (10 класс)

Открытый урок "Циклы в Python"
план-конспект урока по информатике и икт (10 класс)

Цель урока: знакомство учащихся с циклом while, for; создание программ на языке Python.

Образовательные: познакомить учащихся с циклами; формирование умений и навыков записи конструкции while, for на языке программирования Python; определять цель работы; выбирать рациональные способы выполнения работы; получение новых знаний (знакомство с новыми понятиями).

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

Развивающие: развить навыки программирования в среде программирования Python; развить алгоритмическое мышление учащихся; развитие умственной деятельности (выполнения операций анализа).

Предметные: владение понятиями «операция», «оператор», умение создавать программы на языке Python.

Личностные: сформированность навыков сотрудничества со сверстниками; готовность и способность к образованию, в том числе самообразованию.

Метапредметные: умения записи простых последовательностей действия на формальном языке.

Форма обучения: фронтальная, групповая, индивидуальная.

Ресурсы: ПК, мультимедийный проектор, экран, презентация, среда программирования Python 3.7.

Организационный этап. Повторение 1 мин.
Проверка домашнего задания. Тестовое задание в МЭШ по уровням. 5 мин
Усвоение нового материала (групповая работа). 15 минут
Подведение итогов работы.10 минут
Первичное закрепление.2 минуты
Самостоятельная работа по изученному материалу.6 минут
Подведение итогов урока. 1 мин.

Организационный этап. Разминка.1 мин.

Приветствие класса, проверка готовности. Фиксация отсутствующих. Разминка.

Проверка ранее изученного материала. Тестовое задание в МЭШ.5 мин

Проверка проводится с использованием электронного образовательного ресурса.

3. Усвоение нового материала. Групповая работа. 14 минут.

Постановка задачи.1 мин.

4. Подведение итогов работы. 10 мин

n = int(input()) factorial = 1 while n > 1: factorial *= n n -= 1 print (factorial)

for i in range(1,N): s = s + i if (s == N): print ('Это число совершенно') break elif s > N: print ('Это число не совершенно.') break else : continue

while a!=0 and b!=0: if a > b: a = a % b else: b = b % a print (a+b)

fib1 = fib2 = 1 n = int(input()) if n print (fib1, end=' ') print (fib2, end=' ') for i in range(2, n): fib1, fib2 = fib2, fib1 + fib2 print (fib2, end=' ') print ()

n=int(input('задайте N: '))
for i in range(1,n):
d=10
while (i>=d):
d=d*10
if ((i*i % d)==i):
print('число ',i)

5. Первичное закрепление. 2 мин

Цикл while выполняется до тех пор, пока истинно условие s

Заметим, что значение s каждый шаг увеличивается на 10. На 8 шаге значение s станет равно 80 и условие s

6. Самостоятельная работа по вариантам(работа в презентации). 6 минут

for i in range (10000,100000):

if i%133==125 and i%134==111

7. Подведение итогов урока.1 мин.

Задания для групповой работы

1 Группа — задача 36 Совершенные числа

2 Группа — задача 21 Модифицированный алгоритм Евклида

3 Группа – задача 34 Числа Фибоначчи

4 Группа – задача 11 Автоморфные числа

5 группа — Задача 31 Факториал

Предварительный просмотр:

Вложенные циклы Python

Добро пожаловать в другую главу учебного курса по Python — Nested Loops. Отличный способ создания циклов, вложенные циклы доказали свою ценность на любом языке программирования. Сегодня мы сконцентрируемся на Python — на типах, синтаксисе и примерах. Итак, начнем.

Вложенные циклы

Было бы неплохо кратко коснуться Nested Loops в целом, прежде чем переходить к Python специально. Если цикл существует внутри тела другого цикла, он называется «Вложенный цикл». Это означает, что мы хотим выполнить код внутреннего цикла несколько раз. Внешний цикл контролирует, сколько итераций пройдёт внутренний цикл. Базовый пример вложенного цикла for:

for (i=0; i<10; i++)
(
for (j=0; j<10; j++)
(
//This code will execute 100 times.
)
//This code will execute 10 times.
)

Здесь следует отметить, что цикл любого типа может быть вложен в другой цикл. Например, цикл while может быть вложен в цикл for или наоборот.

Вложенные циклы Python

1) Вложено для цикла Синтаксис

Основной синтаксис вложенного цикла for в Python:

for (iterating_variable_1) in (sequence_1): #Outer Loop
for (iterating_variable_2) in (iterating_variable_1/sequence_2): #Inner Loop
(code to execute)

пример

for i in range(11): #line 1
for j in range(i): #line 2
print('*', end='') #line 3
print('') #line 4

Выход:

Выполнение потока

Попробуем понять ход выполнения вышеуказанной программы. В программе мы использовали две итерационные переменные i и j, чтобы напечатать узор звезд.

Компилятор начинается со строки 1. Он встречает цикл for и функцию диапазона. Функция диапазона в Python выводит итеративный массив целых чисел от 0 до числа, указанного в аргументе. Номер аргумента исключен из массива. В нашем случае он сгенерирует массив (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10). Теперь компилятор знает, что он должен выполнить следующий набор операторов 10 раз.

Когда он перемещается в строку 2, он встречает другую функцию цикла и диапазона. Обратите внимание, что аргумент этой функции диапазона является вычисленным значением нашей итерационной переменной i. Таким образом, он динамически генерирует массив в зависимости от значения i. Когда я = 0, массив пуст. Когда i = 1, массив равен (0). Когда я = 2, массив (0, 1) и так далее.

Читайте так же:

Меркурий 200 счетчик этм

Итак, количество раз, когда строка 3 выполняется напрямую, зависит от значения i. Обратите внимание на часть end = '' inline 3. Это сделано для того, чтобы Python не печатал перевод строки после каждой звезды. Нам нужен только перевод строки в конце каждой итерации внешнего цикла. Таким образом, мы явно напечатали перевод строки в строке 4 нашего кода.

Итак, теперь давайте внимательно рассмотрим каждую итерацию нашего вложенного цикла for.

Итерация внешнего цикла 1

I = 0, j = (), output is a blank line.

Итерация по внешнему циклу 2

I = 1, j = (0), output = *

Итерация внешнего цикла 3

I = 2, j = (0, 1), output = **

Итерация внешнего цикла 4

I = 3, j = (0, 1, 2), output = ***

Итерация внешнего цикла 10

I = 9, j = (0, 1, 2, 3, 4, 5, 6, 7, 8), output = *********

Итерация внешнего цикла 11

I = 10, j = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), output = **********

2) Вложенный цикл while

Синтаксис

Синтаксис для размещения цикла while в Python:

while (expression_1): #Outer loop
(code to execute) #Optional
while (expression_2): #Inner loop
(code to execute)

В отличие от цикла for, цикл while не имеет предварительно скомпилированной итерируемой последовательности. Цикл while продолжает выполнять код, пока выражение не станет истинным. Поэтому разработчик должен всегда помнить об обновлении итерируемой переменной / выражения, иначе цикл войдет в режим бесконечного выполнения.

пример

i=1 #line 1
while(i<=5): #line 2
j=5 #line 3
while(j>=i): #line 4
print(j, end=' ') #line 5
j-=1 #line 6
i+=1 #line 7
print() #line 8

Выход:

Выполнение потока

Строка 1 кода устанавливает итерационную переменную внешнего цикла в начальное значение. Следующая строка — начало внешнего цикла while. У него есть выражение i <= 5. Это выражение оценивается для истинного значения после каждой итерации. Выполнение входит в цикл, только если условие истинно. Как только условие становится ложным, цикл прерывается.

Поскольку начальное значение I равно 1, условие в строке 2 выполняется. Таким образом, компилятор переходит к строке 3 и устанавливает итерационную переменную j нашего внутреннего цикла в 5. В строке 4 снова есть цикл while с выражением, которое оценивается как true. Таким образом, компилятор выполняет строки 5 и 6. Затем он возвращается к строке 4 и оценивает условие. Если условие истинно, оно снова входит в строки 5 и 6. Если условие становится ложным, цикл завершается, и следующие строки для выполнения — это строки 7 и 8. То же самое следует для внешнего цикла.

Строки 6 и 7 очень важны, поскольку они обновляют нашу итерационную переменную. Без них поток программы входил бы в бесконечный режим выполнения, поскольку выражения цикла while всегда приводили бы к истине.

Должен ли я сломать, продолжить или пройти

Как и почти во всех других языках программирования, в Python также есть концепция прерывания и продолжения. Эти ключевые слова помогают завершить любой цикл или пропустить конкретную итерацию цикла. У Python также есть другое ключевое слово — pass. Давайте посмотрим на это.

1) Перерыв

Ключевое слово break указывает компилятору выпрыгнуть из цикла и прекратить его выполнение.

пример

for i in range(5):
for j in range(5):
if i == j:
break
print(j, end='')
print('')

Выход:

Программа выше прерывает внутренний цикл for, если значения I и j равны. Он не выполняет дальнейшие итерации цикла. Это можно в дальнейшем понять с помощью оператора continue.

2) Продолжить

Ключевое слово continue указывает компилятору пропустить текущую итерацию цикла и продолжить следующую итерацию.

пример

for i in range(5):
for j in range(5):
if i == j:
continue
print(j, end='')
print('')

Выход:

Обратите внимание, что та же самая программа, но с оператором continue вместо break, не завершает выполнение цикла. Он пропускает только текущую итерацию.

3) пройти

Ключевое слово pass интересно в Python. Это просто значит ничего не делать. Он используется, когда блок кода нужен синтаксически, но вы не хотите, чтобы какая-либо команда выполнялась. Это просто действует как заполнитель.

пример

for i in range(5):
for j in range(5):
if i == j:
#I am not sure what to do when i equals j, so for now I will pass.
pass
print(j, end='')
print('')

Выход:

Вывод

Циклы стратегически очень важны, чтобы научиться выполнять задачу с минимальным количеством строк кода. Это просто базовое введение в циклы. Рекомендуется больше тренироваться, проявлять творческий подход и дальше исследовать потенциал петель.

while

Начнем с простого цикла – он будет выполняться до тех пор, пока какое-то условие истинно. Давайте для наглядности возьмем такой код:

Читайте так же:

Виды обратных клапанов для счетчиков

Фактически, я говорю ~~интерпретатору Питона~~ компьютеру:

Когда дойдешь до выполнения этого кода, проверь, является ли то, что написано в строчке после while истинным значением.
Если да, то
1. выполни все, что находится в блоке после него, отделенное отступами слева (тело цикла)
2. вернись снова к пункту 1
Если вы запустите пример, то увидите, что примерно бесконечное количество раз на экран выводятся фразы «Я тут», «Привет привет»
Программа ушла в бесконечный цикл, пока мы её не остановим, она так и будет работать. Иногда (и довольно часто) это является желаемым поведением, и бесконечные циклы создаются специально, иногда это следствие ошибки программирования. Давайте рассмотрим несколько способов выхода из такого цикла.
Выход по изменению истинности условия.
Кстати говоря, что такое истинность в терминологии Питона? Это либо ключевое слово True, которое мы указывали в примере выше, либо числовое значение не равное нулю, либо непустая последовательность значений.
Давайте начнем с простой проверки условия. Например, истинно ли то, что число 3 больше 5? А то, что 5 больше 3?
Мы видим, как Питон возвращает ключевое слово True или False в зависимости от истинности условия (True это истина, а False означает ложь). Мы могли бы изменить наше условие на что-то похожее
И оно также работало бы бесконечно, потому 3 всегда будет меньше 5 (по крайней мере, в математике).
Однако, если использовать переменные, можно их менять в теле цикла, и выходить из него, когда истинность изменится. Возьмем для примера хулигана Петю, который выбивает зубы у отличника Васи. Петя планирует оставить Васе хотя бы 3 зуба, что бы тот мог есть (и смешно фепелявить). Нет-нет, мы не поддерживаем Петю!
Изначально мы объявили переменную vasyas_teeth, где указали, что у Васи 32 зуба (он же отличник, все зубы мудрости вылезли заранее). Каждый раз Петя проверяет, что осталось больше зубов, чем ~~он умеет считать~~ 3, и выбивает еще один. Когда зубов становится не больше трех, Петя прекращает свои противоправные действия (и едет зону на малолетку, хотя это другая история).
Вот как-то так всё:
Говоря серьезно, каждый раз проверялось условие vasyas_teeth > 3, пока оно было истинным цикл выполнялся, когда значение в переменной vasyas_teeth стало равно 3, вычисление 3 > 3 оказалось ложным, и программа продолжила выполнение в обход тела цикла, и больше никогда к нему не вернется.
Выход по команде
Помимо выхода «логического», как в примерах выше, иногда бывает полезным завершить цикл заранее, при каких-то условиях. В нашем примере, могли появиться родители, полиция, друзья Васи, Петя мог устать, и всякое другое разное, что помешало бы довести задуманное до конца.
Давайте подключим модуль random для генерации псевдослучайных событий, random.random() возвращает случайное число от 0 до 1, после каждого выбитого зуба Петя озирается, и, если random.random() > 0.8 (т.е. с вероятностью 0.2, они же 20%) появляется кто-то, Петя убегает. Хулиганы, они такие. Теперь Пете намного сложное закончить начатое.
В этом примере появилось ключевое слово break.
Это слово обозначает выйти из цикла немедленно, не дожидаясь следующей проверки. Программа продолжит выполнять код дальше по тексту, после тела цикла.
Пропуск шага цикла
Еще есть ключевое слово continue, оно позволяет сразу перейти к следующему шагу цикла. Допустим, зуб выбивается с вероятностью 35%, поэтому удар засчитывать надо, а зуб вычитать – нет. Давайте это реализуем.
Теперь, «Хрясь» происходит как и раньше, каждый раз, однако, если зуб не выбит, срабатывает слово continue, оставшаяся часть логики в теле цикла не выполняется, а цикл уходит на новую проверку. При этом счетчик зубов так же не уменьшается, поэтому Пете приходится долбить еще и еще.
Ну, и что бы довести ситуацию с Петей до более правильного завершения, логично предположить, что посторонние люди могут появиться в любой момент, а не только после удара, поэтому поставим их в начало цикла, потом удар, потом проверка на выбитый зуб и увеличение счетчика. Вот так:
Теперь возможны ситуации, когда Вася вообще не пострадает. И это правильно.
Как не надо писать циклы FOR на Python?
Для цикла используются многие, в том числе и нижеописанные, конструкции. На самом деле, это даже быстрее, чем в других языках. Кроме того, такой код весьма читаем.
Цикл по диапазону значений в Python
Одним из самых распространенных является цикл перебора некоторого диапазона значений. Что-то типа от 0 до 1000, от 1 до 99 — в общем, какие угодно диапазоны. Хороший способ использовать циклы в Python показан ниже.
В примере используется функция range(). В нее надо передавать значение, до которого будет идти перебор. При этом само значение включено не будет. В функцию можно передавать начало, конец и даже шаг перебора в качестве аргументов.
Цикл с использованием индексов и значений в Python
Еще одним частым применением циклов является цикл по последовательностям, в которых используются пары «индекс-значение».
Используемая функция enumerate() возвращает кортеж, состоящий из пар «индекс-значение». В примере это i и val. Еще функция умеет смещаться — для этого нужно передать ей индекс, с которого нужно начать перебор.
Цикл в обратном порядке в Python
И последнее, что рассмотрим в этой статье — это цикл по последовательности в обратном порядке. Циклы в Python конечно-же можно строить и с конца последовательности, постепенно приближаясь к ее началу. Только делать это нужно правильно.
Функция reversed() просто перебирает последовательность в обратном порядке. Большего о ней рассказать нельзя. Берет последовательность, перебирает с конца, и точка.
На этом все. В статье показаны три общие идиомы для циклов, которые вероятно помогут вам сделать код лаконичнее и читабельней. Согласитесь, это: reversed(array) понять гораздо проще, чем это: range(len(array) -1, -1, -1).
Цикл while в Python
Цикл — это некоторые повторяющееся действия или явления. Вспомним про годовой цикл: зима -> весна -> лето -> осень -> зима.
While используется для повторения частей кода. Он выполняется до тех пор, пока используемое условие является истиной.

Давайте рассмотрим работу подобного цикла на примере:
Результат выполнения будет выглядеть так:
Часть кода выполняется столько раз, сколько условие было истинно. За счет увеличения i на каждом шаге удалось достигнуть такой величины, что условие цикла стало ложью.
§ 8.8. Программирование циклических алгоритмов. Цикл с условием
Цикл – это алгоритмическая структура, в которой одни и те же инструкции выполняются периодически, в зависимости от условия. В качестве условия (как и в условной инструкции) может быть любое выражение возвращающее числовое значение. Если оно отлично от нуля, то это интерпретируется как True . Если выражение вычисляется как 0 (в том числе, как действительный ноль 0.0 ), то это интерпретируется как False . Условие, которое вычисляется как True , позволяет выполнить один шаг цикла, который состоит в том, что будут выполнены одна или несколько инструкций, находящихся в теле цикла.

Существуют несколько разновидностей циклов. Все они сводятся к трем основным видам:
- цикл с предусловием,
- цикл с постусловием и
- цикл с параметром.
Инструкция while
В языке python цикл с предусловием реализован с помощью инструкции while . Инструкция while имеет следующий синтаксис:
while в python отличается наличием необязательного блока else , который выполняется, если логическое выражение приобретает ложное значение.
Этот тип цикла является универсальным, т. к. с помощью него может быть решена любая задача с циклом. Но цикл должен завершать свою работу по выполнению определенного количества шагов, а для этого необходимо изменять значения объектов (переменных влияющих на условие) в теле цикла так, чтобы условие могло, рано или поздно, принять значение False . В этом и есть основная сложность разработки циклического алгоритма с помощью while . Если алгоритм как следует не продумать, то цикл может уйти в бесконечное выполнение (“зацикливание”) и алгоритм никогда не завершит свою работу. Тем не менее, бесконечный цикл может быть организован намеренно (в программировании такое не редкость), скажем, для анализа вводимых данных.
Задача 1. Составить программу, в которой новое значение переменной присваивается в цикле.
В этом случае, выход из цикла программируется в теле цикла, например, с помощью инструкций if и break . В программе 8.8.1 цикл будет изменять значение переменной до тех пор, пока не будет введен 0 .
Рассмотрим несколько типичных задач в которых используется цикл типа while .
Счетчики и накопители
Самым простым способом выхода из цикла – это проверка выполненных шагов цикла. Для этих целей используется переменная-счетчик. Эта переменная изменяет свое значение с шагом 1 , начиная с 0 . Нулевое значение переменной присваивается до входа в цикл, а в теле цикла переменной инкрементируется новое значение. В условии цикла сравнивается текущее значение счетчика с максимально возможным (количеством шагов).
Задача 2. Вывести на экран n -первых натуральных чисел.
Блок-схема

Во многих задачах требуется “накапливать” значение переменной. Накапливать можно как сумму, так и произведение. Накопителю суммы до входа в цикл присваивается значение 0 , а накопителю произведения – 1 , т. е. значения, которые не изменят окончательный результат.
Примером задачи получения в цикле произведения является вычисление факториала числа: n! = 1 · 2 · 3 · . · n .
Задача 3. Дано целое n . Получить значение n!
Аналогично программируется и накопление суммы.
Задача 4. С клавиатуры вводится n целых чисел. Определить среднее арифметическое n введенных чисел.
На самом деле, в подобных задачах счетчик не так уж и нужен! Действительно, если известно общее количество шагов цикла n , то мы можем уменьшать значение n с каждым шагом цикла на единицу до тех пор, пока значение n не станет равным 0 (если, конечно, начальное значение n больше в программе не потребуется). Сформулировав логическое выражение сравнения n с 0 , мы можем создать условие выхода из цикла.
Задача 5. Составьте программу рисования n квадратов c общим центром и шагом (расстояние между сторонами квадратов) равным d .
Вывод

Параметры: n = 20, d = 10
Счетчик с произвольным шагом
В программах выше использовался счетчик с целочисленным шагом равным единице для определения количества шагов цикла. Но, в общем случае, счетчик может иметь произвольный шаг, в том числе дробный. Покажем это на примере.
Задача 6. Составить программу вывода таблицы значений квадратного корня чисел от 0.2 до 10.0 с шагом 0.2 и точностью до 4 знаков после запятой.
Возможно, программный код выглядит не очень изящно, но это неизбежная плата за табличное оформление вывода. Приведем пример с черепахой.
Задача 7. Составить программу в которой черепаха рисует параболу
Вывод
Проход циклом по разрядам числа
В заключении, обсудим еще один тип задач в которых производится действия с разрядами числа. В этих задачах для работы с отдельными разрядами числа применяются операции целочисленного деления, которые мы изучили ранее. Поскольку количество разрядов в числе заранее неизвестно, то исходное число, на каждом шаге цикла, делится на 10 (с каждым шагом удаляется младший разряд), пока частное не станет равным нулю. Это значение является основанием прекратить деление и выйти из цикла.
Усовершенствуем программу 8.5.1 так, чтобы в итоге обрабатывалось число произвольной разрядности.
Одна из задач такого рода – это перевод числа из 10 системы счисления (далее – с.с.) в с.с. по основанию q .
Задача 8. Дано цело десятичное число n . Перевести это число в с.с. с основанием q (целое число в интервале 2..9 )
Идея алгоритма основана на способе “деления” описанного здесь. Суть его заключается в следующем. Исходное число делим на основание с.с. и получаем остатки от этого деления в цикле. Первый остаток – это младший разряд q -ичного числа. Последний – старший разряд. Для того, чтобы повысить старшинство разряда, мы умножаем полученный в каждом шаге цикла остаток на значение переменной p , которое, с каждым шагом цикла, возрастает в 10 раз. Само же число получаем в накопителе суммы – d (т. е. фактически мы производим расчеты в 10 с.с.). Встроенные возможности языка по переводу чисел в с.с. по основаниям 2..36 описаны нами ранее.
Базовые алгоритмы с помощью Python
Алгоритмизация — очень важная штука в жизни программиста. Все владеют этим навыком на разном уровне, однако владеть базовыми вещами должен каждый.
Во многих книгах для алгоритмов используется особый язык — псевдокод.
Пример псевдокода на английском
Как мы видим, тут используются отступы, символ ∈ для перебора элементов множества и многое другое, что в обычных языках не увидишь. Однако если внимательно посмотреть, то многое станет понятным. Использовать псевдокод сегодня мы не будем, информация предоставлена для дополнительного понимания происходящего.
Что здесь будет происходить?
Существует куча алгоритмов, подходящих для определенной задачи. Сегодня мы посмотрим на три базовых алгоритма, о которых будет чуть позже.
Данная статья будет по такой схеме:
Надеюсь всё понятно, теперь поговорим о языке, который мы будем использовать.
Python
Для демонстрации работы таких алгоритмов в реальном языке программирования нам необходим очень понятный и интуитивно понятный синтаксис. Как вы уже поняли из названия, в качестве такого языка я выбрал Python. Объясню несколько вещей, которые могут быть непонятны тем, кто не работал с этим языком:
a, b = b, a — распаковка кортежа(в данном случае обмен значениями двух переменных).
for a in list: — перебор всех элементов массива(эквивалентно foreach в C#)
while a < b: — обычный цикл while(отличие в том, что условие может быть не скобках)
range(N) — все члены арифметической прогрессии с первым членом равным нулю, шагом равным единице и последним членом, равным N — 1.
a %= b — присваивание переменной a значения остатка при делении a / b.
Алгоритм Евклида
Реализация
Задача: найти НОД(наибольший общий делитель) натуральных чисел a и b.
Ввод: a, b ∈ N.
Для этой задачи мы будем использовать алгоритм Евклида. Основная суть этого алгоритма:
НОД(a, b) = НОД(a % b, b)
Используем простой цикл с условием, что и a и b не равны нулю. Наибольшим делителем будет сумма a и b по окончанию цикла. Для грамотного оформления мы оформим алгоритм в виде функции для многоразового использования.

Т.к. b в определенный момент может стать больше a, при такой ситуации «свапаем» их значения.
Тестирование
Немного протестируем наш алгоритм. Для этого вручную создадим хэш-таблицу(dict) типа <a, b : НОД(a, b)>.
Выглядеть это всё дело будет примерно так:

Теперь оформим тестирование. Для этого воспользуемся форматированием строки.

Конструкция a, b = pair — распаковывает кортеж, присваивая переменной a значение pair[0], а переменной b — pair[1]. Далее подставляем все необходимые значения в строку и смотрим результат:

Все тесты наш алгоритм прошел, что не может не радовать. Теперь подумаем над улучшением нашего алгоритма.
Улучшение
Сейчас нам предстоит подумать над улучшением алгоритма. Мы можем убрать распаковку кортежа и просто через конструкцию if/else изменять числа. Выглядеть это будет так:

Заново протестируем наш алгоритм:

Результат всё тот же. Мы немного улучшили алгоритм и улучшили его читабельность(всё-таки распаковка кортежа может быть кому-то непонятна), при этом не повлияв на результат его работы.
Решето Эратосфена
Реализация
Задача: вывести все простые числа до натурального числа a(a > 2).
Ввод: a ∈ N
Для такой задачи возможно использование простого перебора, однако это будет неэффективно. Здесь мы будем использовать решето Эратосфена, подробное описание есть в Википедии(там даже есть интересная наглядная анимация работы этого алгоритма).
Для тех, кому лень читать, объясню кратко. Суть такова: мы создаем массив всех натуральных чисел от 2 до a по возрастанию. Затем мы берём каждый индекс i и приравниваем к нулю каждый элемент с индексом k*i(k = 1, 2, 3, …).

Здесь мы создаем маску, заполненную единицами(мы можем заменить 1 и 0 на True, False соответственно).
Далее работаем с индексами с помощью вложенного цикла. Здесь мы меняем значения в маске, а позже по маске осуществляем выбор элементов из массива. Для простоты пользуемся методом типа list — list.append().
Тестирование
По традиции, вручную создадим несколько тестов. Алгоритм довольно прост, потому нам понадобятся 3 наборa.

Также само тестируем алгоритм:

Улучшение
Если рассматривать пути улучшения, то можно убрать выбор по маске и воспользоваться возможностями языка в помощи очистки массива от полученных нулей. Получим нечто такое:

С помощью конструкции list(set()) мы очищаем массив от повторений. Затем удаляем лишний ноль и сортируем массив, из-за того, что set() не сохраняет порядок.
Однако такой метод мне не очень нравится, поскольку мы использовали слишком много особенных возможностей языка.
Бинарный поиск
Реализация
Задача: дан отсортированный массив натуральных чисел. Также дано число K. Установить номер позиции, куда необходимо вставить K, чтобы массив не перестал был отсортированным. Если в массиве встречаются числа, равные K, вставлять K следует перед ними.
Ввод: K ∈ N, arr : array;
Для этой задачи подойдёт и способ перебора, однако он имеет линейную сложность (O(N)), а бинарный поиск(тот самый алгоритм, который мы сейчас будем реализовывать) имеет логарифмическую сложность — O(log(N)).
Немного про О большое. Оценка сложности алгоритма служит для понимания, как будут увеличиваться затраты на вычисление в зависимости от изменения вводных данных. Например, если нам на ввод подается число N и для вычисления нам потребуется два цикла, один из которых вложенный, длиною N, то сложность алгоритма оценивается как O(N^2). Обычно константы в О-большом откидываются, ведь никак не влияют на результат(это только отчасти правда, иногда именно константы решают всё).
Именно поэтому существует запись log(N). Разложим log 2 (N) = log A (N) / log A (2), где A — любое число больше нуля и не равны единице. Т.к. log A (2) это константа, то её мы откидываем. Получаем log A (N). А так как A любое число, то мы просто пишем log(N).
Суть бинарного поиска — разделение массива на две части и путём сравнения откидывание одной из них.
Для нашей задачи алгоритм будет выглядеть примерно так:

Отбираем особый случай, когда массив пуст, а дальше ничего сложного.
Тестирование
Теперь мы случайно будем генерировать тестовые данные. Для этого воспользуемся генераторами(не будем вникать в тонкости их работы, просто расскажу, что делает фрагмент кода ниже).

Наш генератор принимает два параметра: N — кол-во возвращаемых массивов и l — их длину. Далее создаем массив с помощью спискового включения, и увеличиваем коэффициенты для следующего.
Теперь, по образцу, запускаем тестирование.

У меня вышло так:

Конечно же, у вас будут другие массивы, т.к. их мы генерируем с помощью random(не забудьте импортировать этот модуль в начале программы).
Насчет улучшения, то тут предоставлена стандартная реализация алгоритма, читабельная и понятная, потому пункт «Улучшение» мы пропустим.
Заключение
Сегодня мы реализовали три базовых алгоритма на языке Python. Вышло довольно неплохо, надеюсь полученные сегодня знания пригодятся вам в будущем. В этой статье переплетаются очень много тем, по которым можно написать отдельные материалы(например О-большое), так что можете попробовать найти интересную информацию об этом в интернете.
голоса
Рейтинг статьи