Инфоурок Информатика ПрезентацииПрограммирование на языке Python § 62. Массивы

Программирование на языке Python § 62. Массивы

Скачать материал
Скачать материал "Программирование на языке Python § 62. Массивы"

Получите профессию

Фитнес-тренер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Методические разработки к Вашему уроку:

Получите новую специальность за 2 месяца

Ландшафтный архитектор

Описание презентации по отдельным слайдам:

  • Программирование на языке Python§ 62. Массивы1

    1 слайд

    Программирование на языке Python
    § 62. Массивы
    1

  • Что такое массив?2Массив – это группа переменных одного типа, расположенных в...

    2 слайд

    Что такое массив?
    2
    Массив – это группа переменных одного типа, расположенных в памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер (индекс).
    Надо:
    Как ввести 10000 переменных?
    ?
    выделять память
    записывать данные в нужную ячейку
    читать данные из ячейки

  • Что такое массив?3Aмассив215НОМЕР элемента массива
(ИНДЕКС)A[0]A[1]A[2]A[3]A...

    3 слайд

    Что такое массив?
    3
    A
    массив
    2
    15
    НОМЕР
    элемента массива
    (ИНДЕКС)
    A[0]
    A[1]
    A[2]
    A[3]
    A[4]
    ЗНАЧЕНИЕ элемента массива
    A[2]
    НОМЕР (ИНДЕКС)
    элемента массива: 2
    ЗНАЧЕНИЕ
    элемента массива: 15
    Массив = таблица!
    !

  • Массивы в Python: списки4A = [1, 3, 4, 23, 5]  Что будет??A = [1, 3] + [4, 23...

    4 слайд

    Массивы в Python: списки
    4
    A = [1, 3, 4, 23, 5]
    Что будет?
    ?
    A = [1, 3] + [4, 23] + [5]
    [1, 3, 4, 23, 5]
    A = [0]*10
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    A = list ( range(10) )
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

  • Генераторы списков5A =[ i  for i in range(10) ][0, 1, 2, 3, 4, 5, 6, 7, 8, 9]...

    5 слайд

    Генераторы списков
    5
    A =[ i  for i in range(10) ]
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    A =[ i*i  for i in range(10) ]
    [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
    Что будет?
    ?
    for i in range(10)
    i*i
    from random import randint
    A = [ randint(20,100)
    for x in range(10)]
    randint(20,100)
    A = [ i for i in range(100)  
    if isPrime(i)  ]
    if isPrime(i)
    случайные числа
    условие отбора

  • Как обработать все элементы массива?6Создание массива:



Обработка:N = 5
A =...

    6 слайд

    Как обработать все элементы массива?
    6
    Создание массива:



    Обработка:
    N = 5
    A = [0]*N
    # обработать A[0]
    # обработать A[1]
    # обработать A[2]
    # обработать A[3]
    # обработать A[4]
    1) если N велико (1000, 1000000)?
    2) при изменении N программа не должна меняться!
    ?

  • Как обработать все элементы массива?7Обработка с переменной:i = 0;
# обработа...

    7 слайд

    Как обработать все элементы массива?
    7
    Обработка с переменной:
    i = 0;
    # обработать A[i]
    i += 1
    # обработать A[i]
    i += 1
    # обработать A[i]
    i += 1
    # обработать A[i]
    i += 1
    # обработать A[i]
    i += 1
    Обработка в цикле:
    i = 0
    while i < N:
    # обработать A[i]
    i += 1
    Цикл с переменной:
    for i in range(N):
    # обработать A[i]

  • Ввод массива с клавиатуры8Создание массива:



