Зона кода

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

Задача о взвешиваниях с помощью четырёх гирь

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

Вот какую задачу я обнаружил недавно в Интернете.

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

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

Данная статья адресована новичкам в программировании.

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

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

Первый вопрос, который я себе задал: а имеет ли вообще эта задача решение? Интуитивно кажется, что четырёх гирь явно недостаточно, чтобы "покрыть" ими диапазон от 1 до 40кг.

Предположим, что мы будем класть взвешиваемые грузы, скажем, на правую чашу весов, а гири — на левую. Сколько всего различных комбинаций гирь можно положить на левую чашу? Ответить на этот вопрос несложно: любая из четырёх гирь может либо находиться на левой чаше, либо не участвовать во взвешивании. Всего 2 варианта, а гирь — 4, поэтому количество всевозможных комбинаций равно 24, т. е. 16.

Одна из этих комбинаций соответствует пустой чаше весов, поэтому её нужно исключить из рассмотрения. Остаётся 15 вариантов размещения гирь на левой чаше. Даже, если массы гирь подобраны таким образом, что каждому такому варианту соответствует "уникальная" (т. е. неповторяющаяся) суммарная масса гирь, находящихся на чаше, то взвесить мы сможем лишь 15 грузов различной массы, удовлетворяющих условию задачи, но никак не 40. Неужели, задача действительно поставлена некорректно?

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

Вычислим количество всевозможных вариантов размещения гирь на двух чашах весов. Теперь каждая гиря может быть размещена на левой чаше, на правой, а может и не участвовать во взвешивании. Всего 3 варианта. Гирь, по-прежнему, 4. В итоге получаем: количество всех вариантов равно 34, т. е. 81.

Один вариант, соответствующий отсутствию гирь на обеих чашах, следует исключить. Остаются 80 вариантов. Исключим также варианты, при которых суммарные массы гирь, расположенных на каждой из чаш, совпадают, поскольку для взвешиваний такие расположения гирь неприменимы. Допустим, таких вариантов k. Остаются 80 − k вариантов.

Наконец, исключим из рассмотрения варианты, при которых суммарная масса гирь, расположенных на правой чаше, превышает суммарную массу гирь, расположенных на левой. Очевидно,что при взвешиваниях данные расположения использоваться не могут. Руководствуясь соображениями симметрии, можно утверждать, что количество таких вариантов составляет ровно половину из оставшихся. После исключения получаем: окончательное количество оставшихся вариантов равно 40 − k / 2. Таким образом, чтобы задача имела решение, необходимо, чтобы k равнялось 0.

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

Задачу можно переформулировать следующим образом. Найти такой набор, состоящий из 4-х натуральных чисел, чтобы каждое натуральное число, не превышающее 40, могло быть представлено в виде арифметического выражения, составленного из чисел, принадлежащих набору, а также из знаков "+" и "−". Числам, входящим в выражение со знакам "+", будут соответствовать гири, находящиеся на левой чаше весов, а со знаком "−" — гири, находящиеся на правой.

Сначала я пытался угадать эти 4 числа. Для выяснения того, удовлетворяет ли тот или иной набор чисел условию задачи, я написал программу, вычисляющую значения всех выражений, составленных из чисел набора, знаков "+" и "−". Программа упорядочивала значения по возрастанию, поэтому легко было проверить, имеются ли среди этих значений все целые числа от -80 до 80 включительно. Наличие всех таких чисел среди набора значений означало бы, что набор, из чисел которого составлялись выражения, удовлетворяет условию задачи. Увы, найти такой набор методом угадывания мне не удалось.

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

Диапазоном [p; q], где p и q — целые, причём, pq, назовём множество всех целых чисел от p до q включительно. Например, диапазон [-1; 2] состоит из чисел -1, 0, 1, 2.

А теперь — сама гипотеза.

Гипотеза 1. Для любого натурального числа n найдутся такие n чисел a1, a2, …, an, что любое натуральное число m, не превышающее (3n − 1) / 2, может быть представлено в виде

