Зона кода

А давайте немного попрограммируем...

Задача о двенадцати монетах и трёх взвешиваниях

C99Решение задач

Рассмотрим следующую задачу.

Среди двенадцати монет одинакового достоинства имеется одна фальшивая (все остальные — настоящие). Фальшивая монета отличается от настоящей только весом. Необходимо с помощью трёх взвешиваний на весах, позволяющих сравнивать массы любых двух грузов, выяснить, какая из монет является фальшивой, и в какую сторону её вес отличается от веса настоящей монеты. Постройте алгоритм решения задачи и напишите реализующую его программу.

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

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

Такой подход я придумал и назвал его "информационным". Этот подход можно использовать для решения достаточно широкого круга задач на сравнительные взвешивания. В этой статье я познакомлю с ним читателя, опишу процесс построения с помощью него искомого алгоритма, а также приведу текст программы, написанной на языке C99, этот алгоритм реализующей.

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

Предварительные замечания

Перед тем, как мы обратимся к рассмотрению "информационного подхода", введём терминологию, которая потребуется нам в дальнейшем.

Совокупность результатов ряда взвешиваний назовём элементарным исходном взвешиваний. Если мы произвели три взвешивания, то элементарным исходом можно назвать, например, перевес левой чаши весов в первом взвешивании, равновесие чаш во втором и перевес правой чаши в третьем. Кратко такой элементарный исход можно записать в виде символов ">=<". Полагаю, смысл каждого из трёх символов сравнения в данном контексте понятен и не требует дополнительных пояснений.

Подозрительным набором монет назовём такой набор монет, о котором известно, что одна из монет набора — фальшивая. Будем говорить, что фальшивая монета имеет тип "перевес", если она тяжелее настоящей, или тип "недовес", если легче. Эталонной монетой или эталоном будем называть монету, о которой известно, что она — настоящая.

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

Давайте сразу же рассмотрим пример. Попробуем ответить на вопрос. А хватит ли нам вообще информации, которую мы получим в результате трёх взвешиваний, для того, чтобы не только выяснить, какая монета является фальшивой, но и установить её тип?

Любая из 12-ти монет гипотетически может оказаться фальшивой (т. е. всего имеются 12 возможных вариантов), причём для каждого из вариантов допустимы 2 возможных типа фальшивой монеты. Таким образом, мы получаем 12 · 2 = 24 возможных вариантов ответа.

А сколько всего существует элементарных исходов трёх взвешиваний? Ответить на этот вопрос несложно. В общем случае результатом каждого взвешивания может быть один из трёх возможных вариантов, а взвешиваний всего три. В итоге, получаем 33 = 27 элементарных исходов.

Поскольку 27 > 24, гипотетически информации нам должно хватить, причём с запасом. Это не доказывает существование решения задачи, но если бы выяснилось, что количество вариантов ответов превышает число элементарных исходов, то мы могли бы утверждать, что задача решений не имеет.

В дальнейшем мы будем на основе "информационного подхода" как откидывать заведомо тупиковые варианты взвешиваний, так и "подгонять" сценарии взвешиваний под нужный нам результат.

Первое взвешивание

Пожалуй, первая мысль, которая приходит в голову среднестатистического человека, решающего нашу задачу, такая: нужно разделить монеты поровну и положить на каждую часу весов по 6 монет. А что дальше? А дальше — посмотрим.

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

Это значит, что при трёх взвешиваниях в рассматриваемом варианте может быть не более 2 · 32 = 18 элементарных исходов. А требуется, чтобы их было, напомню, не меньше 24-х. Нам просто не хватит информации для получения ответа! Так что вариант "6 + 6" отметаем сразу.

А теперь давайте с помощью "информационного подхода" получим точный ответ на вопрос о том, каким должно быть первое взвешивание.

Ясно, что при каждом взвешивании необходимо класть на каждую из чаш одно и то же количество монет. Пусть при первом взвешивании это количество монет равно k. Тогда вне чаши остаются 12 − 2k монет.

Предположим, что одна из чаш при первом взвешивании перетянула другую. Какие в этом случае варианты правильных окончательных ответов возможны? Либо фальшивая монета находится на более лёгкой чаше и имеет тип "недовес" (k вариантов), либо она находится на более тяжёлой и имеет тип "перевес" (ещё k вариантов). В итоге получаем 2k возможных вариантов правильных ответов.

А теперь допустим, что чаши оказались в равновесии. Тогда фальшивой может быть любая монета из оставшихся 12 − 2k монет, причём её тип может быть любым. Таким образом имеем 24 − 4k вариантов.

