Содержание
- 2. Что такое сортировка? Сортировка – это расстановка элементов массива в заданном порядке. …по возрастанию, убыванию, последней
- 3. Метод пузырька (сортировка обменами) Идея: пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов
- 4. Метод пузырька 2-й проход: 3-й проход: 4-й проход:
- 5. Метод пузырька 1-й проход: сделать для j от N-2 до 0 шаг -1 если A[j+1] #
- 6. Метод пузырька 1-й проход: for j in range(N-2, -1 ,-1): if A[j+1] # поменять местами A[j]
- 7. Метод пузырька for i in range(N-1): for j in range(N-2, i-1 ,-1): if A[j+1] A[j], A[j+1]
- 8. Задачи «A»: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в
- 9. Метод выбора (минимального элемента) Идея: найти минимальный элемент и поставить его на первое место. for i
- 10. Метод выбора (минимального элемента) for i in range(N-1): if i!= nMin: A[i], A[nMin] = A[nMin], A[i]
- 11. Задачи «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию,
- 12. Задачи «B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Пример: Массив:
- 13. Сортировка слиянием Слияние отсортированных массивов: A B С Na = len(A); Nb = len(B) iA =
- 14. Сортировка слиянием def mergeSort( A ): if len(A) mid = len(A) // 2 L = A[:mid]
- 15. Сортировка слиянием def merge( A, B ): Na = len(A); Nb = len(B) iA = iB
- 16. Сортировка слиянием задача разбивается на несколько подзадач меньшего размера; эти подзадачи решаются с помощью рекурсивных вызовов
- 17. Быстрая сортировка (QuickSort) разделение Медиана – такое значение X, что слева и справа от него в
- 18. Быстрая сортировка (QuickSort) B1: B2: > X BX: = X import random def qSort ( A
- 19. Сравнение алгоритмов сортировки
- 20. Быстрая сортировка «на месте» Шаг 2: переставить элементы так: при сортировке элементы не покидают « свою
- 21. Быстрая сортировка Разделение: выбрать любой элемент массива (X=67) установить L = 0, R = N-1 увеличивая
- 22. Быстрая сортировка
- 23. Быстрая сортировка N = 7 A = [0]*N # заполнить массив qSort( A, 0, N-1 )
- 24. Быстрая сортировка def qSort ( A, nStart, nEnd ): if nStart >= nEnd: return L =
- 25. Быстрая сортировка Случайный выбор элемента-разделителя: from random import randint def qSort ( A, nStart, nEnd ):
- 26. Сортировка в Python B = sorted( A ) алгоритм Timsort По возрастанию: B = sorted( A,
- 27. Сортировка в Python – на месте A.sort() По возрастанию: A.sort ( reverse = True ) По
- 28. Задачи «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой
- 29. Задачи «B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм
- 30. Задачи «C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и
- 31. Программирование на языке Python § 65. Двоичный поиск
- 32. Двоичный поиск X = 7 X 8 4 X > 4 6 X > 6 Выбрать
- 33. Двоичный поиск X = 44
- 34. Двоичный поиск L = 0; R = N # начальный отрезок while L c = (L+R)
- 35. Двоичный поиск скорость выше, чем при линейном поиске нужна предварительная сортировка Число сравнений:
- 36. Задачи «A»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить,
- 37. Задачи «B»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить,
- 38. Задачи «C»: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя
- 39. Программирование на языке Python § 66. Символьные строки
- 40. Символьные строки Начальное значение: Вывод на экран: print ( s ) s = "Привет!" Длина строки:
- 41. Символьные строки Ввод с клавиатуры: s = input ( "Введите имя: " ) Изменение строки: s[4]
- 42. Символьные строки s = input( "Введите строку:" ) s1 = "" # строка-результат for c in
- 43. Задачи «A»: Ввести с клавиатуры символьную строку и заменить в ней все буквы «а» на «б»
- 44. Задачи «B»: Ввести с клавиатуры символьную строку и определить, сколько в ней слов. Словом считается последовательности
- 45. Задачи «C»: Ввести с клавиатуры символьную строку и найдите самое длинное слово и его длину. Словом
- 46. Операции со строками Объединение (конкатенация) : s1 = "Привет" s2 = "Вася" s = s1 +
- 47. Операции со строками Срезы: s = "0123456789" s1 = s[:8] # "01234567" от начала строки s
- 48. Операции со строками Срезы с отрицательными индексами: s = "0123456789" s1 = s[:-2] # "01234567" N-2
- 49. Удаление и вставка символов Вставка: s = "0123456789" s1 = s[:3] + "ABC" + s[3:] Удаление:
- 50. Стандартные функции Верхний/нижний регистр: s = "aAbBcC" s1 = s.upper() # "AABBCC" s2 = s.lower() #
- 51. Поиск в строках s = "Здесь был Вася." n = s.find ( "с" ) # n
- 52. Пример обработки строк Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы». Пример: Введите
- 53. Пример обработки строк print ( "Введите имя, отчество и фамилию:" ) s = input() n =
- 54. Пример обработки строк print ( "Введите имя, отчество и фамилию:" ) s = input() fio =
- 55. Задачи «A»: Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести
- 56. Задачи «B»: Ввести адрес файла и «разобрать» его на части, разделенные знаком "/". Каждую часть вывести
- 57. Задачи «C»: Напишите программу, которая заменяет во всей строке одну последовательность символов на другую. Пример: Введите
- 58. Преобразования «строка» – «число» Из строки в число: s = "123" N = int ( s
- 59. Задачи «A»: Напишите программу, которая вычисляет сумму трех чисел, введенную в форме символьной строки. Все числа
- 60. Задачи «C»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки
- 61. Задачи «D»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки
- 62. Строки в процедурах и функциях Задача: построить процедуру, которая заменяет в строке s все вхождения слова-образца
- 63. Замена всех экземпляров подстроки
- 64. Замена всех экземпляров подстроки s = "12.12.12" s = replaceAll ( s, "12", "A12B" ) print(
- 65. Замена всех экземпляров подстроки def replaceAll ( s, wOld, wNew ): lenOld = len(wOld) res =
- 66. Замена всех экземпляров подстроки s = "12.12.12" s = s.replace( "12", "A12B" ) print ( s
- 67. Задачи «A»: Напишите функцию, которая отсекает всю часть строки после первого слова. Пример: Введите строку: Однажды
- 68. Задачи «B»: Напишите функцию, которая заменяет расширение файла на заданное новое расширение. Пример: Введите имя файла:
- 69. Задачи «C»: Напишите функцию, которая заменяет во всей строке все римские числа на соответствующие десятичные числа.
- 70. Рекурсивный перебор Задача. В алфавите языка племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно
- 71. Рекурсивный перебор перебор L символов w[0]="Ы" # перебор последних L-1 символов w[0]="Ш" # перебор последних L-1
- 72. Рекурсивный перебор # основная программа TumbaWords ( "ЫШЧО", "", 3 ); def TumbaWords ( A, w,
- 73. Задачи «A»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести
- 74. Задачи «C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести
- 75. Сравнение строк Сравнение по кодам символов:
- 76. Сравнение строк 5STEAM steam
- 77. Сортировка строк aS = [] # пустой список строк print ( "Введите строки для сортировки:" )
- 78. Задачи «A»: Вводится 5 строк, в которых сначала записан порядковый номер строки с точкой, а затем
- 79. Задачи «B»: Вводится несколько строк (не более 20), в которых сначала записан порядковый номер строки с
- 80. Задачи «C»: Вводится несколько строк (не более 20), в которых сначала записаны инициалы и фамилии работников
- 81. Программирование на языке Python § 67. Матрицы
- 82. Что такое матрица? Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и
- 83. Создание матриц A = [[-1, 0, 1], [-1, 0, 1], [0, 1, -1]] перенос на другую
- 84. Создание матриц N = 3 M = 2 row = [0]*M A = [row]*N Нулевая матрица:
- 85. Вывод матриц print ( A ) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] def
- 86. Простые алгоритмы Заполнение случайными числами: import random for i in range(N): for j in range(M): A[i][j]
- 87. Задачи «A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], и находит максимальный
- 88. Задачи «B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в виде матрицы. Преобразовать рисунок
- 89. Задачи «С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой,
- 90. Перебор элементов матрицы Главная диагональ: for i in range(N): # работаем с A[i][i] Побочная диагональ: for
- 91. Перестановка строк и столбцов 2-я и 4-я строки: A[2], A[4] = A[4], A[2] 2-й и 4-й
- 92. Выделение строк и столбцов 1-я строка: R = A[1][:] 2-й столбец: C = [] for row
- 93. Задачи «A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], а затем записывает
- 94. Задачи «B»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M
- 95. Программирование на языке Python § 68. Работа с файлами
- 96. Как работать с файлами? файлы текстовые двоичные «plain text»: текст, разбитый на строки; из специальных символов
- 97. Принцип сэндвича хлеб хлеб начинка Fin = open ( "input.txt" ) Fout = open ( "output.txt",
- 98. Ввод данных Fin = open( "input.txt" ) s = Fin.readline() # "1 2" Чтение строки: Чтение
- 99. Вывод данных в файл a = 1 b = 2 Fout = open( "output.txt", "w" )
- 100. Чтение неизвестного количества данных пока не конец файла прочитать число из файла добавить его к сумме
- 101. Чтение неизвестного количества данных Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.
- 102. Чтение неизвестного количества данных Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.
- 103. Задачи «A»: Напишите программу, которая находит среднее арифметическое всех чисел, записанных в файле в столбик, и
- 104. Обработка массивов Задача. В файле записаны в столбик целые числа. Вывести в другой текстовый файл те
- 105. Обработка массивов Ввод массива: A = [] while True: s = Fin.readline() if not s: break
- 106. Обработка массивов Вывод результата: Fout = open ( "output.txt", "w" ) Fout.write ( str(A) ) Fout.close()
- 107. Задачи «A»: В файле в столбик записаны числа. Отсортировать их по возрастанию последней цифры и записать
- 108. Обработка строк Задача. В файле записано данные о собаках: в каждой строчке кличка собаки, ее возраст
- 109. Чтение данных из файла Чтение одной строки: s = Fin.readline() Разбивка по пробелам: data = s.split()
- 110. Обработка строк Fin = open ( "input.txt" ) Fout = open ( "output.txt", "w" ) while
- 111. Обработка строк lst = Fin.readlines() for s in lst: age = int ( s.split()[1] ) if
- 112. Задачи «A»: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и
- 113. Задачи «C»: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и
- 114. Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН
- 116. Скачать презентацию