Псевдокод и Python - одна запись, два читателя

В книгах алгоритмы пишут псевдокодом, в жизни - на языке. Разница не косметическая: псевдокод убирает то, что мешает рассуждать, и вместе с этим убирает то, без чего программа не запустится. Читать надо оба, поэтому здесь сразу разберём соответствие.

Как думаешь, почему в учебнике нумеруют с единицы

Классическая запись сортировки вставками выглядит так:

INSERTION-SORT(A)
1  for j = 2 to A.length
2      key = A[j]
3      i = j - 1
4      while i > 0 and A[i] > key
5          A[i+1] = A[i]
6          i = i - 1
7      A[i+1] = key

Нумерация с единицы здесь не традиция ради традиции: она позволяет писать «первые j-1 элементов уже упорядочены» без поправок. В Python индексы идут с нуля, и то же утверждение звучит «первые j элементов упорядочены». Обе записи верны, но смешивать их в одном рассуждении нельзя - отсюда берётся половина ошибок на единицу.

Ещё три соглашения псевдокода стоит знать заранее:

• отступ означает вложенность, как в Python, - фигурных скобок нет;
• = это присваивание, а == - проверка равенства - как в Python и в CLRS 3-го издания, по которому записан код выше. (В CLRS 2-го издания присваивание писали стрелкой ←, а = работал и как равенство; открыв старую книгу, держи разницу в голове.)
• A.length и подобные поля - это просто «свойство объекта», без указания, как оно хранится.

Разбор: та же сортировка на Python

for j in range(1, len(a)):
    klyuch = a[j]
    i = j - 1
    while i >= 0 and a[i] > klyuch:
        a[i + 1] = a[i]
        i = i - 1
    a[i + 1] = klyuch
print(a)

Изменилось три вещи: цикл идёт от 1 (нулевой элемент уже «отсортирован» сам по себе), условие стало i >= 0 вместо i > 0, A.length превратилось в len(a). Логика не изменилась ни на шаг. Дальше в курсе алгоритм сначала разбирается словами и псевдокодом, а потом сразу пишется на Python и прогоняется - иначе неизвестно, разошлись рассуждение и код или нет.

Что даёт машина курса

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

Считает шаги честно. Счётчик растёт не на строку, а на объём работы: проход по списку стоит столько элементов, сколько просмотрел, сортировка - n·log n, снятие из начала - сдвиг хвоста. Поэтому в отчёте видно настоящую цену решения, а не число строк.

Печатает таблицу роста. Если у набора данных объявлен размер, отчёт показывает, во сколько раз выросло число шагов при росте размера. Так порядок роста видно на своей программе: данных втрое больше - шагов втрое (линия), вдевятеро (квадрат) или чуть больше чем втрое (n·log n).

Разбор: как читать таблицу роста

Пусть задача прогнала одну и ту же программу на трёх наборах:

Размер растёт втрое, шаги - вдевятеро. Девять это три в квадрате, значит зависимость квадратичная. Если бы во второй колонке стояло 3,0 - линейная; если бы 3,3-3,5 - n·log n. Этой таблицы достаточно, чтобы поймать лишний вложенный цикл, не читая код.

Трасса

У любой программы в задаче есть пошаговый прогон: после каждой выполненной строки машина печатает значения всех переменных. Это та самая таблица трассировки, которую ты вёл руками в главе «Алгоритм и исполнитель», и пользоваться ей надо в том же порядке: сначала заполнить свою, потом сверить. Открыть машинную трассу раньше - значит прочитать ответ вместо того, чтобы его получить.

Теперь сам

Переведи на Python и скажи, что напечатает программа при A = [3, 1, 2]:

SUM-PREFIX(A)
1  s = 0
2  for i = 1 to A.length
3      s = s + A[i]
4      print s

s = 0
for i in range(len(a)):
    s = s + a[i]
    print(s)