Глава 4. Программирование (язык Python)

До загрузки: 30 сек.



Благодарим, что скачиваете у нас :)

Если, что - то:

  • Поделится ссылкой:
  • Документ найден в свободном доступе.
  • Загрузка документа - бесплатна.
  • Если нарушены ваши права, свяжитесь с нами.
Формат: pdf
Найдено: 07.07.2020
Добавлено: 30.09.2020
Размер: 1.3 Мб

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
1 http://kpolyakov. spb .ru

07.04.2019
Глава 4. П рограммирование (язык Python )
Услоgu_h[hagZq_gby
– задание выполняется на компьютере
– задание выполняется в тетради
– задание выполняется устно
– задание выполняется c использованием дополнител ь-
ных источников (литературы, Интернета)
Матери ал, который изучается только на углублённом уровне,
выделен знаками



§ 19. Симhevgu_kljhdb
Ключевые слова :
символьная строка
длина строки
сцепление строк
подстрока
удаление симв олов
вставка символов
поиск подстроки
Что такое симhevgZykljhdZ?
Если в середине XX века первые компьютеры созд авались,
прежде всего, для выполнения сложных математических расч ё-
тов, то сейчас они чаще всего обрабатывают текстов ую (си м-
вольн ую ) информаци ю .
В языке Python работы со строками использу ется спец и-
альны й тип данных str (от английского слова string ), которы й
позволя ет
работать с целой символьной строкой как с единым объектом;
использовать строки переменной длины.
Пер еменная типа str называется строковой или символьной .
Символьная строка –=это последовательность символов. =

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
2 http://kpolyakov. spb .ru

07.04.2019
Используя дополнительные источники, выясните значение
ан глийского слова string .
Новое значение присваивается строковой переменной с п о-
мощью оператора присваивания:
s = "Вася пошёл гулять"
Проверить её тип можно следу ю щей командой :
print ( type (s) )
которая выведет

Для ввода значени я строковой переменной с клавиатуры
этого используется уже знакомая нам функция input :
s = input ()
Встроенная функция len определяет длину строки – кол и-
чество сим волов в ней. Вот так в переменную n записывается
длина строки s:
n = len(s)
Напишите полную программу, которая вводит строку с
клави атуры и выводит на экран её длину. Проверьте, как
эта програ м ма реагирует на строку с пробелами.
Сраg_gb_kljhd
Строки мо жно сравнивать между собой так же, как числа.
Например, можно проверить равенство двух строк:
password = input( "В_^bl_ пароль :" )
if password == "sEzAm":
print ( "Слушаюсь и поbgmxkv" )
else :
print ( "No pasaran !" )
Можно также определить, какая из д вух строк больше, к а-
кая – меньше. Если строки состоят только из русских или тол ь-
ко из латинских букв, то меньше будет та строка, которая идет
раньше в алфавитном списке. Например, слово « паровоз » будет
«меньше», чем слово « пароход »: они отличаются в пятой букве и
«в» < « х». Это можно проверить экспериментально, например, с
помощью такой программы:

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
3 http://kpolyakov. spb .ru

07.04.2019
s1 = " пароha "
s2 = " пароход "
if s1 < s2:
print( s1, "<", s2 )
elif s1 == s2:
print( s1, "=", s2 )
else:
print( s1, ">", s2 )
Но откуда компьютер знает, что такое алфавитный пор я-
док? Оказывается, при сравнении используются коды символов
(вспомните материал 8 класса) . В современных кодировках 1 и
русские, и английские буквы расположены в алфавитном п о-
рядке, то есть код буквы « в» меньше, чем код буквы « х».
С п омощью программы сравните пары слов и сделайте вы -
во ды:
пар – парк Пар – пар
steam – Пар Steam – steam
5Steam – Steam
Не используя программу, сравните пары слов:
парта – парк ПАрта - Парк
СПАМ – Spam ПОЧТА – spam
ПО4та – ПОЧта почТА - Post
55 – 66 9 - 128
Сложение и умножение
Оператор «+» используется для «сложения» (объединения,
сцепления) строк. Эта операция иногда называется конкатен а-
ция . Например:
s1 = " При_l "
s2 = " Вася "
s = s1 + ", " + s2 + "!"

1 Раньше использовалась кодировка KOI 8-R, в которой русские буквы стояли не
по алфавиту.

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
4 http://kpolyakov. spb .ru

07.04.2019
Запишите в тетради, какое значение б удет иметь
переменная s после выполнения этого фрагмента програм -
мы. Проверьте о т вет с помощью компьютера.
В язык PWKRQ$-!- %3 с-
ло: она заменяет многократное сложение. Например,
s = "Уа! Уа! Уа! Уа! Уа! Уа! Уа! Уа! Уа! Уа! "
можно заменить на
s = "Уа! "*10
или
s = 10*"Уа! "
Обращение к симheZf
В PWKRQ)    
причём нумерация, как и во многих других языках программ и-
рования ( С, C ++, Java ), всегда начинается с нуля.
Индекс можно пон имать как смещение символа от начала
строки. Первый по счёту символ имеет нулевое смещение (нах о-
дится в самом начале строки), поэтому его индекс – 0:
индексы = 0 1 2 3 4 5 6
hello = " П = р= и= в= е= т= >= ?=
К любому символу можно обратиться по индексу, записав
индекс в квадратных скобках после имени строки:
print( hello[1] ) # р
print( hello[5] + hello[2] + "к" ) # ти к
В языке PWKRQ можно указывать отрицательные индексы.
Это значит, что отсчёт ведётся от конца строки, так что символ
hello[ -1] – это последний символ строки hello :
индексы = –7 –6 –5 –4 –3 –2 –1
hello = " П = р= и= в= е= т= >= ?=
Чтобы рассчитать « обычную » позицию символа в строке, к
отрицательному индексу нужно добавить длину строки. Напр и-
мер,
hello [-1] = hello [len (hello )-1] = hello [6]
Пре дыдущую программу можно было переписать, используя
отрицательные индексы:

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
5 http://kpolyakov. spb .ru

07.04.2019
print( hello[ -6] ) # р
print( hello[ -2] + hello[ -5] + "к" ) # тик
Если указать неправильный индекс, произойдёт ошибка – вы-
ход за границы строки, и программа заверши тся аварийно. Для
строки из семи символов правильные индексы – от « –7» до 6.
Перебор k_okbfолов
Поскольку к символу можно обращаться по индексу, для
перебора всех символов можно использовать цикл по переме н-
ной, которая будет принимать все возможные знач ения инде к-
сов.
Пусть нужно вывести в столбик коды всех символов строки с
именем s. Д лину строки можно найти с помощью функции len ,
индекс первого символа равен 0, а индекс последнего равен
len(s) -1. Таким образом, все допустимые индексы – это посл е-
довател ьность, которую строит вызов функции range(len(s)) .
Перебор можно выполнить так :
for i in range(len(s)):
print ( s[i], ord (s[i] ) )
В каждой строке сначала выводится сам символ, а потом – его
код, который возвращает встроенная функция ord .
В языке PWKRQ с уществует еще один удобный способ пер е-
бора всех элементов строки:
for c in s:
print( c, ord(c) )
Заголовок такого цикла можно «прочитать» так: «для всех c,
входящих в состав s». Это означает, что все символы строки s, с
первого до последнего, по очереди оказываются в переменной c,
и в теле цикла нам остаётся вывести код символа c.
В отличие от большинства современных языков программ и-
рования, в PWKRQ нельзя изменить символьную строку, п о-
скольку строка – это неизменяемый объект. Это значит, что оп е-
ратор пр исваивания s[5]="а" не сработает – будет выдано с о-
общение об ошибке.

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
6 http://kpolyakov. spb .ru