Но теперь у нас остаётся всего два взвешивания, количество элементарных исходов которых равно 32, т. е. 9. Так что в обоих случаях мы должны "уложить" количество вариантов ответов в 9 элементарных исходов. Это означает, что должна быть выполнена система неравенств

2k924-4k9 ,

которую можно переписать в виде

15 ≤ 4k  ≤ 18,

откуда

3,75 ≤ k ≤ 4,5.

Очевидно, что данная система неравенств имеет единственное целое решение k = 4.

Таким образом, на первом шаге решения задачи мы должны положить на каждую чашу весов по 4 монеты. В результате взвешивания мы получим в случае неравенства весов подозрительный набор из 8-ми монет, о котором известно, что если фальшивая монета находится в одной (известной) половине набора, то она имеет тип "перевес", а если в другой, то "недовес". А равенство весов даст нам подозрительный набор из 4-х монет, дополнительная информация о котором отсутствует.

Третье взвешивание

Нет, я не ошибся, мы от рассмотрения первого взвешивания сразу переходим к рассмотрению третьего. Это нужно для того, чтобы выяснить, какие результаты второго взвешивания позволят нам в третьем взвешивании установить фальшивую монету и выяснить её тип. Такая информация сильно поможет нам в разработке сценария второго взвешивания.

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

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

Вариант 1. Подозрительный набор состоит из трёх монет; тип фальшивой монеты известен.

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

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

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

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

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

Вариант 3. Фальшивая монета установлена, но её тип неизвестен.

Сравниваем вес фальшивой монеты с весом эталонной. Если фальшивая тяжелее, то её тип — "перевес", а если легче, то "недовес". Равенства весов быть не может, т.е., как и в предыдущем случае, возможны только два результата взвешивания.

Второе взвешивание

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

Напомню, что после первого взвешивания мы имеем либо подозрительный набор из 8-ми монет, причём известно, какая его половина тяжелее другой, либо подозрительный набор из 4-х монет, дополнительная информация о котором отсутствует. Рассмотрим каждый из двух вариантов.

Вариант 1. Подозрительный набор состоит из 8-ми монет, причём известно, какие именно 4 монеты превосходят по суммарной массе оставшиеся 4 монеты.

Нам нужно каким-то образом разбить набор на 3 группы, не более трёх монет в каждой, таким образом, чтобы результат второго взвешивания указал на одну из групп как на подозрительную. Ясно, что разбиение на группы должно иметь вид "3 + 3 + 2" (других вариантов нет).

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

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

Осталось разобраться с двумя оставшимися монетами, образующими последнюю группу. Они не должны смешиваться с монетами из других групп, поэтому их нельзя удалить с весов, но и нельзя оставить на прежних местах. Единственный вариант — поменять их местами, что мы и сделаем.

Итак, что мы имеем? Сразу после первого взвешивания две монеты, лежащие на разных чашах, поменялись местами, а из оставшихся монет три остались лежать на левой чаше, а три, лежавшие на правой, заменены эталонными.

Взвешиваем.

Если левая чаша по-прежнему "перетягивает", то фальшивая находится среди тех трёх монет, которые остались лежать на левой чаше, причём тип фальшивой монеты — "перевес". В дальнейшем используем 1-й вариант третьего взвешивания.

Если теперь "перетягивает" правая, то фальшивая находится среди тех двух монет, которые поменялись местами, причём лежащая на правой чаше тяжелее лежащей на левой. В дальнейшем используем 2-й вариант третьего взвешивания.

Наконец, если устанавливается равновесие, то фальшивая находится среди трёх монет, удалённых с правой чаши, причём тип фальшивой монеты — "недовес". В дальнейшем используем 1-й вариант третьего взвешивания.

Вариант 2. Подозрительный набор состоит из 4-х монет; дополнительная информация отсутствует.

Снова думаем, каким образом разбить набор на группы. Вариант 2 + 2 сразу отметаем по той же причине, по которой вариант 6 + 6 не годится для первого взвешивания. Вариант 1 + 1 + 2 также не годится, поскольку при любых сценариях взвешивания в результате всегда можем получить подозрительный набор, состоящий из двух монет, дополнительная информация о котором отсутствует.

Единственное, что нам остаётся — использовать разбиение 1 + 3. Ясно, что из двух групп нужно поместить на весы, например, на правую чашу, группу из трёх монет, а не одну монету. Тогда на другую (правую) чашу кладём три эталонные монеты.

Взвешиваем.

