Ja bym zrobił to tak.
Ponieważ grzybów jest dwa, a każdego z nich można zjeść po 8 kawałków, to znaczy, że razem jest 16 kawałków.
Ponieważ są dwa grzyby, to oznaczmy pierwszy grzyb przez 0, drugi przez 1.
Potrzebujemy więc maksymalnie 16-elementowy ciąg zer i jedynek.
Ponieważ komputery już zapisują dane w postaci ciągu zer i jedynek, możemy to wykorzystać i pobawić się operacjami bitowymi.
- iterujemy przez wszystkie liczby od 0 do 2^16 - 1 (65536 możliwości). Każda liczba
i reprezentuje ciąg bitów potencjalnego rozwiązania
- każdą liczbę
i potraktujemy jako ciąg bitów, iterując przez bity, nakładamy pierwszą albo drugą operację(grzyb)
- jak znajdziemy pożądany wzrost, to przerywamy pętlę i zapisujemy jeżeli liczba kroków jest mniejsza niż wcześniej
Coś takiego wymyśliłem w JS, ale można by przepisać na C++.
const ops = [
x => x * 2,
x => x - 100,
];
const pieces = 16;
function find(currentHeight, desiredHeight) {
const min = {
count: Infinity,
text: '',
};
for (let i = 0; i < 2**pieces; i++) {
let height = currentHeight;
let s = '';
for (let bit = 0; bit < pieces; bit++) {
const op = (i & (1 << bit)) >> bit;
height = ops[op](height);
if (op == 0) s += 'first\n';
if (op == 1) s += 'second\n';
if (height == desiredHeight && bit < min.count) {
min.text = s;
min.count = bit;
break;
}
}
}
return min;
}
const min = find(115, 120);
console.log(`== Count: ${min.count}\n== Steps: \n${min.text}`);
No i odnośnie może mglistego fragmentu:
const op = (i & (1 << bit)) >> bit;
1 << bit - bo iterujemy przez kolejny bit, więc przesuwamy jedynkę w lewo np. 1 << 3 da nam binarnie 1000
(i & (1 << bit)) robimy operację AND porównując z maską bitową liczby i, która reprezentuje całe rozwiązanie
i całość robimy >> bit żeby z powrotem zawrócić ten bit (zgaszony bądź zapalony) i żeby wyszło zero albo jeden
mamy więc nasz numer grzyba op, którego możemy użyć jako indeks dwuelementowej tablicy ops.