07.04.2019
Тем не менее, можно составить из символов существующей
строки новую строку, и внести в неё нужные изменения. Прив е-
дём полную программу, которая вводит строку с клавиатуры,
заменяет в ней все буквы « э» на буквы « е» и выводит получе н-
ную строку на экран 2.
s = input ( "В_^bl_kljhdm)
sNew = ""
for c in s:
if c == " э": c = " е"
sNew += c
print ( sNew )
Здесь в цикле
for c in s:
...
перебираются все символы, входящие в строку s. В теле цикла
проверяем значение переменной c (это очередной символ исхо д-
ной строки): если оно совпадает с буквой « э», то заменяем его на
букву « е»
if c == " э": c = " е"
и добавляем в конец новой строки sNew с помощью оператора
сложения :
sNew += c
Вспомните, чем отличается запись c == "э" от записи
c = "э".
Запишите решение этой задачи, используя цикл «пока»
(while ).
Срезы
Для того, чтобы выделить часть строки ( подстроку ), в языке
PWKRQ применяется операция получения среза (англ. slicing ).
Например, s[3:8] озна чает «символы строки s с 3 -го по 7 -й» (то

2 И. Ильф и Е. Петров в романе «Золотой теленок» описывают пишущ ую
машинк у «с турецким акцентом» , в которой не хватало буквы «е», и е ё пр и-
шло сь заменить буквой «э» .

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
7 http://kpolyakov. spb .ru

07.04.2019
есть до 8 -го, не включая его). Следующий фрагмент копирует в
строку s1 символы строки s с 3 -го по 7 -й (всего 5 символов):
s = "0123456789"
s1 = s[3:8]
Запишите в тетради, какое значение будет иметь
переменна я s1 после выполнения этого фрагмента прог -
раммы. Проверьте ответ с помощью компьютера.
Можно использовать и отрицательные индексы – в этом
случае отсчёт выполняется с конца строки:
s1 = s[ -7: -2] # s1 = "34567"
Для получения « обычной » позиции символа в с троке к отриц а-
тельному значению добавляется длина строки. Например, вт о-
рой индекс « –2» можно заменить на len(s 1)-2.Это означает,
что п оследние два символа не входят в срез.
Если первый индекс не указан, считается, что он равен н у-
лю (берём начало строки), а если не указан второй индекс, то в
срез включаются все символы до конца строки. Например:
s = "0123456789"
sFirst = s[:4] # sFirst = "0123"
sLast = s[ -4:] # sLast = "6789"
Срезы позволяют легко выполнить реверс строки (перест а-
вить её символы в обрат ном порядке ):
sReversed = s[:: -1]
Так как начальный и конечный индексы элементов строки не
указаны, задействована вся строка. Число « –1» означает шаг
изменения индекса и говорит о том, что все символы перебир а-
ются в обратном порядке.
Используя только опера ции среза и «сложения» строк, п о-
стройте из строки
s = 'информатика'
как можно больше слов русского языка. Постарайтесь и с-
пользовать наименьшее возможное число операций. Пр о-
верьте ваши решения с помощью программы.

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
8 http://kpolyakov. spb .ru

07.04.2019
Приведите несколько способов построения с троки
"А. Семёно" из строки
s = "Семёно:g^j_c "
Какой из них лучше? Как вы сравнивали эти способы?
Встроенные методы
В PWKRQ!' !   )# алгоритмов для
работы с символьными строками. Многие из них вызываются с
помощью точечной запис и, они называются методами обрабо т-
ки строк. Например, методы upper и lower позволяют переве с-
ти строку соответственно в верхний и нижний регистр:
s = "aAbBcC"
sUp = s.upper() # sUp = "AABBCC"
sLow = s.lower() # sLow = "aabbcc"
Слева от точки записываетс я имя строки (или сама строка в к а-
вычках), к которой нужно применить метод, а справа от точки –
название метода. Например, возможна такая запись:
sWow = "Wow!".upper() # "WOW !"
Здесь метод upper применяется к строке « Wow !».
Методы строк мы уже использов али, когда выводили да н-
ные на экран с помощью метода format :
a = 5
b = 4
print( "{}+{}={}".format(a,b,a+b) )
Ещё один метод, isdigit , проверяет, все ли символы стр о-
ки – цифры, и возвращает логическое значение:
s = " ab 1c"
print ( s.isdigit() ) # False
s = " 123"
print ( s.isdigit () ) # True
Полезный метод strip (по -английски – лишать) удаляет
пробелы в начале и в конце строки:
sRaw = " Python & C++ "
sClear = sRaw.strip() # sClear = "Python & C++"

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
9 http://kpolyakov. spb .ru

07.04.2019
Это метод удобно использовать для обработки ввода пользо ва-
теля, когда пробелы в начале и в конце строки не нужны.
О других встроенных методах обработки строк вы можете
узнать в литературе или в Интернете.
Удаление и klZка
Для удаления части строки нужно составить новую строку,
объединив части исходной строки до и после удаляемого учас т-
ка:
s = "0123456789"
s = s[:3] + s[9:]
Запишите в тетради, какое значение будет иметь пе -
ременная s после выполнения этого фрагмента програм -
мы. Проверьте о т вет с помощью компьютера.
Срез s[:3] означает «от начала строки д о символа s[3] , не
включая его», а запись s[9:] – «все символы, начиная с s[9]
до конца строки». Таким образом, в переменной s остаётся зн а-
чение «0129».
С помощью срезов и сцепления строк можно также вставить
новый фрагмент внутрь строки:
s = "0123456789 "
s = s[:3] + "ABC " + s[3:]
Запишите в тетради, какое значение будет иметь
переменная s после выполнения этого фрагмента прог рам -
мы.
Поиск в симhevguokljhdZo
В Python существует метод для поиска подстроки (и отдел ь-
ного символа) в символьной строке, он называется find (по -
английски – найти). В скобках нужно указать образец для п о-
иска, это может быть один символ или символьная строка:
s = "Здесь был Вася."
n = s.find ( "с" ) # n = 3
if n >= 0:

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
10 http://kpolyakov. spb .ru

07.04.2019
print( " Номер симheZ ", n )
else :
print ( "Симheg_gZc^_g ." )
Метод find возвращает целое число – индекс символа, с
которого начинается образец (буква « с») в строке s. Если образец
в строке встречается несколько раз, функция находит первый из
них. В рассмотренном примере в переменную n будет записано
число 3.
Выясните экспериментально, какое значение возвращает
метод find , если образец для поиска не найден в строке.
Аналогичный метод rfind (от англ. reverse find – искать в
обратную сторону) ищет последнее вхождение образца в строку.
Для той же строки s, что и в предыдущем примере, метод rfind
вернёт 12 (индекс последней буквы « с»):
s = "Здесь был Вася."
n = s.rfind ( "с" ) # n = 12
Как можно найти вторую букву «с» с начала строки?
Вводится строка, в которой сначала записана фамилия
человека, а затем через п робел – его имя, например,
"Семёнов Андрей" . Запишите операторы, которые позво -
ляют :
найти номер пробела, разделяющего фамилию и имя,
и записать его в переменную p;
выделить из строки фамилию и записать её в
переменную fam ;
выделить из строки имя и записат ь его в переменную
name ;
приписать перед фамилией первую букву имени,
точку и пр обел.

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
11 http://kpolyakov. spb .ru

07.04.2019
ПреобразоZgbykljhdZ число»
Пусть символьная строка содержит запись числа. С таким
значением нельзя выполнять арифметические операции , пот о-
му что это си м волы, а не число .
Чему будут равны значения переменных n и s после выпо л-
нения этих команд?
n = 12 + 34
s = '12' + '34'
Для того чтобы с числовыми данными можно было выпо л-
нять вычисления , нужно цепочк у символов в числовое знач е-
ние. В языке PWKRQ есть встроенные функции для преобраз о-
вания типов данных, некоторые из них мы уже использовали:
int – переводит строку в целое число;
float – переводит строку в вещественное число;
str – переводит целое или вещественное число в строку.
Приведём прим ер преобразования строк в числовые знач е-
ния:
s = "123"
n = int( s ) # n = 123
s = "123.456"
x = float ( s ) # x = 123.456
Если строку не удалось преобразовать в число (например,
если в ней содержатся буквы), возникает ошибка и выполнение
программы заве ршается аварийно.
Какие из этих строк можно преобразовать в целое число,
какие – в вещественное:
"45" "5 р." "14.5" "14;5"
"tu 154" "543.0" "(30)" "1E3"
Теперь покажем примеры обратного преобразования:
n = 123
s = str ( n ) # s = "123"
x = 12 3.456
s = str ( x ) # s = "123.456"

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
12 http://kpolyakov. spb .ru

07.04.2019
Эти операции всегда завершаются успешно , ошибк и быть не
может.
Функция str использует правила форматирования, уст а-
новленные по умолчанию. При необходимости можно использ о-
вать собственное форматирование, например:
n = 12 3
s = "{:5}". format (n) # s = " ◦◦ 123"
Здесь значение переменной n записано в 5 позициях, то есть в
начале строки будут добавлены два пробела.
Для вещественных чисел можно использовать форматы f (с
фиксированной запятой) и e (научный формат, с плавающей
за пятой):
x = 123.456
s = "{:7.2f}".format(x) # s = " ◦123.46"
s = "{:10.2e}".format(x) # s = " ◦◦ 1.23e+02"
Формат « 7.2f » обозначает «вывести в 7 позициях с двумя
знаками в дробной части», а формат « 10.2e » – «в научном фо р-
мате в 10 позициях с двумя знаками в дробной части».

Практическая работа №12. Посимвольная обработка строк
Практическая работа №13. Обработка строк. Функции
Практическая работа №14. Преобразования «строка число»
Выh^u:
Символьная строка – это последовательность символов.
Длина строки – это количество символов в строке.
Подстрока – это часть символьной строки.
При обращении к отдельному символу строки его номер зап и-
сывают в квадратных скобках. Нумерация символов в строке в
языке PWKRQ% -!-.
Знак «+» при работе со строками означает объединение (ко н-
катенацию) строк.

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
13 http://kpolyakov. spb .ru

07.04.2019
Для о бработки символьных строк используют встроенные
функции стандартной библиотеки.
Функция поиска подстроки возвращает номер символа, с кот о-
рого начинается подстрока, или –1 в сл учае неудачи.
Строку можно преобразовать в число для того, чтобы затем
выполнять с ним вычисления. Число можно преобразовать в
символьную строку.
Нарисуйте интеллект -карту этого параграфа.
Вопросы и задания
1. Во многих языках (в том числе и в P ython ) можно использ о-
вать массивы символов, то есть массивы, каждый элемент
которых – один с имвол. Чем отличается строка от массива
си м волов ?
2. Ч ем отличается действие оператора «+» для чисел и для
символьных строк ?
3. Как определить, что при поиске в строке образец не найден?
4. Как бы вы искали первый символ «с» с конца строки , если
бы не было метода rfind ?
Задачи
1. Напишите программу, которая заменяет в символьной стр о-
ке все точки на нули и все буквы X на единицы. Например,
из строки ' ..XX..X. ' должна получиться строка '00110010’.
2. Напишите программу, которая выполняет инверсию битов в
символьной строке: заменяет в ней все нули на единицы и
наоборот. Например, из строки «00110010 » должна пол у-
читься строка «11001101 ».
3. Введите битовую строку и дополните её последним битом,
который должен быть равен 0, если в исходной строке чё т-
ное число единиц, и равен 1, ес ли нечётное (в получивше й-
ся строке должно всегда быть чётное число единиц). Н а-
пример, из строки «00110010 » должна получиться строка
«001100101 ».

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
14 http://kpolyakov. spb .ru

07.04.2019
4. Напишите программу, которая принимает символьную
строку, с одержащую фамилию и имя (они раздел ены одним
пробелом ). Нужно построить новую строку, в которой зап и-
сан инициал (первая буква имени с точкой) и через пр о-
бел – фамилия.
5. Напишите программу, которая принимает строку, содерж а-
щую ф амилию, имя и отчество человека (каждая пара слов
разделена о дним пробелом). Нужно построить новую строку,
в которой записаны инициалы (первые буквы имени и отч е-
ства с точками после них) и через пробел – фамилия.
6. Напишите программу, которая вводит адрес файла и «ра з-
бирает» его на части, разделенные знаком «/». Каждую
часть нужно выве сти в отдельной строке.

7. Напишите программу, которая определяет количество слов
в строке. Слова разделены пробелами, причём в начале
строки, в конц е строки и между словами может быть сколько
угодно пробелов.
8. Напишите программу, кото рая принимает символьную
строку и проверяет, является ли она перевёртышем (слово -
перевёртыш или палиндром читается одинаково в обоих
направлениях, например, слово «казак»).
9. Напишите программу, которая «переворачивает» введённое
слово , то есть переставляет буквы так, чтобы первая буква
стала после дней, вторая – предпоследней и т.д.
10. Напишите программу, которая вычисляет сумму двух нат у-
ральных чисел, записанную в виде символьной строки, н а-
пример, «1+25 ».
11. Напишите программу, которая вычисляет сумму трёх нат у-
ра льных чисел, записанную в виде символьной строки, н а-
пример, «1+25+56 ».
12. *Напишите программу, которая вычисляет сумму неизвес т-
ного количества натуральных чисел, записанную в виде
символьной стр оки, например, «1+25+12+34+89 ».

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
15 http://kpolyakov. spb .ru

07.04.2019
§ 20. Обра ботка массиh\
Ключевые слова :
массив
перестановка элементов
выход за границы массива
линейный поиск
сортировка
Современные компьютеры работают с огромны ми масс и-
вами данных. При этом размер программы не зависит от разм е-
ра массива: можно написать очень ко роткую программу, кот о-
рая обрабатывает милл иарды чисел.
Из курса 8 класса вы уже знаете, как найти сумму элеме н-
тов массива и его максимальный (минимальный) элемент, о п-
ределить количес тво элементов, удовлетворяющих условию. В
этом параграфе мы изучим некото рые более сложные алгори т-
мы.
Вспомните и запишите в тетрадь, как
выделить место в памяти под массив из N элементов;
заполнить массив нулями;
заполнить массив натуральными числами от 1 до N ;
заполнить массив случайными числами из отрезка
[50,100] ;
найти сумму всех элементов массива;
найти сумму чётных элементов массива;
найти количество отрицательных элементов массива;
найти максимальный элемент массива.
ПерестаноdZ элементов массиZ
Во многих задачах нужно переставлять элементы массива,
то есть требуетс я поменять местами значения двух ячеек пам я-
ти.
Представьте себе, что в кофейной чашке налит сок, а в
стакане – кофе, и вы хотите, чтобы было наоборот. Что
вы сделаете?

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
16 http://kpolyakov. spb .ru

07.04.2019
Вернёмся к программированию. Чтобы поменять местами
значения двух переменных, a и b, н ужно использовать третью
переменную того же типа:
с = a
a = b
b = c
Перестановка двух элементов массива, например, A [i] и A [k],
выполн яется так же:
с = A[i]
A[i] = A[k]
A[k] = c
Кроме того, в языке PWKRQ есть красивый приём перестановки
без использования вспомогательной переменной :
A[i], A[k] = A[k], A[i]
Р ассмотрим несколько задач, в которых требуется пер е-
став ля ть элементы массива.
Задача 1. Массив A содержит чётное количество элементов
N . Нужно поменять местами пары соседних элементов: первый
со вторым , третий – с четвёртым и т.д. (Рис. 4.1 ).

Рис. 4.1.
С каким элементо м нужно поменять местами элемент
A [i]? Зависит ли ваш ответ от свойств числа i?
Сергей написал такой алгоритм для решения задачи 1:
for i in range(N):
# поменять местами A[i] и A[i+1]
Выполните его вручную этот алгоритм для массива [1, 2,
3, 4 ] (N = 4). Объясните результат. Найдите ошибки в
алгоритме Сергея .
Обратите внимание, что при выполнении алгоритма Се р-
гея на последнем шаге цикла мы будем менять местами эл е-
0 1 2 3 N–2 N–1
7 12 38 5 40 23
0 1 2 3 N–2 N–1
12 7 5 38 23 40

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
17 http://kpolyakov. spb .ru

07.04.2019
мент A [N –1] с несуществующим элементом A [N ]. Это вызовет
ошибку, которая называется «выход за границы массива». Но
даже если испол ьзовать диапазон range( N-1), программа все
равно будет работать неправильно , то есть прив едёт к неверн о-
му решению зад ачи 1 . Получится , что первый элемент просто
«перее дет » на место последн его.
Для того чтобы исправить программу, нужно изменять п е-
ременную i с шагом 2:
N = len(A)
for i in range(0,N -1,2):
A[i], A[i+1] = A[i+1], A[i]
print( *A )
Предложите другое решение этой задачи, записав нужные
операторы в теле цикла while .
i = 0
while i < N -1:
...
Ре_jk массиZ
Задача 2. Требуется в ыполнить реверс массива , то есть п е-
реставить элементы массива в обратном порядке, так чтобы
первый элемент стал послед ним, а последний – первым:

Рис. 4.2.
С каким элементом нужно поменять местами элемент
A [0]? элемент A [1]? элемент A [i]?
Если индекс первого элемента в паре увеличивается на 1, а
индекс второго элемента уменьшится на 1, что можно
сказа ть о сумме индексов этих элементов?
0 1 2 N–3 N–2 N–1
7 12 5 34 40 23
0 1 2 N–3 N–2 N–1
23 40 34 5 12 7

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
18 http://kpolyakov. spb .ru

07.04.2019
В этой задаче с умма индексов элементов, участвующих в
обмене, для всех пар равна N – 1, поэтому элемент с номером i
должен меняться местами с (N – 1 – i)-м элементом.
Выполните вручную следующий алгоритм для массива [1,
2, 3, 4 ] (N = 4). Объясните результат. Найдите ошибки в
этом алгоритме .
for i in range(N):
# поменять местами A[i] и A[N -1-i]
Для того, чтобы не выполнять реверс дважды , нужно ост а-
новить цикл на середине массива:
for i in range( N // 2 ):
# поменя ть местами A[i] и A[N -1-i]
Запишите в тетради операторы, которые нужно
добавить в тело последнего цикла.
Запишите в тетради другое решение задачи реверса
массива , которое использует цикл с условием (while ).

Линейный поиск  м асси_
Очень часто требуется найти в массиве заданное значение
или опред елить, что его там нет. Для этого нужно просмотреть
все элементы массива с первого до последнего. Как только на й-
ден элемент, равный заданному значению X , надо завершить
поиск и вывест и результат. Такой алгоритм поиск а называется
линейным поиском .
Сколько операций сравнения придётся выполнить, если в
массиве N элементов? В каком случае количество срав -
нений будет на именьшим? наибольшим?
Катя торопилась и написала такой алгоритм линей ного
поиска:
i = 0
while A[i] ! = X:
i += 1
print ( "A[{}]={}". format( i,X) )

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
19 http://kpolyakov. spb .ru

07.04.2019
Проверьте, правильно ли сработает алгоритм, если
искать в массиве [1, 2, 3 ] число 2? число 4?
Этот алгоритм хорошо работает, если нужный элемент в
массиве есть, однако приведет к ошибке, если такого элемента
нет – получится зацикливание и выход за границы массива.
Чтобы этого не произошло, в условие после while нужно доб а-
вить еще одно ограничение: i < N . Если после окончания цикла
это условие нарушено, значит, поиск был неудачным – элеме н-
та нет:
i = 0
while i < N and A[i] != X:
i += 1
if i < N:
print( "A[{}]={}".format(i,X) )
else:
print( "Не нашли!" )
Отметим одну тонкость. При i N элемента A [i] в массиве
нет. В этом случае проверка условия A [i] != X приведёт к вых оду
за границы массива , и программа завершится аварийно.
К счастью, этого можно избежать. Если первая часть сло ж-
ного условия с операцией and ложна, то вторая часть не пров е-
ряется 3 – уже понятно, что всё условие тоже ложно. Поэтому в
сложном условии
i < N and A[i]!= X
сначала нужно записать именно отношение i < N . Если это у с-
ловие ложно, цикл сразу завершится.
Возможен ещё один поход к решению этой задачи. Испол ь-
зуя цикл с переменной, можно перебрать все элементы массива
и досрочно завершить цикл, если найдено требуемое значение.
nX = -1
for i in range(N):
if A[i] == X:

3 Во многих современных языках (например, в Python, C++, Javascript, PHP)
такое поведение гара нтировано стандартом.

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
20 http://kpolyakov. spb .ru

07.04.2019
nX = i
break
if nX >= 0:
print( "A[{}]={}".format(nX,X) )
else:
print( "Не нашли!" )
Для выхода из цикла используется оператор break , индекс
найденного элемента сохраняется в пере менной nX . Если её
значение осталось равным « –1» (не изменилось в ходе выполн е-
ния цикла), то в массиве нет элемента, равного X .
Последний пример можно упростить, используя особые во з-
можности цикла for в языке Python:
for i in range(N):
if A[i] == X:
print( "A[{}]={}".format(i,X) )
break
else:
print( "Не нашли!" )
Здесь мы выводим результат сразу, как только нашли нужный
элемент, а не после цикла. Слово else после цикла for нач и-
нает блок, который выполняется при нормальном завершении
цикла (без п рименения break ). Таким образом, сообщение «Не
нашли!» будет выведено только тогда, когда условие в операт о-
ре if ни разу не выполнилось.
В языке Python возможен и другой способ решения этой з а-
дачи, использующий встроенные методы для массивов (сп и-
сков). Опе ратор in определяет, есть ли нужный элемент в ма с-
сиве. Он возвращает логическое значение ( True или False ):
if X in A:
print ( "Нашли!" )
else :
print ( "Не нашли!" )
А метод index возвращает индекс первого найденного эл е-
мента, равного X :
nX = A.index(X)

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
21 http://kpolyakov. spb .ru

07.04.2019
Поэтому поиск элемента, равного X , и определение его индекса
можно записать так:
if X in A:
nX = A.index(X)
print( "A[{}]={}".format(i,X) )
else:
print( "Не нашли!" )

Сортировка массивов
Сортировка – это расстановка э лементов списка (массива) в
заданном порядке.
Возникает естественный вопрос: «зачем сортировать да н-
ные?». На него легко ответить, вспомнив, например, работу со
словарями: сортировка слов по алфавиту облегчает поиск ну ж-
ной информации.
Для чисел обычно испо льзуют сортировку по возрастанию
(каждый следующий элемент больше предыдущего) или убыв а-
нию (следующий элемент меньше предыдущего). Если в масс и-
ве есть одинаковые элементы, их можно расставить по неуб ы-
ванию (каждый следу ю щий элемент не меньше предыдущего)
или невозрастанию.
Математики и п рограммисты изобрели множество способов
сортировки. В целом их можно разделить на две группы: 1) пр о-
стые, но медленно работающие (на больших массивах) и 2)
сложные, но быстрые.
Мы изучим один из простых методов, который на зывается
методом выбора . Для примера будем рассматривать сортиро в-
ку по возра станию (неубыванию).
Предположим, что мы нашли минимальный элемент
массива. Где он должен размещаться в отсортированном
ма ссиве?
Запишите в тетради фрагмент программы для поиска
номера минимального элемента массива.

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
22 http://kpolyakov. spb .ru

