Вчера я написал вопрос об этой же задаче, слегка улучшил свой алгоритм, но всё таки хотел бы узнать как можно решить её алгоритмом перебора.
Юного программиста Васю заинтересовал следующий вопрос: предположим, что мы взвешиваем боксёров на чашечных весах и пользуемся двумя двоичными наборами гирь: граммовым и килограммовым. Понятно, что граммовый набор является стандартным и состоит из гирек весом в 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 и 1024 грамм. Аналогично обстоит дело и с килограммовым набором – просто гири потяжелее, но при этом их немного меньше… Для простоты далее в этой задаче будем считать, что волшебным образом на прошедшей олимпиаде оказалось, что вес каждого спортсмена в точности мог быть измерен только килограммовым набором. Найти количество гирь.
40 <= вес спортсмена <= 130.
Суть в том, что я даже не понимаю что да как с этим алгоритмом. Что он должен перебирать? Рассмотрим пример моего решения.
У меня есть число n = 97
(для примера).
Его соседи из массива w[]
есть 128 < 97 < 64
.
Сперва проверим разницу между первым: 128 - 97 = 31
, а потом и вторым: 97 - 64 = 33
.
Видем, что 31 < 33
, по-этому n = w[i] (тоесть 128) - n
. А в другом случаи n -= w[i + 1] (тоесть 64, а не 128)
.
Делаем так до тех пор, пока n > 0
.
Но, могу ли я считать это алгоритмом перебора? Я же здесь толком то и ничего не перебираю. Возможно Вы знаете какой-то другой вариант решения нужным мне способом!?
#include <iostream>
using namespace std;
int w[] = { 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1 };
int neighbor(int n) {
int i = 0;
while (n > 0) {
if (n - w[i] < 0) {
i++;
}
if (n - w[i] >= 0) {
return i;
break;
}
}
}
int main() {
int n;
cin >> n;
int i, count = 0;
while (n > 0) {
i = neighbor(n) - 1;
if (w[i] - n < n - w[i + 1]) {
count++;
n = w[i] - n;
} else if (w[i] - n >= n - w[i + 1]) {
n -= w[i + 1];
count++;
}
}
cout << count << endl;
return 0;
}