Как думает программист

Ни одной строчки кода в этом уроке не будет. Вместо этого — один сундук с кодовым замком, который нужно вскрыть без единой отмычки. Интересно смотреть, как ты сам, с нуля, придёшь к тем же ходам мышления, которыми пользуются программисты — причём не к одному ходу, а сразу к нескольким, часто непохожим друг на друга.

01Что ты изучишь

• Два разных, одинаково законных способа заставить компьютер найти решение — грубый перебор и рассуждение по ограничениям
• Как человеческий план решения превращается в алгоритм — точную пошаговую процедуру — ещё до того, как появится хоть один язык программирования
• Восемь разных линз, через которые можно посмотреть на застрявшую задачу, — не рецепт «делай раз-два-три», а набор углов зрения, между которыми приходится выбирать
• Почему «сесть и сразу писать код» почти никогда не первый шаг — и почему даже заведомо неуклюжий план лучше, чем его отсутствие

02Зачем это раньше синтаксиса

В прошлом уроке появились инструкции и выражения — строительные кирпичи языка. Но кирпичи сами по себе ничего не строят: знание, что такое if, ещё не значит, что ты сможешь применить его к конкретной незнакомой задаче с первой попытки. Между «я знаю слова языка» и «я умею решить задачу» лежит отдельный навык, который редко объясняют явно — потому что к моменту, когда программист набирается опыта, этот навык работает у него на автомате и он сам о нём не задумывается. Здесь его проще выделить и показать без синтаксиса — синтаксис в первый раз слишком отвлекает внимание на себя.

03Сундук с тремя дисками

В игре, которую ты, возможно, когда-нибудь соберёшь, есть сундук с сокровищем. Замок на нём — три вращающихся диска, на каждом цифры от 0 до 9. Итого — тысяча возможных комбинаций, перебирать которые руками означало бы стоять у сундука очень, очень долго. На стене рядом — потускневшая надпись, оставленная кем-то давно:

1. Сумма всех трёх цифр равна 12.
2. Первая цифра ровно в два раза больше третьей.
3. Вторая цифра — нечётная.

Прежде чем читать дальше, стоит остановиться — но не над вопросом «какой код у сундука». Над другим: если бы код искал не ты, а бездумная машина, которая не умеет «просто увидеть» ответ и способна только выполнять точные инструкции одну за другой, — что бы ты ей поручил? Компьютер не умеет догадываться. Ему нужна процедура, которую можно выполнять механически, шаг за шагом, вообще не понимая по существу, что такое сундук, код или сокровище.

04Два способа заставить компьютер найти код

Здесь есть не один хороший ответ, а два — и оба честные. Ниже — оба по очереди, а не только тот, что покороче.

Способ А: грубый перебор. Компьютеру не нужно ничего понимать про сумму, чётность или соотношение цифр как единую систему — достаточно уметь проверять три отдельных факта про одну комбинацию и повторять эту проверку тысячу раз подряд. Вот эта процедура, расписанная так, чтобы её можно было выполнять, вообще не думая:

1. Взять следующую ещё не проверенную комбинацию, начиная с 0-0-0.
2. Проверить: сумма трёх цифр равна 12?
3. Если да — проверить: первая цифра равна удвоенной третьей?
4. Если да — проверить: вторая цифра нечётная?
5. Если все три проверки пройдены — запомнить эту комбинацию как подходящую.
6. Если хоть одна проверка не пройдена — отбросить комбинацию и вернуться к шагу 1 со следующей.
7. Повторять, пока не переберём все комбинации от 000 до 999.

Тысяча повторений для человека, крутящего диски руками, — форменная пытка. Для машины, которая умеет повторять одно и то же без раздражения и без усталости, — меньше секунды работы. Способ А не хитрый, зато его легко объяснить и легко проверить: в нём просто негде ошибиться, потому что он не требует ни одной догадки, только терпения. Это не «неправильный» алгоритм — это рабочий алгоритм с конкретной ценой: он платит временем там, где могла бы быть мысль.

Способ Б: сузить пространство поиска рассуждением. Раз уж мы не бездумная машина, а люди с ограниченным терпением, есть смысл поискать способ не перебирать тысячу вариантов вслепую, а сначала присмотреться к самим подсказкам — они явно даны не просто так, а чтобы перебор такого размера вообще не понадобился.

Переведём условие с человеческого языка на язык, с которым удобнее работать — обозначим цифры буквами. Пусть первая цифра — A, вторая — B, третья — C. Тогда три подсказки со стены превращаются в три равенства: A + B + C = 12, A = 2 × C, и «B — нечётное». Условие не стало короче, но теперь с ним можно возиться по частям, а не держать в голове длинное предложение целиком.

С какого из трёх равенств начать? Не с первого — оно связывает все три буквы сразу и само по себе почти ничего не сужает. Начать стоит с самого «тесного» условия — того, что жёстче всего ограничивает выбор. A = 2 × C — самое подходящее: если C — обычная цифра от 0 до 9, то A, будучи вдвое больше, не может быть больше 9 — а значит, C вообще не может быть больше 4. Одно равенство только что срезало диапазон для C с десяти вариантов до пяти (0, 1, 2, 3, 4) — и заодно сразу определило A для каждого из них: 0, 2, 4, 6 или 8.

