Содержание
- 2. Алгоритмизация и программирование § 38. Целочисленные алгоритмы
- 3. Решето Эратосфена Эратосфен Киренский (Eratosthenes, Ερατοσθδνη) (ок. 275-194 до н.э.) Новая версия – решето Аткина .
- 4. Решето Эратосфена Задача. Вывести все простые числа от 2 до N. Объявление переменных: цел i, k,
- 5. Решето Эратосфена Вычёркивание непростых: k:= 2 нц пока k*k если A[k] то i:= k*k нц пока
- 6. Решето Эратосфена Вывод результата: нц для i от 2 до N если A[i] то вывод 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 нц для i от 0 до N s:= A[i]*k + r A[i]:=
- 13. Вывод длинного числа [A] = 1000002000003 найти старший ненулевой разряд вывести этот разряд вывести все следующие
- 14. Вывод длинного числа нц для k от i-1 до 0 шаг -1 Write6(A[k]) кц for k:=i-1
- 15. Вывод длинного числа Вывод числа с лидирующими нулями: алг Write6 (цел x) нач цел M, xx
- 16. Вывод длинного числа Вывод числа с лидирующими нулями: procedure Write6(x: longint); var M: longint; begin M:=
- 17. Алгоритмизация и программирование § 39. Структуры (записи)
- 18. Зачем нужны структуры? Книги в библиотеках: автор название количество экземпляров … символьные строки целое число Задачa:
- 19. Структуры (записи) Структура – это тип данных, который может включать в себя несколько полей – элементов
- 20. Объявление структур const N = 100; var B: TBook; { одна структура } Books: array[1..N] of
- 21. Обращение к полям структур B.author { поле author структуры B } Точечная нотация: Books[5].count { поле
- 22. Обращение к полям структур B.author:= 'Пушкин А.С.'; B.title:= 'Полтава'; B.count:= 1; p:= Pos(' ', B.author); fam:=
- 23. Запись структур в файлы 'Пушкин А.С.';'Полтава';12 'Лермонтов М.Ю.';'Мцыри';8 Текстовые файлы: символ-разделитель Типизированные файлы: var F: file
- 24. Чтение структур из файла Assign(F, 'books.dat'); Reset(F); Read(F, B); writeln(B.author,', ',B.title, ', ',B.count); Close(F); только для
- 25. Сортировка структур Ключ – фамилия автора: for i:=1 to N-1 do for j:=N-1 downto i do
- 26. Указатели Указатель – это переменная, в которой можно сохранить адрес любой переменной заданного типа. type PBook
- 27. Сортировка по указателям var p: array[1..N] of PBook; for i:=1 to N do p[i]:= @Books[i]; Задача
- 28. Сортировка по указателям for i:= 1 to N-1 do for j:= N-1 downto i do if
- 29. Алгоритмизация и программирование § 40. Множества 2-е издание
- 30. Зачем нужны множества? Задача. Определить количество знаков препинания в символьной строке. count:= 0; for i:=1 to
- 31. Использование множеств if s[i] in ['0'.. '9'] then count:= count + 1; диапазон if s[i] in
- 32. Использование множеств Задача. Вывести все различные цифры, присутствующие в символьной строке s. var s: string; i:
- 33. Использование множеств var cs: set of char; bs: set of byte; до 255 элементов Имена для
- 34. Вывод множества на экран type TFontStyles = (fsBold, fsItalic, fsUnderline); var style: TFontStyles; fs:= [fsBold, fsItalic];
- 35. Сравнение множеств Равенство/неравенство: if A = B then write('A = B'); { нет } if B
- 36. Множества в памяти Пустое множество: var digits: set of 0..9; digits:= []; Непустое множество: digits:= [1,
- 37. [1, 2, 3, 4, 5, 7] Множества в памяти Объединение множеств: digits:= [1, 3, 5, 7]
- 38. Алгоритмизация и программирование § 40. Динамические массивы
- 39. Чем плох обычный массив? const N = 100; var A: array[1..N] of integer; статический массив память
- 40. Динамические структуры данных создавать новые объекты в памяти изменять их размер удалять из памяти, когда не
- 41. Динамические массивы (FreePascal) Объявление: var A: array of integer; размер не указан Выделение памяти: read(N); SetLength(A,
- 42. Динамические массивы (FreePascal) Определение длины: writeln( Length(A) ); Освобождение памяти: SetLength(A, 0); Динамические матрицы: var A:
- 43. Динамические массивы (FreePascal) В подпрограммах: procedure printArray(X: array of integer); begin for i:= 0 to High(X)
- 44. Расширение массива Задача. С клавиатуры вводятся натуральные числа, ввод заканчивается числом 0. Нужно вывести на экран
- 45. Расширение массива Расширение по 10 элементов: N:= 0; { счётчик элементов } read(x); while x 0
- 46. Как это работает? Эксперимент: SetLength(A, 100); write(sizeof(A)); write(100*sizeof(integer)); 4 200 размер массива type TArray = record
- 47. Как это работает? var A: array of array of integer; SetLength(A, 10); выделить массив указателей for
- 48. Алгоритмизация и программирование § 41. Списки
- 49. Зачем нужны списки? Задача. В файле находится список слов, среди которых есть повторяющиеся. Каждое слово записано
- 50. Алгоритм (псевдокод) нц пока есть слова в файле прочитать очередное слово если оно есть в списке
- 51. Хранение данных type TPair = record word: string; { слово } count: integer { счётчик }
- 52. Хранение данных var L: TWordList; Переменная-список: SetLength(L.data, 0); L.size:= 0; Начальные значения: Вывод результата: Assign(F, 'output.dat');
- 53. Основной цикл while not Eof(F) { пока не конец файла } do begin readln(F, s); {
- 54. Поиск слова function Find(L: TWordList; word: string): integer; var i: integer; begin Find:= -1; for i:=0
- 55. Поиск места вставки function FindPlace(L: TWordList; word: string): integer; var i, p: integer; begin p:= -1;
- 56. Вставка слова дерево for i:=L.size-1 downto k+1 do L.data[i]:= L.data[i-1]; Сдвиг вниз: с последнего
- 57. Вставка слова procedure InsertWord(var L: TWordList; k: integer; word: string); var i: integer; begin IncSize(L); for
- 58. Расширение списка procedure IncSize (var L: TWordList); begin Inc(L.size); if L.size > Length(L.data) then SetLength(L.data, Length(L.data)
- 59. Вся программа program AlphaList; { объявления типов TPair и TWordList } var F: text; w: string;
- 60. Модули program AlphaList; { процедура 1 } { процедура 2 } { процедура 3 } {
- 61. Структура модуля unit WordList; interface … implementation … end. «интерфейс» – общедоступная информация: объявление типов данных
- 62. Модуль WordList unit WordList; interface { объявления типов TPair и TWordList } function Find(L: TWordList; word:
- 63. Подключение модуля program AlphaList; uses WordList; { подключение модуля } var F: text; s: string; L:
- 64. Связные списки узлы могут размещаться в разных местах в памяти только последовательный доступ Рекурсивное определение: пустой
- 65. Связные списки Head Циклический список: Двусвязный список: Head Tail «хвост» обход в двух направлениях сложнее вставка
- 66. Связные списки: структуры данных Односвязный список: Двусвязный список: type PNode = ^TNode; TNode = record data:
- 67. Алгоритмизация и программирование § 42. Стек, дек, очередь
- 68. Что такое стек? Стек (англ. stack – стопка) – это линейный список, в котором элементы добавляются
- 69. Реверс массива Задача. В файле записаны целые числа. Нужно вывести их в другой файл в обратном
- 70. Использование динамического массива type TStack = record data: array of integer; size: integer end; procedure Push(var
- 71. Использование динамического массива function Pop(var S:TStack): integer; begin S.size:= S.size-1; Pop:= S.data[S.size] end; изменяется procedure InitStack(var
- 72. Использование динамического массива InitStack(S); while not Eof(F) do begin read(F, x); Push(S, x) end; Заполнение стека:
- 73. Вычисление арифметических выражений (5+15)/(4+7-1) инфиксная форма (знак операции между данными) первой стоит последняя операция (вычисляем с
- 74. Вычисление арифметических выражений (5+15)/(4+7-1) 1950-е: постфиксная форма (знак операции после данных) не нужны скобки вычисляем с
- 75. Использование стека 5 15 + 4 7 + 1 - / 5 15 + 4 7
- 76. Скобочные выражения Задача. Вводится символьная строка, в которой записано некоторое (арифметическое) выражение, использующее скобки трёх типов:
- 77. Скобочные выражения (стек) когда встретили закрывающую скобку, на вершине стека лежит соответствующая открывающая в конце работы
- 78. Скобочные выражения (стек) type TStack = record data: array of char; size: integer end; Модель стека:
- 79. Скобочные выражения (стек) const L = '([{'; { открывающие скобки } R = ')]}'; { закрывающие
- 80. Скобочные выражения (стек) for i:=1 to Length(str) do begin p:= Pos(str[i], L); if p > 0
- 81. Что такое очередь? Очередь – это линейный список, для которого введены две операции: • добавление элемента
- 82. Заливка области Задача. Рисунок задан в виде матрицы A, в которой элемент A[y,x] определяет цвет пикселя
- 83. Заливка: использование очереди добавить в очередь точку (x0,y0) запомнить цвет начальной точки нц пока очередь не
- 84. Очередь (динамический массив) type TPoint = record x, y: integer end; TQueue = record data: array
- 85. Очередь (динамический массив) Добавить точку в очередь: procedure Put(var Q: TQueue; pt: TPoint); begin if Q.size
- 86. Очередь (динамический массив) Получить первую точку в очереди: function Get(var Q:TQueue): TPoint; var i: integer; begin
- 87. Заливка const XMAX = 5; YMAX = 5; NEW_COLOR = 2; var Q: TQueue; x0, y0,
- 88. Заливка (основной цикл) while not isEmpty(Q) do begin pt:= Get(Q); { взять точку из очереди }
- 89. Очередь: статический массив нужно знать размер не двигаем элементы голова хвост Удаление элемента: Добавление элемента:
- 90. Очередь: статический массив Замыкание в кольцо: Очередь заполнена: Очередь пуста:
- 91. Что такое дек? Дек – это линейный список, в котором можно добавлять и удалять элементы как
- 92. Алгоритмизация и программирование § 43. Деревья
- 93. Что такое дерево? «Сыновья» А: B, C. «Родитель» B: A. «Потомки» А: B, C, D, E,
- 94. Рекурсивные определения пустая структура – это дерево дерево – это корень и несколько связанных с ним
- 95. Деревья поиска Ключ – это значение, связанное с узлом дерева, по которому выполняется поиск. слева от
- 96. Обход дерева Обойти дерево ⇔ «посетить» все узлы по одному разу. ⇒ список узлов КЛП –
- 97. Обход дерева ЛПК: КЛП: ЛКП: * + 1 4 – 9 5 1 + 4 *
- 98. Обход КЛП – обход «в глубину» записать в стек корень дерева нц пока стек не пуст
- 99. Обход КЛП – обход «в глубину» * + 1 4 – 9 5
- 100. Обход «в ширину» записать в очередь корень дерева нц пока очередь не пуста V:= выбрать узел
- 101. Обход «в ширину» (1+4)*(9-5) * + - 1 4 9 5 голова очереди
- 102. Вычисление арифметических выражений 40–2*3–4*5 В корень дерева нужно поместить последнюю из операций с наименьшим приоритетом.
- 103. Вычисление арифметических выражений найти последнюю выполняемую операцию если операций нет то создать узел-лист выход все поместить
- 104. Вычисление арифметических выражений n1:= значение левого поддерева n2:= значение правого поддерева результат:= операция(n1, n2) значение левого
- 105. Использование связанных структур Дерево – нелинейная структура ⇒ динамический массив неудобен! type PNode = ^TNode; {
- 106. Работа с памятью Выделить память для узла: var p: PNode; { указатель на узел } New(p);
- 107. Основная программа var T: PNode; { ссылка на дерево } s: string; { строка с выражением
- 108. Построение дерева function Tree(s: string): PNode; var k: integer; begin New(Tree); { выделить память } k:=
- 109. Вычисление по дереву function Calc(Tree: PNode): integer; var n1, n2, res: integer; begin if Tree^.left =
- 110. Приоритет операции function Priority(op: char): integer; begin case op of '+','-': Priority:= 1; '*','/': Priority:= 2
- 111. Последняя выполняемая операция function LastOp(s: string): integer; var i, minPrt: integer; begin minPrt:= 50; { любое
- 112. Двоичное дерево в массиве ? ?
- 113. Алгоритмизация и программирование § 44. Графы
- 114. Что такое граф? Граф – это набор вершин и связей между ними (рёбер). петля Матрица смежности:
- 115. Связность графа Связный граф – это граф, между любыми вершинами которого существует путь.
- 116. Дерево – это граф? дерево ABC ABDC BCD CCC… Дерево – это связный граф без циклов
- 117. Взвешенные графы Весовая матрица: вес ребра
- 118. Ориентированные графы (орграфы) Рёбра имеют направление (начало и конец), рёбра называю дугами.
- 119. Жадные алгоритмы Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее
- 120. Жадные алгоритмы Задача. Найти кратчайший маршрут из А в F.
- 121. Задача Прима-Крускала Задача. Между какими городами нужно проложить линии связи, чтобы все города были связаны в
- 122. Раскраска вершин 4 B 2 1 2 9 7 8 1 3 D E F A
- 123. Раскраска вершин const N = 6; var { весовая матрица } W: array[1..N,1..N] of integer; {
- 124. Раскраска вершин for k:= 1 to N-1 do begin { поиск ребра с минимальным весом }
- 125. Кратчайший маршрут Алгоритм Дейкстры (1960): кратчайшее расстояние откуда ехать ближайшая от A невыбранная вершина
- 126. Кратчайший маршрут Алгоритм Дейкстры (1960): кратчайшее расстояние откуда ехать W[x,z] + W[z,y] может быть так, что
- 127. Кратчайший маршрут Алгоритм Дейкстры (1960): кратчайшее расстояние откуда ехать W[x,z] + W[z,y] может быть так, что
- 128. Кратчайший маршрут Алгоритм Дейкстры (1960): кратчайшее расстояние откуда ехать 7 E 8 E
- 129. Кратчайший маршрут длины кратчайших маршрутов из A в другие вершины A → C → E →
- 130. Алгоритм Дейкстры const N = 6; var W: array[1..N,1..N] of integer; active: array [1..N] of boolean;
- 131. Алгоритм Дейкстры for i:= 1 to N-1 do begin min:= MaxInt; for j:= 1 to N
- 132. Алгоритм Дейкстры i:= N; { конечная вершина } while i 0 do begin write(i:5); i:= P[i]
- 133. Алгоритм Флойда for k:= 1 to N do for i:= 1 to N do for j:=
- 134. Алгоритм Флойда + маршруты for i:=1 to N do begin for j:=1 to N do P[i,j]:=
- 135. Задача коммивояжера Коммивояжер (бродячий торговец) должен выйти из города 1 и, посетив по разу в неизвестном
- 136. Некоторые задачи Задача на минимум суммы. Имеется N населенных пунктов, в каждом из которых живет pi
- 137. Алгоритмизация и программирование § 44. Динамическое программирование
- 138. Что такое динамическое программирование? Числа Фибоначчи: ; . F1 = F2 = 1 Fn = Fn-1
- 139. Динамическое программирование Объявление массива: const N = 10; var F: array[1..N] of integer; Заполнение массива: F[1]:=
- 140. Динамическое программирование Динамическое программирование – это способ решения сложных задач путем сведения их к более простым
- 141. Количество вариантов Задача. Найти количество KN цепочек, состоящих из N нулей и единиц, в которых нет
- 142. Количество вариантов Задача. Найти количество KN цепочек, состоящих из N нулей и единиц, в которых нет
- 143. Оптимальное решение Задача. В цистерне N литров молока. Есть бидоны объемом 1, 5 и 6 литров.
- 144. Оптимальное решение Сначала выбрали бидон… KN – минимальное число бидонов для N литров KN = 1
- 145. Оптимальное решение (бидоны) 1 1 2 1 3 1 4 1 1 5 1 6 2
- 146. Задача о куче Задача. Из камней весом pi (i=1, …, N) набрать кучу весом ровно W
- 147. Задача о куче Задача. Из камней весом pi (i=1, …, N) набрать кучу весом ровно W
- 148. Задача о куче Добавляем камень с весом 4: для w 0 2 2 для w ≥
- 149. Задача о куче Добавляем камень с весом 5: для w 0 2 2 4 5 6
- 150. Задача о куче Добавляем камень с весом 7: для w 0 2 2 4 5 6
- 151. Задача о куче Добавляем камень с весом pi: для w Рекуррентная формула:
- 152. Задача о куче Оптимальный вес 7 5 + 2
- 153. Задача о куче Заполнение таблицы: W+1 N псевдополиномиальный
- 154. Количество программ Задача. У исполнителя Утроитель есть команды: 1. прибавь 1 2. умножь на 3 Сколько
- 155. Количество программ Как получить число N: N если делится на 3! последняя команда Рекуррентная формула: KN
- 156. Количество программ Заполнение таблицы: Рекуррентная формула: KN = KN-1 если N не делится на 3 KN
- 157. Количество программ Только точки изменения: 12 20 Программа: K[1]:= 1; for i:= 2 to N do
- 158. Размен монет Задача. Сколькими различными способами можно выдать сдачу размером W рублей, если есть монеты достоинством
- 159. Размен монет Пример: W = 10, монеты 1, 2, 5 и 10 w pi базовые случаи
- 160. Размен монет Пример: W = 10, монеты 1, 2, 5 и 10 Рекуррентная формула (добавили монету
- 161. Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН
- 163. Скачать презентацию