07.04.2019
Для того чтобы поставить на место минимальный элемент,
мы просто поменяем его мест ами с первым элементом массива.
Запишите в тетради фрагмент программы, который
меняет местами элементы A [0] и A [nMin ].
После того как мы установили на место первый (мин и-
мальный) элемент, находим минимальный из оставшихся и
ставим его на второе место, и т.д. Полный алгоритм записыв а-
ется в виде вложе нного цикла:
for i in range(N -1):
nMin = i
for j in range(i+1, N):
if A[j] < A[nMin]: nMin = j
if nMin != i:
A[i], A[nMin] = A[nMin], A[i]
Фоном выделен поиск номера минимального элемента в той
части массива, которая начинается с элемента A [i].
На первом шаге внешнего цикла значение i равно 0, и мы
ставим на место первый элемент , A [0] . На следующем шаге
i = 1, то есть мы ищем минимальный элемент среди всех, кроме
самого пе рвого, и т.д.
Обратите внимание, что внешний цикл выполняется N – 1
раз (а не N ). Этого достаточно, потому что если N – 1 эл ементов
стоят на своих местах, то последний тоже стоит на своём месте
(др угого свободного места для него нет).
Какой результат можно гарантировать , если внешний
цикл (по переменной i) выполнить только 1 раз? только 3
раза?
Практическая работа №15. Перестановка элементов массива
Практическая работа №16. Линейный поиск в массиве
Практическая работа №17. Сортировка

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
23 http://kpolyakov. spb .ru

07.04.2019
Выh^u:
Выход за границы массива – это обращение к элементу масс и-
ва с несуществующим индексом.
Линейный поиск – это перебор всех элементов массива до тех
пор, пока не будет найден нужный элемент или не закончи тся
мас сив.
Сортировка – это расстановка элементов списка (массива) в
заданном порядке. Данные сортируют для того, чтобы уск о-
рить посл едующий поиск.
Для чисел обычно используют сортировку по возрастанию (н е-
убыванию) или убыванию (невозрастанию).
Нарисуйте интелл ект -карту этого параграфа.
Вопросы и задания
1. Что такое выход за границы массива? Что опаснее – чтение
или з апись данных за границами массива ?
2. На какой идее основан метод сортировки выбором?
3. Объясните, зачем нужен вложенный цикл в алгоритме со р-
тировки.
4. Как нужно изменить программу сортировки, чтобы элеме н-
ты ма ссива были отсортированы по убыванию?
Задачи
1. В переменных записаны значения a = 1, b = 2 и с = 3. Как
изменятся значения переменных после выполнении алг о-
ритма:
c = a
b = a
a = c
Исправьте один символ так , чтобы получился правильный
алгоритм обмена значений пер еменных a и b.
2. Что произойдет с массивом [1, 2, 3, 4 ] (N = 4) при выполн е-
нии следующего фрагмента пр ограммы:
for i in range(N -1):
A[i] = A[i+1]

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
24 http://kpolyakov. spb .ru

07.04.2019
3. Что произойдет с массивом [1, 2, 3, 4 ] (N = 4) пр и выполн е-
нии следующего фрагмента пр ограммы:
for i in range( N-1):
A[i+1] = A[i]
4. Напишите программу, которая меняет местами пары сосе д-
них элементов, кроме первого и последнего.
5. Напишите программу, которая выполняет реверс отдельно
первой и второй половин массива. При изменении значения
N на другое чётное натуральное число программа должна
работать правильно без дополнительных изменений.
6. Напишите программу, которая сортирует массив в порядке
убыв ания.
7. Напишите программу, которая сортирует массив по возра с-
танию последней цифры числа.
8. Напишите программу сортировки массива по возрастани ю ,
в которой на каждом шаге ище тся максимальный элемент.

9. Что произойдет с массивом [1, 2, 3, 4, 5, 6 ] (N = 6) при в ы-
полнении следующего фра гмента пр ограммы:
i = 0
while i < N-1:
c = A[i]
A[i] = A[i+1]
A[i+1] = A[i+2]
A[i+2] = c
i = i + 3
10. Напишите программу, которая выполняет циклический
сдвиг массива влево. При этом элемент A [1] переходит на
место A [0], A [2] – на место A [1] и т.д., а элемент A [0] «п ере-
езж ает» на место п оследнего:

0 1 N–2 N–1
12 5 34 40 23 7

0 1 2 N–2 N–1
7 12 5 34 40 23

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
25 http://kpolyakov. spb .ru

07.04.2019
11. Напишите программу, которая выполняет циклический
сдвиг ма ссива вправо.
12. Заполните массив случайными числами и выполните р е-
верс для части массива между элементами с индексами K и
M (вк лючая эти элементы). Значения K и M вводятся с
клавиат уры.
13. Напишите программу, которая находит максимальный и
минимальный из чётных положительных элементов масс и-
ва. Если в массиве нет чётных положительных элементов,
нужно вывести соо бщение об этом.
14. Введит е массив с клавиатуры и найдите количество эл е-
ментов, имеющих максимальное значение.
15. Напишите программу, которая находит индекс первого эл е-
мента массива , равного введённому числу X . Программа
должна вывести ответ «не найден», если в массиве таких
элеме нтов нет.
16. Напишите программу, которая находит индекс последнего
элемента массива , равного вв едённому числу X .
17. Напишите программу, которая находит индексы всех эл е-
ментов массива , равных введённ ому числу X .
18. Напишите программу, которая выполняет неполную сорт и-
ровку массива: ставит в начало массива K самых меньших
по величине элемент ов в порядке возрастания (неубыв а-
ния). Число K вводится с клавиатуры.
19. *Как, используя операции сложения и вычитания, пом е-
нять местами значения двух ячеек памяти без использов а-
ния трет ьей переменной?
20. *Напишите программу, которая сортирует массив по убыв а-
нию суммы цифр числа.
21. *Напишите программу, которая сортирует первую половину
масс ива по возрастанию, а вторую – по убыванию (элементы
из первой половины не должны попадать во вторую и н а-
оборот).

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
26 http://kpolyakov. spb .ru

07.04.2019
22. *Напишите программу, которая сортирует массив , а затем
находит количество различных чисел в нём.
23. *Напишите программу, которая сортирует массив, а затем
находит максимальное из чисел, встречающихся в массиве
несколько раз.

Темы сообщений:
а) «Сортировка методом пузырька»
б) «Сортировка методом вставки»


§ 21. Матрицы (дmf_jgu_fZkkbы)
Ключевые слова :
матрица
строка
столбец
главная диагональ
побочная диагональ
Что такое матрицы?
Многие программы работ ают с данными, организованн ы-
ми в виде таблиц. Например, при составлении программы для
игры в крестики -нолики нужно запоминать состояние каждой
клетки квадратной доски. Можно поступить так: пустым кле т-
кам присвоить код « –1», клетке, где стоит нолик – код 0, а кле т-
ке с крестиком – код 1. Тогда информация о состоянии поля м о-
жет быть зап исана в виде таблицы:

Рис. 4.3.
Такие таблицы называются матрицами или двухмерными
массивами.
0 1 2
0 -1 0 1
1 -1 0 1
2 0 1 -1

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
27 http://kpolyakov. spb .ru

07.04.2019
Матрица — это прямоугольная таблица, составленная из эл е-
ментов одного типа (чисел, строк и т.д.).
Каждый элемент матрицы, в отличие от обычного (лине й-
ного) массива, имеет два индекса – номер строки и номер
столбца . Это похоже на координаты пикселя растрового рису н-
ка или точки на плоскости. На Рис. 4.3 фоном выделен элемент,
находящийся на пересечении строки 1 и столбца 2, он обознач а-
ется в программе как A[1][2] . Нумерация строк и стол бцов, как и
индексов одномерных массивов, в языке PWKRQ начинается с
нуля.
Матрицу часто называют двуме рным массивом, потому что
каждый элемент матрицы имеет два индекса – номера строки и
столбца.
Определите значения элементов A [0][1 ], A [1][0 ] и A [2][3 ] на
Рис. 4.3 .
Создание матрицы
Поскольку в Python нет массив ов, то нет и матриц в кла с-
сическом понимании. Для того, чтобы работать с таблицами,
используют списки. Двухмерная таблица хранится как «список
списков» – список, каждый элемент которого тоже представляет
собой список. Например, таблицу, показанную на Рис. 4.3 , мо ж-
но записать так:
A = [[ -1, 0, 1],
[-1, 0, 1],
[0, 1, -1]]
или в одну строчку:
A = [[ -1, 0, 1], [ -1, 0, 1], [0, 1, -1]]
Конечно, первый способ более нагляден.
Иногда нужно создать в памяти матрицу заданного р азм е-
ра, заполненную некоторыми начальными значениями, напр и-
мер, нулями. Первая мысль – применить такой алгоритм, и с-
пользующий операцию повторения « *»:
N = 3

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
28 http://kpolyakov. spb .ru

07.04.2019
M = 2
# не_jgh_kha^Zgb_fZljbpu!
row = [0]* M # создаём список -строку длиной M
A = [row ]* N # созда ём масси kibkhd ba N строк
Однако этот способ работает неверно из -за особенностей
языка PWKRQ Например, если после этого выполнить присва и-
вание
A[0][0] = 1
мы увидим, что все элементы столбца 0, то есть A[0][0] ,
A[1][0] и т.д. стали равны 1. Дело в то м, что матрица – это
список ссылок на списки -строки (список адресов строк). При в ы-
полнении оператора
row = [0]* M
транслятор создаёт в памяти одну единственную строку, а затем
следующий оператор
A = [row ]* N
устанавливает на эту единственную строку все ссыл ки в массиве
A (Рис. 4.4 ).

Рис. 4.4.
Естественно, что когда мы меняет элемент с индексом 0 в
строке 0 (он выделен фоном на Рис. 4.4 ), меняются и все эл е-
менты с индексом 0 во всех строк ах .
Для создания полноценной матрицы нам нужно как -то з а-
ставить транслятор создать все строки в памяти как разные
объекты. Для этого сначала построим пустой список, а потом б у-
дем в цикле добавлять к нему (с помощью метода append ) н о-
вые строки, состоя щие из нулей:
A = []
for i in range (N):
A.append( [0]*M )
A
0
1
2

0 1
1 0

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
29 http://kpolyakov. spb .ru

07.04.2019
или так, с помощью генератора:
A = [ [0]*M for i in range(N) ]
Теперь все строки расположены в разных областях памяти (Рис.
4.5 ).

Рис. 4.5.
Каждому элементу матрицы можно присвоить любое зн а-
чение. Поскольку индексов два, для заполнения матрицы или
обработки всех её элементов нужно использовать вложенный
цикл. В одном (обычно – во внешнем) цикле изменяется индекс
строки, а во втором – индекс столбца.
Далее будем считать, что сущ ествует матрица A , состоящая
из N строк и M стол бцов, а i и j – целочисленные переменные,
обозначающие индексы строки и столбца. В этом примере ма т-
рица заполняется случайными числами из отрезка [ 20; 80 ]:
from random import randi nt
A = [ [0]*M for i in range(N) ]
for i in range(N):
for j in range(M):
A[i][ j] = randint ( 20, 80 )
Запишите в тетради фрагмент программы, который
вычисляет сумму всех элементов матрицы в переменной s.
Запишите в тетради фрагмент программы, которы й
вычисляет количество ненулевых элементов матрицы в
переменной k.
Выh^fZljbpugZwdjZg
Простейший способ вывода матрицы – с помощью одного
вызова функции print :
print ( A )
A
0
1
2

0 0

0 0

0 0

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
30 http://kpolyakov. spb .ru

07.04.2019
В этом случае матрица выводится в одну строку, что не
очень удобно. Поскольку ч еловек воспринимает матрицу как
таблицу, лучше и на экран выводить её в виде таблицы. Для
этого можно написать такую процедуру (в классическом стиле):
def printMatrix ( A ):
for i in range(len(A)):
for j in range(len(A[i])):
print( "{:4d}".forma t(A[i][j]), end="" )
print()
Здесь i – это номер строки, а j – номер столбца; len(A) – это
число строк в матрице, а len(A[i]) – число элементов в строке
i (совпадает с числом столбцов).
После вывода значения очередного мы не делаем перевод
строки на э кране ( end="" ), а после вывода всей строки – делаем
с помощью вызова функции print без аргументов.
Можно написать такую функцию и в стиле PWKRQ:
def printMatrix ( A ):
for row in A:
for x in row:
print( "{:4}".format(x), end="" )
print ()
П ервый цикл перебирает все строки в матрице; каждая из них
по очереди попадает в переменную -массив row . Затем внутре н-
ний цикл перебирает все элементы это го массива (строки) и в ы-
водит их на э кран.
Перебор элементов матриц ы
Каждый элемент матрицы имеет два ин декса, поэтому для
перебора всех элементов нужно использовать вложенный цикл.
Обычно внешний цикл перебирает индексы строк, а внутре н-
ний – индексы столбцов. Вот так можно найти сумму всех эл е-
ментов матрицы:
summa = 0
for i in range(N):
for j in range(M):

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
31 http://kpolyakov. spb .ru