Осталось подставить каждую из этих пяти пар в первое равенство и проверить третье. Раз A + B + C = 12, то B = 12 − A − C, а раз A всегда вдвое больше C, то B = 12 − 3 × C. Пройдёмся по всем пяти значениям C подряд, ничего не пропуская:

Из тысячи возможных комбинаций осталось ровно две: 2-9-1 и 6-3-3. Обе идеально подходят под все три подсказки одновременно — надпись на стене не называет единственный код, она просто не рассчитывала, что кто-то честно распишет условия по шагам вместо того, чтобы сразу перебирать всё руками.

Заметь, что оба способа доводят задачу до конца, и оба — законные алгоритмы, а не один правильный и один «для ленивых». Способ А почти не требует мысли, зато требует тысячи проверок. Способ Б требует нескольких минут рассуждения, зато сокращает работу до двух проверок. Какой выбрать — зависит от того, чего у тебя больше в моменте: времени машины или времени на подумать. Этот же выбор — обменять вычисления на рассуждение или наоборот — будет всплывать в курсе снова, когда речь пойдёт о том, что одни способы решить одну и ту же задачу быстрее других.

05От человеческого плана к алгоритму

Способ Б выше был рассказан как рассуждение — со всеми «почему» и попутными объяснениями. Но если вычленить из него только сами действия и выбросить объяснения, получится вот что:

1. Обозначить неизвестные буквами: A, B, C — вместо «первая, вторая, третья цифра».
2. Записать все три подсказки как равенства: A + B + C = 12, A = 2 × C, «B нечётное».
3. Из трёх равенств выбрать то, что жёстче всего ограничивает диапазон одной переменной — здесь это A = 2 × C.
4. Перебрать только значения C, допустимые этим равенством (0, 1, 2, 3, 4) — не все десять цифр.
5. Для каждого значения C вычислить A и B по формулам и проверить оставшееся условие — нечётность B.
6. Собрать все значения C, прошедшие проверку, — это кандидаты на решение.
7. Проверить оставшихся кандидатов физически, на самом замке.

Это уже не рассказ о числах — это алгоритм: точная, конечная последовательность шагов, которую можно передать кому-то другому (или чему-то другому) и каждый раз получать тот же результат. Компьютер не понимает, что такое «сундук» или «подсказка на стене», — но он прекрасно понимает пошаговую инструкцию вроде «для каждого значения C от 0 до 4 вычисли…». Через несколько уроков появятся переменные, условия и циклы — те самые кирпичики, которыми этот план запишут на C++. Сам план при этом не изменится ни на шаг — изменится только язык, на котором он записан: с русского на код.

06Несколько разных линз на мышление программиста

До сих пор в уроке был один путь мышления — путь к решению конкретно этой задачи с сундуком. Но свести программистское мышление к одному рецепту было бы неправдой: это скорее набор разных линз, через которые можно посмотреть на застрявшую задачу, и опытный программист не проходит по ним по порядку сверху вниз, а перебирает, какая подойдёт именно сейчас — иногда две линзы даже подсказывают противоположные ходы. Ниже — восемь таких линз, каждая с примером, отличным от сундука, чтобы было видно: это не приёмы решения именно этой головоломки, а привычки мышления, которые переносятся куда угодно.

1. План — даже заведомо неуклюжий — лучше, чем его отсутствие. Способ А из предыдущего раздела, перебор всех тысячи комбинаций, — плохой план по меркам человека, которому лень крутить диски тысячу раз. Но это всё равно план: он отвечает на вопрос «что делать прямо сейчас» в любой момент времени, а это единственное, что вообще делает план планом. Отсутствие плана выглядит иначе: сесть перед задачей, попробовать что-то наугад пару раз, отвлечься, вернуться, попробовать ещё раз — без единого способа сказать, сколько работы уже сделано и сколько осталось. Даже заведомо неэффективный план даёт то, чего никогда не даёт хаотичное тыканье: возможность остановиться на середине и точно понять, где ты находишься.

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

3. Раздели задачу — держать всё сразу в голове дороже, чем кажется. Три условия сундука проверялись не одновременно, а по очереди: сначала A = 2 × C резало список вариантов, затем для оставшихся пяти пар проверялась сумма, и только в конце — чётность. Слить все три проверки в одно многоэтажное условие было бы технически возможно, но удержать в голове сразу три взаимозависимых требования и ничего не перепутать — тяжелее, чем пройти по ним по одному. Задача, которая на бумаге выглядит как один большой шаг, почти всегда прячет внутри несколько маленьких, которые проще решать по отдельности.

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

