Строка. Список. Массив. Функция. Объект. Ссылка.

Python 3. Курс лекций с видео. Конспект. 1-ый семестр.

С чего начать учить Питон ? ... Начните с основ Python ... Можно почитать книги или посмотреть онлайн-уроки ... Очень полезно практиковаться самостоятельно, написав несколько простых программ ... Для повышения своего уровня знаний - рекомендуется решать задачи и делать проекты ... Python может быть использован для разработки многих различных проектов, включая веб-приложения, игры, аналитические инструменты, решать задачи машинного обучения и многое другое ... Рассмотрите варианты примеров, для которых лучше всего подходит Питон : ...
- Разработка веб-приложений с использованием фреймворков, таких как Django или Flask ...
- Разработка игр с использованием библиотек для игрового движка, например PyGame ...
- Написание скриптов, автоматизирующих задачи ...
- Создание инструментов для анализа и визуализации данных, с использованием библиотек MathPlotLib ...
- Машинное обучение и анализ данных, применяя Scikit-learn и TensorFlow ...

Однако, чтение руководств по языкам программирования и наблюдение примеров решения реальных задач по видео - может стать далеко не очевидным путём погружения в осознавание изучаемого материала ... Намного более предпочтительным вариантом - может стать способ обучения по доступным видео лекциям от преподавателей, преподающим материал в систематизированном и последовательном виде ... Как, например, видео курс лекций изучения языка программирования Python 3 в МФТИ, лектор Т. Ф. Хирьянов, 2017 год ... Краткий конспект курса для первокурсников московского физико / технического института (ФизТех) ...

В процессе изучения курса обучаемый столкнётся с рядом задач, которые, вероятно, большинству - никогда не потребуются решать в реальной жизни ... Зачем нужна такая сложность, зачем ботать все эти алгоритмы ? ... Это - вопрос актуальности всего курса ... Будет глубокое погружение в довольно большое множество сложных алгоритмов ... Каковы причины ? ...
- прокачать собственный интеллект ... научиться мыслить рекурсивно, алгоритмически и не по человечески ))) ...
- пользование стандартными библиотечными функциями даст понятие, сколько это стоит по времени и асимптотической сложности алгоритмов - стоит ли морочится, чтобы написать своё решение или проще использовать - готовое ... подойдет ли, оно - для решения специфической задачи ...
- знание алгоритмов умножает пути решения задач и повышает вероятность правильного чтения и понимания сути программного кода ...
- алгоритмическое суждение даёт существенное преимущество среди других программистов ...
- современные научные специалисты крайне нуждаются в программировании ... это - не только знание языка, но и, в том числе - знание алгоритмов ... динамическое программирование - как можно рекурсию свести к циклам, чтобы не делать - перевычислений ... overcalc / recalculation ... динамическое программирование - сложное, пока не ясна - цель и суть вычислений ; после этого, все становится - просто ...
- Во время изучения курса, большинство обучаемых - даже не сможет себе представить, для чего все эти знания понадобятся или пригодятся, им - впоследствии ...

# ... judge.mipt.ru, Дополнительные источники материалов по изучению Python 3, практика, видео.

# ... en.wikipedia.org, Метасинтаксические переменные foo, bar, biz в Википедии.

... Примечание ... Хотя, именно в этом курсе, имена foo, bar, biz - не используются, это - так называемые метасинтаксические переменные, являющиеся примерами имен переменных, используемыми во многих примерах программирования или документации ... Эти речевые обороты используются в случае, когда конкретное имя переменной - не имеет значения ... Также, они могут использоваться в качестве заглушек в комментариях при написании кода или для создания примеров кода - не связанных с конкретной программой или проектом ...

... Лекция 1. Введение в программирование.

... В информатику входит много областей и навыков, многие из которых - полезно изучать самостоятельно ... Видение кафедры - научить студентов кодить / программировать ... Однако, и тут - не всё так просто ... Алгоритмы и структуры данных ... Ремесло, искусство программирования, практика ... Синтаксис ... Прикладные библиотеки ... Архитектура и дизайн ПО ... Навыки групповой работы ... Языки программирования - рождаются и отмирают ... Цель курса : первые три области составляющих программирования на языке Python 3 - то, что останется на годы вперёд ...
Книги - не нужны ...
Изучение лекций - обязательно ...
Без лабораторных работ, эффект обучения, может быть - снижен ...

Синтаксис.

Пустой файл .py - уже является правильной программой ...
print - вывод на экран ... строка print("hello, world") ... переменная print(x) ...
В Python - нет переменных ... То, что считается мнимой переменной : имя (идентификатор) = значение (объект) ... Оператор равно = это - присваивание, но не копирование (то есть - ссылка) ...

Питон критически относится к переносу строки, и в случае необходимости - (заключить длинную строку кода с переносом - в скобки) ...
После двоеточия : цикл, функция - всегда происходит сдвиг текста на 4 позиции вправо ; это - обязательное условие ...
Окончание сдвига - является завершением подпрограммы ...

x=int(input()) - присваивание значения именованному объекту x со стандартного ввода (с клавиатуры) ... В ходе программы могут быть использованы и неименованные временные объекты, как строка 'привет мир' в print("hello, world") ... Временные неименованные объекты, необходимые для вычислений - создаются автоматически и после обработки - немедленно удаляются сборщиком мусора для очистки и экономии памяти ... сразу, как только ссылка на этот объект будет переназначена / удалена ... То есть, вычисляемое выражение - может создать новый объект, а присвоение - нет (только : заполнить, изменить или удалить значения ячеек памяти объекта) ... Также - удаляются объекты, потерявшие имя / ссылку и превратившиеся в неименованные ...

print(type(x)) - узнать тип данных переменной ... int - числа ... float - с плавающей точкой ... complex - комплексные ... math - подключаемые математические данные ... string - строки ... list - модифицируемые разнотиповые списки ... tuple - кортежи (неизменяемые списки) ... dict - словари ... file - файлы ...
Переменные / имена ссылок - ничего не знают о типе, лишь отсылая к объекту ...
Объекты - со строгой динамической типизацией : не создают сюрпризов автоматической модификацией типа (вызывающей ошибку обработки), но позволяют легко изменить тип данных - по указанию программиста ... При вводе значений указывать тип - необязательно, это дело - добровольное, исключительно для красоты и определённости чтения кода ...

Обмен значений через переменную ...
Обмен двух переменных через третью ... a = 2 ... b = 5 ... tmp = a ... a = b ... b = tmp ...
Обмен значений через две дополнительные переменные ... a = 2 ... b = 5 ... tmp1 = b ... tmp2 = a ... a = tmp1 ... b = tmp2 ...

Нестандартное присваивание.

x = y = z = 0 ... каскадное ...
a, b, c = 1, 2, 3 ... множественное, через кортеж ...
a, b = b, a ... обмен значений переменных через кортеж временных переменных ...

Математические операции, приоритет.

Унарные (с одним операндом, аргументом) - более высокого приоритета, чем бинарные (с двумя и более переменными) ...
x**y = x в степени y ...
3**0.5 = корень из 3 ...
a**b**c = a в степени b в степени c ; арифметические операции в Python выполняются справа налево, для однотипных, скобки - не нужны ...
-x = унарный минус ...
унарный плюс - просто не отображается ...
x*y = умножение ...

x+y = сложение ...
x-y = вычитание ...
x = x + 1, то же самое, что и x += 1 - укороченный оператор присваивания, синтаксический сахар ... Также, включая -=, *=, /=, //=, %= ... Укороченные операторы можно использовать в Питон, однако важно понимать, как это использование - влияет на исходную переменную, поэтому их следует использовать с осторожностью, особенно при работе с объектами, которые не являются изменяемыми, такими как кортежи и строки ... Также, вычисленное значение временного объекта - может не изменять исходного - вопреки ожиданиям ...

Три типа деления ...
x/y = обычное деление ... целые числа int, в результате - могут дать float с плавающей запятой ...
x//y = целочисленное деление с отбрасыванием остатка ... (-12) // 10 = -1 ... Частное (-1), умноженное на делитель (10) + остаток (-2) должно дать искомое делимое (-12) ...
x%y = получить остаток от деления ... применяется при поиске четных чисел, иных задач сопоставления с нужным числом, вычислений по модулю, шифрование и дешифрование ...
Вычисление по модулю, группы вычетов по модулю - задает границы остатков, не включая само число ... %5 остаток в границах 0 1 2 3 4 ... %10 остаток в границах 0 - 9 ...
С отрицательными числами, деление, работает более - математически правильно, чем - архитектурно (алгоритмически вшито в процессор CPU) - это следует учитывать для ожидания результата ...
(-11) // 10 = -2 ...
(-11) %% 10 = -1 ... ответ процессора Intel ... эта дрянь - нарушает математику в академическом представлении ...
(-11) %% 10 = 9 ... ответ языка Python ...

Управляющие операции. Циклы и ветвления.

while - универсальный цикл с предусловием ...
for - синтаксический сахар (необязательно, но делает жизнь программиста - слаще) ...
if else - оператор логического условия, либо / либо ...
Обязательное условие форматирования вида тела цикла - отступ в четыре пробела ... Конец отступа - грубо означает конец цикла ...
Итерация - однократное выполнение команд тела цикла ... Один прогон ... Тело команд цикла - это статика, а итерация - это динамика, ход выполнения ... Перед каждой следующей итерации - происходит проверка условия цикла ...
else - блок команд, выполняемый однократно - при выходе из цикла ...
if break - инструкция принудительного прерывания цикла по условию и выход - минуя все остальные команды, включая блок else ...
if continue - прерывание исполнения или вычислений текущего шага цикла / итерации (по условию) и переход к следующей ...
Вложенные циклы - допускаются, но - без злоупотребления и снижения читабельности кода ...