07.04.2019
summa += A[i][j]
print(summa)
Эту задачу можно красиво решить в стиле PWKRQ:
summa = 0
for row in A:
summa += sum(row)
print(summa)
Здесь в цикле перебираются все строки матрицы A , каждая из
них по очереди записывается в переменную row . В теле цикл а
сумма элементов очередной строки прибавляется к значению
переменной summa .
Квадратные матрицы
На практике (например, при решении шахматных задач)
часто приходится работать с квадратными матрицами , у кот о-
рых количество строк и кол ичество столбцов одинаков ые.
Для квадратной матрицы используют понятия « главная
диагональ » (серые клетки на Рис. 4.6 , а) и « побочная диагональ »
(Рис. 4.6 , б). На Рис. 4.6 , в выделена главная диагональ и все
элементы под ней.

Рис. 4.6.
Главная диагональ – это элементы A [0] [0], A [1][1 ], …,
A [N –1][ N –1], то есть элементы, у которых номер строки равен
номеру столбца. Для переб ора эти х элементов достаточно одного
цикл а:
for i in range(N):
# работаем с A[i][i]
Элементы побочной диагонали – это A [0][N –1], A [1][ N –2],
…, A[ N –1][0 ]. Заметим, что сумма номеров строки и столбца для















  

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
32 http://kpolyakov. spb .ru

07.04.2019
каждого элемента равна N – 1, поэтому получаем такой цикл
перебора:
for i in range(N):
# работаем с A[i][N -1-i]
С помощью генератора легко выделить элементы главной
диагонали в отдельный массив:
D = [ A[i][i] for i in range(N) ]
Запишите в тетради фрагмент программы, который
вычисляет сумму всех элементов гла вной диагонали
квадратной матрицы в переменной s.
Запишите в тетради фрагмент программы, который
вычисляет количество ненулевых элементов побочной
диагонали матрицы в переменной k.
Для обработки всех элементов на главной диагонали и под
ней ( Рис. 4.6 , в) нужен вложенный цикл: номер строки будет
меняться от 0 до N – 1, а номер столбца для каждой строки i – от
0 до i:
for i in range(N):
for j in range(i+1):
# работаем с A[i][j]
Запишите в тетради фрагмент программы, кот орый
вычисляет среднее арифметическое элементов матрицы,
находящихся на главной диагонали и под ней.
Чтобы переставить столбцы матрицы, достаточно одного
цикла. Например, переставим столбцы с индексами 2 и 4, и с-
пользуя вспомогательную переменную temp :
for i in range(N):
temp = A[i][2]
A[i][2] = A[i][4]
A[i][4] = temp
или, используя множественно присваивание в Python :
for i in range(N):
A[i][2], A[i][4] = A[i][4], A[i][2]

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
33 http://kpolyakov. spb .ru

07.04.2019
Переставить две строки можно вообще без цикла, учитывая,
что A [i] – это ссылка на список элементов строки i. Поэтому до с-
таточно просто переставить ссылки. Оператор
A[ 0], A[ 3] = A[ 3], A[ 0]
переставляет строки матрицы с индексами 0 и 3.
Для того чтобы создать копию строки с индексом i, нельзя
делать так:
R = A[i] # это не_jgh!
потому что при этом мы получим новую ссылку на существу ю-
щую строку. Вместо этого нужно создать копию в памяти с п о-
мощью среза, включающего все элементы строки:
R = A[i][:]
Построить копию столбца с индексом j несколько сложнее,
так как матрица расположена в памя ти по строкам. В этой з а-
даче удобно использовать генератор:
C = [ row[j] for row in A ]
В цикле перебираются все строки матрицы A , они по очереди
попадают в переменную -массив row . Генератор выбирает из
каждой строки элемент с индексом j и составляет список из этих
знач ений.
Практическая работа №18. Матрицы
Выh^u:
Матрица — это прямоугольная таблица, составленная из эл е-
ментов одного типа (чисел, строк и т.д.).
Каждый элемент матрицы имеет два индекса – номера стр оки
и столбца.
Главная диагональ квадратной матрицы – это элементы, у к о-
торых индекс строки равен индексу столбца.
Нарисуйте интеллект -карту этого параграфа.
Вопросы и задания
1. Сравните понятия «массив» и «матрица».

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
34 http://kpolyakov. spb .ru

07.04.2019
2. Как вы думаете, можно ли считать, что первый индекс эл е-
мента матрицы – это номер столбца, а второй – номер стр о-
ки?
3. Почему суммирование элементов главной диагонали треб у-
ет одиночного цикла, а суммирование элементов под гла в-
ной диагон алью – вложенного?
Задачи
1. Напишите программу, которая находит максимальный эл е-
мент на главной диагонали ква дратной матрицы.
2. Напиш ите программу, которая находит максимальный эл е-
мент матрицы и его индексы (н омера строки и столбца).
3. *Напишите программу, которая находит минимальный из
чётных положительных элементов матрицы. Учтите, что т а-
ких элементов в матрице может и не быть.
4. *Напишит е программу, которая выводит на экран строку
матрицы, сумма элементов которой наибольшая.
5. *Напишите программу, которая выводит на экран столбец
матрицы, сумма элементов кот оро го наименьшая.
6. Напишите программу, которая заполняет матрицу из N
строк и M столб цов нулями и единицами в шахматном п о-
рядке.
7. Напишите программу, которая заполняет матрицу из N
строк и N столбцов нулями и единицами так , что все эл е-
менты выше главной диагонали равны нулю, а остальные –
ед инице.
8. Напишите программу, которая заполняет матри цу из N
строк и N столбцов нулями и единицами так , что все эл е-
менты выше побочной диагонали равны нулю, а остал ь-
ные – един ице.
9. *Заполните матрицу, содержащую N строк и M столбцов,
натуральными числами по спирали и змейкой, как на р и-
сунках:

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
35 http://kpolyakov. spb .ru

07.04.2019

10. **Напишите программу, которая играет с человеком в кр е-
стики -нолики на поле 3 3.
Темы сообщений:
«Игра "Жизнь"»

1 2 3 4
10 11 12 5
9 8 7 6

1 3 4 9
2 5 8 10
6 7 11 12

1 6 7 12
2 5 8 11
3 4 9 10

а) = б) = в) =

Инфо рматика, 9 класс К.Ю. Поляко?:?j_fbg
36 http://kpolyakov. spb .ru

07.04.2019
§ 22. Сложность алгоритмов
Ключевые слова :
временная сложность
пространственная сло ж ность
время работы алго ритма
асимптотическая сло ж ность
линейная сложность
квадратичная сложность
Как сраgbать алгоритмы ?
Чаще всего для решения задачи известно несколько алг о-
ритмов. Поэтому возникает вопрос – как выбрать лучший? И
ещё один важный вопрос – способен ли совр емен ный компьютер
за приемлемое время найти решение задачи ? Например, в игре
в шахматы возможно лишь конечное количество позиций и,
значит, только конечное количество различных партий. Значит,
теоретически можно перебрать все возможные партии и выя с-
нить, кто п обеждает при правильной игре – белые или черные.
Однако количество вариантов настолько велико, что совреме н-
ные компьютеры не могут выполнить такой перебор за прие м-
лемое время.
Что мы хотим от алгоритма? Во -первых, чтобы он работал
как можно быстрее. Во -вт орых, чтобы объем необходимой пам я-
ти был как можно меньше. В -третьих, чтобы он был как можно
более прост и понятен, это упрощает отладку программ ы . К с о-
жалению, эти требования противоречивы, и в серьезных зад а-
чах редко удается найти алгоритм, который был б ы лучше о с-
тальных по всем показат елям.
Часто говорят о временнóй сложности алгоритма (быстр о-
действии) и пространственной сложности , которая определ я-
ется объ ёмом необходимой памяти.
Временем работы алгоритма называется количество элеме н-
тарных операций , выполне нных исполнителем. =
Такой подход позволяет оценивать именно качество алгоритма,
а не свойства исполнителя (например, быстродействие компь ю-T

Информатика, 9 класс К.Ю. Поляко?:?j емин
37 http://kpolyakov. spb .ru

07.04.2019
тера, на к отором выполняется алгоритм). При этом мы считаем,
что время выпо лнения всех эле ментарных операций одинаково.
Как правило, величина будет существенно зависеть от
объема исходных данных: поиск в списке из 10 элементов з а-
вершится гораздо быстрее, чем в списке из 10000 элементов. П о-
этому сложность алгоритма обычн о связывают с размером вхо д-
ных данных N и определяют как функцию T (N ). Например, для
алгоритмов обработки массивов в качестве размера N испол ь-
зуют длину массива. Функция T (N ) называется временн óй
сложностью алгоритма.
Временная сложность алгоритма определ яется функцией
T (N ) = 2N 3. Во сколько раз увеличивается время работы
алгоритма , если размер данных N увеличится в 10 раз?
Пространственная сложность – это зависимость объёма
занимаемой памяти от размера данных N . Д ля ускорения раб о-
ты некоторых а лгоритмов нужно использовать дополнительную
память, которая может быть намного больше, чем память для
хранения исходных да нных.
Для быстрой сортировки массива из N элементов с пом о-
щью алгоритма Семёна требуется N вспомогательных
массивов, ка ж дый из которых содержит N элементов. Как
изменится объём нужной дополнител ьной памяти, если N
увеличится в 10 раз?
Поскольку память постоянно дешевеет, а быстродействие
компьютеров растет медленно, более важна временн áя сло ж-
ность алгоритмов. Пространственную сложность мы дальше
рассматривать не будем.
Примеры
Рассмотрим алгоритмы выполнения различных операций с
массивом A длины N .
Пример 1 . Вычислить сумму первых трёх элементов ма с-
сива (при N 3).
Решение этой задачи содержит всего один оператор: T

Информатика, 9 класс К.Ю. Поляко?:?j емин
38 http://kpolyakov. spb .ru

07.04.2019
Sum = A[ 0] + A[ 1] + A[ 2]
Этот ал горитм включает две операции сложения и одну опер а-
цию зап иси значения в память, поэтому его сложность T (N ) = 3
не зависит от размера массива вообще.
Вычислите количество операций (считая сравнения и
присваивание значений переменным) при выполнении
фрагмен та програ м мы:
a = 8
b = 15
if a < b :
c = 2*a + b
else :
c = 2*b + a
Пример 2. Вычислить сумму всех эл ементов массива.
В этой задаче уже не обойтись без цикла:
Sum = 0
for i in range( N):
Sum = Sum + A[i]
Здесь выполняется N операций сложения и N+ 1 опер аций зап и-
си в память, поэтому его сложность T (N ) = 2 N + 1 возрастает л и-
нейно с увел ичением длины массива.
Вычислите количество операций при выполнении фра г-
мента программы:
a = 0; b = 1
for i in range(N) :
a = a + b*b
b = b + 1
Пример 3. Отсортировать в се элементы массива по возра с-
танию методом выб ора.
Напомним, что метод выбора предполагает поиск на ка ж-
дом шаге минимального из оставшихся неупорядоченных зн а-
чений:
for i in range( N-1):
nMin = i
for j in range( i+1 ,N):

Информатика, 9 класс К.Ю. Поляко?:?j емин
39 http://kpolyakov. spb .ru

07.04.2019
if A[j] < A[nMin] : nMin = j
c = A[i]
A[i] = A[nMin]
A[nMin ] = c
Подсчитаем отдельно количество сравнений и количество пер е-
стан овок. Количество сравнений элементов массива не зависит
от данных и определяется числом шагов вну треннего цикла:
.
Здесь использо вана формула для суммы первых членов ари ф-
метич еской прогрессии.
На каждом шаге внешнего цикла происходит перестановка
двух элементов, общее количество перестановок равно
T п(N ) = N – 1, то есть сложность по перестановкам – линейная.
Определите количество о пераций при вычислении сумм ы
эл ементов квадратной матрицы A размером N N :
Sum = 0
for i in range( N):
for j in range( N):
Sum = Sum + A[i][ j]
По результатам этих примеров можно сделать выводы:
простой цикл, в котором количество шагов пропорци онально
N , – это алгоритм линейной сложности;
вложенный цикл, в котором количество шагов внешнего и
внутреннего цикла пропорционально N , – это алгоритм с
квадратичной функцией сложности.
Что такое асимптотическая сложность?
Допустим, что нужно сделать выбор между несколькими
алгоритмами, которые имеют разную сложность. Какой из них
лучше (работает быстрее)? Оказывается, для этого необходимо
знать размер массива данных, которые нужно обрабатывать.
Сравним, например, три алгоритма, сло ж ность которых
T 1(N ) = 10000 N , T 2(N ) = 100 N 2, T 3(N ) = N 3. N N N N N N N Tc 2
1
2
1
2
)1 ( 1 2 ... )2 ( )1 ( ) ( 2

Информатика, 9 класс К.Ю. Поляко?:?j емин
40 http://kpolyakov. spb .ru

07.04.2019
Построим эти зависимости на графике (см. Рис. 4.7 ). При
N 100 получаем T 3(N ) < T 2(N ) < T 1(N ), при N = 100 количество
операци й для всех трёх алгоритмов совпадает, а при больших N
им еем T 3(N ) > T 2(N ) > T 1(N ).

Рис. 4.7.
Обычно в теоретической информатике при сравнении а л-
горитмов используется их асимптотическая сложность , то
есть скорость роста количества операций при больших значен и-
ях N .
Запись O (N ) (читается «О б ольшое от N ») обозначает ли-
нейную сложность алгоритма. Это значит, что , начиная с нек о-
торого значения N = N 0, количество операций будет меньше,
чем c N , где c – некоторая постоянная :
T (N ) c N для N N 0.
П ри увеличении размера данных в 10 раз объем вычи слений
алгоритма с линейной сложностью увеличивается тоже пр и-
мерно в 10 раз.
Пусть, например, T (N ) 2N – 1, как в алгоритме поиска
суммы элементов массива. Очевидно, что при этом T (N ) 2N
для всех N 1, поэтому алг оритм имеет линейную сложность.
Опред елите люб ы е подходящ ие значени я c и N 0, так ие что
T (N ) c N для N N 0, для алгоритмов с линейной асимп -
то тической сложностью:
а) T (N ) = 2N – 8 б) T (N ) = 7N + 5
Многие известные алгоритмы имеют квадратичную сло ж-
ность , O (N 2). Это значит, что количество операций при бол ьших
N не больше , чем c N 2:
0 10 0 N
T T 3
T 2
T 1