5. Урежь задачу — временно убери часть трудности, чтобы освободить голову для оставшейся. Если бы на стене была только одна подсказка — «сумма равна 12» — задача решалась бы иначе: пришлось бы честно перебирать все комбинации, где цифры складываются в 12, а их не одна и не пять, а несколько десятков. Разобраться сначала с такой урезанной версией — не потому, что она нужна сама по себе, а чтобы понять, как вообще работает перебор, прежде чем добавлять к нему остальные условия, — законный рабочий приём, а не капитуляция перед полной задачей.

6. Ищи, где эта задача уже встречалась в другой одежде. За вычислительной сутью задачи про сундук стоит вопрос, который в программировании возникает постоянно под совсем другими декорациями: «есть несколько связанных друг с другом чисел и набор ограничений на них — какие сочетания допустимы». Тот же вопрос всплывёт, когда понадобится подобрать стартовые характеристики персонажа так, чтобы их сумма не превышала бюджет очков, или разложить предметы по ячейкам ограниченного размера. Форма задачи меняется, а внутренний скелет — нет; распознавать этот скелет через разные декорации — самый долго нарабатываемый из всех навыков в этом списке, потому что для него нужен уже накопленный запас решённых задач, с которыми можно сравнивать новую.

7. Проверяй экспериментом, а не догадкой. В финале разбора сундука было два оставшихся кандидата, и их проверка на реальном замке — не выстрел наугад, а контролируемый эксперимент: заранее было известно, что именно проверяется и почему кандидатов ровно два, а не сто. Настоящая догадка выглядела бы иначе — крутить диски, не считая, сколько вариантов вообще осталось и откуда взялись именно эти цифры. Разница между экспериментом и догадкой не в результате, а в том, знаешь ли ты заранее, что именно должно случиться, если гипотеза верна.

8. Разочарование — сигнал остановиться и сменить угол, а не работать усерднее. Если бы на моменте «с какого равенства начать» читатель продолжал давить в лоб — пробовать варианты по одному вручную, раздражаясь, что чисел слишком много, — правильным ответом было бы не «постараться сильнее» на том же пути, а остановиться и спросить: какое из трёх условий вообще самое узкое? Раздражение от задачи почти всегда означает не «задача слишком сложная», а «выбранный угол атаки не тот». Заметить это и переключиться на одну из линз выше почти всегда быстрее, чем упрямо продолжать давить в прежнем направлении.

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

07Вынесенные уроки

• Перебор всех 1000 комбинаций — не позорный, а вполне законный алгоритм; он просто платит временем там, где рассуждение платит усилием мысли.
• Не все три подсказки одинаково полезны в качестве отправной точки — начинать стоит с той, что сильнее всего сужает пространство вариантов.
• Человеческое рассуждение, если вычленить из него только действия и убрать объяснения «почему», превращается в алгоритм — точную пошаговую процедуру, которую дальше можно записать на любом языке программирования.
• Задача не обязана иметь единственный формально верный ответ на бумаге (условию удовлетворяют оба кода) — иногда решение находится только на последнем шаге, физической проверкой.
• «Как думает программист» — это не один рецепт, а восемь разных, иногда противоречащих друг другу углов зрения на застрявшую задачу.

08Проверь себя

Ниже — вопросы разных типов: не только «что это», но и «зачем», «что произойдёт», «объясни своими словами». Каждый вопрос сначала стоит попробовать закрыть рукой ответ и подумать самому — ответ открывается отдельно, он никуда не убежит.

09Мысленная разминка

Без кода, просто на подумать — те же ходы мышления, на новом материале:

10Что ты теперь умеешь

Здесь не было ни строчки кода, но именно поэтому легче увидеть навык отдельно от синтаксиса, в который он обычно завёрнут:

• Ты можешь для одной и той же задачи назвать два разных законных алгоритма — грубый перебор и рассуждение по ограничениям — и объяснить, чем один расплачивается за экономию другого.
• Ты можешь превратить человеческое рассуждение в пошаговый план, из которого убраны все «почему» и остались только действия, — то есть в алгоритм, а не просто в объяснение.
• Ты можешь заметить, что порядок, в котором условия перечислены, не обязан быть порядком, в котором их стоит применять, — и начать не с первого условия, а с того, что сильнее всего сужает выбор.
• Ты можешь узнать хотя бы одну из восьми линз мышления в чужом, не игрушечном контексте — в сообщении об ошибке компилятора, в поиске бага, в незнакомой задаче на .lab-task — а не только там, где она специально показана на сундуке.

11Кратко

• У одной задачи может быть несколько законных алгоритмов решения — грубый перебор и рассуждение по ограничениям — и выбор между ними зависит от того, чего у тебя больше: времени машины или времени на подумать.
• Человеческий план, если убрать из него объяснения и оставить только действия, — это уже алгоритм; код появится позже, но сама последовательность шагов не изменится.
• Из нескольких ограничений начинай с самого тесного — того, что сильнее всего сужает пространство вариантов.
• Мышление программиста — это не один рецепт, а набор из восьми разных линз (план, пересказ, разбиение, старт с понятного, упрощение, аналогия, эксперимент, работа с разочарованием), между которыми приходится выбирать заново для каждой новой задачи.