m=i=1nriai,

где ri ∈ [-1; 1] для любого i (вообще говоря, ai зависят от n, а ri — как от n, так и от m, но мы опускаем соответствующие индексы, чтобы не усложнять обозначения).

Отметим, что, если гипотеза верна, то сумма всех ai, очевидно, должна быть равна максимальному числу, представимому в приведённой выше форме, т. е. числу (3n − 1) / 2. Другими словами, должно выполняться равенство

i=1nai=3n-1/2.

Проверим нашу гипотезу для n = 1. В этом случае нам нужно представить в приведённой выше форме лишь одно число — (31 − 1) / 2, т. е. 1. Ясно, что в качестве a1 нужно взять также единицу. Получаем следующее разложение: 1 = 1. Итак, при n = 1 гипотеза верна.

Пусть теперь n = 2. Количество чисел, которые необходимо раскладывать, увеличивается до (32 − 1) / 2, т. е. до 4. Должно выполняться: a1 + a2 = 4. Число 1 невозможно представить в виде разности натуральных чисел, сумма которых равна 4, откуда следует, что одно из чисел a1 или a2 должно равняться 1. Пусть, для определённости, a1 = 1, тогда a2 = 3. Числа от 1 до 4 выразить через a1 и a2 нужным нам способом достаточно легко:

1 = 1,
2 = 3 − 1,
3 = 3,
4 = 1 + 3.

Теперь уже появляется подозрение, что при переходе от n к n + 1 уже имеющийся набор чисел a1, a2, …, an, следует оставить без изменения. Если это верно, то в качестве an+1, в силу приведённого выше замечания, необходимо брать разность между числами (3n+1 − 1) / 2 и (3n − 1) / 2. Имеем:

an+1 = (3n+1 − 1) / 2 − (3n − 1) / 2 = (3n+1 − 3n) / 2 =3n (3 − 1) / 2 = 3n.

Получается, что, если наши предположения верны, то в качестве чисел ai, следует брать степени троек.

Значит для случая n = 3 нужно брать a1 = 1, a2 = 3, a3 = 9, для случая n = 4, соответствующего нашей задаче, — a1 = 1, a2 = 3, a3 = 9, a4 = 27 и т. д.

Теперь нашу гипотезу можно усилить.

Гипотеза 2. Любое натуральное число m, не превышающее (3n − 1) / 2, где n — натуральное, можно представить в виде:

m=i=1nri3i-1,

где ri ∈ [-1; 1] для любого i.

Отметим, что в рамках этой гипотезы ai уже не зависят от n, а ri зависят только от m.

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

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

Для случая n = 1, очевидно, разложение по степеням тройки имеет место: 1 = 30.

Предположим теперь, что доказываемое утверждение выполняется для всех n из диапазона [1; t], и докажем, что оно выполняется, также, и для случая n = t + 1.

Существование разложений по степеням тройки чисел из диапазона [1; (3t − 1) / 2], в силу нашего предположения, уже доказано. Остаётся лишь доказать, что могут быть разложены, также, и числа из диапазона [(3t + 1) / 2; (3t+1 − 1) / 2]. Разобьём этот диапазон на 3 части: [(3t + 1) / 2; 3t − 1], 3t, [3t + 1; (3t+1 − 1) / 2]. Покажем, как раскладываются по степеням тройки числа, входящие в каждую из этих частей. Это и будет доказательством существования данных разложений.

1. Пусть m ∈ [(3t + 1) / 2; 3t − 1]. Тогда натуральное число l = 3tm, очевидно, удовлетворяет неравенству l ≤ (3t − 1) / 2, а значит, в силу нашего предположения, оно разложимо по степеням тройки. Пусть l раскладывается, например, так:

l=i=1tri3i-1.

Тогда соответствующее разложение числа m, будет, очевидно, таким:

m=i=1t-ri3i-1+3t.

