ИНФОРМАТИКА · 8 КЛАСС
Глава 1. Основы алгоритмизации и программирования

§ 7. Использование основных алгоритмических конструкций для решения практических задач

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

Попробовать на модели ↓
Разбираемся в теме

Основные пункты параграфа

1

Использование числовых последовательностей

Формула, связь с предыдущим элементом, случайные числа.

Числовые последовательности позволяют описывать многие процессы, происходящие в природе и обществе. Например, последовательность чисел 2, −1, 0, 2, 0, 1, −2 может задавать значения температуры по дням недели; последовательность 2970, 3041, 3002 — значения средней заработной платы сотрудников по месяцам квартала и т. п.

Последовательности могут задаваться формулой, в которой значение элемента зависит от его номера в последовательности (пример 7.1). Другим способом задания является определение значения нового элемента через значение предыдущего (пример 7.2). Есть последовательности, которые можно задавать и первым, и вторым способом (пример 7.3). Последовательности могут строиться и из случайных чисел.

Пример 7.1. Элементы последовательности нечётных положительных чисел можно описать формулой an = 2n − 1, где n — номер элемента (минимальное n = 1): 1, 3, 5, 7… Элементы могут быть рациональными числами: формула an = n / (n² + 1) задаёт последовательность 0.5, 0.4, 0.3, 0.235…

Пример 7.2. Последовательность Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13… Каждый её элемент, начиная с третьего, равен сумме двух предыдущих: an = an−1 + an−2, a1 = 0, a2 = 1.

Пример 7.3. Последовательность 2, 4, 8, 16… можно задать формулой an = 2n, а можно заметить, что каждый элемент, начиная со второго, в два раза больше предыдущего: an = 2an−1 (для n > 1, a1 = 2).

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Последовательности на Python

Пример 7.4 выводит первые k чётных чисел (попробуйте k = 100). Пример 7.5 выводит числа Фибоначчи, меньшие x: в таблице трассировки видно, как значения «сдвигаются»: c = b, b = a.

Пример 7.4

Вывести на экран первые k чётных чисел. I. Исходные данные: k (количество чисел). II. Результат: k чётных чисел, начиная с 2. III. Алгоритм: для получения чётного числа запишем формулу an = 2n; количество чисел известно — цикл for; текущее число хранится в переменной a, его значение зависит от счётчика цикла n, который меняется от 1 до k; числа выводим через пробел. IV. Описание переменных: k, a — int.

k = int(input("k = "))
for n in range(1, k + 1):
    a = 2 * n
    print(a, end = " ")
k = 5
2 4 6 8 10

Пример 7.5

Вывести на экран все элементы последовательности Фибоначчи, меньшие x (x вводится). Выводим первые два элемента (0 и 1); числа, начиная с третьего, получают по формуле an = an−1 + an−2. Используются три переменные: значение, которое нужно вывести (a), и два предыдущих (b и c). После вывода значения a нужно «сдвинуть» значения переменных: c = b; b = a, — и получить новое значение a = b + c. Количество чисел заранее неизвестно — цикл while с условием a < x. IV. Описание переменных: x, a, b, c — int.

n1234567
Числа Фибоначчи0112358
Текущий шагcba
Следующий шагcba
x = int(input("x = "))
c = 0; b = 1
# вывод первых двух элементов
print(c, b, end = " ")
a = c + b
while a < x:
    # вывод текущего значения
    print(a, end = " ")
    # сдвиг
    c = b
    b = a
    # новый элемент
    a = b + c
x = 100
0 1 1 2 3 5 8 13 21 34 55 89

Чтобы узнать, сколько чисел получено, определим переменную k: она увеличивает своё значение на 1 каждый раз, когда выводится очередное число; после цикла выведем k.

x = int(input("x = "))
c = 0; b = 1;
print(c, b, end = " ")
a = b + c
k = 2
while a < x:
    print(a, end = " ")
    k += 1 # подсчёт количества
    c = b
    b = a
    a = b + c
print()
print("k = ", k)
x = 1000
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
k =  17
НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Благотворительная лотерея

