Содержание
- 2. Алгоритмизация и программирование. Язык Python § 38. Целочисленные алгоритмы
- 3. Решето Эратосфена Эратосфен Киренский (Eratosthenes, Ερατοσθδνη) (ок. 275-194 до н.э.) Новая версия – решето Аткина. 2
- 4. Решето Эратосфена Задача. Вывести все простые числа от 2 до N. Массив (сначала все не вычеркнуты):
- 5. Решето Эратосфена или так: from math import sqrt for k in range(2, int(sqrt(N))+1): if A[k]: #
- 6. Решето Эратосфена Вывод результата: for i in range(2,N+1): if A[i]: print ( i ) или так:
- 7. «Длинные» числа Ключи для шифрования: ≥ 256 битов. Целочисленные типы данных обычно ≤ 64 битов. Длинное
- 8. «Длинные» числа A = 12345678 неудобно вычислять (с младшего разряда!) неэкономное расходование памяти (одна цифра в
- 9. «Длинные» числа Упаковка элементов: 12345678 = 12·10002 + 345·10001 + 678·10000 система счисления с основанием 1000!
- 10. Вычисление факториала Задача 1. Вычислить точно значение факториала 100! = 1·2·3·…·99·100 1·2·3·…·99·100 201 цифра 6 цифр
- 11. Вычисление факториала основание d = 1 000 000 [A] = 12345678901734567 734 567·3 = 2 203
- 12. Вычисление факториала r = 0 for i in range(len(A)): s = A[i]*k + r A[i] =
- 13. Вывод длинного числа A = 1000002000003 вывести старший ненулевой разряд вывести все следующие разряды, добавляя лидирующие
- 14. Квадратный корень Задача. Извлечь квадратный корень из «длинного» целого числа; если это не целое число, найти
- 15. Квадратный корень Метод Герона в целых числах: x = (x + a // x)// 2 x
- 16. Квадратный корень Метод Герона в целых числах: def isqrt(a): x = a # начальное приближение while
- 17. Алгоритмизация и программирование. Язык Python § 39. Структуры
- 18. Зачем нужны структуры? Книги в библиотеках: автор название количество экземпляров … символьные строки целое число Задачa:
- 19. Структуры Структура – это тип данных, который может включать в себя несколько полей – элементов разных
- 20. Работа со структурами B = TBook() Заполнение: B.author = "Пушкин А.С." B.title = "Полтава" B.count =
- 21. Работа со структурами Обработка: B.author = "Пушкин А.С." fam = B.author.split()[0] # фамилия print ( fam
- 22. Массив структур Books = [TBook()]*100 Создание: Books[5].author = "Пушкин А.С." Books[5].title = "Полтава" Books[5].count = 1
- 23. Запись структур в файлы "Пушкин А.С.";"Полтава";12 "Лермонтов М.Ю.";"Мцыри";8 Текстовые файлы: разделитель Двоичные файлы: B = TBook()
- 24. Запись массива структур в файлы pickle.dump ( Books, F ); Сразу все: По одной структуре: for
- 25. Чтение структур из файла F = open ( "books.dat", "rb" ) B = pickle.load ( F
- 26. Чтение структур из файла Books = [] while True: try: B = pickle.load ( F )
- 27. Сортировка структур Ключ – фамилия автора: # B – массив структур TBook N = len(B) for
- 28. Сортировка структур (в стиле Python) def getAuthor ( B ): return B.author Books.sort ( key =
- 29. Алгоритмизация и программирование. Язык Python § 40. Словари
- 30. Что такое словарь? Задача. В файле находится список слов, среди которых есть повторяющиеся. Каждое слово записано
- 31. Алгоритм (псевдокод) создать пустой словарь while есть слова в файле: прочитать очередное слово if слово есть
- 32. Работа со словарями в Python D = {} # пустой словарь Создание: D = { "бегемот":
- 33. Работа со словарями в Python Изменение с проверкой: if "самолёт" in D: D["самолёт"] += 1 else:
- 34. Основной цикл D = {} F = open ( "input.txt" ) while True: word = F.readline().strip()
- 35. Вывод результата allKeys = D.keys() Получить массив всех ключей: sortKeys = sorted(D.keys()) отсортировать ключи: или так:
- 36. Ещё о словарях for i in D.values(): print ( i ) Перебор значений: for k, v
- 37. Словарь и массив пар Массив (список) пар «ключ-значение»: A = list(D.items()) D = {"бам": 2, "там":
- 38. Словарь и массив пар Сортировка: A.sort() по ключам, если ключи равны – по значениям A.sort( key
- 39. Словарь и массив пар Вывод массива пар for x in A: print( x[0], ": ", x[1],
- 40. Алгоритмизация и программирование. Язык Python § 41. Стек, дек, очередь
- 41. Что такое стек? Стек (англ. stack – стопка) – это линейный список, в котором элементы добавляются
- 42. Реверс массива Задача. В файле записаны целые числа. Нужно вывести их в другой файл в обратном
- 43. Использование списка stack = [] Создать стек: stack.append ( x ) «Втолкнуть» x в стек: x
- 44. Инверсия массива неизвестной длины F = open ( "input.txt" ) stack = [] while True: s
- 45. Инверсия массива неизвестной длины F = open ( "output.txt", "w" ) while len(stack) > 0: x
- 46. Вычисление арифметических выражений (5+15)/(4+7-1) инфиксная форма (знак операции между данными) первой стоит последняя операция (вычисляем с
- 47. Вычисление арифметических выражений (5+15)/(4+7-1) 1950-е: постфиксная форма (знак операции после данных) не нужны скобки вычисляем с
- 48. Использование стека 5 15 + 4 7 + 1 - / 5 15 + 4 7
- 49. Вычисление постфиксной формы data = input().split() stack = [] for x in data: if x in
- 50. Скобочные выражения Задача. Вводится символьная строка, в которой записано некоторое (арифметическое) выражение, использующее скобки трёх типов:
- 51. Скобочные выражения (стек) когда встретили закрывающую скобку, на вершине стека лежит соответствующая открывающая в конце работы
- 52. Скобочные выражения (стек) L = "([{" # открывающие скобки R = ")]}" # парные закрывающие stack
- 53. Скобочные выражения (стек) for c in s: p = L.find(c) if p >= 0: stack.append(c) p
- 54. Что такое очередь? Очередь – это линейный список, для которого введены две операции: • добавление элемента
- 55. Заливка области Задача. Рисунок задан в виде матрицы A, в которой элемент A[y][x] определяет цвет пикселя
- 56. Заливка: использование очереди добавить в очередь точку (x0,y0) color = цвет начальной точки while очередь не
- 57. Заливка YMAX = len(A) XMAX = len(A[0]) NEW_COLOR = 2 y0 = 0 x0 = 1
- 58. Заливка (основной цикл) while len(Q) > 0: x, y = Q.pop(0) if A[y][x] == color: A[y][x]
- 59. Очередь: статический массив нужно знать размер не двигаем элементы голова хвост Удаление элемента: Добавление элемента:
- 60. Очередь: статический массив Замыкание в кольцо: Очередь заполнена: Очередь пуста:
- 61. Что такое дек? Дек – это линейный список, в котором можно добавлять и удалять элементы как
- 62. Алгоритмизация и программирование. Язык Python § 42. Деревья
- 63. Что такое дерево? «Сыновья» А: B, C. «Родитель» B: A. «Потомки» А: B, C, D, E,
- 64. Рекурсивные определения пустая структура – это дерево дерево – это корень и несколько связанных с ним
- 65. Деревья поиска Ключ – это значение, связанное с узлом дерева, по которому выполняется поиск. слева от
- 66. Обход дерева Обойти дерево ⇔ «посетить» все узлы по одному разу. ⇒ список узлов КЛП –
- 67. Обход дерева ЛПК: КЛП: ЛКП: * + 1 4 – 9 5 1 + 4 *
- 68. Обход КЛП – обход «в глубину» записать в стек корень дерева while стек не пуст: выбрать
- 69. Обход КЛП – обход «в глубину» * + 1 4 – 9 5
- 70. Обход «в ширину» записать в очередь корень дерева пока очередь не пуста: выбрать узел V из
- 71. Обход «в ширину» (1+4)*(9-5) * + - 1 4 9 5 голова очереди
- 72. Вычисление арифметических выражений 40–2*3–4*5 В корень дерева нужно поместить последнюю из операций с наименьшим приоритетом.
- 73. Вычисление арифметических выражений найти последнюю выполняемую операцию if операций нет: создать узел-лист return поместить операцию в
- 74. Вычисление арифметических выражений n1 = значение левого поддерева n2 = значение правого поддерева результат = операция(n1,
- 75. Использование связанных структур Дерево – нелинейная структура ⇒ динамический массив неудобен! class TNode: data = ""
- 76. Основная программа s = input ( "Введите выражение: " ) T = makeTree ( s )
- 77. Построение дерева def makeTree ( s ): k = lastOp(s) # номер последней операции if k
- 78. Вычисление по дереву def calcTree ( Tree ): if Tree.left == None: return int(Tree.data) else: n1
- 79. Вспомогательные функции def priority ( op ): if op in "+-": return 1 if op in
- 80. Двоичное дерево в массиве ? ?
- 81. Алгоритмизация и программирование. Язык Python § 43. Графы
- 82. Что такое граф? Граф – это набор вершин и связей между ними (рёбер). петля Матрица смежности:
- 83. Связность графа Связный граф – это граф, между любыми вершинами которого существует путь.
- 84. Дерево – это граф? дерево ABC ABDC BCD CCC… Дерево – это связный граф без циклов
- 85. Взвешенные графы Весовая матрица: вес ребра
- 86. Ориентированные графы (орграфы) Рёбра имеют направление (начало и конец), рёбра называю дугами.
- 87. Жадные алгоритмы Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее
- 88. Жадные алгоритмы Задача. Найти кратчайший маршрут из А в F.
- 89. Задача Прима-Крускала Задача. Между какими городами нужно проложить линии связи, чтобы все города были связаны в
- 90. Раскраска вершин 4 B 2 1 2 9 7 8 1 3 D E F A
- 91. Раскраска вершин N = 6 W = [] for i in range(N): W.append ( [0]*N )
- 92. Раскраска вершин ostov = [] # список выбранных рёбер for k in range(N-1): minDist = 1e10
- 93. Кратчайший маршрут Алгоритм Дейкстры (1960): кратчайшее расстояние откуда ехать ближайшая от A невыбранная вершина
- 94. Кратчайший маршрут Алгоритм Дейкстры (1960): кратчайшее расстояние откуда ехать W[x,z] + W[z,y] может быть так, что
- 95. Кратчайший маршрут Алгоритм Дейкстры (1960): кратчайшее расстояние откуда ехать W[x,z] + W[z,y] может быть так, что
- 96. Кратчайший маршрут Алгоритм Дейкстры (1960): кратчайшее расстояние откуда ехать 7 E 8 E
- 97. Кратчайший маршрут длины кратчайших маршрутов из A в другие вершины A → C → E →
- 98. Алгоритм Дейкстры N = 6 W = [] for i in range(N): W.append ( [0]*N )
- 99. Алгоритм Дейкстры for i in range(N-1): minDist = 1e10 for j in range(N): if active[j] and
- 100. Алгоритм Дейкстры i = N-1 while i >= 0: print ( i, end = "" )
- 101. Алгоритм Флойда for k in range(N): for i in range(N): for j in range(N): if W[i][k]
- 102. Алгоритм Флойда + маршруты P = [] for i in range(N): P.append ( [i]*N ) P[i][i]
- 103. Списки смежности вершина 1: ( 4 ) вершина 2: ( 1, 3 ) вершина 3: (
- 104. Списки смежности Graph = [[], [4], [1,3], [], [2,3,5], [3]] print ( pathCount (Graph, 1, 3,
- 105. Число путей: функция def pathCount ( graph, vStart, vEnd, visited ): if vStart == vEnd: return
- 106. Задача коммивояжера Коммивояжер (бродячий торговец) должен выйти из города 1 и, посетив по разу в неизвестном
- 107. Некоторые задачи Задача на минимум суммы. Имеется N населенных пунктов, в каждом из которых живет pi
- 108. Алгоритмизация и программирование. Язык Python § 43. Динамическое программирование
- 109. Что такое динамическое программирование? Числа Фибоначчи: ; . F1 = F2 = 1 Fn = Fn-1
- 110. Динамическое программирование Создание массива: F = [1]*(N+1) # чтобы начать с 1 Заполнение массива: for i
- 111. Динамическое программирование Динамическое программирование – это способ решения сложных задач путем сведения их к более простым
- 112. Количество вариантов Задача. Найти количество KN цепочек, состоящих из N нулей и единиц, в которых нет
- 113. Количество вариантов Задача. Найти количество KN цепочек, состоящих из N нулей и единиц, в которых нет
- 114. Оптимальное решение Задача. В цистерне N литров молока. Есть бидоны объемом 1, 5 и 6 литров.
- 115. Оптимальное решение Сначала выбрали бидон… KN – минимальное число бидонов для N литров KN = 1
- 116. Оптимальное решение (бидоны) 1 1 2 1 3 1 4 1 1 5 1 6 2
- 117. Задача о куче Задача. Из камней весом pi (i=1, …, N) набрать кучу весом ровно W
- 118. Задача о куче Задача. Из камней весом pi (i=1, …, N) набрать кучу весом ровно W
- 119. Задача о куче Добавляем камень с весом 4: для w 0 2 2 для w ≥
- 120. Задача о куче Добавляем камень с весом 5: для w 0 2 2 4 5 6
- 121. Задача о куче Добавляем камень с весом 7: для w 0 2 2 4 5 6
- 122. Задача о куче Добавляем камень с весом pi: для w Рекуррентная формула:
- 123. Задача о куче Оптимальный вес 7 5 + 2
- 124. Задача о куче Заполнение таблицы: W+1 N псевдополиномиальный
- 125. Количество программ Задача. У исполнителя Утроитель есть команды: 1. прибавь 1 2. умножь на 3 Сколько
- 126. Количество программ Как получить число N: N если делится на 3! последняя команда Рекуррентная формула: KN
- 127. Количество программ Заполнение таблицы: Рекуррентная формула: KN = KN-1 если N не делится на 3 KN
- 128. Количество программ Только точки изменения: 12 20 Программа: K = [0]*(N+1) K[1] = 1 for i
- 129. Размен монет Задача. Сколькими различными способами можно выдать сдачу размером W рублей, если есть монеты достоинством
- 130. Размен монет Пример: W = 10, монеты 1, 2, 5 и 10 w pi базовые случаи
- 131. Размен монет Пример: W = 10, монеты 1, 2, 5 и 10 Рекуррентная формула (добавили монету
- 132. Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН
- 134. Скачать презентацию