2. Пусть m = 3t. Это уже готовое разложение по степеням тройки.

3. Пусть m ∈ [3t + 1; (3t+1 − 1) / 2]. Тогда натуральное число l = m − 3t, очевидно, удовлетворяет неравенству l ≤ (3t − 1) / 2, а значит, в силу нашего предположения, оно разложимо по степеням тройки. Пусть l раскладывается, например, так:

l=i=1tri3i-1.

Тогда соответствующее разложение числа m, будет, очевидно, таким:

m=i=1tri3i-1+3t.

Итак, доказываемое утверждение верно при n = 1, а также при n = t + 1, при условии, что верно при любых nt. В силу индуктивного перехода это означает справедливость утверждения при любых натуральных n. Доказательство завершено.

Таким образом, массы гирь, необходимых для взвешивания грузов от 1 до 40кг. равны 1кг., 3кг., 9кг. и 27кг. Задача решена.

Алгоритм построения разложений

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

Итак, пусть необходимо разложить натуральное число m по степеням троек.

Шаг 1. Находим наименьшее число n, удовлетворяющее неравенству m ≤ (3n+1 − 1) / 2.

Шаг 2. Если m < 3n, то полагаем: l = 3nm. С помощью данного алгоритма находим разложение числа l по степеням тройки: l=i=1nri3i-1. Получаем окончательное разложение: m=i=1n-ri3i-1+3t и завершаем работу.

Шаг 3. Если m = 3n, то считаем это равенство окончательным разложением и завершаем работу.

Шаг 4. Если m > 3n, то полагаем: l = m − 3n. С помощью данного алгоритма находим разложение числа l по степеням тройки: l=i=1nri3i-1. Получаем окончательное разложение: m=i=1nri3i-1+3t и завершаем работу.

Давайте теперь во втором шаге положим: l = m − 3n (вместо l = 3nm) и перепишем его следующим образом:

Шаг 2. Если m < 3n, то полагаем: l = m − 3n. С помощью данного алгоритма находим разложение числа l по степеням тройки: l=i=1nri3i-1. Получаем окончательное разложение: m=i=1nri3i-1+3t и завершаем работу.

На первый взгляд, теперь шаги 2 и 4 можно объединить в один-единственный шаг, соответствующий случаю m ≠ 3n, т. к. действия во втором ("новом") и в четвёртом ("старом") шагах теперь совпадают. Однако это не так, поскольку на втором шаге предлагается с использованием данного алгоритма разложить по степеням тройки отрицательное число l. Но ведь наш алгоритм не предназначен для разложений отрицательных чисел!

Так что, если мы хотим объединить 2 шага в один, то мы должны расширить наш алгоритм таким образом, что бы он мог "обрабатывать", также, и отрицательные числа. Сделать это несложно, поскольку разложения противоположных чисел различаются только тем, что коэффициенты данных разложений противоположны. Так что, зная разложение натурального m можно легко получить разложение -m.

Действовать будем следующим образом. Предполагая, что m может теперь быть отрицательным, перепишем наш алгоритм, заменяя везде число m его модулем. А окончательные разложения числа m будем получать из разложений его модуля, домножая коэффициенты разложения на знак m. Поясним, на всякий случай, что знак числа m, обозначаемый как sign(m), — это 1, если m > 0, -1, если m < 0 и 0, если m = 0.

Теперь уже можно записать новую, "расширенную" версию алгоритма, не забыв объединить два шага в один.

Итак, пусть необходимо разложить целое ненулевое число m по степеням троек. Обозначим для краткости: s = sign(m). Теперь наш алгоритм будет иметь вид следующий вид.

Шаг 1. Находим наименьшее число n, удовлетворяющее неравенству |m| ≤ (3n+1 − 1) / 2.

Шаг 2. Если |m| = 3n, то получаем окончательное разложение m = s3n и завершаем работу.