Пример 7.6: номера билетов — случайные числа от 1 до 100, выигрывают номера, кратные 5. Выполните программу несколько раз при n = 20: результат каждый раз разный.

Пример 7.6

Катя и Петя организовали благотворительную лотерею: случайным образом генерируют номер билета из промежутка [1; 100]. Выигрышный билет — тот, номер которого кратен 5. Определить, сколько выигрышных билетов среди n сгенерированных. До начала генерации выигрышных билетов нет: k = 0. В цикле for номер билета a = randint(1, 100) выводится на экран и проверяется: если остаток от деления на 5 равен нулю, k увеличивается на 1. IV. Описание переменных: n, k, a — int.

from random import *
n = int(input("n = "))
k = 0
for _ in range(n):
    # случайное число
    a = randint(1, 100)
    print(a, end = " ")
    # проверка выигрыша
    if a % 5 == 0:
        k += 1
print()
print("выиграло", k, "билета(ов)")

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

Главная мысль: Последовательность задают формулой от номера элемента (an = 2n) или через предыдущие элементы (an = an−1 + an−2); в программе её элементы получают в цикле.
2

Сумма, минимум и максимум

Пункты 7.2 и 7.3: накопление суммы и поиск наименьшего и наибольшего.

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Сумма, минимум и максимум

Пример 7.7: при m = 3 сумма равна 13.823…; проверьте m = 30, 100, 365. Пример 7.8: следите в таблице трассировки, когда меняется текущий минимум (максимум) m.

Нахождение суммы элементов числовой последовательности

Пример 7.7. В лаборатории выводят полезные бактерии. Количество бактерий (в млн) зависит от номера дня n: an = n³ / (√(n³) − n + 1). Определить, сколько бактерий вывели за m дней. Для вычисления суммы нужно последовательно добавлять количество бактерий за текущий день к уже полученной сумме s; начальное значение суммы s = 0. Количество дней известно — цикл for, n меняется от 1 до m. IV. Описание переменных: m — int, s, a — float.

from math import *
m = int(input("m = "))
# начальное значение суммы
s = 0
for n in range(1, m + 1):
    x = n ** 3
    # вычисление элемента
    # последовательности
    a = x / (sqrt(x) - n + 1)
    # изменение значения суммы
    s += a
print("всего бактерий", s, "млн")

Переменная x используется для того, чтобы значение выражения n ** 3 не вычислялось дважды; вместо n ** 3 можно писать n * n * n. Проверка на калькуляторе при m = 3: a1 = 1; a2 = 2³ / (√8 − 2 + 1) ≈ 4.38; a3 = 3³ / (√27 − 3 + 1) ≈ 8.45; s ≈ 13.82.

m = 3
всего бактерий 13.82300247729722 млн
m = 30
всего бактерий 2613.361980513916 млн

Нахождение минимального и максимального элементов

Пример 7.8. Последовательность из n целых положительных трёхзначных чисел генерируется случайным образом. Определить, какое минимальное число было сгенерировано. До генерации определим m = 1000 — это число заведомо больше любого элемента. На каждой итерации сравниваем сгенерированное число a с m: если a меньше m, заменяем m на a. После генерации число a выводится, чтобы увидеть все элементы последовательности. IV. Описание переменных: m, n, a — int.

from random import *
n = int(input("n = "))
m = 1000
for _ in range(0, n):
    # случайное число
    a = randint(100, 999)
    print(a, end = ' ')
    # сравнение с текущим
    # минимумом
    if a < m:
        m = a
print()
print("min = ", m)

Для определения максимального элемента нужно: а) заменить начальное значение m на 0 (это число заведомо меньше любого элемента); б) заменить знак «<» на знак «>» в условии команды ветвления: if a > m:.

from random import *
n = int(input("n = "))
m = 0
for _ in range(0, n):
    a = randint(100, 999)
    print(a, end = ' ')
    if a > m:
        m = a
print()
print("max = ", m)
Главная мысль: Сумму накапливают в переменной с начальным значением 0 (s += a); для минимума начальное значение берут заведомо больше любого элемента, для максимума — заведомо меньше.
3

Таблицы значений и графики функций