Ввод с клавиатуры:N = 10
A = [...

    8 слайд

    Ввод массива с клавиатуры
    8
    Создание массива:



    Ввод с клавиатуры:
    N = 10
    A = [0]*N
    for i in range(N):
    print ( "A[", i, "]=",
    sep = "", end = "" )
    A[i] = int( input() )
    A[0] =
    A[1] =
    A[2] =
    A[3] =
    A[4] =
    5
    12
    34
    56
    13
    sep = ""
    end = ""
    не разделять элементы
    не переходить на новую строку

  • Ввод массива с клавиатуры9Ввод без подсказок:


Ввод в одной строке:A = [  in...

    9 слайд

    Ввод массива с клавиатуры
    9
    Ввод без подсказок:


    Ввод в одной строке:
    A = [  int(input())  for i in range(N) ]
    data = input() # "1 2 3 4 5"
    s = data.split() # ["1","2","3","4","5"]
    A = [ int(x) for x in s ]
    # [1,2,3,4,5]
    int(input())
    int(x)
    или так:
    s = input().split() # ["1","2","3","4","5"]
    A = list( map(int, s) ) # [1,2,3,4,5]
    применить int ко всем элементам s
    построить список

  • Вывод массива на экран10Как список:print ( A )[1, 2, 3, 4, 5]В строчку через...

    10 слайд

    Вывод массива на экран
    10
    Как список:
    print ( A )
    [1, 2, 3, 4, 5]
    В строчку через пробел:
    for i in range(N):
    print ( A[i], end = " " )
    1 2 3 4 5
    или так:
    for x in A:
    print ( x, end = " " )
    1 2 3 4 5
    или так:
    print ( *A )
    print (1, 2, 3, 4, 5)

  • Заполнение случайными числами11from random import randint
N = 10
A = [ randin...

    11 слайд

    Заполнение случайными числами
    11
    from random import randint
    N = 10
    A = [ randint(20,100)
    for x in range(N)]
    randint(20,100)
    случайные числа
    [20,100]
    from random import randint
    N = 10
    A = [0]*N
    for i in range(N):
    A[i] = randint(20,100)
    или так:

  • Перебор элементов12Общая схема (можно изменять A[i]):for  i in range(N):
  .....

    12 слайд

    Перебор элементов
    12
    Общая схема (можно изменять A[i]):
    for i in range(N):
    ... # сделать что-то с A[i]
    Если не нужно изменять A[i]:
    for x in A:
    ... # сделать что-то с x
    for i in range(N):
    A[i] += 1
    x = A[0], A[1], ..., A[N-1]
    for x in A:
    print ( x )

  • Подсчёт нужных элементов13Задача. В массиве записаны данные о росте баскетбол...

    13 слайд

    Подсчёт нужных элементов
    13
    Задача. В массиве записаны данные о росте баскетболистов. Сколько из них имеет рост больше
    180 см, но меньше 190 см?
    count = 0
    for x in A:
    if 180 < x and x < 190:
    count += 1
    Как решать?
    ?
    Python:
    180 < x < 190

  • Перебор элементов14Сумма:summa = 0
for x in A:
  if 180 &lt; x &lt; 190:
    summa...

    14 слайд

    Перебор элементов
    14
    Сумма:
    summa = 0
    for x in A:
    if 180 < x < 190:
    summa += x
    print ( summa )
    print ( sum(A) )
    или так:

  • Перебор элементов15Среднее арифметическое:count = 0
summa = 0
for x in A:
  i...

    15 слайд

    Перебор элементов
    15
    Среднее арифметическое:
    count = 0
    summa = 0
    for x in A:
    if 180 < x < 190:
    count += 1
    summa += x
    print ( summa/count )
    среднее арифметическое
    или так:
    B = [ x for x in A ]
    if 180 < x < 190]
    print ( sum(B)/len(B) )
    отбираем нужные

  • Задачи16«A»: Заполните массив случайными числами в интервале [0,100] и найдит...

    16 слайд

    Задачи
    16
    «A»: Заполните массив случайными числами в интервале [0,100] и найдите среднее арифметическое его значений.
    Пример:
    Массив:
    1 2 3 4 5
    Среднее арифметическое 3.000
    «B»: Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50.
    Пример:
    Массив:
    3 2 52 4 60
    Ср. арифм. элементов [0,50): 3.000
    Ср. арифм. элементов [50,100]: 56.000

  • Задачи17«C»: Заполните массив из N элементов случайными числами в интервале [...

    17 слайд

    Задачи
    17
    «C»: Заполните массив из N элементов случайными числами в интервале [1,N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку).
    Пример:
    Массив:
    3 2 1 4 5

  • Программирование на языке Python§ 63. Алгоритмы обработки массивов 18

    18 слайд

    Программирование на языке Python
    § 63. Алгоритмы обработки массивов
    18

  • Поиск в массиве19Найти элемент, равный X:i = 0
while A[i] != X:
  i += 1
prin...

    19 слайд

    Поиск в массиве
    19
    Найти элемент, равный X:
    i = 0
    while A[i] != X:
    i += 1
    print ( "A[", i, "]=", X, sep = "" )
    Что плохо?
    ?
    i = 0
    while i < N and A[i] != X:
    i += 1
    if i < N:
    print ( "A[", i, "]=", X, sep = "" )
    else:
    print ( "Не нашли!" )
    Что если такого нет?
    ?
    i < N

  • Поиск в массиве20nX = -1
for i in range ( N ):
  if A[i] == X:
    nX = i...

    20 слайд

    Поиск в массиве
    20
    nX = -1
    for i in range ( N ):
    if A[i] == X:
    nX = i
    break
    if nX >= 0:
    print ( "A[", nX, "]=", X, sep = "" )
    else:
    print ( "Не нашли!" )
    Вариант с досрочным выходом:
    break
    досрочный выход из цикла
    номер найденного элемента

  • for i in range ( N ):
  if A[i] == X:
    print ( &quot;A[&quot;, i, &quot;]=&quot;, X, sep = &quot;&quot;...

    21 слайд

    for i in range ( N ):
    if A[i] == X:
    print ( "A[", i, "]=", X, sep = "" )
    break
    else:
    print ( "Не нашли!" )
    Поиск в массиве
    21
    Варианты в стиле Python:
    если не было досрочного выхода из цикла
    if X in A:
    nX = A.index(X)
    print ( "A[", nX, "]=", X, sep = "" )
    else:
    print ( "Не нашли!" )

  • Задачи22«A»: Заполните массив случайными числами в интервале [0,5]. Введите ч...

    22 слайд

    Задачи
    22
    «A»: Заполните массив случайными числами в интервале [0,5]. Введите число X и найдите все значения, равные X.
    Пример:
    Массив:
    1 2 3 1 2
    Что ищем:
    2
    Нашли: A[2]=2, A[5]=2
    Пример:
    Массив:
    1 2 3 1 2
    Что ищем:
    6
    Ничего не нашли.

  • Задачи23«B»: Заполните массив случайными числами в интервале [0,5]. Определит...

    23 слайд

    Задачи
    23
    «B»: Заполните массив случайными числами в интервале [0,5]. Определить, есть ли в нем элементы с одинаковыми значениями, стоящие рядом.
    Пример:
    Массив:
    1 2 3 3 2 1
    Есть: 3
    Пример:
    Массив:
    1 2 3 4 2 1
    Нет

  • Задачи24«C»: Заполните массив случайными числами. Определить, есть ли в нем э...

    24 слайд

    Задачи
    24
    «C»: Заполните массив случайными числами. Определить, есть ли в нем элементы с одинаковыми значениями, не обязательно стоящие рядом.
    Пример:
    Массив:
    3 2 1 3 2 5
    Есть: 3, 2
    Пример:
    Массив:
    3 2 1 4 0 5
    Нет

  • Максимальный элемент25M = A[0]
for i in range(1,N):
  if A[i] &gt; M: 
    M  =...

    25 слайд

    Максимальный элемент
    25
    M = A[0]
    for i in range(1,N):
    if A[i] > M:
    M = A[i]
    print ( M )
    M = A[0]
    for x in A:
    if x > M:
    M = x
    Как найти его номер?
    ?
    Варианты в стиле Python:
    M = max ( A )
    Если range(N)?
    ?

  • Максимальный элемент и его номер26M = A[0]; nMax = 0
for i in range(1,N):
  i...

    26 слайд

    Максимальный элемент и его номер
    26
    M = A[0]; nMax = 0
    for i in range(1,N):
    if A[i] > M:
    M = A[i]
    nMax = i
    print ( "A[", nMax, "]=", M, sep = "" )
    nMax = 0
    nMax = i
    Что можно улучшить?
    ?
    По номеру элемента можно найти значение!
    !
    nMax = 0
    for i in range(1,N):
    if A[i] > A[nMax]:
    nMax = i
    print ( "A[", nMax, "]=", A[nMax], sep = "" )
    A[nMax]
    A[nMax]

  • Максимальный элемент и его номер27M = max(A)
nMax = A.index(M)
print ( &quot;A[&quot;,...

    27 слайд

    Максимальный элемент и его номер
    27
    M = max(A)
    nMax = A.index(M)
    print ( "A[", nMax, "]=", M, sep = "" )
    Вариант в стиле Python:
    номер заданного элемента (первого из…)

  • Задачи28«A»: Заполнить массив случайными числами и найти минимальный и максим...

    28 слайд

    Задачи
    28
    «A»: Заполнить массив случайными числами и найти минимальный и максимальный элементы массива и их номера.
    Пример:
    Массив:
    1 2 3 4 5
    Минимальный элемент: A[1]=1
    Максимальный элемент: A[5]=5
    «B»: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера.
    Пример:
    Массив:
    5 5 3 4 1
    Максимальный элемент: A[1]=5
    Второй максимум: A[2]=5

  • Задачи29«C»: Введите массив с клавиатуры и найдите (за один проход) количеств...

    29 слайд

    Задачи
    29
    «C»: Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение.
    Пример:
    Массив:
    3 4 5 5 3 4 5
    Максимальное значение 5
    Количество элементов 3

  • Реверс массива30«Простое» решение:for i in range(  N  ):
  поменять местами A...

    30 слайд

    Реверс массива
    30
    «Простое» решение:
    for i in range( N ):
    поменять местами A[i] и A[N-1-i]
    N//2
    Что плохо?
    ?
    остановиться на середине!

  • Реверс массива31for i in range(N//2):
  c = A[i]
  A[i] = A[N-1-i]
  A[N-1-i]...

    31 слайд

    Реверс массива
    31
    for i in range(N//2):
    c = A[i]
    A[i] = A[N-1-i]
    A[N-1-i] = c
    Варианты в стиле Python:
    for i in range(N//2):
    A[i], A[N-i-1]= A[N-i-1], A[i]
    A.reverse()

  • Циклический сдвиг элементов32«Простое» решение:c = A[0]
for  i in range(N-1):...

    32 слайд

    Циклический сдвиг элементов
    32
    «Простое» решение:
    c = A[0]
    for i in range(N-1):
    A[i] = A[i+1]
    A[N-1] = c
    Что плохо?
    ?
    Почему не до N?
    ?

  • Срезы в Python33 A[1:3]  [12, 5]  A[2:3]  [5]  A[:3]  [7, 12, 5]  A[0:3] с на...

    33 слайд

    Срезы в Python
    33
    A[1:3]
    [12, 5]
    A[2:3]
    [5]
    A[:3]
    [7, 12, 5]
    A[0:3]
    с начала
    A[3:N-2]
    [8,…,18,34]
    разрезы
    A[3:]
    [8,…,18,34,40,23]
    A[3:N]
    до конца
    A[:]
    [7,12,5,8,…,18,34,40,23]
    копия массива

  • Срезы в Python – отрицательные индексы34 A[1:-1] [12,5,8,…,18,34,40] разрезы...

    34 слайд

    Срезы в Python – отрицательные индексы
    34
    A[1:-1]
    [12,5,8,…,18,34,40]
    разрезы
    A[1:N-1]
    A[-4:-2]
    [18, 34]
    A[N-4:N-2]

  • Срезы в Python – шаг 35 A[1:6:2]  [12, 8, 18] разрезы A[::3]  [7, 8, 34]  A[8...

    35 слайд

    Срезы в Python – шаг
    35
    A[1:6:2]
    [12, 8, 18]
    разрезы
    A[::3]
    [7, 8, 34]
    A[8:2:-2]
    [23, 34, 76]
    A[::-1]
    [23,40,34,18,76,8,5,12,7]
    реверс!
    A.reverse()
    шаг

  • Задачи36«A»: Заполнить массив случайными числами и выполнить циклический сдви...

    36 слайд

    Задачи
    36
    «A»: Заполнить массив случайными числами и выполнить циклический сдвиг элементов массива вправо на 1 элемент.
    Пример:
    Массив:
    1 2 3 4 5 6
    Результат:
    6 1 2 3 4 5
    «B»: Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине.
    Пример:
    Массив:
    1 2 3 4 5 6
    Результат:
    3 2 1 6 5 4

  • Задачи37«C»: Заполнить массив случайными числами в интервале [-100,100] и пер...

    37 слайд

    Задачи
    37
    «C»: Заполнить массив случайными числами в интервале [-100,100] и переставить элементы так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов.
    Пример:
    Массив:
    20 -90 15 -34 10 0
    Результат:
    20 15 10 -90 -34 0
    Количество положительных элементов: 3

  • Отбор нужных элементов38Простое решение:Задача. Отобрать элементы массива A,...

    38 слайд

    Отбор нужных элементов
    38
    Простое решение:
    Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B.
    B = []
    сделать для i от 0 до N-1
    если условие выполняется для A[i] то
    добавить A[i] к массиву B
    B = []
    for x in A:
    if x % 2 == 0:
    B.append(x)
    добавить x в конец массива B
    Какие элементы выбираем?
    ?

  • Отбор нужных элементов39Решение в стиле Python:Задача. Отобрать элементы масс...

    39 слайд

    Отбор нужных элементов
    39
    Решение в стиле Python:
    Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B.
    B = [ x for x in A ] 
    if x % 2 == 0  ]
    если x – чётное число
    перебрать все элементы A

  • Задачи40«A»: Заполнить массив случайными числами в интервале [-10,10] и отоб...

    40 слайд

    Задачи
    40
    «A»: Заполнить массив случайными числами в интервале
    [-10,10] и отобрать в другой массив все чётные отрицательные числа.
    Пример:
    Массив А:
    -5 6 7 -4 -6 8 -8
    Массив B:
    -4 -6 -8
    «B»: Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым.
    Пример:
    Массив А:
    12 13 85 96 47
    Массив B:
    13 47

  • Задачи41«C»: Заполнить массив случайными числами и отобрать в другой массив в...

    41 слайд

    Задачи
    41
    «C»: Заполнить массив случайными числами и отобрать в другой массив все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи.
    Пример:
    Массив А:
    12 13 85 34 47
    Массив B:
    13 34

  • Особенности работы со списками42A = [1, 2, 3]
B = A[1, 2, 3]ABA[0] = 0[0, 2,...

    42 слайд

    Особенности работы со списками
    42
    A = [1, 2, 3]
    B = A
    [1, 2, 3]
    A
    B
    A[0] = 0
    [0, 2, 3]
    A
    B
    A = [1, 2, 3]
    B = A[:]
    копия массива A
    [1, 2, 3]
    A
    [1, 2, 3]
    B
    A[0] = 0
    [0, 2, 3]
    A
    [1, 2, 3]
    B

  • [1,2,3]A[4,5,6]B[A,B]C[A,B]DКопирование списков43«Поверхностное» копирование:...

    43 слайд

    [1,2,3]
    A
    [4,5,6]
    B
    [A,B]
    C
    [A,B]
    D
    Копирование списков
    43
    «Поверхностное» копирование:
    import copy
    A = [1, 2, 3]
    B = copy.copy(A)
    A = [1, 2, 3]
    B = [4, 5, 6]
    C = [A, B]
    D = copy.copy(C)
    C[0][0] = 0
    [1,2,3]
    A
    [4,5,6]
    B
    0
    A
    Влияет на C и D!
    !
    «Глубокое» копирование:
    D = copy.deepcopy(C)
    [A,B]
    C
    [,]
    D
    [1,2,3]
    A
    [4,5,6]
    B
    [1,2,3]
    [4,5,6]

  • Программирование на языке Python§ 64. Сортировка 44

    44 слайд

    Программирование на языке Python
    § 64. Сортировка
    44

  • Что такое сортировка?45Сортировка – это расстановка элементов массива в задан...

    45 слайд

    Что такое сортировка?
    45
    Сортировка – это расстановка элементов массива в заданном порядке.
    …по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, …
    Алгоритмы:
    простые и понятные, но неэффективные для больших массивов
    метод пузырька
    метод выбора
    сложные, но эффективные
    «быстрая сортировка» (QuickSort)
    сортировка «кучей» (HeapSort)
    сортировка слиянием (MergeSort)
    пирамидальная сортировка
    время
    работы
    N

  • Метод пузырька (сортировка обменами)46Идея: пузырек воздуха в стакане воды по...

    46 слайд

    Метод пузырька (сортировка обменами)
    46
    Идея: пузырек воздуха в стакане воды поднимается со дна вверх.
    Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).
    сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
    за 1 проход по массиву один элемент (самый маленький) становится на свое место
    1-й проход:

  • Метод пузырька472-й проход:3-й проход:4-й проход:  Для сортировки массива из...

    47 слайд

    Метод пузырька
    47
    2-й проход:
    3-й проход:
    4-й проход:
    Для сортировки массива из N элементов нужен
    N-1 проход (достаточно поставить на свои места N-1 элементов).
    !

  • Метод пузырька481-й проход:сделать для j от N-2 до 0 шаг -1
  если A[j+1]&lt; A[...

    48 слайд

    Метод пузырька
    48
    1-й проход:
    сделать для j от N-2 до 0 шаг -1
    если A[j+1]< A[j] то
    # поменять местами A[j] и A[j+1]
    2-й проход:
    сделать для j от N-2 до 1 шаг -1
    если A[j+1]< A[j] то
    # поменять местами A[j] и A[j+1]
    1
    единственное отличие!

  • Метод пузырька491-й проход:for j in range(N-2, -1 ,-1):
  if A[j+1]&lt; A[j]:...

    49 слайд

    Метод пузырька
    49
    1-й проход:
    for j in range(N-2, -1 ,-1):
    if A[j+1]< A[j]:
    # поменять местами A[j] и A[j+1]
    2-й проход:
    for j in range(N-2,  0 ,-1):
    if A[j+1]< A[j]:
    # поменять местами A[j] и A[j+1]
    0
    единственное отличие!
    от N-2 до 0 шаг -1

  • Метод пузырька50for i in range(N-1):
  for j in range(N-2, i-1 ,-1):
    if A...

    50 слайд

    Метод пузырька
    50
    for i in range(N-1):
    for j in range(N-2, i-1 ,-1):
    if A[j+1] < A[j]:
    A[j], A[j+1] = A[j+1], A[j]
    i-1
    Как написать метод «камня»?
    ?
    Как сделать рекурсивный вариант?
    ?

  • Задачи51«A»: Напишите программу, в которой сортировка выполняется «методом ка...

    51 слайд

    Задачи
    51
    «A»: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.
    «B»: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок.
    «С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.

  • Метод выбора (минимального элемента)52Идея: найти минимальный элемент и поста...

    52 слайд

    Метод выбора (минимального элемента)
    52
    Идея: найти минимальный элемент и поставить его на первое место.
    for i in range(N-1):
    найти номер nMin минимального
    элемента из A[i]..A[N]
    if i != nMin:
    поменять местами A[i] и A[nMin]

  • Метод выбора (минимального элемента)53for i in range(N-1):




  if i!= nMin:...

    53 слайд

    Метод выбора (минимального элемента)
    53
    for i in range(N-1):




    if i!= nMin:
    A[i], A[nMin] = A[nMin], A[i]
    nMin = i
    for j in range(i+1,N):
    if A[j] < A[nMin]:
    nMin = j

  • Задачи54«A»: Массив содержит четное количество элементов. Напишите программу,...

    54 слайд

    Задачи
    54
    «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине.
    Пример:
    Массив:
    5 3 4 2 1 6 3 2
    После сортировки:
    2 3 4 5 6 3 2 1

  • Задачи55«B»: Напишите программу, которая сортирует массив и находит количеств...

    55 слайд

    Задачи
    55
    «B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем.
    Пример:
    Массив:
    5 3 4 2 1 6 3 2 4
    После сортировки:
    1 2 2 3 3 4 4 5 6
    Различных чисел: 5
    «C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

  • Быстрая сортировка (QuickSort)56Ч.Э.ХоарИдея: выгоднее переставлять элементы,...

    56 слайд

    Быстрая сортировка (QuickSort)
    56
    Ч.Э.Хоар
    Идея: выгоднее переставлять элементы, который находятся дальше друг от друга.
    Для массива из N элементов нужно всего N/2 обменов!
    !

  • Быстрая сортировка57Шаг 2: переставить элементы так: 

 при сортировке элеме...

    57 слайд

    Быстрая сортировка
    57
    Шаг 2: переставить элементы так:


    при сортировке элементы не покидают « свою область»!
    Шаг 1: выбрать некоторый элемент массива X
    Шаг 3: так же отсортировать две получившиеся области
    Разделяй и властвуй (англ. divide and conquer)
    Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).
    Как лучше выбрать X?
    ?

  • Быстрая сортировка58Разделение: 
выбрать любой элемент массива (X=67)


устан...

    58 слайд

    Быстрая сортировка
    58
    Разделение:
    выбрать любой элемент массива (X=67)


    установить L = 1, R = N
    увеличивая L, найти первый элемент A[L],
    который >= X (должен стоять справа)
    уменьшая R, найти первый элемент A[R],
    который <= X (должен стоять слева)
    если L<=R то поменять местами A[L] и A[R]
    и перейти к п. 3
    иначе стоп.

  • Быстрая сортировка59  L &gt; R : разделение закончено!!

    59 слайд

    Быстрая сортировка
    59
    L > R : разделение закончено!
    !

  • Быстрая сортировка60N = 7
A = [0]*N
# заполнить массив 
qSort( A, 0, N-1 )  #...

    60 слайд

    Быстрая сортировка
    60
    N = 7
    A = [0]*N
    # заполнить массив
    qSort( A, 0, N-1 ) # сортировка
    # вывести результат
    Основная программа:

  • Быстрая сортировка61def qSort ( A, nStart, nEnd ):
  if nStart &gt;= nEnd: retur...

    61 слайд

    Быстрая сортировка
    61
    def qSort ( A, nStart, nEnd ):
    if nStart >= nEnd: return
    L = nStart; R = nEnd
    X = A[(L+R)//2]
    while L <= R:
    while A[L] < X: L += 1
    while A[R] > X: R -= 1
    if L <= R:
    A[L], A[R] = A[R], A[L]
    L += 1; R -= 1
    qSort ( A, nStart, R )
    qSort ( A, L, nEnd )
    qSort ( A, nStart, R )
    qSort ( A, L, nEnd )
    рекурсивные вызовы
    while A[L] < X: L += 1
    while A[R] > X: R -= 1
    разделение на 2 части
    массив
    начало
    конец

  • Быстрая сортировка62Случайный выбор элемента-разделителя: from random import...

    62 слайд

    Быстрая сортировка
    62
    Случайный выбор элемента-разделителя:
    from random import randint
    def qSort ( A, nStart, nEnd ):
    ...
    X = A[randint(L,R)]
    ...
    X = A[randint(L,R)]
    или так:
    from random import choice
    def qSort ( A, nStart, nEnd ):
    ...
    X = choice ( A[L:R+1] )
    ...
    X = choice ( A[L:R+1] )

  • Быстрая сортировка63В стиле Python: from random import choice
def qSort ( A )...

    63 слайд

    Быстрая сортировка
    63
    В стиле Python:
    from random import choice
    def qSort ( A ):
    if len(A) <= 1: return A
    X = choice(A)
    B1 = [ b for b in A  if b < X ]
    BX = [ b for b in A  if b == X ]
    B2 = [ b for b in A  if b > X ]
    return qSort(B1) + BX + qSort(B2)
    рекурсивные вызовы
    Что плохо?
    ?
    окончание рекурсии
    Asort = qSort( A )

  • Быстрая сортировка64Сортировка массива случайных значений:

    64 слайд

    Быстрая сортировка
    64
    Сортировка массива случайных значений:

  • Сортировка в Python65B = sorted( A )алгоритм TimsortПо возрастанию: B = sorte...

    65 слайд

    Сортировка в Python
    65
    B = sorted( A )
    алгоритм Timsort
    По возрастанию:
    B = sorted( A, reverse = True )
    По убыванию:
    reverse = True
    По последней цифре:
    def lastDigit ( n ):
    return n % 10
    B = sorted( A, key = lastDigit )
    key = lastDigit
    или так:
    B = sorted( A, key = lambda x: x % 10  )
    lambda x: x % 10
    «лямбда»-функция
    (функция без имени)

  • Сортировка в Python – на месте66A.sort()По возрастанию: A.sort ( reverse = Tr...

    66 слайд

    Сортировка в Python – на месте
    66
    A.sort()
    По возрастанию:
    A.sort ( reverse = True )
    По убыванию:
    reverse = True
    По последней цифре:
    def lastDigit ( n ):
    return n % 10
    A.sort ( key = lastDigit )
    key = lastDigit
    или так:
    A.sort( key = lambda x: x % 10  )
    lambda x: x % 10

  • Задачи67«A»: Массив содержит четное количество элементов. Напишите программу,...

    67 слайд

    Задачи
    67
    «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки.
    Пример:
    Массив:
    5 3 4 2 1 6 3 2
    После сортировки:
    2 3 4 5 6 3 2 1

  • Задачи68«B»: Напишите программу, которая сортирует массив и находит количеств...

    68 слайд

    Задачи
    68
    «B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки.
    Пример:
    Массив:
    5 3 4 2 1 6 3 2 4
    После сортировки:
    1 2 2 3 3 4 4 5 6
    Различных чисел: 5

  • Задачи69«C»: Напишите программу, которая сравнивает число перестановок элемен...

    69 слайд

    Задачи
    69
    «C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.
    «D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки c с выбором среднего элемента показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

  • Программирование на языке Python§ 65. Двоичный поиск70

    70 слайд

    Программирование на языке Python
    § 65. Двоичный поиск
    70

  • Двоичный поиск71X = 7X &lt; 884X &gt; 46X &gt; 6Выбрать средний элемент A[c] и сравнит...

    71 слайд

    Двоичный поиск
    71
    X = 7
    X < 8
    8
    4
    X > 4
    6
    X > 6
    Выбрать средний элемент A[c] и сравнить с X.
    Если X == A[c], то нашли (стоп).
    Если X < A[c], искать дальше в первой половине.
    Если X > A[c], искать дальше во второй половине.

  • Двоичный поиск72LRсLсRX = 44LсRLR  L = R-1 : поиск завершен!!

    72 слайд

    Двоичный поиск
    72
    L
    R
    с
    L
    с
    R
    X = 44
    L
    с
    R
    L
    R
    L = R-1 : поиск завершен!
    !

  • Двоичный поиск73L = 0; R = N     	# начальный отрезок 
while L &lt; R-1:
  c = (...

    73 слайд

    Двоичный поиск
    73
    L = 0; R = N # начальный отрезок
    while L < R-1:
    c = (L+R) // 2 # нашли середину
    if X < A[c]: # сжатие отрезка
    R = c
    else: L = c
    if A[L] == X:
    print ( "A[", L, "]=", X, sep = "" )
    else:
    print ( "Не нашли!" )

  • Двоичный поиск74скорость выше, чем при линейном поискенужна предварительная с...

    74 слайд

    Двоичный поиск
    74
    скорость выше, чем при линейном поиске
    нужна предварительная сортировка
    Когда нужно применять?
    ?
    Число сравнений:

  • Задачи75«A»: Заполнить массив случайными числами и отсортировать его.  Ввести...

    75 слайд

    Задачи
    75
    «A»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений.
    Пример:
    Массив:
    1 4 7 3 9 2 4 5 2
    После сортировки:
    1 2 2 3 4 4 5 7 9
    Введите число X:
    2
    Число 2 найдено.
    Количество сравнений: 2

  • Задачи76«B»: Заполнить массив случайными числами и отсортировать его.  Ввести...

    76 слайд

    Задачи
    76
    «B»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве.
    Пример:
    Массив:
    1 4 7 3 9 2 4 5 2
    После сортировки:
    1 2 2 3 4 4 5 7 9
    Введите число X:
    4
    Число 4 встречается 2 раз(а).
    Пример:
    Массив:
    1 4 7 3 9 2 4 5 2
    После сортировки:
    1 2 2 3 4 4 5 7 9
    Введите число X:
    14
    Число 14 не встречается.

  • Задачи77«C»: Заполнить массив случайными числами и ввести число и отсортирова...

    77 слайд

    Задачи
    77
    «C»: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X.
    Пример:
    Массив:
    1 4 7 3 9 2 4 5 2
    После сортировки:
    1 2 2 3 4 4 5 12 19
    Введите число X:
    12
    Число 12 найдено.
    Пример:
    Массив:
    1 4 7 3 9 2 4 5 2
    После сортировки:
    1 2 2 3 4 4 5 12 19
    Введите число X:
    11
    Число 11 не найдено. Ближайшее число 12.

  • Программирование на языке Python§ 66. Символьные строки78

    78 слайд

    Программирование на языке Python
    § 66. Символьные строки
    78

  • Символьные строки79Начальное значение:Вывод на экран:print ( s )s = &quot;Привет!&quot;...

    79 слайд

    Символьные строки
    79
    Начальное значение:
    Вывод на экран:
    print ( s )
    s = "Привет!"
    Длина строки:
    n = len ( s )
    print ( s[5] )
    Строка – это
    последовательность
    символов!
    !
    print ( s[-2] )
    s[len(s)-2]

  • Символьные строки80Ввод с клавиатуры:s = input ( &quot;Введите имя: &quot; )Изменение с...

    80 слайд

    Символьные строки
    80
    Ввод с клавиатуры:
    s = input ( "Введите имя: " )
    Изменение строки:
    s[4] = "a"
    Строка – это неизменяемый объект!
    !
    ... но можно составить новую строку:
    s1 = s + "a"

  • Символьные строки81s = input( &quot;Введите строку:&quot; )
s1 = &quot;&quot;   # строка-результа...

    81 слайд

    Символьные строки
    81
    s = input( "Введите строку:" )
    s1 = "" # строка-результат
    for c in s:
    if c == "а":
    c = "б"
    s1 = s1 + c
    print ( s1 )
    Задача: заменить в строке все буквы "а" на буквы "б".
    перебрать все символы в строке
    добавить символ к строке-результату

  • Задачи82«A»: Ввести с клавиатуры символьную строку и заменить в ней все буквы...

    82 слайд

    Задачи
    82
    «A»: Ввести с клавиатуры символьную строку и заменить в ней все буквы «а» на «б» и все буквы «б» на «а» (заглавные на заглавные, строчные на строчные).
    Пример:
    Введите строку:
    ааббААББссСС
    Результат:
    ббааББААссСС

  • Задачи83«B»: Ввести с клавиатуры символьную строку и определить, сколько в не...

    83 слайд

    Задачи
    83
    «B»: Ввести с клавиатуры символьную строку и определить, сколько в ней слов. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы.
    Пример:
    Введите строку:
    Вася пошел гулять
    Найдено слов: 3

  • Задачи84«C»: Ввести с клавиатуры символьную строку и найдите самое длинное сл...

    84 слайд

    Задачи
    84
    «C»: Ввести с клавиатуры символьную строку и найдите самое длинное слово и его длину. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы.
    Пример:
    Введите строку:
    Вася пошел гулять
    Самое длинное слово: гулять, длина 6

  • Операции со строками85Объединение (конкатенация) :s1 = &quot;Привет&quot; 
s2 = &quot;Вася&quot;...

    85 слайд

    Операции со строками
    85
    Объединение (конкатенация) :
    s1 = "Привет"
    s2 = "Вася"
    s = s1 + ", " + s2 + "!"
    "Привет, Вася!"
    Срезы:
    s = "0123456789"
    s1 = s[3:8] # "34567"
    разрезы

  • Операции со строками86Срезы:s = &quot;0123456789&quot;
s1 = s[:8]         # &quot;01234567&quot;...

    86 слайд

    Операции со строками
    86
    Срезы:
    s = "0123456789"
    s1 = s[:8] # "01234567"
    от начала строки
    s = "0123456789"
    s1 = s[3:] # "3456789"
    до конца строки
    s1 = s[::-1] # "9876543210"
    реверс строки

  • Операции со строками87Срезы с отрицательными индексами:s = &quot;0123456789&quot;
s1 =...

    87 слайд

    Операции со строками
    87
    Срезы с отрицательными индексами:
    s = "0123456789"
    s1 = s[:-2] # "01234567"
    N-2
    s = "0123456789"
    s1 = s[-6:-2] # "4567"
    N-2
    N-6

  • Операции со строками88Вставка:s = &quot;0123456789&quot;
s1 = s[:3] + &quot;ABC&quot; + s[3:]Удал...

    88 слайд

    Операции со строками
    88
    Вставка:
    s = "0123456789"
    s1 = s[:3] + "ABC" + s[3:]
    Удаление:
    s = "0123456789"
    s1 = s[:3] + s[9:] # "0129"
    "012"
    "9"
    "012ABC3456789"

  • Стандартные функции89Верхний/нижний регистр:s = &quot;aAbBcC&quot;
s1 = s.upper()  # &quot;A...

    89 слайд

    Стандартные функции
    89
    Верхний/нижний регистр:
    s = "aAbBcC"
    s1 = s.upper() # "AABBCC"
    s2 = s.lower() # "aabbcc"
    Проверка на цифры:
    s = "abc"
    print ( s.isdigit() ) # False
    s1 = "123"
    print ( s1.isdigit() ) # True
    … и много других.

  • Поиск в строках90s = &quot;Здесь был Вася.&quot;
n = s.find ( &quot;с&quot; )		# n = 3
if n &gt;= 0:...

    90 слайд

    Поиск в строках
    90
    s = "Здесь был Вася."
    n = s.find ( "с" )# n = 3
    if n >= 0:
    print ( "Номер символа", n )
    else:
    print ( "Символ не найден." )
    Находит первое слева вхождение подстроки!
    !
    s = "Здесь был Вася."
    n = s.rfind ( "с" )# n = 12
    Поиск с конца строки:

  • Пример обработки строк91Задача:  Ввести имя, отчество и фамилию. Преобразоват...

    91 слайд

    Пример обработки строк
    91
    Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы».
    Пример:
    Введите имя, отчество и фамилию:
    Василий Алибабаевич Хрюндиков
    Результат:
    Хрюндиков В.А.
    Алгоритм:
    найти первый пробел и выделить имя
    удалить имя с пробелом из основной строки
    найти первый пробел и выделить отчество
    удалить отчество с пробелом из основной строки
    «сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы…
    Алибабаевич Хрюндиков
    Хрюндиков
    Хрюндиков В.А.

  • Пример обработки строк92print ( &quot;Введите имя, отчество и фамилию:&quot; )
s = inpu...

    92 слайд

    Пример обработки строк
    92
    print ( "Введите имя, отчество и фамилию:" )
    s = input()
    n = s.find ( " " )
    name = s[:n] # вырезать имя
    s = s[n+1:]
    n = s.find ( " " )
    name2 = s[:n] # вырезать отчество
    s = s[n+1:] # осталась фамилия
    s = s + " " + name[0] + "." + name2[0] + "."
    print ( s )

  • Пример обработки строк93print ( &quot;Введите имя, отчество и фамилию:&quot; )
s = inpu...

    93 слайд

    Пример обработки строк
    93
    print ( "Введите имя, отчество и фамилию:" )
    s = input()
    fio = s.split()
    s = fio[2] + " " + fio[0][0] + "." + fio[1][0] + "."
    print ( s )
    Решение в стиле Python:
    Василий Алибабаевич Хрюндиков
    fio[2]
    fio[1]
    fio[0]

  • Задачи94«A»: Ввести с клавиатуры в одну строку фамилию, имя и отчество, разде...

    94 слайд

    Задачи
    94
    «A»: Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести фамилию и инициалы.
    Пример:
    Введите фамилию, имя и отчество:
    Иванов Петр Семёнович
    П.С. Иванов

  • Задачи95«B»: Ввести адрес файла и «разобрать» его на части, разделенные знако...

    95 слайд

    Задачи
    95
    «B»: Ввести адрес файла и «разобрать» его на части, разделенные знаком "/". Каждую часть вывести в отдельной строке.
    Пример:
    Введите адрес файла:
    C:/Фото/2013/Поход/vasya.jpg
    C:
    Фото
    2013
    Поход
    vasya.jpg

  • Задачи96«C»: Напишите программу, которая заменяет во всей строке одну последо...

    96 слайд

    Задачи
    96
    «C»: Напишите программу, которая заменяет во всей строке одну последовательность символов на другую.
    Пример:
    Введите строку:
    (X > 0) and (Y < X) and (Z > Y) and (Z <> 5)
    Что меняем: and
    Чем заменить: &
    Результат
    (X > 0) & (Y < X) & (Z > Y) & (Z <> 5)

  • Преобразования «строка» – «число» 97Из строки в число:s = &quot;123&quot;
N = int ( s )...

    97 слайд

    Преобразования «строка» – «число»
    97
    Из строки в число:
    s = "123"
    N = int ( s ) # N = 123
    s = "123.456"
    X = float ( s ) # X = 123.456
    Из числа в строку:
    N = 123
    s = str ( N ) # s = "123"
    s = "{:5d}".format(N) # s = " 123"
    X = 123.456
    s = str ( X ) # s = "123.456"
    s = "{:7.2f}".format(X) # s = " 123.46"
    s = "{:10.2e}".format(X) # s = " 1.23e+02"

  • Задачи98«A»: Напишите программу, которая вычисляет сумму трех чисел, введенну...

    98 слайд

    Задачи
    98
    «A»: Напишите программу, которая вычисляет сумму трех чисел, введенную в форме символьной строки. Все числа целые.
    Пример:
    Введите выражение:
    12+3+45
    Ответ: 60
    «B»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение вводится как символьная строка, все числа целые.
    Пример:
    Введите выражение:
    12-3+45
    Ответ: 54

  • Задачи99«C»: Напишите программу, которая вычисляет выражение, состоящее из тр...

    99 слайд

    Задачи
    99
    «C»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/»). Выражение вводится как символьная строка, все числа целые. Операция «/» выполняется как целочисленное деление.
    Пример:
    Введите выражение:
    12*3+45
    Ответ: 81

  • Задачи100«D»: Напишите программу, которая вычисляет выражение, состоящее из т...

    100 слайд

    Задачи
    100
    «D»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/») и круглых скобок. Выражение вводится как символьная строка, все числа целые. Операция «/» выполняется как целочисленное деление (div).
    Пример:
    Введите выражение:
    2*(3+45)+4
    Ответ: 100

  • Строки в процедурах и функциях101Задача: построить процедуру, которая заменяе...

    101 слайд

    Строки в процедурах и функциях
    101
    Задача: построить процедуру, которая заменяет в строке s все вхождения слова-образца wOld на слово-замену wNew.
    пока слово wOld есть в строке s
    удалить слово wOld из строки
    вставить на это место слово wNew
    Что плохо?
    ?
    wOld: "12"
    wNew: "A12B"
    зацикливание

  • Замена всех экземпляров подстроки102sresб)wNewsresв)sresг)wOldressа)wNew

    102 слайд

    Замена всех экземпляров подстроки
    102
    s
    res
    б)
    wNew
    s
    res
    в)
    s
    res
    г)
    wOld
    res
    s
    а)
    wNew

  • Замена всех экземпляров подстроки103s = &quot;12.12.12&quot;
s = replaceAll ( s, &quot;12&quot;,...

    103 слайд

    Замена всех экземпляров подстроки
    103
    s = "12.12.12"
    s = replaceAll ( s, "12", "A12B" )
    print( s )

  • Замена всех экземпляров подстроки104def replaceAll ( s, wOld, wNew ):
  lenOl...

    104 слайд

    Замена всех экземпляров подстроки
    104
    def replaceAll ( s, wOld, wNew ):
    lenOld = len(wOld)
    res = ""
    while len(s) > 0:
    p = s.find ( wOld )
    if p < 0:
    res = res + s
    return
    if p > 0: res = res + s[:p]
    res = res + wNew
    if p+lenOld >= len(s):
    s = ""
    else:
    s = s[p+lenOld:]
    return res
    добавить слово-замену
    строка кончилась
    взять «хвост»
    взять начало перед образцом
    искать образец
    если не нашли

  • Замена всех экземпляров подстроки105s = &quot;12.12.12&quot;
s = s.replace( &quot;12&quot;, &quot;A12B...

    105 слайд

    Замена всех экземпляров подстроки
    105
    s = "12.12.12"
    s = s.replace( "12", "A12B" )
    print ( s )
    Встроенная функция:

  • Задачи106«A»: Напишите функцию, которая отсекает всю часть строки после перво...

    106 слайд

    Задачи
    106
    «A»: Напишите функцию, которая отсекает всю часть строки после первого слова.
    Пример:
    Введите строку: Однажды в студёную зимнюю пору...
    Первое слово: Однажды

  • Задачи107«B»: Напишите функцию, которая заменяет расширение файла на заданное...

    107 слайд

    Задачи
    107
    «B»: Напишите функцию, которая заменяет расширение файла на заданное новое расширение.
    Пример:
    Введите имя файла: qq
    Введите новое расширение: tmp
    Результат: qq.tmp
    Пример:
    Введите имя файла: qq.exe
    Введите новое расширение: tmp
    Результат: qq.tmp
    Пример:
    Введите имя файла: qq.work.xml
    Введите новое расширение: tmp
    Результат: qq.work.tmp

  • Задачи108«C»: Напишите функцию, которая заменяет во всей строке все римские ч...

    108 слайд

    Задачи
    108
    «C»: Напишите функцию, которая заменяет во всей строке все римские числа на соответствующие десятичные числа.
    Пример:
    Введите строку:
    В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов.
    Результат:
    В 2013 году в школе 123 состоялся очередной выпуск 11 классов.

  • Рекурсивный перебор109Задача. В алфавите языка племени «тумба-юмба» четыре бу...

    109 слайд

    Рекурсивный перебор
    109
    Задача. В алфавите языка племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все слова, состоящие из L букв, которые можно построить из букв этого алфавита.
    перебор L-1
    символов
    задача для слов длины К сведена к задаче для слов длины L-1!

  • Рекурсивный перебор110перебор L символов
  w[0]=&quot;Ы&quot;
   # перебор последних L-...

    110 слайд

    Рекурсивный перебор
    110
    перебор L символов
    w[0]="Ы"
    # перебор последних L-1 символов
    w[0]="Ш"
    # перебор последних L-1 символов
    w[0]="Ч"
    # перебор последних L-1 символов
    w[0]="О"
    # перебор последних L-1 символов

  • Рекурсивный перебор111# основная программа
TumbaWords ( &quot;ЫШЧО&quot;, &quot;&quot;, 3 );def T...

    111 слайд

    Рекурсивный перебор
    111
    # основная программа
    TumbaWords ( "ЫШЧО", "", 3 );
    def TumbaWords ( A, w, L ):
    if len(w) == L:
    print ( w )
    return
    for c in A:
    TumbaWords ( A, w + c, L )
    нужная длина слова
    слово полной длины
    по всем символам алфавита
    алфавит
    слово

  • Задачи112«A»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «...

    112 слайд

    Задачи
    112
    «A»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых вторая буква «Ы». Подсчитайте количество таких слов.
    «B»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов.
    Программа не должна строить другие слова, не соответствующие условию.

  • Задачи113«C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «...

    113 слайд

    Задачи
    113
    «C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом.
    Программа не должна строить другие слова, не соответствующие условию.

  • Сравнение строк114парпаркПар??Сравнение по кодам символов:

    114 слайд

    Сравнение строк
    114
    пар
    парк
    Пар
    ?
    ?
    Сравнение по кодам символов:

  • Сравнение строк1155STEAM 

    115 слайд

    Сравнение строк
    115
    5STEAM < STEAM < Steam < steam 
    steam < ПАР < Пар < пАр < пар < парк

  • Сортировка строк116aS = []    # пустой список строк 	
print ( &quot;Введите строки...

    116 слайд

    Сортировка строк
    116
    aS = [] # пустой список строк
    print ( "Введите строки для сортировки:" )
    while True:
    s1 = input()
    if s1 == "": break
    aS.append ( s1 ) # добавить строку в список
    aS.sort() # сортировка
    print ( aS )

  • Задачи117«A»: Вводится 5 строк, в которых сначала записан порядковый номер ст...

    117 слайд

    Задачи
    117
    «A»: Вводится 5 строк, в которых сначала записан порядковый номер строки с точкой, а затем – слово. Вывести слова в алфавитном порядке.
    Пример:
    Введите 5 строк:
    1. тепловоз
    2. арбуз
    3. бурундук
    4. кефир
    5. урядник
    Список слов в алфавитном порядке:
    арбуз, бурундук, кефир, тепловоз, урядник

  • Задачи118«B»: Вводится несколько строк (не более 20), в которых сначала запис...

    118 слайд

    Задачи
    118
    «B»: Вводится несколько строк (не более 20), в которых сначала записан порядковый номер строки с точкой, а затем – слово. Ввод заканчивается пустой строкой. Вывести введённые слова в алфавитном порядке.
    Пример:
    Введите слова:
    1. тепловоз
    2. арбуз
     
    Список слов в алфавитном порядке:
    арбуз, тепловоз

  • Задачи119«C»: Вводится несколько строк (не более 20), в которых сначала запис...

    119 слайд

    Задачи
    119
    «C»: Вводится несколько строк (не более 20), в которых сначала записаны инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой. Отсортировать строки в алфавитном порядке по фамилии.
    Пример:
    Введите ФИО:
    А.Г. Урядников
    Б.В. Тепловозов
    В.Д. Арбузов
     
    Список в алфавитном порядке:
    В.Д. Арбузов
    Б.В. Тепловозов
    А.Г. Урядников

  • Программирование на языке Python§ 67. Матрицы120

    120 слайд

    Программирование на языке Python
    § 67. Матрицы
    120

  • Что такое матрица?121  Как закодировать??Матрица — это прямоугольная таблица,...

    121 слайд

    Что такое матрица?
    121
    Как закодировать?
    ?
    Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца.
    нет знака
    нолик
    крестик
    строка 1, столбец 2

  • Создание матриц122A = [[-1, 0, 1], 
     [-1, 0, 1], 
     [0, 1, -1]]  Матри...

    122 слайд

    Создание матриц
    122
    A = [[-1, 0, 1],
    [-1, 0, 1],
    [0, 1, -1]]
    Матрица – это список списков!
    !
    перенос на другую строку внутри скобок
    A = [[-1, 0, 1], [-1, 0, 1], [0, 1, -1]]
    или так:
    Нумерация элементов с нуля!
    !

  • Создание матриц123N = 3
M = 2
row = [0]*M
A = [row]*NНулевая матрица:rowAA[0]...

    123 слайд

    Создание матриц
    123
    N = 3
    M = 2
    row = [0]*M
    A = [row]*N
    Нулевая матрица:
    row
    A
    A[0][0] = 1
    1
    а правильно так:
    A = []
    for i in range(N):
    A.append ( [0]*M )
    A
    A[0][0] = 1
    1

  • Вывод матриц124print ( A )[[1, 2, 3], [4, 5, 6], [7, 8, 9]]def printMatrix (...

    124 слайд

    Вывод матриц
    124
    print ( A )
    [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    def printMatrix ( A ):
    for row in A:
    for x in row:
    print ( "{:4d}".format(x), end = "" )
    print ()
    1 2 3
    4 5 6
    7 8 9
    Зачем форматный вывод?
    ?

  • Простые алгоритмы125Заполнение случайными числами:import random
for i in rang...

    125 слайд

    Простые алгоритмы
    125
    Заполнение случайными числами:
    import random
    for i in range(N):
    for j in range(M):
    A[i][j] = random.randint ( 20, 80 )
    print ( "{:4d}".format(A[i][j]),
    end = "" )
    print()
    Суммирование:
    s = 0
    for i in range(N):
    for j in range(M):
    s += A[i][j]
    print ( s )
    Вложенный цикл!
    !
    s = 0
    for row in A:
    s += sum(row)
    print ( s )

  • Задачи126«A»: Напишите программу, которая заполняет квадратную матрицу случай...

    126 слайд

    Задачи
    126
    «A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], и находит максимальный и минимальный элементы в матрице и их индексы.
    Пример:
    Матрица А:
    12 14 67 45
    32 87 45 63
    69 45 14 11
    40 12 35 15
    Максимальный элемент A[2,2]=87
    Минимальный элемент A[3,4]=11

  • Задачи127«B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в вид...

    127 слайд

    Задачи
    127
    «B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму:
    вычислить среднюю яркость пикселей по всему рисунку
    все пиксели, яркость которых меньше средней, сделать черными (записать код 0), а остальные – белыми (код 255)
    Пример:
    Матрица А:
    12 14 67 45
    32 87 45 63
    69 45 14 11
    40 12 35 15
    Средняя яркость 37.88
    Результат:
    0 0 255 255
    0 255 255 255
    255 255 0 0
    255 0 0 0

  • Задачи128«С»: Заполните матрицу, содержащую N строк и M столбцов, натуральным...

    128 слайд

    Задачи
    128
    «С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой, как на рисунках:

  • Перебор элементов матрицы129Главная диагональ:for i in range(N):
  # работаем...

    129 слайд

    Перебор элементов матрицы
    129
    Главная диагональ:
    for i in range(N):
    # работаем с  A[i][i]
    Побочная диагональ:
    for i in range(N):
    # работаем с  A[i][N-1-i]
    Главная диагональ и под ней:
    for i in range(N):
    for j in range( i+1 ):
    # работаем с  A[i][j]

  • Перестановка строк и столбцов1302-я и 4-я строки:A[2], A[4] = A[4], A[2]2-й и...

    130 слайд

    Перестановка строк и столбцов
    130
    2-я и 4-я строки:
    A[2], A[4] = A[4], A[2]
    2-й и 4-й столбцы:
    for i in range(N):
    A[i][2], A[i][4] = A[i][4], A[i][2]

  • Выделение строк и столбцов1311-я строка:R = A[1][:]2-й столбец:C = []
for row...

    131 слайд

    Выделение строк и столбцов
    131
    1-я строка:
    R = A[1][:]
    2-й столбец:
    C = []
    for row in A:
    C.append(row[2])
    R = A[i]
    или так:
    C = [ row[2] for row in A ]
    главная диагональ:
    D = [ A[i][i] for i in range(N) ]

  • Задачи132«A»: Напишите программу, которая заполняет квадратную матрицу случай...

    132 слайд

    Задачи
    132
    «A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], а затем записывает нули во все элементы выше главной диагонали. Алгоритм не должен изменяться при изменении размеров матрицы.
    Пример:
    Матрица А:
    12 14 67 45
    32 87 45 63
    69 45 14 30
    40 12 35 65
    Результат:
    12 0 0 0
    32 87 0 0
    69 45 14 0
    40 12 35 65

  • Задачи133«B»: Пиксели рисунка закодированы числами (обозначающими цвет) в вид...

    133 слайд

    Задачи
    133
    «B»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните отражение рисунка сверху вниз:
    «С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов:

  • Программирование на языке Python§ 68. Работа с файлами 134

    134 слайд

    Программирование на языке Python
    § 68. Работа с файлами
    134

  • Как работать с файлами?135файлытекстовыедвоичные«plain text»: 
текст, разбиты...

    135 слайд

    Как работать с файлами?
    135
    файлы
    текстовые
    двоичные
    «plain text»:
    текст, разбитый на строки;
    из специальных символов только символы перехода на новую строку
    любые символы
    рисунки, звуки, видео, …

  • Принцип сэндвича136открыть файлработа с  файломзакрыть файлхлебхлебначинкаFin...

    136 слайд

    Принцип сэндвича
    136
    открыть файл
    работа с файлом
    закрыть файл
    хлеб
    хлеб
    начинка
    Fin = open ( "input.txt" )
    Fout = open ( "output.txt", "w" )
    # здесь работаем с файлами
    Fin.close()
    Fout.close()
    файловые переменные-указатели
    "r" - чтение
    "w" – запись
    "a" – добавление
    по умолчанию – на чтение (режим "r")

  • Ввод данных137Fin = open( &quot;input.txt&quot; )s = Fin.readline()    # &quot;1 2&quot;Чтение ст...

    137 слайд

    Ввод данных
    137
    Fin = open( "input.txt" )
    s = Fin.readline() # "1 2"
    Чтение строки:
    Чтение строки и разбивка по пробелам:
    s = Fin.readline().split() # ["1","2"]
    Чтение целых чисел:
    s = Fin.readline().split() # ["1","2"]
    a, b = int(s[0]), int(s[1])
    или так:
    a, b = [int(x) for x in s]
    или так:
    a, b = map( int, s )

  • Вывод данных в файл138a = 1
b = 2
Fout = open( &quot;output.txt&quot;, &quot;w&quot; )
Fout.write...

    138 слайд

    Вывод данных в файл
    138
    a = 1
    b = 2
    Fout = open( "output.txt", "w" )
    Fout.write ( "{:d} + {:d} = {:d}\n".format(
    a, b, a+b) )
    Fout.close()
    Все данные преобразовать в строку!
    !

  • Чтение неизвестного количества данных139пока не конец файла
  прочитать число...

    139 слайд

    Чтение неизвестного количества данных
    139
    пока не конец файла
    прочитать число из файла
    добавить его к сумме
    Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.
    Fin = open ( "input.txt" )
    sum = 0
    while True:
    s = Fin.readline()
    if not s: break
    sum += int(s)
    Fin.close()
    если конец файла, вернёт пустую строку

  • Чтение неизвестного количества данных140Задача. В файле записано в столбик не...

    140 слайд

    Чтение неизвестного количества данных
    140
    Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.
    sum = 0
    Fin = open ( "input.txt" )
    lst = Fin.readlines()
    for s in lst:
    sum += int(s)
    Fin.close()
    прочитать все строки в список строк

  • Чтение неизвестного количества данных141Задача. В файле записано в столбик не...

    141 слайд

    Чтение неизвестного количества данных
    141
    Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.
    sum = 0
    with open ( "input.txt" ) as Fin:
    for s in Fin:
    sum += int(s)
    Не нужно закрывать файл!
    !
    или так:
    sum = 0
    for s in open ( "input.txt" ):
    sum += int(s)

  • Задачи142«A»: Напишите программу, которая находит среднее арифметическое всех...

    142 слайд

    Задачи
    142
    «A»: Напишите программу, которая находит среднее арифметическое всех чисел, записанных в файле в столбик, и выводит результат в другой файл.

    «B»: Напишите программу, которая находит минимальное и максимальное среди чётных положительных чисел, записанных в файле, и выводит результат в другой файл. Учтите, что таких чисел может вообще не быть.

    «C»: В файле в столбик записаны целые числа, сколько их – неизвестно. Напишите программу, которая определяет длину самой длинной цепочки идущих подряд одинаковых чисел и выводит результат в другой файл.

  • Обработка массивов143Задача. В файле записаны в столбик целые числа. Вывести...

    143 слайд

    Обработка массивов
    143
    Задача. В файле записаны в столбик целые числа. Вывести в другой текстовый файл те же числа, отсортированные в порядке возрастания.
    В чем отличие от предыдущей задачи?
    ?
    Для сортировки нужно удерживать все элементы в памяти одновременно.
    !

  • Обработка массивов144Ввод массива:A = []
while True:
  s = Fin.readline()
  i...

    144 слайд

    Обработка массивов
    144
    Ввод массива:
    A = []
    while True:
    s = Fin.readline()
    if not s: break
    A.append ( int(s) )
    Ввод в стиле Python:
    s = Fin.read().split()
    A = list ( map(int, s) )
    Сортировка:
    A.sort()

  • Обработка массивов145Вывод результата:Fout = open ( &quot;output.txt&quot;, &quot;w&quot; )
Fout....

    145 слайд

    Обработка массивов
    145
    Вывод результата:
    Fout = open ( "output.txt", "w" )
    Fout.write ( str(A) )
    Fout.close()

    или так:
    for x in A:
    Fout.write ( str(x)+"\n" )
    [1, 2, 3]
    1
    2
    3
    или так:
    for x in A:
    Fout.write ( "{:4d}".format(x) )
    1 2 3

  • Задачи146«A»: В файле в столбик записаны числа. Отсортировать их по возрастан...

    146 слайд

    Задачи
    146
    «A»: В файле в столбик записаны числа. Отсортировать их по возрастанию последней цифры и записать в другой файл.

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

    «C»: В двух файлах записаны отсортированные по возрастанию массивы неизвестной длины. Объединить их и записать результат в третий файл. Полученный массив также должен быть отсортирован по возрастанию.

  • Обработка строк147Задача. В файле записано данные о собаках: в каждой строчке...

    147 слайд

    Обработка строк
    147
    Задача. В файле записано данные о собаках: в каждой строчке кличка собаки, ее возраст и порода:
    Мухтар 4 немецкая овчарка
    Вывести в другой файл сведения о собаках, которым меньше 5 лет.
    пока не конец файла Fin
    прочитать строку из файла Fin
    разобрать строку – выделить возраст
    если возраст < 5 то
    записать строку в файл Fout

  • Чтение данных из файла148Чтение одной строки:s = Fin.readline()Разбивка по пр...

    148 слайд

    Чтение данных из файла
    148
    Чтение одной строки:
    s = Fin.readline()
    Разбивка по пробелам:
    data = s.split()
    Выделение возраста:
    sAge = data[1]
    age = int ( sAge )
    Кратко всё вместе:
    s = Fin.readline()
    age = int ( s.split()[1] )

  • Обработка строк149Fin = open ( &quot;input.txt&quot; )
Fout = open ( &quot;output.txt&quot;, &quot;w&quot;...

    149 слайд

    Обработка строк
    149
    Fin = open ( "input.txt" )
    Fout = open ( "output.txt", "w" )
    while True:
    s = Fin.readline()
    if not s: break
    age = int ( s.split()[1] )
    if age < 5:
    Fout.write ( s )
    Fin.close()
    Fout.close()
    Полная программа:

  • Обработка строк150lst = Fin.readlines()
for s in lst:
  age = int ( s.split()...

    150 слайд

    Обработка строк
    150
    lst = Fin.readlines()
    for s in lst:
    age = int ( s.split()[1] )
    if age < 5:
    Fout.write ( s )
    или так:
    for s in open ( "input.txt" ):
    age = int ( s.split()[1] )
    if age < 5:
    Fout.write ( s )
    или так:

  • Задачи151«A»: В файле записаны данные о результатах сдачи экзамена. Каждая ст...

    151 слайд

    Задачи
    151
    «A»: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами:
    <Фамилия> <Имя> <Количество баллов>
    Вывести в другой файл фамилии и имена тех учеников, которые получили больше 80 баллов.

    «B»: В предыдущей задаче добавить к полученному списку нумерацию, сократить имя до одной буквы и поставить перед фамилией:
    П. Иванов
    И. Петров
    ...

  • Задачи152«C»: В файле записаны данные о результатах сдачи экзамена. Каждая ст...

    152 слайд

    Задачи
    152
    «C»: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами:
    <Фамилия> <Имя> <Количество баллов>
    Вывести в другой файл данные учеников, которые получили больше 80 баллов. Список должен быть отсортирован по убыванию балла. Формат выходных данных:
    П. Иванов 98
    И. Петров 96
    ...

  • 153Конец фильмаПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СО...

    153 слайд

    153
    Конец фильма
    ПОЛЯКОВ Константин Юрьевич
    д.т.н., учитель информатики
    ГБОУ СОШ № 163, г. Санкт-Петербург
    kpolyakov@mail.ru
    ЕРЕМИН Евгений Александрович
    к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
    eremin@pspu.ac.ru

Получите профессию

HR-менеджер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 624 860 материалов в базе

Скачать материал

Другие материалы

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 27.04.2020 23135
    • PPTX 5.2 мбайт
    • 380 скачиваний
    • Рейтинг: 4 из 5
    • Оцените материал:
  • Настоящий материал опубликован пользователем Демидова Елена Владимировна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

    Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

    Удалить материал
  • Автор материала

    Демидова Елена Владимировна
    Демидова Елена Владимировна
    • На сайте: 3 года и 3 месяца
    • Подписчики: 0
    • Всего просмотров: 95482
    • Всего материалов: 221

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой

Курс профессиональной переподготовки

Менеджер по туризму

Менеджер по туризму

500/1000 ч.

Подать заявку О курсе

Курс профессиональной переподготовки

Теория и методика обучения информатике в начальной школе

Учитель информатики в начальной школе

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 94 человека из 34 регионов

Курс повышения квалификации

Использование компьютерных технологий в процессе обучения информатике в условиях реализации ФГОС

36 ч. — 144 ч.

от 1700 руб. от 850 руб.
Подать заявку О курсе
  • Сейчас обучается 140 человек из 44 регионов

Курс профессиональной переподготовки

Математика и информатика: теория и методика преподавания в образовательной организации

Учитель математики и информатики

500/1000 ч.

от 8900 руб. от 4450 руб.
Подать заявку О курсе
  • Сейчас обучается 680 человек из 79 регионов

Мини-курс

Стратегии и инструменты для эффективного привлечения и удержания клиентов

6 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Развитие предметно-практических действий, игровых навыков и математических представлений у детей раннего возраста

6 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Проектный подход к рекламе: эффективные стратегии и инструменты

8 ч.

1180 руб. 590 руб.
Подать заявку О курсе