Информатика, 9 класс К.Ю. Поляко?:?j емин
41 http://kpolyakov. spb .ru

07.04.2019
T (N ) c N 2 для N N 0.
Если размер данных увеличивается в 10 раз, то количество оп е-
раций (и время выполнения такого алг оритма) увеличивается
примерно в 100 раз. Пример алгоритма с квадратичной сложн о-
стью – сорт ировка методом выбора, для которой число сравн е-
ний
для всех N 0.
Определите любые подходящие значения c и N 0, так ие что
T (N ) c N 2 для N N 0, для алгоритмов с квадратичной
асимптотической сложностью:
а) T (N ) = 5N 2 – 3N – 2 б) T (N ) = 7N 2 + 5N
Это значит, что график функции c f(N ) проходит выше, чем
график функции T (N ), по крайней мере , при N N 0 (см. Рис.
4.8 ).

Рис. 4.8.
Строго говоря , обозначение O (f(N )) определяет множество
всех алгоритмов, для которых количество операций T (N ) растёт
не быстрее, чем f(N ). Тогда, н априме р, алгоритм с количеством
операций T (N ) = N + 5 относится к классам O (N ), O (N 2) , O (N 3) и
даже O (2 N). Однако на практике выражение «алгоритм имеет
сложность O (N 2)» чаще всего означает, что O (N 2) – это наилу ч-
шая асимптотическая оценка роста количеств а опера ций T (N ),
Алгоритм относится к классу =O (f(N )), если найдется такая п о-
стоянная c, что, начиная с некоторого N = N 0 выполняется усл о-
вие T (N ) c f(N ).
0 N
T (N )
T
c f(N )
N 0 2 2
2
1
2
1
2
1 ) ( N N N N Tc

Информатика, 9 класс К.Ю. Поляко?:?j емин
42 http://kpolyakov. spb .ru

07.04.2019
то есть по крайней мере для некоторых данных T (N ) растёт б ы-
стрее, чем O (N ), O (N 1,5 ) и д аже O (N 1,99999 ).
Если количество операций не зависит от размера данных,
то говорят, что асимпт отическая сложность алгоритма O (1), то
есть количество операций м еньше некоторой постоянной при
любых N .
Существует также немало алгоритмов с кубич еск ой сло ж-
ностью, O (N 3). При больших значениях N алгоритм с кубич е-
ск ой сложностью требует б óльшего количества вычислений, чем
алгоритм со сложностью O (N 2), а тот, в свою очер едь, работает
дольше, чем алгоритм с линейной сложностью. Однако п ри не-
больших значениях N вс ё может быть наоборот, это зависит от
пост оянной c для каждого из алгоритмов.
Известны и алгоритмы, для которых количество операций
растет быстрее, чем любой мног очлен, например, как O (2N). Они
встречаются чаще всего в задачах поиска оптимального (на и-
лучшего) варианта, которые решаются только методом по лного
перебора. Самая известная задача такого типа – это задача
коммивояжера (бродячего торговца), который должен посетить
по одному разу каждый из указанных городов и вернуться в н а-
чальную точку. Для него ну ж но выбрать маршрут, при котором
стоимость поездки (или общая длина пути) будет мин имальной.
В таблице на Рис. 4.9 показано примерное время работы
алгоритмов, имеющих разную временную сложность, при
N = 100 на компьютере с быстродействием 1 миллиард опер а-
ций в с екунду.
T (N ) время выполн ения =
N 100 нс =
N 2 10 мс =
N 3 0,001 с =
ON 10 13 лет =
Рис. 4.9.
Юный программист Григорий поспор ил с учителем, что
сможет с помощью компьютера решить сложную задачу

Информатика, 9 класс К.Ю. Поляко?:?j емин
43 http://kpolyakov. spb .ru

07.04.2019
перебора вариантов к завтрашнему уроку. Дома он
определил временную сложность алгоритма: T (N ) = 2N.
Для какого наибольшего значения N сможет Григорий
решить задачу за сутки, если его комп ьютер выполняет 1
миллиард операций в секунду?
Выh^u:
Временем работы алгоритма называется количество элеме н-
тарных операций T , выполненных испо лнителем.
Временная сложность алгоритма обычно зависит от объёма
исходных данных N , например, от размера массива .
Пространственная сложность – это объём памяти, необход имой
для работы алгоритма.
Простой цикл, в котором количество шагов пропорционально
N , – это алгоритм линейной сложности;
Вложенный цикл, в котором количество шагов внешнего и
внутреннего цикла пропо рционально N , – это алгоритм ква д-
ратичной сло ж ности.
Алгоритм относится к классу O (f(N )), если найдется такая п о-
стоянная с, что, начиная с некоторого N = N 0 выполняется у с-
ловие T (N ) c f(N ).
Линейная сложность означает, что при увеличении размера
массива в K раз количество операций увеличивается пр имерно
в K раз.
Квадратичная сложность означает, что при увеличении ра з-
мера массива в K раз количество операций увеличивается
примерно в K 2 раз.
Нарисуйте интеллект -карту этого параграфа.
Вопросы и задания
1. Каки е критерии используются для оценки качества алг о-
ритмов?
2. Почему скорость работы алгоритма оценивается не врем е-
нем в ы полнения, а количеством элементарных операций?

Информатика, 9 класс К.Ю. Поляко?:?j емин
44 http://kpolyakov. spb .ru

07.04.2019
3. Как учитывается размер данных при оценке быстродейс т-
вия алг оритма?
4. В каких случаях алгоритм, имеющий асимптотическую
сложность O (N 2), может работать быстрее, чем алгоритм с
асимптотической сложностью O (N )?
Задачи
1. Оцените асимптотическую сложность для а лгоритмов:
а) вычисления произведения первого и последнего элеме н-
тов массива;
б) вычисления суммы эл ементов первой половины массива;
в) нахождения минимального и максимального элементов
масс ива;
г) определения количества положительных элементов ма с-
сива;
д) определения количества нулевых элементов квадратной
матр ицы ;
е) поиска всех делителей числа N.
Считайте, что ма ссив содержит N элементов, а матрица им е-
ет ра змеры N N .
2. Определите асимптотическую сложность алгоритмов, для
которых известно количество оп ераций:
а) T (N ) = 5 N+ 6
б) T (N ) = 3 N 2+2 N+ 19
в) T (N ) = 2 N 3+100
г) T (N ) = 4 2N + 25 N 18 +8
3. Алгоритм обработки массива имеет асим птотическую сло ж-
ность O (N 2), где N – длина массива. Во сколько раз увел и-
чится время выполнения алгоритма, если длина массива
увел ичится в 5 раз?
4. *Алгоритм обработки массива имеет асимптотическую
сложность O (2N), где N – длина массива. Как увеличится
время выполнения алгоритма, если длина массива увел и-
чится на 5 эл ементов? в 5 раз?
Темы сообщений:
«Задача коммивояжёра»

Информатика, 9 класс К.Ю. Поляко?:?j емин
45 http://kpolyakov. spb .ru

07.04.2019
§ 23. Как разрабатыZxlijh]jZffu?
Ключевые слова :
постановка задачи
построение модели
разработка алгоритма и
способа представления
данных
кодиро вание
отладка
тестирование
документирование
внедрение и сопровожд ение
Как вы знаете, новые программы для компьютеров пишут
программисты. Но это не совсем точно : любая достаточно сло ж-
ная пр ограмма проходит несколько этапов от рождения идеи до
выпуска готов ого продукта, и в этом участвует множество сп е-
циалистов.
Этапы разработки программ
1. Постановка задачи . Сначала определяют задачи, к о-
торые дол ж на решать программа, и записывают все требования
к ней в виде документа – технического задания . Это очень
важны й этап, потому что ошибка в самом начале разработки
приведёт к тому, что будет решена сове ршенно другая задача.
2. Построение модели. Когда задача поставлена, нужно
выполнить формализацию – записать все требования на фо р-
мальном языке, н апример, на языке м атематических формул. В
результате строится м одель исходной задачи, в которой чётко
определяются все связи между исходными данными и жела е-
мым результатом.
3. Разработка алгоритма и способа представления
данных. Любая компьютерная программа служит для обра бо т-
ки данных. Поэтому очень важно определить, как будут пре д-
ставлены данные в памяти компьютера (например, в виде о т-
дельных переменных или массивов).
Способ хранения данных определяет и алгоритмы работы с
ними: если выбрана неудачная структура данных, оче нь сложно
написать хороший алгоритм обработки. Известная книга шве й-
царского специалиста Никлауса Вирта, автора языка Паскаль,

Информатика, 9 класс К.Ю. Поляко?:?j емин
46 http://kpolyakov. spb .ru

07.04.2019
так и называется «Алгоритмы + структуры данных = програ м-
мы».
4. Кодирование . Только теперь, когда выбран способ хр а-
нения данных и готовы алгоритмы для работы с ними, пр о-
граммисты приступают к написанию программы. Эта работа
называется кодированием , потому что программист кодирует
алгоритм – записывает его на языке программирования. Р е-
зультат его работы – текст программы – часто назыв ают пр о-
граммным к одом .
5. Отладка . Ни один человек не может написать достато ч-
но большую программу без ошибок. Поэтому программисту пр и-
ходится искать и устранять ошибки в программ ах . Этот процесс
называется отладкой программы .
Все ошибки можно разделит ь на две группы: синтаксич е-
ские и л огические . Синтаксические ошибки – несоответствия
правилам языка программирования – обнаруживаются тран с-
лятором, поэтому найти и исправить их достаточно просто .
Сложнее исправ ля ть логические ошибки – ошибки в со-
ставлении алгор итма. Из -за логических ошибок программа ра-
ботает не так, как требуется . Чтобы исправить такую ошибку,
программисту приходится внимательно изучить работу пр о-
граммы, иногда даже выполнить все вычисления вручную, без
компьютера , и сравнить результаты каждого шага с теми ре-
зультатами, которые даёт пр ограмма.
Л огически е ошибк и могут привести к отказ у – аварийн ой
ситуаци и, например, к делени ю на ноль. Часто при отказ е оп е-
рационная система завершает работ у программы , и данные м о-
гут быть потеряны. Отказы часто наз ывают ошибками времени
выполнения (англ. runtime error ).
5. Тестирование . Когда программист исправил все обн а-
руженные им ошибки, он передаёт программу на тестиров а-
ние – тщательную проверку в различных режимах. Обычно эту
работу выполняют специально обученн ые люди – тестировщ и-
ки .

Информатика, 9 класс К.Ю. Поляко?:?j емин
47 http://kpolyakov. spb .ru

07.04.2019
Тестирование в компании, которая разрабатывает пр о-
грамму, называется альфа -тестированием. Когда оно заверш е-
но, начинается бета -тестирование (внешнее тестирование). Пр о-
гра м ма (так называемая «бета -версия») рассылается некоторым
клие нтам или даже распространяется свободно. Цель этого эт а-
па – привлечь к тестированию множество людей, чтобы они
смогли найти как можно больше ошибок в пр ограмме.
6. Документирование – это разработка документации на
программу. Этим занимаются технические пи сатели . Т ехнич е-
ская документация описывает, как работает программа , а рук о-
водство пользователя содержит инструкцию по испол ьзованию
программы.
7. Внедрение и сопровождение . Когда программа отл а-
жена и документация по ней готова, её нужно передать зака з-
чику . Компания берёт на себя сопровождение программы – об у-
чение пользователей, исправление найденных ими ошибок,
техническую поддержку (ответы на вопросы). Часто компании
выпускают новые версии программ, в которых исправляются
ошибки и д обавляются новые возмож ности.
Методы п роектировани я программ
Современные программы очень сложны, они могут сост о-
ять из сотен тысяч и миллионов строк. Написать такую пр о-
грамму в одиночку невозможно, поэтому над проектом работают
большие команды программистов.

Рис. 4.10.
Задача =
Подз адача 1 = Подз адача 2 = Подз адача 3 =
2.1 = 2.O = 2.P = 1.1 = 1.2 = 3.1 = 3.O =

Информатика, 9 класс К.Ю. Поляко?:?j емин
48 http://kpolyakov. spb .ru

07.04.2019
Всю работу нужно как -то разделить между программист а-
ми, чтобы каждый мог выполнять свою часть независимо от
других. Для этого необходимо разбить задачу на подзадачи
(Рис. 4.10 ).
Решение к ажд ой подзадач и оформляется в виде подпр о-
граммы – вспомогательного алгоритма (вспомните материал
7 класса). Программист получает персональное задание – нап и-
сать одну или несколько подпрограмм. Он может работать нез а-
висимо от других, важно только соблюдать правила обмена
данными между «его» по дпрограммой и остальными.
Если нужно, подзадачи разбиваются на более мелкие по д-
задачи (см. третий уровень дерева на Рис. 4.10 ) и так далее , так
чтобы каждая подпрограмма была не длиннее , чем 30 -40 стр о-
че к.
Такой приём называется последовательным уточнен и-
ем или пр оектированием «сверху вниз» , от основной задачи
к мелким подзад ачам.
Существует и другой подход ( проектирование «снизу
вверх» ) – сначала разработать подпрограммы для решения с а-
мых простых задач , а потом собирать из них подпрограммы для
более крупных задач, как из кубиков. При этом мы строим д е-
рево, показанное на Рис. 4.10 , снизу вверх, с нижнего уровня.
На практике программисты обычно сочетают оба по дход а.
Отладка программ ы
Простейший метод отладки программы – это вывод отл а-
дочной информации . Рассмотрим этот способ на примере.
Программисту нужно было написать программу, которая
вычисляет корни квадратного уравнения ax 2 + bx + c = 0. Он п о-
спешил и написал пр ограмму так:
from math import sqrt
print ( "В_^bl_DEF: " )
a = float( input() )
b = float( input() )
c = float( input() )

Информатика, 9 класс К.Ю. Поляко?:?j емин
49 http://kpolyakov. spb .ru

