Osiem osiem

Zagadka

Używając tylko dodawania jak otrzymać 1000 mając do dypozycji tylko osiem cyfr 8? Nie wolno używać żadnego innego operatora matematycznego (takiego jak mnożenie czy nawiasy).

Rozwiązanie

Implementacja

Zadanie

Napisz program, który dla podanej cyfry oraz ile cyfr jest do dyspozycji wypisze wszystkie możliwe sumy do uzyskania. Wśród sum nie powinno być zduplikowanych wartości. Przetestuj działanie programu.

Strategia

Napisana funkcja poszukująca wszystkich sum będzie rekurencyjna. W każdym wywołaniu funkcja będzie wiedziała ile zostało jeszcze cyfr do przydziału oraz jaka jest dotychczasowa suma. Wewnatrz funkcji jeśli jest chociaż jedna cyfra do przydziału to program sprawdzi co się stanie jeśli przydzieli dowolną ilość. Przykładowo jeśli zostało n cyfr to program wywoła się rekurencyjnie uprzednio zabierając n, n-1, ..., 2, 1 cyfrę. Jednak znajdowane wartości mogą być takie same. Z tego powodu dane zapisywane na listę znalezionych wartości będą odrzucane jeśli już w niej występują.

Rozwiązanie

Poniższa funkcja szukaj() przyjmuje cztery argumenty: lista - zmienna do której zostaną zapisane znalezione wyniki, c - grupowane cyfry, zostalo - ile zostało cyfr do przydziału oraz suma - suma liczb z poprzednich wywołań (dla danej gałęzi wywołań).

1. void szukaj(vector<int> &lista, int c, int zostalo, int suma = 0) {
2.   if (zostalo > 0) {
3.     for (int i = zostalo; i > 0; i--)
4.       szukaj(lista, c, zostalo - i, suma + generuj(c, i));
5.   } else {
6.     int pos = 0;
7.     while (pos < lista.size() && lista[pos] < suma)
8.       pos++;
9.     if (pos == lista.size())
10.       lista.push_back(suma);
11.     if (suma != lista[pos])
12.       lista.insert(lista.begin() + pos, suma);
13.   }
14. }

(2.) Jeśli wciąż są wartości do rodzielenia to (3. - 4.) sprawdź każdy przydział. Jednak (5.) gdy już nie możliwości przydziału to (6. - 8.) wyszukaj gdzie wstawić na listę i (9. - 12.) wstaw jeśli zostaną spełnione odpowiednie warunki.

Funkcja korzysta z pomocniczej funkcji generuj(), która generuje liczbę złożoną z ile cyfr c.

1. int generuj(int c, int ile) {
2.   int a = 0;
3.   for (int i = 0; i < ile; i++)
4.     a = a * 10 + c;
5.   return a;
6. }

Testowanie funkcji

Działanie napisanej funkcji można przetestować przy pomocy poniższego fragmentu kodu

1. int main () {
2.   int c, q;
3.   cout << "Podaj cyfre:\n c = ";
4.   cin >> c;
5.   cout << "Podaj ile jest cyfr:\n q = ";
6.   cin >> q;
7.   vector<int> wyniki;
8.   szukaj(wyniki, c, q);
9.   for (int i = 0; i < wyniki.size(); i++)
10.     cout << wyniki[i] << " ";
11.   system("pause");
12.   return 0;
13. }

Przykładowo podając, że w zadaniu jest osiem cyfr osiem okazuje się, że do uzyskania są, aż 22 różne sumy! Zostały one przedstawione poniżej:

1. 64 136 208 280 352 928 1000 1072 1792 1864 8920 8992 9064 9784 17776 88912 88984 89776 888904 888976 8888896 88888888

• Kod źródłowy Implementacja