Если левая чаша "перетягивает", то фальшивая находится среди трёх монет, лежащих на левой чаше, причём тип фальшивой монеты — "перевес". Далее используем 1-й вариант третьего взвешивания.

Если "перетягивает" правая, то фальшивая находится среди трёх монет, лежащих на левой чаше, причём тип фальшивой монеты — "недовес". Далее используем 1-й вариант третьего взвешивания.

Ну а если массы грузов оказываются равными, то делаем следующий вывод: 4-я монета, не участвовавшая в третьем взвешивании — фальшивая. Для определения её типа переходим к 3-му варианту первого взвешивания.

Запись алгоритма решения задачи

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

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

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

Каждое взвешивание будем обозначать двумя парами парных круглых скобок, разделённых вопросительным знаком, т. е. символом "?". Внутри первой пары будут через запятую перечисляться номера монет, помещаемых на левую чашу, а внутри второй — помещаемые на правую. Например, если на левую чашу кладутся монеты с номерами 1, 2, 3, 4, а на правую — с номерами 5, 6, 7, 8, то данное взвешивание будет обозначаться так: "(1,2,3,4)?(5,6,7,8)".

Если на какую-то чашу весов кладутся эталоны, то им будут соответствовать не номера монет, а символы "Э". Разумеется, можно было бы сразу подставлять номера тех монет, которые можно использовать в качестве эталонных, но мы не будем этого делать, чтобы не усложнять восприятие алгоритма "лишними" номерами монет. А при написании программы для компьютера уже будут, разумеется, задействованы конкретные номера.

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

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

Результат каждого взвешивания будем обозначать символами сравнений. Символ ">" будет означать, что груз, лежащий на левой чаше, перевесил груз, лежащий на правой, символ "<" — что груз, лежащий на правой, перевесил груз, лежащий на левой, а символ "=" будет использоваться для обозначения равновесия чаш.

После символа, обозначающего результат взвешивания, будет идти один из символов "→" (стрелка вправо) или "⇒" (значок следствия).

Первый из них будет использоваться для указания перехода к очередному шагу алгоритма в соответствии с результатом взвешивания. Например, запись "> → шаг 1" означает, что если груз на левой чаше оказался тяжелее груза на правой, то следует перейти к шагу 1 алгоритма.

Второй символ будет использоваться в случае, когда результат взвешивания приводит к искомому ответу. Сам ответ будет записываться в виде номера фальшивой монеты и её типа. Тип зададим символами "П" и "Н", означающими "перевес" и "недовес" соответственно. Символ, "отвечающий" за тип, будет следовать непосредственно за номером фальшивой монеты. Так, например, запись "= ⇒ 8Н" означает, что из равновесия чаш следует, что фальшивой является монета номер 8, причём весит она меньше настоящей.

Если же результат взвешивания недопустим, то вместо ответа будем записывать символ пустого множества ("∅"). Например, запись "> ⇒ ∅" означает, что левая чаша не может перевесить правую.

Ну что ж, переходим к записи алгоритма!

Алгоритм решения задачи

  • Шаг 0. (1,2,3,4)?(5,6,7,8): > → шаг 1, = → шаг 2, < → шаг 3.
  • Шаг 1. (1,2,3,5)?(Э,Э,Э,4): > → шаг 1.a, = → шаг 1.b, < → шаг 1.c.
    • Шаг 1.a. (1)?(2): > ⇒ 1П, = ⇒ 3П, < ⇒ 2П.
    • Шаг 1.b. (6)?(7): > ⇒ 7Н, = ⇒ 8Н, < ⇒ 6Н.
    • Шаг 1.с. (5)?(Э): > ⇒ ∅, = ⇒ 4П, < ⇒ 5Н.
  • Шаг 2. (9,10,11)?(Э,Э,Э): > → шаг 2.a, = → шаг 2.b, < → шаг 2.c.
    • Шаг 2.a. (9)?(10): > ⇒ 9П, = ⇒ 11П, < ⇒ 10П.
    • Шаг 2.b. (12)?(Э): > ⇒ 12П, = ⇒ ∅, < ⇒ 12Н.
    • Шаг 2.с. (9)?(10): > ⇒ 10Н, = ⇒ 11Н, < ⇒ 9Н.
  • Шаг 3. (5,6,7,1)?(Э,Э,Э,8): > → шаг 3.a, = → шаг 3.b, < → шаг 3.c.
    • Шаг 3.a. (5)?(6): > ⇒ 5П, = ⇒ 7П, < ⇒ 6П.
    • Шаг 3.b. (2)?(3): > ⇒ 3Н, = ⇒ 4Н, < ⇒ 2Н.
    • Шаг 3.с. (1)?(Э): > ⇒ ∅, = ⇒ 8П, < ⇒ 1Н.

