Strona główna » Algorytmy » Artykuły » Równe Sumy Części
 

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. static 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. static bool dzielLiczbe(int a) {
  2.   List<string> historia = new List<string>();
  3.   int n = (int)(Math.Log10(a) + 1);
  4.   int mn = 10;
  5.   bool wynik = false;
  6.   for (int i = 1; i < n; i++) {
  7.     historia.Add(naTekst(a % mn, i));
  8.     wynik |= dzielLiczbe(a / mn, sumujCyfry(a % mn), ref historia);
  9.     historia.RemoveAt(historia.Count - 1);
  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. static bool dzielLiczbe(int a, int suma, ref List<string> historia) {
  2.   if (a == 0) {
  3.     for (int i = historia.Count - 1; i >= 0; i--)
  4.       Console.Write("{0}\t", historia[i]);
  5.     Console.WriteLine();
  6.     return true;
  7.   }
  8.   int n = (int)(Math.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.Add(naTekst(a % mn, i + 1));
  15.       wynik |= dzielLiczbe(a / mn, suma, ref historia);
  16.       historia.RemoveAt(historia.Count - 1);
  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. static string naTekst(int a, int dl) {
  2.   StringBuilder wynik = new StringBuilder();
  3.   for (int i = dl - 1; i >= 0; i--) {
  4.     wynik.Insert(0, (char)('0' + (a % 10)));
  5.     a /= 10;
  6.   }
  7.   return wynik.ToString();
  8. }

Testowanie funkcji

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

  1. static void Main(string[] args) {
  2.   Console.Write("Podaj liczbę do podziału\n a = ");
  3.   int a = Convert.ToInt32(Console.ReadLine());
  4.   if (!dzielLiczbe(a)) {
  5.     Console.WriteLine("Brak podziałów");
  6.   }
  7.   Console.ReadKey();
  8. }
Zadania
Zadanie 1
Napisz program, który przeprowadzi analizę podziału na równe części, ale w systemie szesnastkowym. Przetestuj działanie napisanego programu.
Przykładowo w systemie szesnastkowym prawidłowym podziałem liczby A21B11C jest {A21, B11, D}.
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1