07.04.2019
D = b*b - 4*a*a
x1 = (-b + sqrt(D))/ 2*a;
x2 = (-b - sqrt(D))/ 2*a;
print ( "x1= {:. 3}, x2={ :.3 }".format( x1, x2) )
Для вычислени я квадратного корня здесь используется встр о-
енная функция sqrt из модуля math .
Оказалось, что программа в некоторых случаях работает
верно (например, при a = 1, b = 2 и c = 1), а в других случа ях –
неверно (например, при a = 1, b = –5 и c = 6).
Для того чтобы найти ошибку, нужно определить её во з-
можные причины . В нашем случае есть три варианта:
1) неверно вводятся данные;
2) неверно вычисляется дискриминант D = b 2 – 4ac;
3) неверно вычисляются корни .
Добавим в программу две дополнительны е команды для
вывода отл адочной информации (они выделены фоном) :
a = float( input() )
b = float( input() )
c = float( input() )
print( a, b, c )
D = b*b - 4*a*a
print( "D={}".format(D) )
С помощью этих команд мы
1) вывед ем значения коэффициентов a, b и с сразу после вв о-
да;
2) выведем вычисленное значение дискриминанта.
Значения корней уравнения уже и так выводятся в конце раб о-
ты пр ограммы.
При вводе коэффициентов 1, –5 и 6 программа выводит
1.0 -5.0 6.0
D=21.0
x1=4.79, x2=0.20 9
По первой строчке видим, чт о ввод выполнен правильно –
именно такие числа мы вводили. А вот значение дискримина н-a
D b x a
D b x 2 , 2 2 1

Информатика, 9 класс К.Ю. Поляко?:?j емин
50 http://kpolyakov. spb .ru

07.04.2019
та, вычисленного программой , отличается от того, что мы ож и-
даем получить: D = (–5) 2 – 4 1 6 = 1. Поэтому нужно искать
ошибку в выражении для в ы числения D .
Если исправить эту ошибку (сделайте это самостоятельно),
мы увидим, что дискриминант считается правильно, а корни
уравнения – нет (при a = 1, b = –5 и c = 6 мы должны получить
x1 = 3 и x2 = 2).
Исправьте ошибки в тех строчках программы , где вычис -
ляются корни уравнени я.
Современные среды программирования содержат встрое н-
ный отладчик, кот орый позволяет:
выполнять программу в пошаговом режиме;
после выполнения очередной команды просматривать зн а-
чения п еременных в памяти;
устанавливать точки останова , где программа долж на о с-
тановит ься и перейти в пошаговый режим .
Доработайте программу так, чтобы учесть случай, когда
уравнение не имеет вещес т венных корней.

Документирование программ ы
К выпуску программы компания -разработчик должна по д-
готовит ь документацию на программу. Р уководств о пользов а-
теля (это наиболее важная часть документации) обычно соде р-
жит:
назначение программы;
ф ормат входных данных;
ф ормат выходных данных;
пример ы использования программ ы .
Для примера составим документацию на прост ую программу,
отладкой которой мы только что з анимались .
Назначение программы : вычисление вещественных корней
квадратн ого уравнения ax 2 + bx + c = 0.

Информатика, 9 класс К.Ю. Поляко?:?j емин
51 http://kpolyakov. spb .ru

07.04.2019
Формат входных данных : значения коэффициент ов a, b и c
вводятся с клавиатуры по одному числу в строке.
Формат выходных данных : значения вещественных корней
корни уравнения выводятся на экран через пробел в одной
строке; перед значением первого корня выводится текст « x1= »,
перед значением второго корня – текст « x2= ». Если вещес т-
венных корней нет, выв одится с лово «нет».
Пример использования программ ы (решение уравнения
x2 – 5x + 6 = 0):
В_^bl_DEF 1 -5 6
x1= 3. 0 x2= 2.0
В_^bl_DEF 1 1 1
нет

Практическая работа №19. Отладка программы
Выh^u:
Этапы разработки программного обеспечения:
– постановка задачи
– построение мо дели
– разработка алгоритма и способа представления данных
– кодирование
– отладка
– тестирование
– документирование
– внедрение и сопровождение
При использовании метода проектирования «сверху вниз» (м е-
тода последовательного уточнения) задача разбива ется на
подзадачи.
При использовании метода проектирования «снизу вверх»
разработка программы начинается с наиболее мелких подз а-
дач, из которых основная программа затем собирается как из
куб иков.
Нарисуйте интеллект -карту этого параграфа.

Информатика, 9 класс К.Ю. Поляко?:?j емин
52 http://kpolyakov. spb .ru

07.04.2019
Вопросы и задан ия
1. Почему способы хранения данных и алгоритмы и х обрабо т-
ки обычно разрабатываю тся одновременно?
2. Чем отличается тестирование от отладки?
3. Можно ли считать, что программа, успешно прошедшая те с-
тирование, не содержит ош ибок?
4. Может ли произойти отказ в программ е, в которой нет лог и-
ческих ошибок ?
5. Если программа плохо документирована, к каким последс т-
виям это может привести?
6. Как вы думаете, почему важно сопровождение программы
после её сдачи заказчику?
7. Чем отличаются два подхода к проектированию программ:
«сверху вниз» и «снизу вверх»?
Задачи
1. Требуется написать программу, которая загружает массив
из файла и выводит отсортированный массив в другой
файл. Выделите по дзадачи в этой задаче.
2. Требуется написать программу, которая загружает изобр а-
жение из файла, выполняет его обрезку, преобразует из
цветного формата в чёрно -белый и выводит полученное из о-
бражение в другой файл. Выделите подзадачи в этой зад а-
че.
3. Требуется написать программу для игры с человеком в
«крестики -нолики». Выделите по дзадачи в этой задаче.
4. Отладьте п рограмму для вычисления корней квадратного
уравнения. Учтите, что уравнение может не иметь вещес т-
венных корней.
5. Используя образец , приведённый в тексте параграфа, с о-
ставьте документацию на одну из написанных вами пр о-
грамм и предложите соседу ей воспользова ться. Вместе с
ним исправьте описание пр ограммы, если это потребуется.

Информатика, 9 класс К.Ю. Поляко?:?j емин
53 http://kpolyakov. spb .ru

07.04.2019
Темы сообщений :
а) «Структурное программирование»
б) «Парадигмы (стили) программирования»

Информатика, 9 класс К.Ю. Поляко?:?j емин
54 http://kpolyakov. spb .ru

07.04.2019
§ 24. Процедуры
Ключевые слова :
процедура
параметр
локальная переменная
рекурсивная процедура
Что тако е подпрограмм а?
Когда мы в 7 классе работали с исполнителем Робот, мы
уже использовали вспомогательные алгоритмы (подпрограммы,
процедуры). Каждая процедура решала одну подзадачу, из них
строилась программа для решения основной з адачи.
Подпрограммы полезн ы, в первую очередь, потому, что г о-
товые алгоритмы можно испол ьзовать много раз при решении
более сложных задач, не «изобретая велосипед». Из подпр о-
грамм составляются би блиотеки, некоторые из которых входят в
состав языков программирования. Мы просто испол ьзуем их,
задумываясь только о том, как они работают. Это экономит вр е-
мя программистов, освобождая их от повторного выполнения
работы, которая уже была кем -то сделана ран ьше.
Подпрограммы бывают дву х типов – процедуры и фун к-
ции. Подпрограммы -процедуры выполняют некоторые дейс т-
вия. Н апример, print в языке Python – это встроенная подпр о-
грамма -процедура, которая выводит данные на экран. Подпр о-
граммы -функции возвращают результат (число, строку). По д-
прогр амма sqrt , вычисляющая квадратный корень числа, – это
функция.
В этом пар аграфе мы научимся писать свои подпрогра м-
мы -процедуры, а в следующем за ймёмся функциями.
Определите тип подпрограммы (процедура или функция),
которая
а) рисует окружность на экране;
б) определяет площадь круга;
в) вычисляет значение синуса угла;
г) изменяет режим раб оты программы;

Информатика, 9 класс К.Ю. Поляко?:?j емин
55 http://kpolyakov. spb .ru

07.04.2019
д) возводит число x в степень y;
е) включает двигатель автомобиля;
ж) проверяет оставшееся количество бензина в баке;
з) измеряет высоту полёта самолёта.
Простая процедур а
Предположим, что в нескольких местах программы треб у-
ется выводить на экран строчк у из 10 знаков «–» (например, для
того чтобы отделить два блока результатов друг от друга). Это
можно сделать, н апример, так:
print ( "---------- " )
Конечно, можно вставить этот оператор вывода везде, где
нужно вывести такую строчку. Но это решение имеет д ва недо с-
татка. Во -первых, строка из минусов будет храниться в памяти
много раз. Во -вторых, если мы задумаем как -то изменить эту
строку (например, заменить знак « –» на «=»), нужно будет и с-
кать эти операторы вывода по всей программе.
Для таких случаев в язы ках программирования предусмо т-
рены процедуры . Посмотрим на программу с процедурой:
def printLine ():
print( " ---------- " )
...
printLine ()
...
printLine()
Многоточием в текстах программ будем обозначать некот орые
операторы, которые нас пока не интересую т.
Сначала в программе расположена процедура, выделенная
фоном. Она начинается со служебного слова def (от англ. de-
fine – определить). После имени процедуры записаны пустые
скобки (чуть далее мы увидим, что они могут быть и непустые!)
и двоеточие.
Все ком анды, входящие в тело процедуры, записываются с
отступом (так же, как и команды, входящие в тело цикла или
условного оператора).

Информатика, 9 класс К.Ю. Поляко?:?j емин
56 http://kpolyakov. spb .ru

07.04.2019
Для того чтобы процедура заработала, в основной програ м-
ме (или в другой процедуре) необходимо её вызвать по имени
(не забыв ск обки), причём таких вызовов может быть сколько
угодно (в нашей программе – два).
Процедура должна быть определена к моменту её вызова, то
есть должна быть выполнена инструкция def , которая создает
объект -процедуру в памяти. Если процедура вызывается из о с-
новной программы, то нужно поместить её определение раньше
точки вызова.
Что произойдёт, если вызвать процедуру, но не включить
её текст в программу? Проверьте этот вариант с пом о-
щью ко м пьютера.
Что произойдёт, если включить текст процедуры в пр о-
грамму, но не вызывать её? Проверьте этот вариант с
помощью комп ьютера.
Использование процедур сокращает код, если какие -то оп е-
рации должны выполняться несколько раз в разных местах
программы. Кроме того, большую программу всегда разбивают
на несколько подпрограмм для удобства, выделяя этапы сло ж-
ного алгоритма. Такой подход делает всю программу более п о-
нятной и позволяет разделить работу между программистами.
Когда процедура написана и тщательно протестирована,
можно передать её другим программистам для использован ия в
этом же или другом проекте. Очень важно, чтобы автор проц е-
дуры подробно описал, что она делает, её входные и выходные
данные. Тем, кто использует готовую процедуру, нужно уб е-
диться, что она выполняет именно то, что требуется в данной
задаче.
Процедур а с п араметр ом
Теперь представьте себе, что нужно выводить строки из
минусов разной длины (5, 10 и др). Конечно, можно сделать н е-
сколько проц едур, например, так:
def printLine5():
print ( "----- " )

Информатика, 9 класс К.Ю. Поляко?:?j емин
57 http://kpolyakov. spb .ru

07.04.2019
def printLine10():
print ( "---------- " )
Но так делать не ну жно. Дело в том, что обе процедуры вывод ят
цепочки знак ов «минус» (то есть, выполняют те же самые дейс т-
вия!), только разно й длины . Поэтому хочется использовать всего
одну процедуру, передавая ей нужную длину цепочки.
Процедуру printLine10 можно переписать, применив «у м-
ножение» строки на число (заменяющее, как и в математике,
многократное сложение):
def printLine 10():
print ( " -"*10 )
Эта процедура делает то же самое, что и первый вариант – вы-
водит 10 «минусов» подряд и переходит на новую строчку.
Чем буде т отличаться процедура, рисующая 5 знаков
«минус», от последнего варианта процедуры printLine10 ?
Если мы хотим, чтобы длину строки можно было менять, в
процедуре вместо числа нужно использовать переменную. И
значение этой переменной необходимо как -то перед ать проц е-
дуре. Оформляется это так:
def printLine( n ):
print( " -"*n )
Величина n называется параметром процедуры. Теперь в
круглые скобки в заголовке процедуры не пустые. В них зап и-
сано имя параметра – специальной переменной, с помощью к о-
торой можно упр авлять работой процедуры.
Параметр — =это переменная, от значения которой зависит р а-
бота подпрограммы. Имена параметров перечисляются в заг о-
ловке подпрограммы. =
Наша процедура printLine имеет один параметр, обозн а-
ченный именем n – это длина строки из «минус ов».
При вызове такой процедуры в скобках нужно записать
фактическое значение, которое присваивается переменной n
внутри проц едуры:
printLine( 10 )

Информатика, 9 класс К.Ю. Поляко?:?j емин
58 http://kpolyakov. spb .ru

07.04.2019
Такое значение называется аргументом (или фактическим п а-
раметром).
Аргумент — =это значение параметра, которо е передаётся по д-
программе при её вызове. =
Аргументом может быть не только постоянное значение
(число, символ), но также и переменная, и даже арифметич е-
ское выражение.
Что будет выведено на экран при выполнении фрагмента
программы
printLine( 7 );
printLi ne( 5 );
printLine( 3 );
Для тестирования процедуры printLine Иван хочет н а-
писать небольшую программу, в которой длина линии вв о-
дится с клавиатуры. Где нужно поместить оператор вв о-
да – в процедуре или в основной программе?
Локальные и глобал ьные переменны е
Переменные, которые введены в основной программе, н а-
зываются глобальными (общими). Их могут использовать все
подпрограммы (процедуры и функции).
Часто бывает нужно ввести дополнительные переменные,
которые будут использоваться только в подпрограмме. Так ие
переменные называются локальными (местными), к ним мо ж но
обращаться только внутри этой подпрограммы, и остальные
подпрограммы (а также основная программа) про них ничего не
«зн ают».
Где вы уже встречались со словом «локальный» в курсе
информатики? Всп омните, от какого иностранного слова
оно произошло.
Такой приём называется инкапсуляция (от лат. «помещ е-
ние в капсулу») – мы ограничиваем область видимости (о б-
ласть действия) переменной только той подпрограммой, где она
де йствительно нужна.

Информатика, 9 класс К.Ю. Поляко?:?j емин
59 http://kpolyakov. spb .ru

07.04.2019
Составим проце дуру , которая «рисует» на экране треугол ь-
ник из символов «О» высотой n (Рис. 4.11 ).