for - списочный цикл с диапазоном ...
range(S,S,S) - диапазон, понимая Start, Stop (не включая это значение границы), Step (шаг) ... универсальный генератор геометрической прогрессии ...
range(5) - по умолчанию 5 - это стоп ; старт = 0, степ = 1 ... От 0 до N-1 диапазон содержит ровно N чисел : 0, 1, 2, 3, 4 (всего 5 чисел, для случая этого примера) ...

... #2. Алгебра логики.

... Истина = 1 ... Ложь = 0 ... Логика верна в той системе ценностей, для которой, она - рассматривается ... Абсолютная истина - невыразима ... Любая система аксиом, либо - не полна, либо - противоречива ... При общем применении - возникают противоречия, которые не позволяют использовать логику - универсально ... Логика объединяет атомарные высказывания - в составные, и оперирует ими ...

Логические операции.

не A , ! , NOT ... Отрицание, инверсия ...
A и B , & , И ... Логическое умножение, конъюнкция ...
A или B , || , ИЛИ ... Логическое сложение, дизъюнкция ...
A -> B ... Следование, импликация ...
A <=> B ... Эквиваленция ...
A ^ B ... XOR, Исключающее ИЛИ, исключающая дизъюнкция ... Сложение по модулю 2 (0 1) ... Антиэквиваленция ... Побитовое сравнение, исключающее ИЛИ - будет истиной, если операнды - не равны (противоположны) ...

Таблицы истинности.

1+1=1 ... Какая в этом логика ? ... Нет чисел больше единицы ... Нельзя быть истиннее, чем - истина ...

Чем интересна алгебра логики ? ... Именно она заставляет работать компьютеры ... Операторов И, ИЛИ и НЕ - будет достаточно для записи любых высказываний ... Дизъюнктивная нормальная форма, так же, как и конъюнктивная - традиционные формы записей логических функций ... Для каждой произвольной таблицы истинности можно составить выражение, которое соответствует ей ... Упростить запись выражения помогут законы алгебры логики ...

Законы алгебры логики.

1) Взаимодействие с константами ... 0+x=x ... 1+x=1 ... 0*x=0 ... 1*x=x ...
2) Простые повторения ... A*A=A ... A+A=A ...
3) Третий лишний ... A+!A=1 ... A*!A=0 ...
4) Поглощение ... A*(A+B)=A ... A+A*B=A ...

5) Свойства логических операций И и ИЛИ ...
(A*B)*C = A*(B*C) ... Ассоциативность, сочетательность ... Скобки можно не писать ... A*B*C ...
A*B=B*A ... A+B=B+A ... Коммутативность, переместительный закон ...
A*(B+C)=A*B+A*C ... Дистрибутивность, распределительный закон ... В логике алгебры - работает и таким образом : A+B*C=(A+B)*(A+C) ...

Волшебные законы Де Моргана ... Законы отрицания И и ИЛИ ...
!(A+B)=!A*!B ... !(A*B)=!A+!B ...
!!A=A ... Закон двойного отрицания : не не А это А ... Отрицание отрицания - есть утверждение ...

В дизъюнктивной нормальной форме можно раскрыть оставшиеся операции : импликацию и эквиваленцию ...
A->B=!A+B ... по конъюнктивной нормальной форме ...
A<=>B=A*B+!A*!B ... Эквивалентность, когда A и B одновременно истинны или ложны ...

Глубокий вдох и выдох, потому-что глубже, в алгебру логики, мы заходить - не будем ... Алгебра логики изучается прежде всего - потому, что на ней работает компьютер и, при желании - любую логическую функцию можно зашить в схему и распаять её ...

Логические значения.

True / истина и False / ложь ... Логические операторы пишут с большой буквы ...
== два знака равно - это оператор сравнения, равенство ...
!= - это оператор сравнения, неравенство ...
Операторы сравнения if - без ущерба для функциональности можно заменить - на логические ...
flag=(x%10==0) or flag ... flag=(flag and x%10==0) ...

Конструкции выбора и ветвления.

Конструкции IF : вложенность, последовательность и эквивалентность логическим операциям ...
В некоторых случаях else может влиять на результат if ...

Каскадные условные конструкции if ...
Линейная, более читабельная ... Каждый следующий if else - требует сдвига на 4 позиции ... Избежать этой ситуации поможет совмещенный оператор elif ...
Дерево ветвления, более трудная конструкция для визуального восприятия кода ...
if y>0:
    if x>0:
    print('I')
    else:
    print('II')
else:
    if x<0:
    print('III')
    else:
    print('IV')

Системы счисления.

... #3. Системы счисления.

... цифра - это символ для кодирования числа ...
число, его значение - существует независимо от способа записи ...

Разложение десятичного числа 1234 (по основанию 10) = 1000 + 200 + 30 + 4 или 1*10^3 + 2*10^2 +3*10^1 + 4*10^0 ... Степень десятки указывает количество нулей после числа ...

Разложение числа 1234 (по основанию 5) = 1*5^3 + 2*5^2 +3*5^1 + 4*5^0 = 125 + 50 + 15 + 4 = 194 (по основанию 10) ...
Число 510 (по основанию 5) - недопустимо, так как в числе пятеричной системы не должны быть цифры равные или превышающие основание системы счисления (допустимо 0, 1, 2, 3, 4) ...

Двоичная система - самая простая из позиционных систем счисления, где значение знака цифры зависит от его положения в числе ... Слева от числа свободные ячейки разрядов - могут заполнять незначащие нули ... Бит это примерно то же самое, что и двоичный разряд ... Увеличение младшего разряда более единицы вызывает его переполнение и увеличивает более старший разряд ...

Последовательность накопления систем счисления - совпадает ... Зачем переводить восьмеричное число 73652_8 - в десятичную, а затем - в четверичную, если можно использовать короткий путь - через двоичную систему - напрямую ... При нехватке знака, незначащий ноль, всегда добавляется - слева от числа ...
73652_8 - представить, как триады = 111 011 110 101 010, а затем - разбить на диады = 01 11 01 11 10 10 10 10 = 13132222_4 ...
Представив это двоичное число, как - тетрады и переведя биты в байты - легко перейти к 16-теричной системе счисления : 0111 0111 1010 1010 = 77AA_16 ...

Схема Горнера - более интеллектуальный метод вычисления числа - слева направо ...
Возьмем уже известное число 1234_5 ...
Что значит 1 в этом числе - в пятеричной системе счисления ? ... 1 = 1 ...
А, что значит 12 ? - Это 1 с дописанным нулём + 2 ... С дописанным нулём - означает, что число нужно умножить на основание системы, в данном случае 1*5+2 ...
А, что значит 123 ? - Это 12 с дописанным нулём +3 = чему равно 12 - уже известно выше, и получается = (1*5+2)*5+3 ...
А, что значит 1234 ? - Это 123 с дописанным нулём +4 ... Подставляем известные значения и получаем = ((1*5+2)*5+3)*5+4 = 194 (по основанию 10) ...

Особенность схемы Горнера - в обратном кодировании числа ... Легко узнать последнюю цифру - делением и собрать число по остаткам деления - в обратном порядке, справа - налево ...
194 / 5 = 38 + 4 ...
38 / 5 = 7 + 3 ...
7 / 5 = 1 + 2
1 / 5 = 0 + 1
0 / 5 = 0
Собираем число справа налево (с конца - в начало), используя остатки деления и включая незначащий ноль : 0 1 2 3 4 - конвертация из десятичной в пятеричную систему осуществлена, число = 01234_5 = 1234_5 ...

В Python есть возможность напрямую писать числа в этих предопределённых константах систем счисления ...
0b111101 - двоичный код ...
0o0732 - восьмеричный код ...
0xFA0B - шестнадцатеричный код ...
x=int('Z3F', base=36) ... В Питоне можно ввести число, вплоть до 36 системы счисления (26 букв + 10 цифр) и последней значимой буквой цифры = Z ... Именованный параметр base позволяет указать нужный индекс ... Печать print(x) будет выдавать число в человеческой 10-тичной форме, независимо от способа внутреннего использования ...

Специальный формат представления вывода числа ...
print(bin(x)) - бинарный ...
print(oct(x)) - восьмеричный ...
print(hex(x)) - шестнадцатеричный ...

Пример перевода числа в систему счисления ...
base=7
x=int(input()) #ввод с клавиатуры ...
while x>0: # считывать, пока в числе есть цифры ...
    digit=x%base # считать последнюю цифру числа / остатка от деления ...
    print(digit, end='') # именованный параметр end указывает не переводить каретку после окончания печати ... варианты : ' ' - печатать пробел ; \n\n\n - несколько переносов строк ...
    x//=base # удалить последнюю цифру числа - разделить нацело на основание ...

Однопроходный алгоритм.

Алгоритм, где нужно обрабатывать одно число ...
Из числа - получить число ... Из одного - два ... Из двух - одно ... Из числа - последовательность чисел ... Из последовательности чисел - одно число (статистическая выжимка) ...
Есть класс алгоритмов, которые не требует запоминать все числа ...
Функция, по имеющейся статистической выжимке и новому числу - позволяет получить новую статистическую выжимку ...