Как можно заметить, алгоритм имеет иерархическую структуру. По этой причине кому-нибудь, возможно, будет удобнее воспринимать его, если он будет представлен в виде дерева, "упакованного", например, в следующую таблицу (щёлкните для увеличения):

Табличное представление алгоритма решения задачи

Табличное представление алгоритма решения задачи

А теперь можно переходить к составлению программы!

Структура программы

Программа будет трижды предоставлять пользователю варианты взвешиваний и запрашивать их результаты. После третьего взвешивания программа выведет ответ в виде номера и типа фальшивой монеты.

Диалог между программой и пользователем будет вестись на языке условных обозначений, использованных нами при описании алгоритма. Программа каждый раз будет выводить две пары парных скобок, разделённых знаком вопроса, внутри каждой из которых перечислены номера монет, а пользователь будет "реагировать" вводом одного из символов ">", "<" или "=". Окончательный ответ будет представлен в виде номера фальшивой монеты, за которым следует один из символов "П" или "Н".

Весь код нашей программы мы поместим в один файл.

Функцию, считывающую и обрабатывающую символ, введённый пользователем с клавиатуры, назовём get_result(). Символ будет обрабатываться сразу же после того, как он введён, с помощью функции getche(), возвращающей введённый символ. Данная функция описана в заголовочном файле conio.h. Нужно иметь в виду, что ни этот файл, ни функция getche() не определены в стандарте языка C99, поэтому компилятор, поддерживающий данный стандарт, функции, описанные в conio.h, поддерживать не обязан.

Но компилятор MinGW64, используемый мною, включает в себя библиотеку conio.h, так что функцией getche() я не премину воспользоваться в силу её удобства.

Функции, обрабатывающие результаты взвешивания, будут иметь названия вида procn(), где proc — сокращение от processing (англ. обработка), а n — количество монет, входящих в подозрительный набор перед данным взвешиванием. Таким образом, n принимает значения 1, 2, 3, 4, 8, 12, причём за третье взвешивание отвечают функции с номерами 1, 2, 3, за второе — с номерами 4 и 8, а за третье — с номером 12.

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

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

Функция main() будет вызывать не менее одного раза функцию proc12(). Остальные вызовы будут выполняться уже по желанию пользователя в случае, если он захочет неоднократно воспроизвести процесс решения задачи.

Начинается наш файл с исходным кодом со следующих директив #include:

#include <stdio.h>
#include <conio.h>

Перейдём к рассмотрению функций. Их определения будем располагать в файле таким образом, который позволит нам обойтись без прототипов.

Получение результата взвешивания: функция get_result()

Вот код функции get_result():

//Получение результата взвешивания
char get_result()
{
    char c;
    while(1)
        switch(c = getche())
        {
            case '>':
            case '<':
            case '=':
                return c;
            default:
                printf("\nНедопустимый символ. Попробуйте ещё раз\n");
        }
}

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

Обработка результатов третьего взвешивания: функции proc1(), proc2(), proc3()

Вот функции, обрабатывающие результат третьего взвешивания:

//монета №12 - фальшивая
void proc1()
{
    printf("\n(12)?(11)\n");
    char c;
    while ((c = get_result()) == '=')
        printf("\nНедопустимый результат взвешивания. Попробуйте ещё раз\n");
    printf("\n12%c", c == '>' ? 'П' : 'Н');
}

//первая монета легче второй
void proc2(int n1, int n2)
{
    printf("\n(%d)?(2)\n", n1);
    char c;
    while ((c = get_result()) == '>')
        printf("\nНедопустимый результат взвешивания. Попробуйте ещё раз\n");
    if (c == '=')
        printf("\n%dП", n2);
    else
        printf("\n%dН", n1);
}

//среди трёх одна фальшивая; перевес (если t == 'П') или недовес (t == 'Н')
void proc3(int n1, int n2, int n3, char t)
{
    printf("\n(%d)?(%d)\n", n1, n2);
    char c = get_result();
    switch(c)
    {
        case '>':
            printf("\n%d", t == 'П' ? n1 : n2);
            break;
        case '<':
            printf("\n%d", t == 'П' ? n2 : n1);
            break;
        default:
            printf("\n%d", n3);
    }
    putchar(t);
}