Форматный вывод и модуль matplotlib (пункты 7.4 и 7.5*).

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Таблица значений функции

Пример 7.9: значения выводятся строго одно под другим благодаря форматному выводу. Измените k и сравните столбцы.

Построение таблицы значений функции

Пример 7.9. Вывести таблицу значений функции y = (x + 2) / (x² + 3). Количество значений k вводится, начальное x = −3, шаг h = 0.5. В цикле for вычисляем и выводим значение аргумента и функции; новое значение аргумента получаем, увеличивая текущее на шаг h. IV. Описание переменных: k — int, x, y, h — float.

Для вывода значений строго одно под другим используют форматный вывод: он определяет количество позиций для вывода числа и количество цифр после запятой. Запись '{:7.2f}' означает, что для вывода переменной типа float (буква f) используется 7 позиций, после запятой выводятся 2 цифры. Само значение выводится с помощью функции format. Для целого числа: print('{:6d}'.format(k)) — 6 позиций, буква d означает вывод целого числа.

k = int(input("k = "))
x = -3; h = 0.5
for _ in range(k):
    # вычисление значения функции
    y = (x + 2)/(x * x + 3)
    # форматированный вывод чисел
    print('{:7.2f}'.format(x),
          '{:9.3f}'.format(y))
    x += h
k = 5
  -3.00    -0.083
  -2.50    -0.054
  -2.00     0.000
  -1.50     0.095
  -1.00     0.250

Добавим вывод границ таблицы:

k = int(input("k = "))
x = -3; h = 0.5
print('-----------------------')
print('|    x     |     y    |')
print('-----------------------')
for _ in range(k):
    y = (x + 2)/(x * x + 3)
    print('|',
          '{:7.2f}'.format(x),
          ' |',
          '{:9.3f}'.format(y),
          '|')
    x += h
print('-----------------------')

Построение графиков функций

В математике таблицу значений функции чаще всего строят для того, чтобы потом построить график. В Python для построения графиков можно использовать модуль matplotlib.pyplot. В окне графика есть инструменты управления: начальные настройки, сдвиг и масштабирование графика.

Запись на PythonОписание
xlabel(" ")задаёт название горизонтальной оси
ylabel(" ")задаёт название вертикальной оси
title(" ")задаёт имя графика
legend()выводит легенду
grid(f)добавляет сетку; если f = True, сетка видна, иначе — нет
scatter(x, y)рисует точки с координатами из x по горизонтальной оси и из y по вертикальной
plot(x, y)как scatter, но точки соединяются в том порядке, в котором заданы
show()показывает нарисованный график

Дополнительно потребуется функция linspace(x0, xn, k) из модуля numpy: она определяет диапазон значений x и количество точек, из которых будет состоять график.

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Графики функций (matplotlib)

Пример 7.11: постройте график при k = 100 и при k = 6 — линия станет ломаной. Вариант со scatter рисует отдельные точки. Пример 7.12 строит два графика с легендой.

Пример 7.11. Построить график функции y = (x + 2) / (x² + 3) на промежутке от −3 до 3. Задаём диапазон значений x, формулу для y, настройки координатной плоскости, строим и показываем график. Если строить график функцией plot, получим сплошную линию; если точек мало, линия будет выглядеть как ломаная — для гладкой линии нужно не менее 50 точек. Функция scatter рисует отдельные точки. IV. Описание переменных: k — int, x, y — float.

import matplotlib.pyplot as pl
import numpy as np
k = int(input("k = "))
# диапазон по x
x = np.linspace(-3, 3, k)
# функция
y = (x + 2)/(x * x + 3)
# надписи
pl.xlabel("x")
pl.ylabel("y")
pl.title("График функции")
# сетка
pl.grid(True)
# вывод графика
pl.plot(x, y)
pl.show()

В одной координатной плоскости можно построить графики нескольких функций: задать новое значение y1 и выполнить plot(x, y1) (аргумент x — тот же). Графики рисуются разными цветами из заранее определённой последовательности. Для выбора цвета и типа линии после x и y вставляется форматная строка: первая буква — цвет ('r' — красный, 'b' — синий, 'g' — зелёный и т. д.), дальше — тип линии ('-' — сплошная, '--' — пунктирная, '-.' — штрихпунктирная). Параметр linewidth определяет толщину линии, label — текст в легенде. В примере 7.12 добавлен график функции y = 0,3x².