Возможные одиночные проходы для обработки входного числа x ...
подсчёт ... n ... n+=1 ...
сумма ... s ... s+=x ...
произведение ... p ... p*=x ...
максимум ... m ... m = max(m,n) ... if x > m => m = x ...
поиск числа ... f ... флаг ... f = f or (x==x0) ... или - какие-нибудь проверки ...

Функции.

... #4. Функции.

... Совсем простая функция имеет процедурный вид ...
def hello(): # функция с пустым списком параметров ... скобки - признак функции, обязательно ...
    print('hello, world')
...
hello() # скобки - признак вызова функции ...
f=hello # создание ссылки на функцию / упоминание ... теперь её можно вызвать, как f() ... Понятно, что можно создать ссылку на функцию ... Непонятно, зачем сразу не сделать её имя - короче, а не перессыливать с новым именем - впоследствии ? ...

def hello(name): ... вызов hello('John') ... Функция с формальным параметром, обязательным ...
def hello(name="World"): ... вызов hello() - теперь не будет являться ошибкой и подставит параметр по умолчанию, либо - явно переданный при вызове ...

Синтаксис возврата функции ...
def max2(x,y):
    if x>y:
        return x # return явно прекращает выполнение функции ...
    else: # else - можно было не писать, так как при истинном условии - уже был бы сделан выход ...
        return y

def max3(x,y,z):
    return max2(x,max2(y,z))
Все требуемые предварительные вычисления будут сделаны автоматически ... Не имеет значения, даже если подставить для сравнения - строки ... Утиный механизм Duck Typing определит типизацию ввода ... Любое нечто, что допустимо сравнивать друг с другом - будет сравнимо ... Будет использован алфавитный лексико-графический порядок сравнения строк ... Кто позже в словаре - тот старше ... Длинное слово - больше короткого ...

Функция с форматированием вывода ...
def hello_separated(name="World", separator="-"):
    print("Hello", name, sep=separator) # именованный параметр присваивается прямо в условии ...
При вызове функции можно предложить изменить параметры по порядку умолчания ...
hello_separated("John","***") или - изменить порядок, указав параметры принудительно ...
hello_separated(separator="***", name="John") ... будет одинаково работоспособно ...

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

Стек вызовов ... В стек набрасываются адреса модулей вызова и строк возврата в исполняемый код программы ... В случае ошибки интерпретатор вывалит Call Stack на экран, чтобы понимать контекст : откуда был сделан вызов ...

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