Функция proc1() не принимает никаких аргументов, поскольку она вызывается лишь в случае, когда фальшивой монетой является монета номер 12 и нужно лишь определить её тип. Функции proc2() в качестве аргументов передаются номера двух монет, входящих в подозрительный набор, причём предполагается, что первая из них легче второй. Наконец, функции proc3() передаются не только номера трёх монет, входящих в подозрительный набор, но и символ "П", если фальшивая монета тяжелее настоящей, или символ "Н", если легче.

Обратите внимание на то, как функции proc1() и proc2() "реагируют" на ввод пользователем недопустимого результата взвешивания: выводится сообщение с предложением исправить ошибку, и этот процесс повторяется до тех пор, пока пользователь не введёт корректный символ.

Обработка результатов второго взвешивания: функции proc8(), proc4()

Ниже приведены функции, обрабатывающие результат второго взвешивания:

//сумма масс первых четырёх превышает сумму масс остальных четырёх
void proc8(int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8)
{
    printf("\n(%d,%d,%d,%d)?(9,10,11,%d)\n", n1, n2, n3, n5, n4);
    char c = get_result();
    switch(c)
    {
        case '>':
            proc3(n1, n2, n3, 'П');
            break;
        case '=':
            proc3(n6, n7, n8, 'Н');
            break;
        default:
            proc2(n5, n4);
    }
}

//фальшивая монета находится среди монет с номерами 9, 10, 11, 12
void proc4()
{
    printf("\n(9,10,11)?(1,2,3)\n");
    char c = get_result();
    switch(c)
    {
        case '>':
            proc3(9, 10, 11, 'П');
            break;
        case '<':
            proc3(9, 10, 11, 'Н');
            break;
        default:
            proc1();
    }
}

Функция proc8() принимает в качестве аргументов номера 8-ми монет, входящих в подозрительный набор, причём предполагается, что сумма масс первых четырёх из них превышает сумму масс остальных. Функция proc4() не принимает никаких аргументов, поскольку известно, что к моменту её вызова в подозрительный набор входят монеты с номерами 9, 10, 11, 12.

Обработка результатов первого взвешивания: функция proc12()

Код функции proc12(), обрабатывающей результаты первого взвешивания, приведён ниже:

//о фальшивой монете ничего не известно
void proc12()
{
    printf("(1,2,3,4)?(5,6,7,8)\n");
    char c = get_result();
    switch(c)
    {
        case '>':
            proc8(1, 2, 3, 4, 5, 6, 7, 8);
            break;
        case '<':
            proc8(5, 6, 7, 8, 1, 2, 3, 4);
            break;
        default:
            proc4();
    }
}

По очевидной причине функция proc12() не принимает аргументов.

Запуск процесса решения задачи: функция main()

А вот и код функции main():

int main()
{
    do
    {
        proc12();
        printf("\nПовторить? y - да, любая другая клавиша - нет\n");
    }
    while(getche() == 'y' && putchar('\n'));
    return 0;
}

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

Обратите внимание на вызов функции putchar() внутри условия продолжения цикла. Функция никогда не вернёт 0, поэтому её вызов никак не влияет на выполнение условия. Но зато она будет вызвана, если пользователь введёт символ "y", и её выполнение приведёт к переводу строки, благодаря чему этот символ "не слипнется" с текстом, который затем будет выведен на печать уже самой программой.

Пример выполнения программы

Откомпилируем программу и запустим её. Трижды загадаем номер и тип фальшивой монеты; пусть, например пары "номер-тип" будут такими: 1П, 6Н, 12П. Посмотрим, как программа будет справляться с нахождением верных ответов:

(1,2,3,4)?(5,6,7,8)
>
(1,2,3,5)?(9,10,11,4)
>
(1)?(2)
>
1П
Повторить? y - да, любая другая клавиша - нет
y
(1,2,3,4)?(5,6,7,8)
>
(1,2,3,5)?(9,10,11,4)
=
(6)?(7)
<
6Н
Повторить? y - да, любая другая клавиша - нет
y
(1,2,3,4)?(5,6,7,8)
=
(9,10,11)?(1,2,3)
=
(12)?(11)
>
12П
Повторить? y - да, любая другая клавиша - нет
n

Как мы видим, программа все 3 раза успешно справилась с задачей.

Заключение

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

Но даже сейчас, "загадывая" номер и тип фальшивой монеты и наблюдая, как программа, написанная мною же, отгадывает и то, и другое всего лишь за три шага, я испытываю на полубессознательном уровне что-то, похожее на удивление. Примерно то же чувство, но несколько более сильное, я испытывал несколько лет назад, когда увлекался широко известным "Акинатором", который с лёгкостью угадывал задуманных мною персонажей.

Скачать исходный код