Шаг 3. Полагаем: l = |m| − 3n. С помощью данного алгоритма находим разложение числа l по степеням тройки: l=i=1nri3i-1. Получаем окончательное разложение: m=si=1nri3i-1+s3t и завершаем работу.

Рассмотрим способ реализации 1-го шага. Заметим, что (3n+1 − 1) / 2 можно представить как сумму степеней тройки от 0 до n:

3n+1-12=i=0n3i.

Таким образом, мы можем суммировать степени тройки, начиная с нулевой, до тех пор, пока сумма степеней не превысит |m|. Тогда последнее добавленное слагаемое и будет равняться 3n. Отметим, что число n само по себе нас не интересует; нам нужна именно степень 3n. Поэтому n мы находить не будем.

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

Теперь можно переходить к его реализации.

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

Наша программа будет целиком содержаться в одном файле.

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

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

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

 1.#include <stdio.h>
 2.#include <stdlib.h>
 3.
 4.struct node
 5.{
 6.    int element;
 7.    struct node *next;
 8.};
 9.
10.typedef struct node node;
11.
12.//добавление элемента в стек
13.node *push(node *stack, int element)
14.{
15.    node *new_node = malloc(sizeof(node));
16.    new_node->element = element;
17.    new_node->next = stack;
18.    return new_node;
19.}
20.
21.//выталкивание элемента из стека
22.int pop(node **pstack)
23.{
24.    node *first_node = *pstack;
25.    *pstack = first_node->next;
26.    int element = first_node->element;
27.    free(first_node);
28.    return element;
29.}

Такого рода стеки мы уже рассматривали ранее, поэтому прокомментирую реализацию стека, приведённую выше, достаточно кратко.

Наш стек предназначен для хранения значений типа int и построен на основе односвязного списка, в узлах которого будут храниться элементы стека. Узлы представлены в программе объектами типа node (см. стр. 4-10). Для доступа к стеку будет использоваться переменная, содержащая адрес первого узла списка; именно в этом узле будет находиться верхний элемент стека. Данную переменную будем называть стековой. Стековая переменная, соответствующая пустому стеку, будет содержать 0.

Добавление элемента в стек осуществляется с помощью функции push() (стр. 13-19). Она принимает в качестве аргументов значение стековой переменной и число, которое нужно поместить в стек. Для этого она создаёт новый узел, помещает в него число и присоединяет узел к списку. В результате новый узел становится первым узлом списка. Функция возвращает его адрес, т. е. новое значение стековой переменной.

Выталкиванием элемента из стека занимается функция pop() (стр. 22-29). Она принимает в качестве аргумента адрес стековой переменной. Функция "отстёгивает" от списка первый узел и извлекает из него хранящееся в нём число. Адрес узла, ставшего первым (или 0, если до выталкивания список состоял из единственного узла) записывается в стековую переменную. Далее функция pop() удаляет "отстёгнутый" узел и возвращает содержавшееся в нём число.

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

node *stack = 0;

Функция decompose()

Переходим к созданию ключевой функции нашей программы — decompose(). Ниже приведён её код.

 1.void decompose(int m)
 2.{
 3.    int s = m > 0 ? 1 : -1;
 4.    m = abs(m);
 5.    int sum = 1, p = 1;
 6.    while (sum < m)
 7.        sum += (p *= 3);
 8.    stack = push(stack, s * p);
 9.    if (m != p)
10.        decompose(s * (m - p));
11.}

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

Раскладываемое число изначально содержится в формальной переменной m. Помещаем в переменную s знак m (стр. 3), а значение самой переменной m заменяем его модулем (стр. 4). В строках 5-7 реализован 1-й шаг алгоритма. В результате их выполнения в переменной p оказывается число 3n (здесь и далее используются те же обозначения, что и в алгоритме). Помещаем это число с соответствующим знаком в стек (стр. 8), т. е. выполняем общую часть шагов 2 и 3.