Некоторые моменты ...
Тройные кавычки , """ , ДокСтрока после описания функции - описывают ее назначение, выводят текст - как помощь для справки и всплывающие подсказки при вводе данных ... Это многострочная документ строка ... Иногда важно писать комментарии на международном английском языке, если предполагается интернациональная разработка программы ...
pass - команда / заглушка, ничего не делает и не предполагает никаких действий ... Однако - возвращает NaN - специфическое ничего, что может не создавать ошибки выполнения кода ...
Имя функции должно отражать ее содержание ... Создание функций - создает каркас программы, а детализация кода - достигает его работоспособности ... Длинные и подробные имена функций - экономят время на чтении кода ... Программа пишется один раз, а читается 100 - 200 и более раз ...
Алгоритм Brute Force, метод грубой силы ... Если ответ, который лежит в некоем множестве данных может быть найден прямым перебором значений - это метод решения задачи грубой силой ...

Список. Массив. Данные.

... #5. Список. Массив. Данные.

... Массив, типа list ... Общее имя переменной и некоторое количество объектов неименованных данных, хранящихся в массиве, как - в контейнере ... Внутри массива объекты представлены, как - список, но при этом, сами - не являются списочными данными ...

Доступ к элементам массива по порядку ...
A = [1,2,3,4,5]
for x in A:
    print(x)

Модель данных в Python делится на изменяемые и не изменяемые объекты ... Значения объектов являются константными и не подлежат само изменению ...
x+=1 свяжет переменную x с временным вычисленным значением x+1, но не изменит данных внутри массива ...

Доступ к элементам массива по индексу ... Индексы начинаются с 0 ...
A = [1,2,3,4,5]
for k in range(5):
    A[k] = A[k]*A[k] # здесь k - не переменная, а индекс ссылки на значение объекта массива ...

A[0]*1000 # создать массив с нулевым значением и размножить его размер до 1000 элементов ...
Можно и нужно отслеживать индекс массива через специально выделенную дополнительную переменную, которую требуется явно модифицировать, чтобы она явно указывала на предел заполнения / потолок стека данных массива ...
C=A - это не новый массив (созданием / копированием), а второе имя - того же самого массива A[] ...
C=list(A) - явный вызов конструктора списка для копирования массива A[] в C[] ...

def array_search(A:list, N:int, x:int): # Тип данных можно предопределять заранее ... Функция ищет число x в массиве A от 0 до N-1 индекса - включительно и возвращает индекс элемента x ...
for k in range(N):
    if A[k]==x:
        return k # возвращает индекс найденного x ...
return -1 # или -1 если ничего не найдено ...

def invert_array(A:list, N:int): # Функция обращения массива (поворот задом - наперед) ...
Списки массива можно сравнить поэлементно ...
B[k]=A[N-1-k] # Зеркальное копирование последнего элемента A[] в первый элемент массива B[] ... или, равносильно обратному порядку копирования B[N-1-k]=A[k] ... Такая фишка прокатит при копировании элементов из одного массива в другой, но внутри одного массива - половина элементов будет затерта - противоположными : A[k] = A[N-1-k] ... Выйти из положения поможет метод обмена значений переменных через кортеж временных переменных, но только при условии половинного диапазона, чтобы избежать двойного : прямого и обратного копирования ...
for k in range(N//2):
    A[k], A[N-1-k] = A[N-1-k], A[k]

Циклический сдвиг массива.

Влево, при пробегании индексов в прямом порядке, первый элемент через переменную направляется в последний ...
tmp = A[0]
for k in range(N-1):
    A[k] = A[k+1]
A[N-1] = tmp ...

Вправо, при пробегании индексов в обратном порядке, последний элемент через переменную направляется в первый ... Реализация - сложнее и есть несколько вариантов кода выполнения сдвига ...
tmp = A[N-1]
for k in range(N-2,-1,-1):
    A[k+1] = A[k]
A[0] = tmp ...

Решето Эратосфена.

Алгоритм нахождения всех простых чисел до некоторого целого числа n ... Простое число - это натуральное число, имеющее ровно два различных натуральных делителя ... Другими словами, натуральное число p является простым, если оно отлично от 1 и делится без остатка только на 1 и на само p ... Последовательность простых чисел начинается : 2, 3, 5, 7, 11, 13, 17, 19, 23 и т.д. ...
A = [True]*N # массив из логических значений ...
A[0] = A[1] = False # эти числа изначально не входят в последовательность простых ...
for k in range (2, N):
    if A[k]: # если A[k]==True ... По логике алгебры изначально предполагается x=1 или x==True, и ещё одно ==True - является избыточным, поэтому и такая короткая запись на проверку соответствия ...
        for m in range (2*k, N, k):
            A[m]=False
for k in range (N):
    print(k, '-', "простое" if A[k] else "составное") # тернарный оператор условия выбора ветвления печати ... if и else разделяют левый и правый операнды действия в зависимости от условия между ними ...

Методы списка. Включения.

... #6. Методы списка. Включения и сортировка.

... В языке Python список list - не является массивом, это - объект ... У массива с фиксированным размером нужно самостоятельно отслеживать индекс ...
Если аллоцированный размер массива A[0]*Nmax, то реально индекс n=0, то есть, уже список list - сам отслеживает индекс элементов ...

Можно объявить A[] условно пустой массив и не использовать переменную отслеживания индекса ...
A.append(x) - это метод само модификации объекта list, в частности - добавление нового элемента в конец ... Аппендить можно - сколько угодно и его размер - не должен закончиться (в пределах разумного ; техническая реализация процесса - не рассматривается в рамках этой лекции) ...
Узнать количество хранимых элементов n = len(A) используя оператор len ... Его даже не нужно присваивать переменной, тупо указывая for k in range(len(A)): ...
A.pop(x) - возвращает последние элемент, удаляя его и уменьшает len(A) - на единицу ...

List Comprehension - упрощение создания / генерации списков ...

A = [x**2 for x in range(10)] ... переменная x - не существует ни до, ни после создания массива - это временная переменная на время создания списка ...
Эта запись эквивалентна конструкции ... Механизм короткой записи, да ещё и работает быстрее ниже приведённого кода ...
A[]
for x in range(10):
    A.append(x**2)

Цикл for - также, списочного характера ...
A = [1,2,3,4,5]
for x in A: # как for знает, где - остановиться ? ... Оказывается A[] помнит len(A) и знает - какой он длины ...

В конец массива вставить элемент - легко, а в начало - требуется сдвиг всех элементов ...

Возвести четные элементы массива в квадрат ...
A = [1,2,3,4,5,7,12,9,6]
B = []
for x in A:
    if x%2==0 # если элемент - четный ...
        B.append(x**2)
Этот код можно записать одной строкой ...
B = [x**2 for x in A if x%2==0] # отсеивать / фильтровать элементы по if - уже встроено List Comprehension в цикл for ... Коротко ... Ясно ... Читабельно ... Шоколадно ... Иногда, сюда же удобно вставить тернарный оператор if else по условию ...
Например, B = [(0 if x < 0 else x**2) for x in A if x%2==0] # в этом случае, тернарный оператор - пишется в скобках ...

Сортировки.

Квадратичные сортировки.

Операции сортировки массива требуют N**2 в квадрате - больше вычислений, нежели другие операции, при N длине массива ... Сравнение массивов - дело затратное по времени ...
insert_sort - сортировка вставками ... По возрастанию и убыванию ... Методом сравнения от первого по порядку ...
choice_sort - сортировка выбором ... Методом поиска минимума и обмена значениями ... Упорядоченные элементы - считаются окончательными и повторно - не проверяются ... Последний элемент сортировать - не надо, он является автоматически отсортированным ...
bubble_sort - методом пузырька ... Сортировка обменом - двух соседних элементов ; больший элемент - всплывает, как - пузырек ...
Эти функции используют ключевые слова top, pos, bypass оператора range ...

print ("Ok" if A==x else "NoOk") # подстановка условия прямо в оператор печати ... Встроенный тернарный оператор ...

A[0]*10 - это операция повторения ... то же самое, что [0] + [0] + [0] + ... + [0] ... Это означает, что списки в Python - можно конкатенировать ... A = B + C создаст новый объект = склеенный список ... Операция + порождает новый объект ...

A = list(range(10,20)) # range - это геометрическая прогрессия, а команда list создаст из неё - список ... Как только A будет присвоено новое значение - старый список без ссылки съест сборщик мусора ... Можно продолжить и конкатенировать один список - с другим
A = list(range(10,20)) + list(range(0,10))

print("фраза", имя_функции.__doc__) # при печати подставит к фразе - строку документации из вызываемой функции (через точку, два подчёркивания до и после) ...

while k>0 and A[k-1]>A[k]: # В Питон, логическое И, является - ленивым, то есть, вторая часть условия - не будет выполнена, если не выполнилась первая часть ... Отчасти - это помогает не вылезти за границы массива, что может быть - крайне критично ...

Сортировки подсчётом.

Однопроходный алгоритм не запоминает числа в памяти, используя счётчик count_sort ... Частотный анализ является частью алгоритма сортировки ...

Рекурсия.

... #7. Рекурсия.

... Простейший пример рекурсии - сказка про Репку ... Задача - решается вызовом подзадач ... Особенность рекурсии : подзадача - проще основной задачи (ближе к крайнему / конечному случаю, кроме предыдущих - рекуррентных) ... Функция не должна вызывать сама себя - до переполнения стека ...

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

Рисование фрактала квадратов.

import graphics as gr # импорт графики как объекта ...
window = gr.GraphWin("заголовок", 600, 600) # назначение объекта графики - окну, с названием и размерами ...
alpha = 0.2 # глобальная константа сдвига вложенных квадратов ...
Создание функции с глубиной, например = 10 ...
def fractal_rectangle(A, B, C, D, deep=10): # ABCD это кортеж параметров ...
    if deep<1:
        return # этот оператор не требует else, так как сам прерывает исполнение вычислений ...
    gr.Line(gr.Point(*A), gr,Point(*B)).draw(window) # звёздочка * это синтаксический сахар, само разворачивающий и подставляющий значения параметров) ... параметры не сохраняются в памяти, так как сразу отрисовываются в окне ... Каждому параметру соответствует два значения координат, по которым рисуется линия - из начала в конец ...

Линия рисуется из точки A в B ; из B в C и так далее ...
Чтобы не перебирать все параметры по очереди - используется оригинальное подставление через временные переменные цикла M, N ... Очень удобно пробежать двумя переменными по списку кортежей ...
Тогда, явный код рисования линии gr.Line(gr.Point(*A), gr.Point(*B)) будет заменён подстановкой M, N ...
for M, N in (A, B), (B, C), (C, D), (D, A):
    gr.Line(gr.Point(*M), gr,Point(*N)).draw(window) # и сразу рисовать линию на экране ...
alpha - сдвиг A0A1x наклона вложенного квадрата по оси AB ... Тогда A1xB0 = 1-alpha (то есть, всё оставшееся, за вычетом длины сдвига alpha) ...
Тогда, A1x = (1-alpha)*Ax+alpha*Bx ... То есть, по оси x точка вложенного квадрата A1 сдвинута от A на расстояние alpha, в то время как, хотя точка B1x - совпадает с BC, но сдвинута от B на длину alpha в сторону C, но уже по оси y ...
    A1 = (A[0]*(1-alpha) + B[0]*alpha, A[1]*(1-alpha) + B[1]*alpha) # расчёт координат x, y ...
    B1 = (B[0]*(1-alpha) + C[0]*alpha, B[1]*(1-alpha) + C[1]*alpha)
    C1 = (C[0]*(1-alpha) + D[0]*alpha, C[1]*(1-alpha) + D[1]*alpha)
    D1 = (D[0]*(1-alpha) + A[0]*alpha, D[1]*(1-alpha) + A[1]*alpha)
    fractal_rectangle(A1, B1, C1, D1, deep-1) # рекурсивный вызов функцией самой себя, с глубиной =-1, то есть - для вложенного со сдвигом квадрата и новыми координатами - внутри цикла ...
fractal_rectangle((100, 100), (500, 100), (500, 500), (100, 500), 100) # явный вызов функции, с указанием начальных координат и глубиной 100 вложений ...

Факториал.

Факториал ... n! = (n-1)!*n ... f(n) = {1, n<=1 ; f(n)*n, n>1} ...
def f(n):
    assert n>=0, "Факториал не определён" # оператор проверки условия ...
    if n==0: # проверка крайнего случая ...
        return 1
    return f(n-1)*n # вход - прямой ход рекурсии (расчёты до передачи управления) ; выход - обратный (на котором, также - могут выполняться определённые действия) ...

Алгоритм Евклида.

Поиск наибольшего общего делителя a, b, где a > b ... Вычитанием (a-b, b) ... Иная логика, остаток деления по модулю (b, a%b) ... def gcd(a, b): ... return a if b==0 else gcd(b, a%b) ... Красивый, функциональный и читабельный стиль ...

Быстрое возведение в степень.

a^n=a*a*a, n раз ... a^n=a^n-1*a ...
если n - чётное, тогда a^n = (a**n)^n//2 ... Умножение, пропорциональное количеству множителей - заменяется на логарифмическое, с огромным приростом в скорости вычисления ...

Ханойские башни, задачка / головоломка.

Переложить все кольца, с первого стержня k - на второй j, по одному, не допуская, чтобы больший диаметр n - лежал на меньшем n-1 ... Третьим стержнем tmp можно пользоваться, как - временным хранилищем ...
Зная, что стержни : 1, 2, 3 ... k + i + tmp = 6 ... Можно вычислить tmp - текущий временный столбец ... tmp = 6 - k - i ...

Рекурсия. Сортировки.

... #8. Рекурсия. Боевая мощь.

Генерация всех перестановок

Комбинаторика расстановки n чисел ... n! факториал различных перестановок ... Решение задачи при помощи рекурсии ...

Упрощенно, от 0 до n-1 ... для n любых чисел, в m позициях, prefix=none, пустой список (false) - то есть генерация начинается с ничто (ещё нет никакого числа - вначале) ...
В Python используется ленивое вычисление, то есть, если первый оператор сравнения = false, то второй - даже не вычисляется ...
for digit in range (n): ... prefix.append(digit) # добавить число в префикс, их останется на -1 меньше ... вызвать рекурсивную функцию (n, m-1, prefix) ... prefix.pop() # удалить значение из префикса, очистить его для следующего ввода ... Рекуррентый вызов в цикле ... Классно, с точки зрения дедуктивного разбора, перебора всех данных ...
В Python можно создавать пустые списки / пустой массив ... prefix = prefix or [] ... print(*prefix) - внедрит все префиксы в ответ ...

Рекуррентные сортировки

Сортировка Тони Хоара ... На средней выборке W(n*log2n) ... Не всегда работает хорошо, может сортировать - до O(n^2) ... Сортировка на прямом ходе рекурсии ... Без дополнительной памяти ... Сортировка по барьеру на три массива с досортировкой ...

Сортировка слиянием ... На любых данных O(n*log2n) ... Сортировка на обратном ходе рекурсии ... Требует дополнительной памяти O(n) по количеству сортируемых элементов, что сравнительно - хуже ... Сортировка пополам, с поэлементным сравнением индексов в новый массив и дополнением результата остатком...

... #9. Алгоритмы сортировки.

... Сортировка слиянием ... Слияние отсортированных массивов ...
A:list - переменная список ...
len(A) - длина массива
C = [0] * (len(A) + len(B)) - список, заполненный нулями, длинной как объекты A+B ...
while i < len(A) and k < len(B) : # пока индексы меньше длины массивов ...
if A[i] < B[k] # если значение по индексу i в списке A - меньше B по k ...
список начинается с -1, индекс начинается с 0, переполнение / выход за границы массива, индекс = его полная длина ...
символ ; следующее выражение в строке ... пользоваться им - не надо ... это - нехорошо, с точки зрения стиля ...
Устойчивость сортировки ... Сортировка называется устойчивой, если она - не меняет порядок равных элементов ... Не все элементы абсолютно одинаковы, если равны друг другу ... Разные комплексные числа по модулю могут быть равны друг другу ...
return C - возвращает отсортированный массив ...

Рекурсивная функция сортировки слиянием.

Функция def merge_sort(A):
Рекурсия начинается с крайнего случая ... if len(A) <= 1 # если массив из одного или менее чисел - return ...
Если в return ничего не случилось - автоматически else ...
middle = len(A) // 2 # делит массив пополам ...
Удобный способ извлечь две половинки массива - использовать срезы, но их вводить - пока рано ...
List Comprehension - абстракция списков или списковое включение - это способ компактного описания операций обработки списков ...
L = [A[i] for i in range (0, middle)] # левая половина - в диапазоне от 0 до середины, не включительно ... двойные квадратные скобки - создание массива по массиву ...
R = [A[i] for i in range (middle, len(A)] # правая половина
merge_sort(L) ... merge_sort(R) ... вызов самой себя функции - поделит и сортирует половинки ...
С = merge (L,R) # два массива сливаются в третий ...
Нельзя явно указать A = C, так как это будет не копирование, а - смена ссылки ; а так как все временные объекты - ссылочные, то по окончании переназначения, они все - будут уничтожены, включая C и A ...
Сработает - цикл поиндексного копирования (то, что в будущем - будут делать срезы) ...
for i in range(len(A)):
    A[i] = C[i]

Сортировка Тони Хоара (QuickSort).

def hoar_sort(A):
сначала - крайний случай рекуррентной функции ... if len(A) <= 1: ... вернуть пустой return - то же самое, что и return None ... Специальный тип None - ничто, ничего - тоже может быть значением ... Значения - легко модифицировать или уничтожить, а имена существуют - пока существует контент кода программы ...
Стандартный способ расширять массив - аппендить в него новые элементы ...
Случайный делитель массива пополам - для создания, сравнением от него - L меньшего, M среднего и R большего подмассивов ...
Складывая подмассивы - нельзя написать L = M = R = [] ... Ссылочная модель Python - все ссылки ведут на один объект ... Нужно вычислить выражение чтобы получить новый объект ...
L = [] ; M = [] ; R = []
barrier = A[0] - случайный делитель, барьерный элемент ...
for x in A: - для перебора всех элементов A, но их индексы, сейчас - не важны ...
     if x < barrier :
         L.append(x)
     elif x==barrier :
         M.append(x)
     else: # ни в коем случае не писать никаких условий для else, это и так - подразумевается ...
         R.append(x)
Эта реализация проще, но она потребляет больше памяти ...
Сортировки списков рекурсивным вызовом функции ...
hoar_sort(L)
hoar_sort(R)
k = 0 # ввести и установить произвольный счётчик копирования ...
Списки можно конкатенировать друг с другом, чтобы не писать код - длинно ... Это - не совсем слияние, более - перекладывание ...
for x in L+M+R:
     A[k] = x ; k+=1 # переложить все значения из объединённого объекта LMR в список A, начиная с первого A[0] ...

Проверка массива на сортировку ...
def check_sorted(A, ascending=True)
True - сортировка по возрастанию, False - по убыванию ...
     """ Проверка отсортированности за O(len(A)) """
flag = True
Как только первая пара значений не совпала с условием - не сортировано, выход ...
ascending - легко превратить в единичку, представив его, как - число ... int(True) - по логике, это =1 ... Соответственно, int(False) = 0 ... Чтобы автоматически переворачивать знак при сортировке (*1 возрастание ; *-1 убывание) - нужно придумать маленькую математическую функцию, которая поможет переворачивать знак ... Фишка s = 2 * int(ascending) -1 ... флаг проверки массива ...
for i in range(0, N-1) # не включительно, чтобы не выйти за границу массива ...
     if s*A[i] > s*A[i+1]:
        flag=False # обнаружена ошибка условия
        break # принудительное прерывание и выход ...
     return flag

Бинарный поиск в массиве.

Если принять и руководствоваться логикой, что левый указатель - на -1 меньше искомого в списке числа, а правый - на +1 больше, то искомый элемент всегда будет между указателями, отстоящими на - не более величины индексов, обрамляющих массив с обеих сторон ...

... #10. Динамическое программирование.

... Реализация бинарного поиска в массиве - доделки с прошлого урока ...
Важное требование для бинарного поиска, массив - должен быть отсортирован ...
В случае, для одинаковых элементов в последовательности - правую границу - приближают к левой, до минимума ... Левая и правая границы - вычисляются раздельно ...
Функция def left_bound(A, key): ...
инициализировать указатели left = -1 ; right = len(A) ...
Запускается условие, пока while right - left > 1: ...
Узнать середина middle = (left + right) // 2 # разделить нацело ...
Если число списка по индексу if A[middle] < key: , то происходит отбрасывание и left = middle, а else: иначе right = middle ... Но, кто-то, из них - обязательно приблизится ... Либо - тот, либо - другой ...
По хорошему, реальный поиск - должен сводиться к двум операциям ... Линейный поиск, в этом случае, будет производить тупой последовательный перебор всех элементов - в поисках границ ...
Установщику границ - нет дела до реального искомого числа - есть, оно, или - нет ... Этим будет заниматься обёртка - другая функция, которая будет пользоваться границами для поиска или проверки - реального числа ...
Для поиска правой границы достаточно изменить строку if A[middle] >= key:

Динамическое программирование.

Вычисление числа Фибоначчи.

def fib(n):
    if n <= 1: # крайний случай ...
        return n ...
    return(fib(n-1)+
    fib(n-2)) # плюс и скобки - для организации переноса длинной строки ...
Структура прямых вызовов и обратных ответов решений с повторным перевычислением отдельных, уже вычисленных ранее ветвей (узлов), называется Фибоначчиевым деревом ... Логика вычисления O(fib(n)), а число Фибоначчи растет экспоненциально - это запредельная асимптотика ... Вычисления идут очень долго ... Вычислить 60 число Фибоначчи на бумажке - будет быстрее, чем это сделает компьютер на быстродействующем C++ ...
Так писать - нельзя ... Это можно сделать - тривиальнее, без функций и рекурсий ...
fib = [0,1]+[0]*(n-1) # ввести данные, с начального крайнего случая, как в табличке и зарезервировать память нулями до n-1 ...
for i in range(2,n+1): # в табличном списке, всего, от 0 до n = n+1 элемент ...
    fib[i]=fib[i-1]+fib[i-2]
Динамическое программирование, в этом примере, это - рекурсия, вывернутая наизнанку ... В некоторых рекурсиях, динамическое программирование - не может быть организовано (например, генерация всех перестановок) ...

Другие примеры динамического программирования.

Задача кузнечик из ЕГЭ по информатике ...
Кузнечик умеет прыгать по меткам на числовой прямой ... Только - вперед, +1 или +2 шага вперёд ... Сколько различных траекторий допрыгать из 1 в n ...
Рассуждать, удобнее - используя рекурсию ... Попасть в клетку n можно только из n-1 или n-2 ... Других способов, методов или вариантов - нет ... Здесь - рассматривается, какой может быть последний прыжок ... Все возможные траектории достичь n - делятся на два типа : прыжком +2 или +1 ...
Количество траекторий, ведущих к n - равно одному из прыжков ... Типы можно просуммировать по комбинаторике Kn = Kn-2 + Kn-1 ... Получилась - рекуррентная формула ... Число траекторий равно числу Фибоначчи ...
Можно изменить логику, используя запрещённые клетки для посещения ... Количество разрешенных прыжков - увеличить до +3 ...
Вопрос интерфейса ... Как передать внутрь функции количество траекторий с запрещёнными клетками ... Через множество ... Через массив логических булевых, как allowed - лист разрешённых значений ... При этом, подставлять неизвестные значения через оцифрованный allowed по индексу в списке ... Первые допустимые от 0 +1 +2 +3 ... Список запрещённых точек - даже не надо указывать заранее - его примет функция при вызове ...
K = [0, 1, int(allowed[2]+[None]*(n-3) # остальные ячейки пока заполнить пустыми значениями, просто инициализировав - выделив и заняв память ... Заполнить None и умножить на n-3 потому-что первые три элемента из всей n последовательности - уже заданы вначале ...
Если на клетку можно наступать ... if allowed [i]: # ни в коем случае не писать в условии для булевых - равно True ... K[i] = K[i-1] + K[i-2] + K[i-3] ... Идеальная асимптотика ...

Допрыгать за минимальную стоимость посещения клетки ... Прайс стоимости точки функция принимает списком ... Посещение точки имеет разную цену и нужно высчитать траекторию с минимальной стоимостью ...
Нулевая клетка - недостижима (прыгать с 1 только вперед) ; её стоимость - бесконечность float("-inf") ...
Цена C1=price1 (стоять на месте) ... C2=price1+ price2, потому-что, попав одним переходом из 1 в 2 - нужно включить стоимости посещения обоих точек ...
C = [float("-inf"), price[1], price[1]+price[2] + [0] * (n-2)] # ... Заполнить нулями и умножить на n-2 потому-что первые два элемента из всей n последовательности - уже заданы вначале ...
for i in range(3,n+1) # цикл для всех элементов, начиная с третьего - до n включительно (обозначается, как n+1) ...
C[i] = price[i] + min(C[i-1], C[i-2])

Двумерное динамическое программирование.

Двумерное динамическое программирование, достаточно - тривиальное ... Первый раз, когда сталкиваемся с двумерными массивами ... Примеры других приложений академического программирования - в следующий раз ... Там будут и другие ценные алгоритмы ... Будьте аккуратны, если вы пропустите следующую лекцию - вам будет очень тяжело ...

На самом деле, никаких двумерных массивов в Питоне - нету ... Список list - невозможно сделать двумерным ... Какие есть варианты ? ...
Вариант 1 : линеаризация массива Aij (N строк, M элементов в строке) - это A[i*M+j] ... Требование : фиксированное количество элементов по ширине ...
Вариант 2 : список списков ...
Неправильное использование ... A = [[0]+M]*N # где, 0 - ссылка на список из 0 в количестве M, построчное копирование ссылок на один и тот же список N раз ... Каждая строка - суть одна и та же первая строка ... Двумерный массив так создавать - нельзя ...
Правильное использование - генерация списка, через вычисляемое выражение, именно которое и создает новый объект ... Цикл генератор вычисляет выражение - столько раз, сколько - сказано ...
A = [[0]*M for i in range (N)] ...
Теоретически, A[0] == A[1], так как они заполнены нулями, по умолчанию, при создании ...
Фактически, команда сравнения A[0] is A[1] = not is, то есть, сравнивается - не содержимое ячеек, а ссылки (ведут ли они к одному объекту или к разным ? ... В этом случае - к разным, поэтому - не равны ...

... #11. Двумерное динамическое программирование.

... Задачка про шахматного короля, который живет на доске M * N клеток ... Требуется узнать, сколькими способами король может добраться из верхней левой (1, 1) до нижней правой (M, N) клетки, если ему разрешено шагать - только вправо и вниз ... Сначала - нужно построить рекуррентую задачу ...
Knm, количество траекторий, где n - номер строки, m - номер элемента в строке ... Это - легче и лучше, чем идентифицировать положение по столбцам ... Так как, двумерный массив выглядит, как - список строк, массив массивов, и столбцов в нём - нет ... Столбец - это множество различных элементов из разных массивов ... Поэтому - так и нужно указывать : n строка m элемент в строке ... Knm - количество способов достичь клетки (N, M) ...
Вертикальная ось N, будет i ...
Горизонтальная ось M, будет j ...
В некую клетку (i, j) можно попасть либо - слева ; либо - сверху ... То, есть - либо из (i, j-1) ; либо из (i-1, j) ...
Чтобы получить общее количество - нужно сложить все отдельные пути (чей расчёт является делом рекуррентной работы) ... Этот расчёт будет расположен в форме динамического программирования, от начала - к концу ... Как это сделать ? ... K(i,j)=K(i-1)j+Ki(j-1) ... Рекуррентный случай найден ...
Рассмотрим - тривиальный случай : клетки, для которых заранее известно количество способов туда попасть ... Начинается заполнение строк массивов - числами путей переходов ... Из (1,1) вправо по j - только одним способом, до конца ... Как и - вниз, по i ... Поэтому, в этих клетках будут - только единицы ...
На самом деле, стоит держать в уме, что к двумерному программированию можно применить способы расчётов, как в одномерном программировании ...
Здесь, удобно внедрить - дополнительные строку и столбец - с нулевыми значениями ... Суммы - удобно считать - с нуля, с некоего начального барьера ... Как распространить функцию на барьерный нулевой элемент, чтобы получить правильный ответ ? ... Заполнить нулевую границу - нулями, и тогда, все последующие значения элементов могут быть - вычислены : 0+1=1 ... Однако - следует явно декларировать, что в клетку (1, 1) - есть только один явный способ попасть туда (0+0 никогда не даст =1) ... Сюда нельзя записывать значение методом вычисления, иначе вся таблица будет записана - нулями ...
Все следующие суммирования ячеек - выльются в повернутый треугольник Паскаля ... В Китае считается, что изобрёл его другой китайский математик, Ян Хуэй (поэтому китайцы называют этот треугольником - его именем) ...
С логической точки зрения порядка вычислений - они происходят слева направо и сверху - вниз, то есть - два вложенных цикла for() ... Точно как же - можно начать считать сверху - вниз, и затем сдвигаться - вправо ... Это происходит из-за того, что все последующие вычисления могут быть произведены - только от заранее вычисленных и предварительно известных значений ... Область известных значений - последовательно расширяется ... Целевая точка может быть достигнута обоими путями ...
Нельзя не упомянуть и о важной и сложной области параллельного программирования для промышленности и научной среды ... Параллельные потоки вычисления огромных матриц нужны для ускорения расчётов и получения результата ... Матрица 6х6 потребует 252 вызова рекурсии, в то время как параллельные вычисления задействуют всего 36 операций, что, как минимум - в 7 раз быстрее ... А, если матрица - миллион на миллион ? ... Однако, в этом курсе, параллельное программирование - не рассматривается ...

Следующая задача - наибольшая общая последовательность ...
A, B - одномерные массивы чисел, где len(A)==N, len(B)==M ... Какая наибольшая подпоследовательность у них возможна ...
Подпоследовательность, это - некий массив C, который содержит элементы A в исходном порядке, но возможно - не все из них ... Пустой [] это подпоследовательность любой последовательности ...
Задача будет упрощена, если удастся найти красивую функцию, которую будет легко посчитать ... Например - длину наибольшей возможной подпоследовательности, и сразу параметризовать ее, как Fij ... или частей A и B, до индексов i и j ...
A[0:i] не включая i, часть A, первые i элементы ...
B[0:j] не включая j, часть B, первые j элементы ...
Задача имеет два варианта решений (в фигурной скобке) по условию ...
Fij = 1+F(i-1)(j-1) , Ai=Bj , когда участки вычислены и конечные элементы равны ... Для участков - неважно, прибавь хоть +Ai , хоть +Bj - неважно, так как они всё равно равны, то - прибавь один любой - даст верный ответ, то есть 1+F(i-1)(j-1) ...
Fij = max(Fi(j-1),F(i-1)j) , Ai != Bj , когда участки вычислены и конечные элементы не равны, тогда берётся участок с максимальной длиной последовательности ...
Крайний случай ... Нулевой ряд ... []=0 ... F0j=0 ... F0i=0 ... В отличии от предыдущей задачи, ячейка (1,1) - будет вычисляться ...

Код функции решения задачи ...
def lcs(A,B):
резервирование памяти ... генератором ... На единицу больше длины, чтобы включить нулевую строчку и столбец ...
F = [[0]*(len(B)+1) for i in range(len(A)+1)]
Нулевые границы (все крайние случаи) - уже посчитаны ... Начиная с 1-го элемента первой строки - внешний цикл будет бежать по i , а внутренний - по j ... +1 включительно ...
for i in range(1, len(A)+1):
вложенный цикл ...
for j in range(1, len(B)+1):
if A[i-1]==B[j-1]:
F[i][j]=1+F[i-1][j-1]
else:
F[i][j] = max(F[i-1][j],F[i][j-1])
return F[-1][-1] ... Секрет списков Python ... В Питоне списки знают свои порядковые номера и зациклены в круговой последовательности отсчётов, то есть, перед первым элементом - идёт последний, с конца ... Вместо того, чтобы писать F[len(A)-1][len(B)-1] проще указать F[-1][-1] то есть : минус первый элемент = последний ...

Вывод ... Иногда, алгоритм - очень трудно прочитать ... Нужно знать алгоритм, чтобы понять, для чего введены - те или иные элементы ... А сама, реализация - простые вложенные циклы ...

Альтернатива решения ... Сравнивать всевозможные подпоследовательности A с подпоследовательностями B ... Полнопереборный метод 2 ^ N на 2 ^ M ... Вариант восстановления последовательности - идти с конца, добавлять и переворачивать результат - наоборот ...

Задача : наибольшая возрастающая подпоследовательность, НВП ...
примечание : ищется общая длина, а не значения элементов ...
Fi - это НВП для части A[0:i], которая заканчивается на и содержит ai = A[i-1] ... Где, ai - это номер элемента в последовательности, а A[i-1] - это его номер по индексу ... При этом, часть A[0:i] - это ни что иное, как - срез ...
Fi = max(Fj) + 1 ... где j < i от нуля до i не включительно ... ai > aj, иначе последовательность - не возрастающая ... теоретически, в условии - могут быть разные варианты ... рассматривается строго возрастающая последовательность ... Поиск максимума - это цикл, значит получается цикл в цикле ...
Крайний случай F0 = 0 ... если все ai < aj, то последовательность равна пустой нулевой + этот единственный элемент aj ...

Реализация ...
def gis(A):
одномерная последовательность ...
F = [0]*(len(A)+1)
for i in range (1, len(A)+1):
указать текущий максимум, m ...
m = 0
обзор - по номерам элементов, второй цикл - по индексам ...
for j in range (0, i):
if A[i-1]>A[j-1] and F[j-1]>m:
m = F[j-1]
F[i-1] = m+1
return F[len(A)]

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

Задача : алгоритм укладки рюкзака ... Есть рюкзак, с максимальным весом M, который можно унести ... И есть набор предметов s1, s2, s3 стоимости, с m1, m2, m3 массой ... Вопрос, какую максимальную стоимость предметов можно унести ... Несмотря на всю простоту, эта задача - не решается иным методом, кроме как - полного перебора ... Перебор всех подмножеств, это - лучшее, что можно сделать ... Если вес вещей - дискретный, в кг - задача может быть решена методом динамического программирования ... Алгоритм Левенштейна, редакционных изменений - механизм кратчайших сравнений ...

... #12. Алгоритмы и структуры данных на Python 3.

... Что ждёт глобально - дальше ... Жёсткая и сложная суть алгоритмов программ динамического программирования ... Дольше - понимать суть, чем - программировать ... И, дальше, будет - ещё жёстче ... От этого - никуда не деться ... Но, понимать алгоритмы по книжкам - ещё сложнее ... Алгоритмы - прокачивают мозг, учат думать ... Это - сложно, но надо учить и знать ...

Редакционное расстояние Левенштейна.

Есть строки , A='колокол' , B='молоко' ... Сколько нужно допустить типографических ошибок и опечаток - в первом слове, чтобы получилось - второе ... Что понимать под ошибками ? ...
1) перепутали символ ...
2) вставили лишний символ ...
3) не вставили [потеряли] нужный символ ...
Есть некоторая траектория редакционных правок ... Нужно научиться вычислять минимальное редакционное расстояние ...
Fij это минимальное расстояние правки между кусочками / срезами строк ... A[:i] от 0 до i символа ... B[:j] от 0 до j символа ...
Глобальные рекуррентные случаи ... Важно понимать и разделять : в алгоритме - от первого номера в последовательности ; в коде - от реального индекса по месту хранения ...
Fij = F(i-1)(j-1) , если A[i] == B[j] ... последний символ - один и тот же ...
если A[i] != B[j] - как упростить задачу, свести функцию к меньшим индексам ? ...
* методом вставки недостающего ...
* методом удаления символа ...
* методом замены символа ...
* какая из траекторий - выгоднее, заранее - неизвестно ...
Fij = 1 + min(F(i-1)j, Fi(j-1), F(i-1)(j-1))
Крайний случай ...
F0j = j , F0i = i , F00 = 0 ...

def levenstein(A, B):
список списков ... чтобы не вводить if i==0 and if j==0 - применить хитрость ...
F = [[(i+j) if i*j==0 else 0 for j in range(len(B)+1)] for i in range(len(A)+1]
тернарный оператор (i+j) if i*j==0 else 0 с вычисляемым выражением подставляет либо переднюю, либо - заднюю части ...
for i in range(1, len(A)+1):
for j in range(1, len(B)+1):
if A[i-1]==B[j-1]:
F[i][j] = F[i-1][j-1]
else:
F[i][j] = 1+min(F[i-1][j], F[i][j-1], F[i-1][j-1])
return F[len(A)][len(B)]

Проверка равенства строк.

Есть строки A='строки' B='равны' ... Проверка равенства по длине строк ... Универсальный алгоритм не всегда есть хорошо ...
def equal(A,B):
if len(A) != len(B):
return False
если длины равны - посимвольное сравнение строк ...
for i in range(len(A)):
if A[i] != B[i]:
return False
return True

Поиск подстроки в строке.

В этом случае строки не обязательно должны иметь одинаковую длину ...
Есть строки S='abacababadabacabaf' и Sub='dabac' образец ... Сама строка может иметь некоторую структуру, которая усложняет поиск ... Есть случаи, когда наивный поиск по строке - работает идеально ... Наивный поиск по строке тупо сравнивает образец по строке со смещением на символ ... Все вхождения ...
def search_substring(S, Sub):
for i in range(0,len(S)-len(Sub)):
Придётся сознаться, что в Питоне есть срезы, автоматически вычисляемые от сих до сих ... Это создание новой строки, копирование, затребование памяти и хуже, чем цикл for ... Прямое посимвольное сравнение A==B затрачивает много ресурсов и времени ... Будьте аккуратны ... В Python есть мощные возможности, которые приводят к плохо предсказуемым результатам ... Всегда следует думать и понимать, какой асимптотикой (сложностью) придётся за это заплатить ...
if equal(S[i:i+len(Sub)],Sub):
print(i)

Чтобы не погрязнуть во времени и скорости вычислений - существуют две функции позволяющие пред / обработать строку ... Для этого изучается структура самой строки ...
Префикс функция Пи от строки ...
Собственный суффикс - суффикс, не равный самой строке ...
Пs - длина максимального собственного суффикса, который является префиксом ...
Пsi - префикс функция среза S[:i] ...
Если срез (префикс равный суффиксу), от 1 до p и следующий символ x ...
Sp+1=x, то Пsi=p+1, где p = Пsi-1 , то есть Пи функции предыдущей строки ...
Но, не всегда Sp+1 == Si конечному символу строки ...
Оказывается, можно идти к наименьшей длине Пи функции ... от Пи функции ... от Пи функции ... Пока последний символ в строке - совпадает Пsi=1 или не совпадает Пsi=0 ...
П = [0 для всех i] ...
для всех i строки s:
p = Пsi-1
пока p > 0 и Si != Sp+1
p = Пsp
если Si = Sp+1, то p += 1 ...
Пi = p ...

Алгоритм Кнута Морриса Пратта, КМП-алгоритм.

Какое отношение префикс функция имеет к поиску подстроки в строке ? ... Быстрое вычисление со скоростью O(N) ...

В алгоритме КМП новая строка s* = Sub + '#' + S состоит их префикса (образца) и самой строки ... Где '#' это спец символ разделитель, не используемый - ни в строке, ни в подстроке ... Используя префикс Sub - искать Пi функцию ...
Когда Пi функция == len(sub) - искомое вхождение найдено, со скоростью поиска Пи функции ... Индекс вхождения будет равен Пi за вычетом длины подстроки ... Скорость вычисления O(N+M) это - не то же самое, что O(N*M) ...
Префикс функция - фундаментальная, она позволяет узнать структуру строки ... Z функция - ещё проще ...

Структуры данных.

... #13. Алгоритмы и структуры данных на Python 3.

... Переменные ... Списки ... Массивы ... Но, оказывается, есть много разных структур данных ... Можно организовать собственную структуру данных при помощи ссылок ... В Python - прекрасная ссылочная модель ... При помощи ссылок (в других языках - при помощи указателей) можно создать особенные специфические структуры данных ...

Стек или очередь LIFO.

Нормальная очередь : первый пришел - первый вышел ...
Стек : последний пришел / push - первый вышел / pop ... Также нужен size / размер, количество (пуст ли стек / is_empty) и top / верхний элемент ...

Правильный путь к разработке структурных данных - методом структурного программирования ...
push не имеет return, просто запихивая элементы в стек ...
use case - случай использования, минимальная документация процедурных директив ...
Реализации ... A_stack : на массиве из списка list ... B_stack : на односвязном списке будет изучен позже ...
документ строка к модулю (что делает, как использовать) ...
""" Модуль, описывающий структуру данных стек ...
clear()
push()
is_empty()
pop()
"""

_stack = [] ... должен жить глобально, вне функции ... функция - только пользует стек ...
def push(x) :
_stack.append(x) ... функция обёртка, которая знает куда положить (x) ...

def pop() :
x=_stack.pop() ...
return x

def clear()
_stack.clear() ...

def is_empty()
return len(_stack) == 0 ...

Функции обёртки сужают большие возможности списков для конкретизации операций ...
функция тестирования, на основе стандартной библиотеки ...
if __name__ == "__main__":
import doctest
doctest.testmod()
doctest делает молчаливое тестирование, пока всё в коде - исправно ... В Питоне есть встроенная поддержка тестирования ...
doctest.testmod(verbose=True) ... запускает громкое тестирование со всеми пошаговыми отчетами ...

Проверка корректности скобочной последовательности.

Открывающие скобки должны быть парные - закрывающим ... Это можно реализовать на простом счётчике, с проверкой на 0 и выход в минус ...
Скобки разных типов, а также уровень их вложенности простой счётчик - не осилит ... Контроль реализуется - через стек ...
импортируется модуль A_stack ...
import A_stack ...
функция проверки скобок с типом - строка ...
def braces(s:str):
for brace in s:
проверка на скобки и игнорирование других символов через строку проверки ... здесь используется стандартная функция поиска строки в подстроке, только она работает гораздо хуже, чем та, которая была изучена при программировании алгоритмов ... но, в простых случаях, этот поиск - работает хорошо ...
if brace not in "()[]":
continue ...
if brace in "([":
A_stack.push(brace)
else:
проверяем ожидание - утверждением ... на всякий случай сделать стрингофикацию типизации в строку ... если утверждение не истинно - сработает конструкция после запятой ... Это - говорящий комментарий, отслеживающий нетипичные случаи ...
assert brace in ")]", "Ожидалась закрывающая скобка: " + str(brace) ...
проверка, что стек - не пуст ...
if A_stack.is_empty():
return False ...
подтверждение приёма открывающей скобки из стека ...
assert left in "([", "Ожидалась открывающая скобка: " + str(brace) ...
if left == "(":
right == ")"
elif left =="[":
right == "]"
if right != brace:
return False
Так как следующий оператор итак логический - нет смысла расписывать коды возврата в три строки, достаточно лишь указать ...
return A_stack.is_empty() ...

Обратная польская нотация (запись), ОПН.

ОПН это алгоритм вычисления арифметических выражений в постфиксной нотации ... Арифметические выражения можно записать так, что скобки - не нужны ...
[5, 2, '+'] <==> 5+2 ... равносильно ...
[2, 7, +, 5, *] <==> (2+7)*5 ...
[2,7,5,*,+] <==> 2+7*5 ...

Как читать польскую нотацию ? ...
Токены - это части арифметического выражения в квадратных скобках ...
Для каждого токена ... Если токен - число - положить в стек ... Иначе, токен - операция ... Тогда : достать из стека y = pop(), x = pop() и выполнить Z = x операция y ... push(Z) - положить вычисленное значение обратно в стек ...
В результате, в стеке должно остаться одно число - ответ ...
result pop() ...
* примечание ... достать из стека y, x ... из-за порядка работы со стеком, в вычисляемом выражении : y - второе число ... x - первое ...

Структура данных, тип list, список.

... #14. Тип list.

... Что такое тип list ? ... Это - не массив, list это - список ссылок ... Можно создать список ссылок на произвольные объекты ...

Например, A = [x, y, z] - не означает, что x, y, z - это однотипные переменные ... Понятия переменной в Питоне в чисто виде - нет ... Есть - имена и есть - объекты ... Объект существует, пока у него есть имя и на него ведёт ссылка ... Иначе - его съедает сборщик мусора ...

Например, A = [True, 2, 5.3, "Hello"] ... Не стоит удивляться, что у переменной x в цикле - будет разный тип на разных итерациях ...
for x in A:
print(type(x)) ... Логический Bool ... Int число ... Float с плавающей запятой ... Str строка ...

В список можно подгружать не только другой список, но и кортеж ... Кортеж - это замороженный список, делает то же самое что и list, включая ссылки на другой список ...
B = (True, 2, 5.3, A) ... Обратите внимание кортеж указан в круглых скобках, в отличии от массива / строки с квадратными скобками ... Имя B - указывает на неизменяемые объекты кортежа, где хранятся 3 ссылки и ссылка на изменяемый объект A ... Кто сказал, что True или 2 - это разные объекты ? ... Нельзя изменить объекты, но можно изменить ссылку на объекты ... Имя - можно начать ссылаться на другой объект другого типа, но сам объект - не может изменить свой тип в процессе своей жизнедеятельности ... Для неизменяемых типов, он - не только тип, но и своё содержимое, изменить - не может ...
Если спросить type(B) ответ будет #tuple ... В Питоне все типы - это классы, даже функция - это тоже - объект класса ... Вполне возможно, что True или 2 - это просто другая ссылка на один и тот же объект ... Python может втайне от вас экономить на создаваемых объектах ...
Если изменить A[0] = False, то неизменяемый B ссылаемый на A[0] - может измениться ... Лучше - быть аккуратнее и кортежи помещать внутрь списков ...

Пройти по списку кортежей точек ... A = [(1,5), (-3,4), (7,2), (8,3), (0,0)] ...
Можно кортежем переменных бежать по списку кортежей ... Кортеж распаковывается для чтения ...
for x,y in A:
print(x,y)

В некоторых ситуациях скобки для кортежей можно не писать - Питон догадывается ...
Можно и наоборот ... x = y = z = 0 ... транзитивное множественное каскадное присваивание ...

За что можно любить язык Python, так это - за работу со строками ... Не дай вам Бог на чистом C работать со строками ... В Питоне работа со строками, это - сказка ...
Создав в интерпретаторе строку s="Hello" ...
далее ввести s. с точкой и подождать - интерпретатор вывалит меню со всеми методами строки - что он умеет ...
""" """ многострочная строка - для документации, для временного сокрытия кода вместо построчного значка # и для многострочных строк с переводом каретки ... Литерал """ - способ представления вывода ... print(s) - напечатает эту строку с переводами каретки, а просто s - в одну строку с символами \n переноса строки ...

