Код, который вы предоставляете, решает другую проблему , чем вы описали. Так что либо вы допустили ошибку в своем описании, либо решение неверное.
Проблема, которую решает ваш код, имеет центральное условие, подобное этому:
У вас есть набор весов, взвешивающий 1, 2, 4, ..., 2 N-1 единиц массы соответственно, с произвольным числом каждого веса
и дополнительно вы можете поместить эти веса на одну сторону только весов (ту, которая противоположна камню).
Это позволяет, например, сбалансировать весы с 2- единица измерения камня в двух направлениях, как показывает ответ от grek40: одно решение - одно взвешивание 2, другое - два взвешивания по 1 единице каждый.
Вот как ваш код достигает it.
Параметр W для функции no_ways представляет несбалансированный (часть) вес вашего камня, а параметр index обозначает наименьший вес, который вы можете использовать. Таким образом, чтобы найти все возможные решения, мы называем no_ways(W,0), что соответствует балансу общего веса W со всеми доступными весами.
Два базовых случая: «не осталось несбалансированного веса», что означает, что мы нашли решение, поэтому мы возвращаем 1; и «мы исчерпали допустимый диапазон весов», что означает, что мы не можем найти решение, поэтому мы возвращаем 0.
Затем мы пытаемся расширить частичное решение, пытаясь добавить самые легкие доступные весы к весам. Самый легкий вес - (1 << index), то есть 2 index , поэтому мы умножаем его, увеличивая значения i и вычитая его из W; это делается с помощью:
for (i = 0; i * (1 << index) <= W; i++)
(W - i * (1 << index), )
, и мы пытаемся сбалансировать оставшиеся W - i * (1 << index) со следующим доступным весом (определяемым следующим значением index), вызывая:
for (i = 0; i * (1 << index) <= W; i++)
no_ways(W - i * (1 << index), index + 1)
Наконец, мы накапливаем количество найденных решений, суммируя результаты:
for (i = 0; i * (1 << index) <= W; i++)
ans += no_ways(W - i * (1 << index), index + 1);
Сумма возвращается по рекурсии, так что на верхнем уровне мы получаем число всех найденных решений.
Я немного изменил ваш код, чтобы построить и распечатать явное представление каждого найденного решения. Он состоит из массива int stack[] и переменной top, которая указывает свободную позицию в стеке. Первоначально top==0, стек пуст.
Всякий раз, когда for() l oop уменьшает значение до W, он помещает значение в стек и перемещает указатель top, так что рекурсивно вызовы создают решение в массиве. По возвращении из рекурсии мы уменьшаем top, чтобы новая итерация for() могла поместить новое значение в то же место.
Когда у нас новое решение, печатается весь стек.
Вот код:
int stack[15];
int top = 0;
void print_stack() {
int k;
for (k = 0; k < top; k ++)
printf(" %d", stack[k]);
printf("\n");
}
int N;
int no_ways(int W, int index) {
if (!W) {
print_stack();
return 1;
}
if (index == N)
return 0;
int ans = 0, i;
for (i = 0; i * (1 << index) <= W; i++) {
stack[top ++] = i * (1 << index);
ans += no_ways(W - i * (1 << index), index + 1);
top --;
}
return ans;
}
Вы можете легко найти все добавленные мной строки - это строки, содержащие 'stack' или 'top'.
Для случая W = 2, N = 2, исследованный grek40, печатает код:
0 2
2
2
В последней строке показано, что найдены два решения: первая - это вес 2, полученный с одним взвешиванием в 2 единицы, и ноль взвешивания в 1 единицу (правильно), а другой - ДВЕ весит одну единицу.
Вот результаты для W = 5 и N = 3:
1 0 4
1 4
3 2
5
4
Это решения: 5 = 1 + 4 (правильно), 5 = 1 + 2 * 2 (при весе 2 единицы, использованном дважды), 5 = 3 * 1 + 2 (при весе 1 единицы, использованном трижды) и 5 = 5 * 1 (с пятью единицами весит единицу).
Всего найдено решений: 4.
Я тестировал код в онлайн-компиляторе / отладчике по адресу https://www.onlinegdb.com/
РЕДАКТИРОВАТЬ
* 10 94 * Для решения поставленной задачи, то есть:
, имеющий ровно один вес, равный 1 единице, один вес, равный 2 единицам, и т. Д. Через степени от 2 до одного веса 2 N-1 единиц, которые могут быть размещены на обеих сторонах весов, находят баланс
. Вы можете изменить решение следующим образом.
Каждый груз может быть помещен либо на ту же тарелку, где находится камень, добавляя вес, либо на противоположный, тем самым (частично) уменьшая вес - или его можно оставить в покое вне весов. Цель состоит в том, чтобы получить нулевой несбалансированный вес. Это соответствует удовлетворению уравнению типа
W + s 0 × 1 + s 1 × 2 + s 2 × 4 + .. . + s N-1 × 2 N-1 = 0
, выбрав каждый s n термин равно –1, 0 или 1.
Этого можно добиться простой модификацией кода:
int no_ways(int W, int index) {
if (!W)
return 1;
if (index == N)
return 0;
int ans = 0, i;
for (i = -1; i <= 1; i++) // i equals -1, 0 or 1
ans += no_ways(W + i * (1 << index), index + 1);
return ans;
}