import matplotlib.pyplot as pl
import numpy as np
k = int(input("k = "))
x = np.linspace(-3, 3, k)
y = (x + 2)/(x * x + 3)
y1 = 0.3 * x ** 2
pl.xlabel("x")
pl.ylabel("y")
pl.title("Графики функций")
pl.grid(True)
pl.plot(x, y, 'g-',
        linewidth = 2,
        label = '(x + 2)/(x*x + 3)')
pl.plot(x, y1, 'r--',
        linewidth = 2,
        label = '0.3 * x ** 2')
pl.legend(fontsize = 10)
pl.show()
Главная мысль: Таблицу значений функции выводят в цикле с форматным выводом '{:7.2f}'.format(x); график строят функциями linspace, plot или scatter и show.
4

Выделение цифр из числа

Остаток от деления на 10 — последняя цифра.

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Цифры числа

Пример 7.13: число делится на 10 до тех пор, пока не станет нулём; остаток от деления на 10 — очередная цифра. Попробуйте n = 1 и n = 0.

Пример 7.13. Дано натуральное число n. Вывести цифры числа по одной в строке (начиная с разряда единиц). Определить, сколько цифр в числе. II. Результат: z (текущая цифра), k (количество цифр). III. Алгоритм: начальное значение счётчика k = 0. Количество цифр числа равно количеству десятичных разрядов. Для нахождения каждой цифры: 1) найти остаток и целую часть от деления на 10 (остаток и будет очередной цифрой); 2) увеличить счётчик; 3) вывести цифру; 4) количество цифр заранее неизвестно — цикл while: пока целая часть от деления больше 0, в числе ещё есть цифры. IV. Описание переменных: k, n, z — int.

n = int(input("n = "))
k = 0
while n > 0:
    #текущая цифра
    z = n % 10
    print(z)
    #уменьшение числа в 10 раз
    n //= 10
    #подсчёт кол-ва цифр
    k += 1
print("в числе", k, "цифр(а)")
n = 13579
9
7
5
3
1
в числе 5 цифр(а)
Главная мысль: Последняя цифра числа — n % 10; команда n //= 10 отбрасывает её; цикл while n > 0 перебирает все цифры.
5

Наибольший общий делитель двух чисел

Алгоритм Евклида, функции gcd и lcm.

Наибольшим общим делителем (НОД) для двух целых чисел называют наибольший из их общих делителей. Например, для чисел 42 и 24 НОД равен 6. Один из алгоритмов нахождения НОД знаком по урокам математики: разложить каждое число на простые множители, выбрать общие и перемножить. Рассмотрим другой алгоритм — алгоритм Евклида:

  1. Вычесть

    Из большего числа вычитаем меньшее.

  2. Проверить

    Если получается 0, то числа равны друг другу, и значение НОД равно любому из них.

  3. Заменить

    Если результат не равен 0, большее число заменяем на разность большего и меньшего.

  4. Повторить

    Переходим к пункту 1.

Пример 7.14. Алгоритм Евклида для чисел 42 и 24:

№ab
14224
218 (42 − 24)24
3186 (24 − 18)
412 (18 − 6)6
56 (12 − 6)6
НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Алгоритм Евклида

Пример 7.15: в таблице трассировки — те же шаги, что в примере 7.14. Для 1449 и 596 ответ 1: числа взаимно простые. Пример 7.16 использует функции gcd и lcm библиотеки math.

Пример 7.15. Ира и Игорь коллекционируют значки: у Иры a значков, у Игоря — b. Ребята решили поделиться значками с друзьями. Какое наибольшее количество общих друзей может быть у Иры и Игоря, если каждый хочет разделить все свои значки между друзьями без остатка? Например, при a = 42 и b = 24 значки можно разделить, если общих друзей 1, 2, 3 или 6; наибольшее количество — 6. Ответом может быть только общий делитель чисел a и b, нужен наибольший. Опишем функцию nod(a, b): пока a и b не равны, если a > b, заменяем a на a − b, иначе заменяем b на b − a; функция может вернуть как a, так и b (они равны).