s.replace - не может изменить содержимое объекта строки, тогда - зачем он нужен ? ... для того, чтобы изменить содержимое исходной строки - в копируемой ...
s="AAAAAAA"
t=s.replace('AAA','BB')
t="BBBB"

Срезы.

Срезы строк ... Можно выделить часть строки в виде среза ...
функция - почти аналогична range [start : stop : step], двоеточие вместо запятой для указания диапазона ...
s = "Hello"
s1 = s[1:4] не включительно ... stop - недостигаемый индекс ... step - шаг, необязательный параметр равный 1 ...
s[0::2] если нужен срез до конца строки len(s) с шагом 2 - stop можно не указывать ...
s[:] если нужен срез от начала до конца с шагом 1 - можно вообще ничего не указывать, кроме двоеточия ...
s[::-1] если нужен срез в обратном порядке, из конца в начало ...

Модификация строки срезом ...
s = "abcdefgh"
x = s
s = s[::2]+s[::-2]
новый объект s = "aсeghfdb"
старый объект x = "abcdefgh" - не изменится ...

Срезы строк - работают и для списков ... Срез - не изменяет сам объект, но по хорошему его нужно сохранять в новый объект ... Срез строки, это - строка ... Срез списка, это - новый список ...
A = [0, 1 , 2, 3, 4]
B = A[1:4]
B = [1, 2, 3] ... Внимание ! копирование в новый объект может отнимать значительное количество ресурсов памяти и времени ...