Рис. 4.11.
Как видно из Рис. 4.11 , рисунок строится из n строчек , причём в
n-й по порядку строч ке выводится ровно n символов . П роцедуру
можно написать так :
def triangle О( n ):
for i in range (1,n+1 ):
print ( " O"* i )
Мы специально построили цикл по переменной так, чтобы п е-
ременная i (она принимает последовательно все целые знач е-
ния от 1 до n) при каждом повторении цикла совпадала с дл и-
ной очередной цепочки символов «O».
Переменная i – это локальная переменная, она введена и
используется внутри процедуры. Другие процедуры и о сновная
программа не могут обращаться к «чужой» локальной переме н-
ной. В д ругих процедурах тоже можно создать локальные пер е-
менные с таким же именем i, но они будут связаны уже с др у-
гими областями памяти, то есть это будут другие переменные.
Локальная переменная — =это переменная, введённая =внутри
подпрограммы. Другие подпрограм мы и основная программа не
могут к ней обращаться. =
=
Локальная переменная создаётся только при вызове пр о-
цедуры. Как только работа процедуры закончена, все локал ь-
ные переменные удаляются из памяти.
Имена локальных переменных в каждой подпрограмме
можно выб ирать независимо от имён локальных переменных
других подпрограмм . Э то очень облегчает коллективную работу
O
OO
OOO
OO OO
n

Информатика, 9 класс К.Ю. Поляко?:?j емин
60 http://kpolyakov. spb .ru

07.04.2019
программистов , каждый из которых может использовать любые
имена локальных переменных в своих процедурах .

П осмотрим на так ую программу:
def show ():
print ( i )
В процедуре выводится значение i, но откуда его взять? Тран с-
лятор сначала ищёт локальную переменную с таким именем –
её нет. Потом он начинает искать глобальную переменную: если
такая переменная есть, на экран выводи тся её значение, если
нет – будет выдано сообщение об ошибке.
Теперь посмотрим на другую процедуру:
def show Local ():
i = 2
print ( i )
Даже если существует глобальная переменная i, в первой
строчке этой процедуры будет создана новая локальная пер е-
мен ная i, и её значение (2) появится на э кране.
Что же делать, если в процедуре необходимо изменить
именно глобальную переменную? Пусть переменная i – гл о-
бальная, её значение задано в основной программе:
i = 15
Изменим её значение в процедуре. Для этого нужн о явно
сказать , что она глобальная, используя к оманду global :
def s how Global():
global i
i = 2
print ( i )
Эта процедура работает с глобальной переменной i. Она пр и-
своит ей новое значение 2 (это «увидят» все остальные подпр о-
граммы!) и выведет его на экран.
Ещё раз подчеркнём, что если мы забудем написать инс т-
рукцию global , транслятор, не сомневаясь, создаст в памяти
новую локальную переменную и будет с ней работать. Глобал ь-
ная пер еменная при этом не изменится.

Информатика, 9 класс К.Ю. Поляко?:?j емин
61 http://kpolyakov. spb .ru

07.04.2019
Нужно стараться писать процедуры, которые не обращаю т-
ся к глобальным переменным (как говорят, не имеют побочных
эффектов). Работа процедуры в идеале должна зависеть только
от переданных значений параметров, тогда можно легко и с-
пользовать её в другом проекте. К сожалению, в языке PWKRQ
это не все гда выполнимо.

Несколько параметров
Давайте немного улучшим процедуру: сделаем так, чтобы
можно было изменять не только длину строки, но и символы, из
которых она строится. Для этого добавим в процедуру ещё один
параметр, котор ый можно назвать symbol :
def printLine( symbol, n ):
print ( symbol *n )
Имена параметров в заголовке процедуры отделяются запятой.
Чем больше параметров у процедуры, тем больше разных
задач она может решать, но тем сложнее её понимать и легче
сделать ошиб ку. Поэтому не рекомендуется передавать в проц е-
дуру больше 3 -4 параметров.
Запишите в тетради полный текст процедуры
printLine , которая использует цикл с условием вместо
операции «умножения» символьных строк .
Что будет выведено на экран при выполнении фр агмента
программы
printLine( ' -', 10 )
printLine( '=', 7 )
printLine( 'o', 5 )

Процедуры ^jm]bo языках программироZgby
Процедура printLine с одним параметром на язык е Паскаль и
м ожет быть записана так:
procedure printLine( n: integer );
var i: integer;

Информатика, 9 класс К.Ю. Поляко?:?j емин
62 http://kpolyakov. spb .ru

07.04.2019
begin
for i:=1 to n do
write(' -');
writeln
end;
П роцедура начинается слов ом procedure , тело процедуры за-
ключено между служебными словами begin и end . После им е-
ни параметра процедуры n через двоеточие указывают тип это й
величины (англ. integer – целый ). Процедура должна распол а-
гаться выше основной пр ограммы.
Вот вариант этой же процедуры на языке С++:
void printLine ( int n )
{
int i;
for( i=1; i<=n; i++ )
putchar(' -');
}
Признак процедуры – слово void в заголов ке (вместо
procedure на Паскале). Тело процедуры заключено в фигу р-
ные скобки. Встроенная функция putchar выводит на экран
один символ , который заключён в апострофы («одиночные к а-
вычки») .
Рекурсия
Составим процедуру, которая выводит на экран двоичную
запись натурального числа. Поскольку мы хотим использовать
процедур у для разных чисел , это должна быть процедура с п а-
раметром:
def printBin( n ):
...
В теле процедуры должен быть алгоритм для перевода чи с-
ла в двоичную систему. Один такой алгоритм мы знаем: нуж но
делить число на 2, каждый раз выписывая остаток от деления,
пока не получится 0. На языке Python этот алгоритм можно з а-
писать так:

Информатика, 9 класс К.Ю. Поляко?:?j емин
63 http://kpolyakov. spb .ru

07.04.2019
while n != 0:
print( n % 2, end="" )
n = n // 2
Напомним, что именованный аргумент end , равный пустой
строке "" , откл ючает переход на новую строку в конце работы
функции print (иначе все цифры будут выведены в столбик).
Проверьте вручную работу этого алгоритма для числа 6.
Удалось ли вам получить правильный ответ? Почему?
Проблема только в том, что первой мы получаем по сле д-
нюю цифру двоичной записи, поэтому остатки выводятся в о б-
ратном порядке (не так, как нужно!) .
Есть разные способы решения этой задачи, которые сводя т-
ся к тому, чтобы запоминать остатки от деления (например, в
символьной строке) и затем, когда результат полностью пол у-
чен, вывести его на э кран. Однако можно применить ещё один
красивый подход. Идея такова: чтобы вывести двоичную з а-
пись числа n, нужно сначала вывести двоичную запись числа
n // 2, а затем – его последнюю двоичную цифру , которая вычи с-
ляется как n % 2.
Что же получилось? Прочитайте еще раз фразу, выделе н-
ную курсивом в предыдущем абзаце . Выходит, что для того,
чтобы решить задачу для исходного числа, нужно предвар и-
тельно решить ту же самую задачу для меньшего числа, n // 2.
Такой алгоритм оче нь просто программируется:
def printBin( n ):
printBin ( n // 2 )
print ( n % 2 , end="" )
У нас получилось, что процедура printBin вызывает сама себя!
Такой приём в программировании называется рекурсией , а
процедура – рекурсивной.
Рекурсивная процедура — =это процедура, которая вызывает
сама себя. =

Информатика, 9 класс К.Ю. Поляко?:?j емин
64 http://kpolyakov. spb .ru

07.04.2019
Проверьте с помощью отладчика в пошаговом режиме,
что произойдет при вызове этой процедуры.
Приведённая процедура printBin ошибочна, вернее, она
не доделана. Представим себе, что мы передали процедуре чи с-
ло 2. Сначала она вызывает сама себя для значения 2 // 2 = 1,
затем – для значения 1 // 2 = 0, и потом ещё бесконечно много
раз для нуля. Такие вызовы никогда не закончатся и програ м-
ма зациклится. Чтобы этого не произошло, нужно выйти из
процедуры (и закончить э ти вложенные вызовы), когда знач е-
ние п араметра стало равно нулю:
def printBin( n ):
if n = = 0: return
printBin( n // 2 )
print ( n % 2 , end=" " )
Убедимся, что теперь процедура остановится при любом
заданном натуральном числе. Д ействительно, при каждом вл о-
женном вызове значение параметра уменьшается (делится на
2). В результате когда -нибудь оно обязательно станет равно н у-
лю, и вложенные вызовы закончатся.
Сформулируйте алгоритм вывода цепочки из n оди на -
ковых символов, использу ющий рекурсию. Напишите рекур -
сивную процедуру. Попробуйте придумать два варианта
решения задачи .

Практическая работа №20. Процедуры
Практическая работа №21. Рекурсивные процедуры
Выh^u:
Процедура – это вспомогательный алгоритм (подпрограмма),
решающий самостоятельную задачу, который может использ о-
ваться несколько раз.

Информатика, 9 класс К.Ю. Поляко?:?j емин
65 http://kpolyakov. spb .ru

07.04.2019
Локальная переменная — это переменная, объявленная вну т-
ри подпрограммы. Другие подпрограммы и основная пр о-
грамма не могут к ней обращаться.
Параметр — это величина, от которой зависит работа подпр о-
граммы. Параметр имеет имя, в теле п одпрограммы с ним
можно работать так же, как с локальной переменной.
Аргумент — это значение параметра, которое передаётся по д-
программе.
Рекурсивная процедура — это процедура, которая вызывает
сама себя.
Нарисуйте интеллект -карту этого параграфа.
Вопросы и задания
1. Зачем нужны процедуры ?
2. Достаточно ли включить процедуру в текст программы, чт о-
бы она «сработала»?
3. Какие возможности появляются, когда в процедуру доба в-
ляются параметры?
4. Как определить, что переменная – локальная?
5. Имеет ли смысл оформлять процеду ру, если она вызывается
в программе только один раз? Обсудите достоинства и н е-
достатки так ого решения.
Задачи
1. Напишите процедуру, которая принимает два параметра :
символ c и натуральное число N , и выводит на экран тр е-
угольник из символов c со стороной N . Н апример, при c = "o"
и N = 5 мы должны п олучить
o
oo
ooo
oooo
ooooo
2. Напишите процедуру, которая принимает два параметра –
W и H , – и рисует на экране рамку из точек, ширина кот о-

Информатика, 9 класс К.Ю. Поляко?:?j емин
66 http://kpolyakov. spb .ru

07.04.2019
рой равна W , а высота – H . Например, для W = 6 и H = 4
програ м ма должна вывест и рисунок:
......
. .
. .
......
3. Напишите процедуру, которая выводит на экран в столбик
все ци ф ры переданного ей числа, начиная с последней.

4. Напишите процедуру, которая выводит на экран все дел и-
тели п ереданного ей числа ( в одну строчку через пробел ).
5. *Напишите процедуру, которая выводит на экран в столбик
все цифры переданного ей чи сла, начиная с первой.
6. *Напишите процедуру, которая выводит на экран запись
переда нного ей числа в римской системе счисления.
7. *Напишите процеду ру, которая принимает числовой пар а-
метр – возраст человека в годах, и выводит этот возраст со
словом «год », «года » или «лет ». Например, «21 год », «22 г о-
да », «12 лет ».
8. *Напишите процедуру, которая выводит переданное ей
число пр описью. Например,
21 «два дцать один».
9. Напишите рекурсивную процедуру для перевода числа в
восьм еричную систему счисления.
10. Напишите рекурсивную процедуру для перевода числа в
любую систему счисления с осн ованием от 2 до 9.
11. *Напишите рекурсивную процедуру для перевода числа в
шестна дцатеричную систему счи сления.

Темы сообщений:
а) «Рекурсия в природе и искусстве »
б) «Ханойские башни»

Информатика, 9 класс К.Ю. Поляко?:?j емин
67 http://kpolyakov. spb .ru

07.04.2019
§ 25. Функции
Ключевые слова :
функция
вызов функции
параметры
рекурсивная функция
Что такое функция ?
Представьте себе, что вы за казываете товар с доставкой по
телефону или в Интернет -магазине. Если говорить на языке
программистов, вы вызываете вспомогательный алгоритм (по д-
программу) . Но, в отличие от процедуры, исполнитель этого а л-
горитма не только выполняет какие -то действия, но и возвр а-
щает результат – товар, который вам привозит курьер. Это
второй тип вспомогательных алгоритмов (подпр ограмм). Такие
подпрограммы называ ю тся функци ями .
Функция — =это вспомогательный алгоритм, который возвр а-
щает результат (число, строку симв олов и др .). =
П остроим функцию, которая возвращает среднее арифм е-
тическое двух целых чисел.
Какой тип данных подходит для хранения среднего
арифметического двух ц елых чисел?
Функция принимает два параметра – исходные целые
числа и возвращает результат , который мо жет быть веществе н-
ным число м :
def Avg ( a, b ):
sr ed = ( a+b)/2
return sred
Заголовок функции ничем не отличается от заголовка пр о-
цедуры. В языках PWKRQ и C++ (в отличие, например, от Па с-
каля) процедуры рассматриваются как функции особого типа,
не возвр ащающие никакого результата.
Функция возвращает результат, записанный после спец и-
ального оператора return . В нашем примере функция Avg во з-
вращает результат – значение локал ьной переменной sred .

Информатика, 9 класс К.Ю. Поляко?:?j емин
68 http://kpolyakov. spb .ru

07.04.2019
Используя дополнительные источники, выясните, что
означает ан глийское слово average , от которого обра зова -
но название функции Avg .
Если вызвать функцию так же, как и процедуру:
Avg (5, 9)
то значение , которое она вернула, потеряется. Но его можно с о-
хранить в переменной:
sr = Avg (5, 9)
В операторе присваивания вмест о вызова функции транслятор
«подставляет» результат вызова – то значение, которое эта
функция вернёт. Поэтому предыдущий оператор равносилен
такому:
sr = 7
Результат функции можно сразу вывести на экран:
print ( Avg (4, 8) )
Что будет выведено на экран в ре зультате работы этого
фрагмента программы:
sr = Avg(3, 5)
print ( sr + Avg (7, 11) );
Функции можно передавать не только постоянные аргуме н-
ты (числа, символы, строки и др.), но также значения переме н-
ных и арифметических выражений:
a = 5
b = 7
sr = Avg (a, b+8)
В этом случае первый аргумент функции будет равен 5, а вт о-
рой – 15.
Наша функция Avg возвращает вещественное число, поэт о-
му вызовы этой функции можно применять везде, где можно
использовать вещественное число, в том числе в арифметич е-
ских выражениях, ус ловных операторах и циклах. Например ,
c = 2* Avg (x, y) + z
if Avg (a, b) > 4:
print( " СbklZlvсех на_jo !" )