def nod(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a

a = int(input("у Иры a = "))
b = int(input("у Игоря b = "))
c = nod(a, b)
print("всего друзей =", c)
у Иры a = 42
у Игоря b = 24
всего друзей = 6

Для a = 1449, b = 596 получим «всего друзей = 1»: числа 1449 и 596 взаимно простые, и все значки достанутся одному другу.

В Python данные вводятся в виде строки. Функцию map используют, чтобы преобразование происходило не с одним числом, а с последовательностью чисел; функция split выделяет числа из строки по разделителю (по умолчанию — пробел): a, b = map(int, input().split()).

Пример 7.16. Написать программу вычисления НОД(x, y, z) и НОК(x, y, z). Числа вводятся в одной строке через пробел; воспользуемся функциями gcd() и lcm() библиотеки math. IV. Описание переменных: x, y, z, d, f — int.

from math import *
print("три числа через пробел")
x, y, z = map(int, input().split())
d = gcd(x, y, z)
#НОД
f = lcm(x, y, z)
#НОК
print("НОД =", d)
print("НОК =", f)
три числа через пробел
30 40 60
НОД = 10
НОК = 120

В учебнике в тексте теста указаны значения x = 20, y = 30, z = 60, но в окне результата введены 30 40 60 — для них НОД = 10, НОК = 120 (для 20, 30, 60 было бы НОД = 10, НОК = 60).

Главная мысль: По алгоритму Евклида, пока числа не равны, большее заменяют разностью большего и меньшего; оставшееся число — НОД. В библиотеке math есть функции gcd() и lcm().
Интерактивная практика

Исследуйте и примените

Текст программ в моделях можно изменять. Решите упражнения учебника и проверьте решения на нескольких наборах исходных данных.

ПРОБУЙТЕ САМИ

Последовательности, суммы, максимум

Упражнения 1–8: изменяйте программы и проверяйте их. Для факториала: 0! = 1, 2! = 2, 5! = 120, 10! = 3 628 800.

ПРОБУЙТЕ САМИ

Таблицы, цифры, НОД

Упражнения 11–17: таблица значений функции, обработка цифр числа, другой способ вычисления НОД, сокращение дроби.

Соберём главное

Шесть выводов

01

Числовую последовательность задают формулой от номера элемента или через предыдущие элементы; в программе элементы получают в цикле.

02

Для чисел Фибоначчи используют три переменные и «сдвиг» значений: c = b; b = a; a = b + c.

03

Сумму накапливают в переменной с начальным значением 0; минимум ищут, начиная с числа, заведомо большего любого элемента, максимум — с заведомо меньшего.

04

Форматный вывод '{:7.2f}'.format(x) выводит число на 7 позициях с 2 цифрами после запятой; '{:6d}' — целое число на 6 позициях.

05

Графики строят модулем matplotlib.pyplot: linspace задаёт точки, plot — линию, scatter — точки, show показывает график.

06

Цифры числа получают операциями n % 10 и n //= 10; НОД вычисляют алгоритмом Евклида или функцией gcd.

Самопроверка

Тест: 10 вопросов

Один верный ответ. За ответ — 1 балл. Откройте и проверьте себя.

1. Какую последовательность задаёт формула an = 2n − 1 при n = 1, 2, 3, …?

2. Какое число следует в последовательности Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, …?

3. Зачем в примере 7.5 выполняются команды c = b и b = a?

4. Какое начальное значение суммы s задают перед циклом в примере 7.7?

5. Почему в примере 7.8 для поиска минимума задают m = 1000?

6. Что означает запись '{:7.2f}'.format(x)?

7. Какая функция модуля matplotlib.pyplot соединяет точки графика линией?

8. Что выведет print(n % 10) при n = 13579?

9. Чему равен НОД чисел 42 и 24?

10. Как в алгоритме Евклида с вычитанием меняются числа a = 42, b = 24 на первом шаге?

ВыводыТестВ началоВсе параграфы
↑

Загрузка прогресса…

↑