Срезы списков создают новый объект - не всегда, а только когда они находятся справа от оператора присваивания ...
A = [0, 1 , 2, 3, 4]
A[0:3] = [10, 20, 30] ... вставка в срез списка - нового списка ...
A = [10, 20, 30, 3, 4] ...
A[0:3] = [0] ...
A = [0, 3, 4] ...
A[0:1] = [] ... пустой список удалит элементы ...
A = [3, 4] ...

Срезы с двумя параметрами никогда не вызывают ошибок ...
A = [0, 1 , 2, 3, 4]
A[1000:2000] ... хотя элементов нет - есть пустой список и получится пустой срез ...
Также, в start / stop можно использовать отрицательные значения ...

Присваивание в срез с тремя пустыми параметрами более трех параметров - вызовет ошибку, так как нужно четко указать, что и куда вставлять ...
Кстати, можно баловаться и класть срез в срез ...
A[::2] = A[::-2] ... Замена крайних значений будет сделана не методом поэлементного присваивания, а через кортеж ... Эта красивая и сложная операция - не является алгоритмически оптимальной и может затребовать много времени и памяти ...

Список чисел ...
s = sum(A) ... суммирование списка чисел ... строки, так - не сконкатенировать, для них используют другой метод ...
m1 = max(A) ... найти максимум ...
m2 = min(A) ... найти минимум ...
reduce() - редуцирование списка или любой итерированной последовательности, арифметической прогрессии - чтобы перемножить все элементы друг на друга или применить исключающее или, например ...