Информатика, 9 класс К.Ю. Поляко?:?j емин
69 http://kpolyakov. spb .ru

07.04.2019
while Avg (a, b) < x:
a += 1
Найдите значени я переменных a, b и x, при которых в
результате работы этого фрагмента программы будет
выведено соо бщение «Да!»:
if Avg(a, b) > x :
print ( "Да! " )
Найдите начальные значения переменных a, b и x, при
которых этот цикл выполнится ровно 4 раза:
while Avg(a, b) < x -1:
b += 1

Функции ^jm]boyaudZoijh]jZffbjhания
Функция Avg на язык е Паскаль может быть записана так:
function Avg(a, b: integer): real;
begin
Avg :=( a+b)/2
end .
В языке Паскаль заголовок функции начинается словом fun c-
tion . В скобках перечисляются параметры (как у процедур) , а
после скобок через двоеточие записывают тип рез ультата – real
(в ещ естве нное число). Результат функции (возвращаемое зн а-
чение) нужно сохранить в специальн ой переменн ой , имя кот о-
рой со впадает с именем функции 4.
Вот вариант той же функции на языке C++:
float Avg( int a, int b )
{
return (a+b)/2.0;
}

4 В современных версиях языка П аскал ь можно также использовать специ аль -
ную переменную Result .

Информатика, 9 класс К.Ю. Поляко?:?j емин
70 http://kpolyakov. spb .ru

07.04.2019
Как и в языке PWKRn , результат работы функции – это знач е-
ние, записанное после служебного слова return («вернуть»).
Тело функ ции в заключается в фигурные скобки.
По умолчанию (если не указано иначе) в языке С ++ при
дел ении целого числа на целое получается це лое число (остаток
отбрасывается). Чтобы получить вещественный результат, мы
разделили сумму a+b (целое чи сло) на вещественное число 2 ,0.
Изучите текст программы на языке С ++ , сравните его с
программой на Паскале и выясните, как в языке С ++
указывается, ч то результат работы функции –
вещественная велич ина .

Примеры функций
Задача 1. Составить функцию, которая определяет на и-
большее и з двух целых чисел .
Алгоритм определения наибольшего из двух чисел вы уже
знаете из курса 8 класса . Остаётся только «завернуть» его в
функцию. Напр имер, так:
def Max( a, b ):
if a > b :
maximum = a
else :
maximum = b
return maximum
Одна функция может вызывать другую. Например, можно
составить функцию Max3 , которая возвращает наибольшее из
трёх чисел, испол ьзуя готовую функцию Max :
def M ax3( a, b, c ):
return Max( Max(a,b), c )
Постройте функцию Max4 , которая вычисляет наиболь -
шее из четырёх чисел, используя функцию Max . Приведите
два варианта решения задачи.

Информатика, 9 класс К.Ю. Поляко?:?j емин
71 http://kpolyakov. spb .ru

07.04.2019
Задача 2. Составить функцию , которая вычисляет сумму
цифр натурального числа.
Последняя цифра – это остаток от деления числа на 10 ( ре-
зультат операци и % ). Для того чтобы « удалить » последнюю
ци ф ру чи сла, можно разделить его на 10 без остатка (операция
// ). Ч тобы получить нужный результат, на ка ждом шаге цикла
«от резаем» от числа после днюю цифру, добавляем её значение к
сумме, и з атем удаляем её из числа. Цикл заканчивается, когда
все цифры уд алены и о сталось нулевое значение:
def sumDigits( n ):
summa = 0
while n != 0:
digit = n % 10
summa += digit
n = n //10
return summa
Как нужно изменить функцию, чтобы она вычисляла
количество цифр числа ?
Как нужно изменить функцию, чтобы она вычисляла
количество единиц в двоичной записи числа.

Задача 3. Состави ть функцию, которая удаляет все дво й-
ные пробелы в символьной строке, заменяя их на одино чные.
Ответьте на вопросы по условию задачи:
какие исходны е данны е (параметр ы ) принимает фун к-
ци я?
какой тип данных нужно использовать для хранения
исхо дных данных?
чт о будет результатом работы этой функции?
какой тип данных нужно использовать для хранения
резул ьтата?
нужно ли внутри функции использовать цикл?

Информатика, 9 класс К.Ю. Поляко?:?j емин
72 http://kpolyakov. spb .ru

07.04.2019
если цикл нужен, то какого типа должен быть цикл (с
известным числом повтор ени й или с условием)?
Функция приним ает один параметр – символьную строку,
и возвращает тоже символьную строку, поэтому её заголовок
выглядит так:
def noDSp( s ):
...
Поскольку двойных пробелов может быть много, в пр о-
грамме нужен цикл. Так как неизвестно, сколько двойных пр о-
белов есть в ст роке , это будет цикл с условием ( while ). Он до л-
жен остановиться, когда дво йных пробелов больше не осталось.
С помощью какой функции можно определить, что в
символьн ой строке больше нет двойных пробелов? Как её
нужно использовать?
Запишите в тетради опера торы языка програм ми ро ва -
ния , с помощью которых:
в переменную p записывается номер символа в строке s,
с которого начинается дво йной пробел;
из строки s удаляется один символ в позиции p.
Приведём полный текст функции:
def noDSp( s ):
p = s.find( ' ' )
while p >= 0:
s = s[:p] + s[p+1:]
p = s.find( ' ' )
return s
Изучите текст функции и ответьте на вопросы:
что означает условие p 0 в заголовке цикла?
что произойдет, если удалить строчку с вызовом мет о-
да find перед циклом? а если удалит ь т акую же строчку
внутри цикла?

Информатика, 9 класс К.Ю. Поляко?:?j емин
73 http://kpolyakov. spb .ru

07.04.2019
Логические функции
Программисты часто используют логические функции, во з-
враща ю щие логические значения («да»/«нет», «истина»/«ложь»,
True /False ). Такие функции полезны для того, чтобы опред е-
лять, успешно ли в ы полнена задача или обладают ли данные
каким -то свойством.
Мы напишем простую функцию, которая определяет чё т-
ность числа – возвращает значение «да» (в Python оно обознач а-
ется как True ), если число -параметр чётное , и «нет» ( False ), если
нечё тное:
def Even ( n ):
return (n % 2 = = 0)
В правой части оператора return записано условие: р е-
зультатом функции будет «да» ( True ), если условие истинно, и
«нет» ( False ), если оно ложно. Можно было записать то же самое
иначе:
if n % 2 == 0:
return True
else :
return False ;
но эта зап ись более длинная и опытные программисты так не
делают.
Запишите в развёрнутой форме возврат логического
значения из функции :
return (a > b + c)
Запишите в краткой форме возврат логического значения
из функции :
if a + b > 10 :
re turn False
else :
re tu rn True
Результат, который возвращает логическая функция, м ож-
но использовать во всех условиях как обычное логическое зн а-
чение. Напр имер, так:

Информатика, 9 класс К.Ю. Поляко?:?j емин
74 http://kpolyakov. spb .ru

07.04.2019
if Even(a):
half = a // 2
или так :
count = 0
while Even (x):
x = x // 2
count += 1
Найдите значени я переменны х a и b, при которых в
результате работы этого фрагмента программы будет
выведено сообщение «Да!»:
if Even( a+3*b ):
print ( "Да !" )
Найдите значени е переменн ой a, при котор ом этот цикл
выполнится ровно 4 раза:
while Even( a ) and a > 5 :
a = a // 2
Ре курсия
Вы уже знакомы с рекурсивными процедурами , которые
вызывают сами себя. Функции тоже могут быть рекурсивными,
в некоторых случаях это позволяет записать решени е задачи
намн ого проще.
Рекурсивная функция — =это функция, которая вызывает с а-
ма себя. =
Вер нёмся к задаче вычисления суммы цифр числа. Можно
сформ улировать алгоритм её решения так: сумма цифр числа N
равна значению последней цифры плюс сумма цифр числа, п о-
лученного отбрас ы ванием последней цифры .
Вход: натуральное число N .
Шаг 1. d = N % 10
Шаг 2. M = N // 10
Шаг 3. s = сумма цифр числа M
Шаг 4. sum = s + d
Результат: sum .

Информатика, 9 класс К.Ю. Поляко?:?j емин
75 http://kpolyakov. spb .ru

07.04.2019
Итак, для того чтобы найти сумму цифр числа, нужно сложить
его последнюю цифру и сумму цифр другого числа , то есть в ы-
полнить тот же самый алгоритм, только с другими исход ными
данными (эта строка в записи алгоритма выделена фоном ).
Получился рекурсивный алгоритм , в программе его можно з а-
писать в в иде рекурсивной функции:
def sumDigRec( N ):
if N == 0: return 0
d = N % 10
s = sumDigRec ( N // 10 )
return s + d
Изуч ите текст функции и ответьте на вопросы:
зачем добавлен условный оператор в начале функции ?
что произойдет, если удалить этот условный оператор ?
как можно доказать, что для любого целого числа реку р-
сия обязательно закончится?
В рекурсивном варианте функции исчез цикл, поэтому
можно сделать вывод: рекурсия м ожет заменить цикл. Верно и
обратное: любую рекурсивную функцию можно записать без р е-
курсии, с помощью циклов. Решение с помощью цикла (оно н а-
зывается итерационным ) обычно работает быстрее, чем реку р-
сивно е, и требует меньше памяти. О днако рекурсивное решение
очень часто короче и проще для понимания.

Практическая работа №22. Функции
Практическая работа №23. Функции -2
Выh^u:
Функция — это подпрограмма, которая возвращает резул ьтат
(число, строку символов и др.).
Вызов функции можно использовать в арифметических выр а-
жениях и условиях так же, как и переменную того типа, кот о-
рый возвращает функция.
4

Информатика, 9 класс К.Ю. Поляко?:?j емин
76 http://kpolyakov. spb .ru

07.04.2019
В теле функции можно вызывать другие функции и процед у-
ры.
Логическая функция возвращает логическое значение «ист и-
на» (True ) или «ложь » ( False).
Рекурсивная функция – это функция, которая вызывает сама
себя.
Нарисуйте интеллект -карту этого параграфа.
Вопросы и задания
1. Чем функция отличается от процедуры?
2. Определите, какие распоряжения начальника можно сч и-
тать выз овом процедуры, а какие – вызовом функции:
а) «Проводите Ивана Ивановича!»
б) «Принесите, пожалуйста, кофе!»
в) «Подготовьте годовой отчёт!»
г) «Постройте конуру для собаки!»
3. Как по тексту программы определить, значение какого типа
во звращает функция?
4. Сравните рекурсивное решение задачи о с умме цифр числа
и решение с помощью цикла. Какое из них вам больше нр а-
вится? Обс удите этот вопрос в классе.
Задачи
1. Напишите функцию, которая вычисляет среднее арифмет и-
ческое пяти целых чисел.
2. Напишите функцию, которая находит количество цифр в
десяти чной з аписи числа.
3. Напишите функцию, которая находит количество единиц в
двои чной записи числа.
4. Напишите функцию, которая удаляет из символьной строки
все пробелы в начале строки и возвращает новую строку.

5. Напишите функцию, которая в озвращает последнюю цифру
дес ятичной записи числа.

Информатика, 9 класс К.Ю. Поляко?:?j емин
77 http://kpolyakov. spb .ru

07.04.2019
6. Напишите функцию, которая определяет минимальное из
пяти ч исел.
7. Напишите функцию, которая «разворачивает» десятичную
запись трёхзначного числа наоборот, например, из числа
123 получается 321, а из 210 – 12 .
8. Напишите функцию, которая возвращает количество цифр
в вос ьмеричной записи числа. Число вводится в десятичной
системе счисления.
9. Напишите функцию, которая возвращает количество дел и-
телей н атурального числа.
10. *На соревнованиях выступление спортсмена оценив ают 5
экспертов, каждый из них выставляет оценку в баллах (ц е-
лое число). Для получения итоговой оценки лучшая и ху д-
шая из оценок экспертов отбрасываются, а для оставшихся
трёх находится среднее арифметическое. Напишите фун к-
цию, которая принимает 5 оценок э кспертов и возвращает
итоговую оценку спортсмена.
11. Напишите функцию, которая удаляет из символьной строки
все пробелы в начале и в конце строки и возвращает новую
строку.
12. Напишите функцию, которая возвращает первое слово из
символьной строки (слева и справ а от этого слова может
быть сколько угодно пробелов).
13. Напишите функцию, которая заменяет в символьной строке
все точки на запятые и возвр ащает новую строку.
14. *На веб -странице команды разметки (тэги) заключаются в
угловые скобки <>. Напишите функцию, которая удаляет в
символьной стр оке все тэги и возвращает новую строку.
15. *Напишите функцию, которая вычисляет значение ари ф-
метическо го выражени я, содерж аще го только целые числа и
знаки сложения и вычитания. Выражение записано в си м-
вол ьной строке.
16. Напишите логическ ую функцию, которая возвращает зн а-
чение «и стина», если переданное ей число помещается в 8 -

Информатика, 9 класс К.Ю. Поляко?:?j емин
78 http://kpolyakov. spb .ru

07.04.2019
битную ячейку памяти (вспомните, какое минимальное и
максимальное число можно записать с помощью 8 битов).
17. *Напишите логическую функцию, которая возвращает зн а-
чение « истина», если переданное ей число простое (делится
только на само себя и на единицу).
18. *Напишите рекурсивную и нерекурсивную функции, кот о-
рые вычисля ю т наибольший общий делитель (НОД) двух
натуральных чисел с помощью алгоритма Евклида. Алг о-
ритм Евклида : зам енять наибольшее из двух чисел на их
разность до тех пор, пока числ а не стан ут равны. Получе н-
ное значение этих чисел и есть их НОД.
19. *Напишите рекурсивную и нерекурсивную функции, кот о-
рые вычисляют наибольший общий делитель (НОД) двух
натуральных чисел с по мощью модифицированного (улу ч-
шенного) алгоритма Евклида. Модифицированный а лг о-
ритм Евклида : заменять наибольшее из двух чисел на о с-
таток от деления большего на меньшее до тех пор, пока этот
остаток не станет равен нулю. Тогда второе число и есть
НОД.

Сообщить о нарушении / Abuse

Все документы на сайте взяты из открытых источников, которые размещаются пользователями. Приносим свои глубочайшие извинения, если Ваш документ был опубликован без Вашего на то согласия.