В случае, если значения m и p совпадают, завершаем работу. Шаг 2 реализован. В противном случае "доделываем" 3-й шаг: вызываем функцию decompose() рекурсивно, передавая ей разность значений переменных m и p с соответствующим знаком, т. е. число l.

Отметим, что в ходе рекурсивных вызовов значения значения переменных p и sum постоянно постоянно будут повторяться. Это означает, что код, размещённый в строках 6-7, можно оптимизировать. Например, можно прибегнуть к кэшированию результатов. Но мы делать этого не будем, поскольку оптимизация приведёт к усложнению кода, а производительность нашей программы для нас не важна. Она и так будет выполняться мгновенно.

Функция main()

Функция main() будет взаимодействовать с пользователем посредством консоли и вызывать функцию decompose(). Вот её код:

 1.int main()
 2.{
 3.    int m;
 4.    printf("Введите ненулевое число или 0 для выхода\n");
 5.    scanf("%d", &m);
 6.    while (m)
 7.    {
 8.        decompose(m);
 9.        printf("%d=%d", m, pop(&stack));
10.        while (stack)
11.        {
12.            if ((m = (pop(&stack))) > 0)
13.                printf("+");
14.            printf("%d", m);
15.        }
16.        printf("\n");
17.        printf("Введите ненулевое число или 0 для выхода\n");
18.        scanf("%d", &m);
19.    }
20.    return 0;
21.}

Код функции main(), полагаю, достаточных понятен и подробных комментариев не требует. Функция предлагает пользователю ввести ненулевое число или 0 для выхода (стр. 4-5). При получении ненулевого числа оно передаётся функции decompose() (стр. 8). По окончанию её работы на консоль выводится результат решения задачи: разложение числа по степеням тройки; при этом члены разложения берутся из стека (см. стр. 9-16). После этого весь процесс повторяется заново (стр. 17-18).

Пользователь волен завершить процесс выполнения программы, введя 0 в ответ на её очередной запрос.

Отметим, что мы не стали "защищаться" от некорректных действий пользователя, чтобы не усложнять код. Предполагается, что пользователь всегда вводит число, попадающее в диапазон допустимых значений типа int. В нашем случае речь идёт о диапазоне [-2147483648, 2147483647].

Выполнение программы.

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

Введите ненулевое число или 0 для выхода
1
1=1
Введите ненулевое число или 0 для выхода
123
123=-3-9-27-81+243
Введите ненулевое число или 0 для выхода
12345
12345=-3+9+27-81-729-6561+19683
Введите ненулевое число или 0 для выхода
-12345
-12345=3-9-27+81+729+6561-19683
Введите ненулевое число или 0 для выхода
0

Как мы видим, программа работает корректно.

Нерекурсивная версия функции decompose()

Новички в программировании могут поставить перед собой задачу: в качестве тренировки привести функцию decompose() к нерекурсивной форме. Впрочем, задача решается достаточно легко. Вот как будет выглядеть нерекурсивная версия этой функции:

void decompose(int m)
{
    do
    {
        int s = m > 0 ? 1 : -1;
        m = abs(m);
        int sum = 1, p = 1;
        while (sum < m)
            sum += (p *= 3);
        stack = push(stack, s * p);
        m = s * (m - p);
    }
    while (m);
}

Заключение.

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

Можно заметить, что задача разложения натурального числа по степеням тройки родственна задаче представления натурального числа в троичной форме. Действительно, представление натурального число в троичной форме тоже сводится к разложению его по степеням тройки, но с коэффициентами 0, 1, 2 (напомню, что в этой статье мы рассматривали разложения с коэффициентами -1, 0, 1). От одного типа разложения можно всегда перейти к другому и наоборот. Читатель, при желании, сможет с лёгкостью построить соответствующие алгоритмы.

Отметим, что при использовании коэффициентов -1, 0, 1 мы можем разложить по степеням тройки любое целое число, тогда как коэффициенты 0, 1, 2 "позволяют" получать разложения лишь неотрицательных целых чисел.

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

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