Równe Sumy Części

Zadanie

Dla pewnej liczby naturalnej sprawdź czy istnieje podział na dowolną ilość części w taki sposób, aby suma cyfr każdej części była identyczna. Znajdź wszystkie możliwe podziały liczby, które spełniają ten warunek. Część liczby to cyfry zapisane w liczbie obok siebie.

Przykładowo liczbę 123 można podzielić na {12, 3}. Innym przykładem jest liczba 42651, którą można podzielić na {42, 6, 51}. W tym przypadku każdy element ma sumę cyfr równą 6.

Analiza zadania

Algorytm

W celu ustalenie czy podział jest możliwy początkowo należy spróbować wybrać 1, 2, .., n-1 cyfr liczby np. z początku lub końca. W ten sposób ustala się sumę jaką każdy element będzie musiał spełnić. Następnie wybierane są wszystkie możliwe kombinacje podziału, aby znaleźć rozwiązanie.

Przykładowo dla liczby 123 sprawdzane są następujące wartości 3 i 23 (123 już nie, ponieważ nie będzie wtedy podziału). Po wybraniu 23 pewne jest, że 1 nie spełni wymogu. Natomiast po wybraniu 3 należy całą pozostałą część potraktować jako całość tj. 12. Wtedy 1 + 2 = 3.

Możliwe rozwiązania

Możliwych podziałów może być więcej niż jedno jeśli w liczbie występuje wartość 0. Otóż jest to wartość neutralna dodawania. Oznacza to, że cyfrę tę można dołączyć do lewego lub prawego elementu (jeśli jest pomiędzy nimi, a nie w nich). Podczas szukania możliwych rozwiązań należy właśnie pamiętać, że część liczby 3 nie jest równa części 03.

Przykłado wstawiając 0 na początku liczby 123 to dalej pozostanie jedno rozwiązanie {01, 23}. Sytuacja się zmienia, gdy wstawimy 0 po 2. Wtedy liczba 1203 może zostać podzielona na dwa różne sposoby: {12, 03} lub {120, 3}. Im więcej zer tym więcej jest możliwych rozwiązań. Możliwe jest też, że 0 wystąpi "wewnątrz elementu" tj. 1023. Takie ustawienie nie powoduje zwiększenia możliwych podziałów.

Implementacja

Sumowanie cyfr

Program można rozpocząć od napisania funkcji, która będzie sumować cyfry liczby. Dla podanej liczby a funkcja sumujCyfry() zwraca sumę cyfr. Składa się ona z pętli, która, aż do usunięcia wszystkich cyfr sumuje je.

1. int sumujCyfry(int a) {
2.   int suma = 0;
3.   while (a > 0) {
4.     suma += a % 10;
5.     a /= 10;
6.   }
7.   return suma;
8. }

Sumowanie cyfr

Funkcja dzielLiczbe() wybiera pierwszy element i ustala sumę cyfr dla kolejnych elementów. Dodatkowo inicjalizuje listę, która będzie przechowywać aktualny podział. Lista ta będzie przekazywana pomiędzy kolejnym rekurencyjnymi wywołaniami. Funkcja zwraca wartość logiczną, która jeśli przyjmie prawdę oznacza, że zostało znalezione chociaż jedno rozwiązanie.

1. bool dzielLiczbe(int a) {
2.   vector<string> historia;
3.   int n = log10(a) + 1;
4.   int mn = 10;
5.   bool wynik = false;
6.   for (int i = 1; i < n; i++) {
7.     historia.push_back(naTekst(a % mn, i));
8.     wynik |= dzielLiczbe(a / mn, sumujCyfry(a % mn), historia);
9.     historia.pop_back();
10.     mn *= 10;
11.   }
12.   return wynik;
13. }

Dalszy proces podziału jest wywołany w poniższej funkcji. Przyjmuje ona liczbę a do podziału, suma - suma cyfr do spełnienia w każdym elemencie oraz historia - lista do której należy dopisać kolejny, wybrany element.

1. bool dzielLiczbe(int a, int suma, vector<string> &historia) {
2.   if (a == 0) {
3.     for (int i = historia.size() - 1; i >= 0 ; i--)
4.       cout << historia[i] << "\t";
5.     cout << endl;
6.     return true;
7.   }
8.   int n = log10(a) + 1;
9.   int mn = 10;
10.   bool wynik = false;
11.   for (int i = 0; i < n; i++) {
12.     int suma_teraz = sumujCyfry(a % mn);
13.     if (suma_teraz == suma) {
14.       historia.push_back(naTekst(a % mn, i + 1));
15.       wynik |= dzielLiczbe(a / mn, suma, historia);
16.       historia.pop_back();
17.     }
18.     mn *= 10;
19.   }
20.   return wynik;
21. }

Kolejne podziały są generowane rekurencyjnie. Warunkiem stopu jest tutaj wartość liczby a, która wynosi 0. Wtedy program wypisuje całą historię znalezionych części. W celu pokazania kolejności wybierania elementy są wypisywane od końca (wtedy są wypisane w kolejności ich ustalenia). Dalsza część jest identyczna z wybieraniem podziału jak w poprzednim kodzie.

Element

Wybrana część liczby nie może być przechowywana jako liczba, ponieważ może zawierać na początku 0, które zostanie utracone podczas zapisu jako liczba (chyba, że zachowamy jaką długość ma liczba). Prostszym rozwiązaniem jest sformatowanie elementu. Funkcja naTekst() zamienia liczbę a na tekst i uzupełnia zerami z lewej strony, aż długość dl zostanie osiągnięta.

1. string naTekst(int a, int dl) {
2.   char * wynik = new char[dl + 1];
3.   wynik[dl] = '\0';
4.   for (int i = dl - 1; i >= 0; i--) {
5.     wynik[i] = (char)('0' + (a % 10));
6.     a /= 10;
7.   }
8.   return wynik;
9. }

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika liczbę, a następnie wypisuje wszystkie możliwe jej podziały.

1. int main() {
2.   int a;
3.   cout << "Podaj liczbe do podzialu\n a = ";
4.   cin >> a;
5.   if (!dzielLiczbe(a)) {
6.     cout << "Brak podzialow" << endl;
7.   }
8.   system("pause");
9.   return 0;
10. }

• Kod źródłowy Implementacja