Список строк ...
s = input('ФИО:') ... ввод принимает фамилию имя отчество ...
A = s.split() ... Функция метода строки позволяет выделить подстроки в список ... Использование литералов 'пробел' 'tab' для указания разделителей (кроме специальных символов) - нежелательно, так как автоматически считаются за один - все последовательные одинаковые символы отступа, а специально указанные - могут преобразоваться в строку и нарушить ввод ... Для разделения времени удобно использовать двоеточие ...
A[0] = A[0].upper() ... преобразовать в верхний регистр ...
s = '-'.join(A) ... разделитель соединить список A - заменит пробелы на дефис ...

Heap (куча, пирамида).

Логика кучи - детская игра царь горы ... Выше - тот, кто больше по размеру ... Структура данных, организованная по такому принципу - очень эффективна ... И, на ней - можно организовать даже алгоритм эффективной нерекуррентной сортировки ...
Данные добавляются в двоичное дерево (пирамида), организованное на массиве, в виде списка ...
После вставки, по порядку заполнения, каждый элемент нижнего уровня - пытается спихнуть элемент верхнего уровня - на своё место и занять его более высокую позицию ...
Каждый элемент нижнего уровня - пробует пробиться выше, согласно своему весу ...
Для каждой дочерней ячейки, родительский parent = (i - 1) % 2 ... поделить нацело на два (по модулю два) ... это формулы специфической связи индексов в двоичном дереве ...
Для каждой родительской ячейки, дочерние индексы ... child1 = i * 2 + 1 ... child2 = i * 2 + 2 ...
Если значение забирает метод heap.pop и освобождает ячейку - происходит восходящее заполнение пустот, а освободившееся место в нижнем ряду по горизонтали - занимает самый последний индекс ...
По хорошему, алгоритм работы кучи - надо знать ...

P.S. На этом семестр изучения языка программирования Python - заканчивается ... Полагаю, этот конспект - не научил вас программировать на Питоне, но, по крайней мере - мог стать отправной точкой для более глубокого погружения в мир изучения этого особенного и сложного языка программирования, который все почему-то называют : лёгким и простым ...

Связанные материалы продолжения исследования работы RTL SDR в составе системы радиосвязи компьютерных программ декодирования радио данных ... Windows ПК софт Linux цифровой обработки радио сигналов на Python ...

* Python, Anaconda, Windows, R ...

* Linux GNU Radio Windows ...

* Программы RTL SDR проекты GitHub ...

* Программы RTL SDR проекты SourceForge ...

* Сайт выбрать список спутников ...

* Windows генератор собственного TLE ...

* Декодеры радио телеметрии ...

* Горизонт Linux Live CD ...

* Радиоконструктор GNU Radio ...

* SDR радио из блоков GNU Radio ...

Раздел computer : список всех страниц ...