Strona główna » Algorytmy » Artykuły » Najmniejsza Wielokrotność z Danych Cyfr
 

Najmniejsza Wielokrotność z Danych Cyfr

Zadanie

Dane jest pewna liczba n oraz zestaw cyfr. Napisz algorytm, który wyznaczy najmniejszą wielokrotność n, który będzie złożona jedynie z cyfr, które zostały podane w zestawie. Poszukiwania powinny zostać ograniczone do pewnego zakresu [0, max]. Jeśli w danym zakresie liczba nie zostało znalezione rozwiązanie to funkcja powinna zwrócić wartość -1.

Przykład

Przykładowo dla liczby n = 13 oraz zestawu cyfr {2, 5} odpowiedzią jest 52. Warto zauważyć, że jeśli w zestawie zostały uwzględnione wszystkie cyfry liczby n to odpowiedzią jest n. Innym przykładem jest n = 17 i zestaw cyfr {1, 2, 3}. Odpowiedzią jest 221. Tu warto zauważyć, że wielokrotność nie musi składać się ze wszystkich cyfr podanego zestawu.

Implementacja

Analiza Zadania

Zadanie można rozwiązać przy pomocy algorytmu z pętlą, który będzie wyliczać kolejne wielokrotności i sprawdzać, która z nich składa się tylko z cyfr podanych w zestawie. Jednak taka metoda jest mało efektywna, ponieważ jeśli dane będą tylko dwie cyfry to wielokrotności spełniaje to kryterium będzie bardzo mało, a więc program będzie sprawdzał bardzo dużo liczb niepotrzebnie. Rozwiązaniem tego problemu jest wykorzystanie algorytmu BFS.

Kod

Zadanie można rozwiązać algorytmem BFS. Oto przykładowa funkcja, która przyjmuje n - liczba, której wielokrotność szukamy, cyfry - zbiór cyfr, które można wykorzystać oraz max - górna granica zakresu poszukiwań.

  1. int SzukajMinimalnejWielokrotnosci(int n, vector<int> cyfry, int max = 1000000) {
  2.   queue<int> bufor;
  3.   sort(cyfry.begin(), cyfry.end());
  4.   bufor.push(0);
  5.   while (!bufor.empty()) {
  6.     int ostatni = bufor.front();
  7.     bufor.pop();
  8.     if (ostatni != 0 && ostatni % n == 0) {
  9.       return ostatni;
  10.     }
  11.     ostatni *= 10;
  12.     if (ostatni < max) {
  13.       for each (int x in cyfry) {
  14.         bufor.push(ostatni + x);
  15.       }
  16.     }
  17.   }
  18.   return -1;
  19. }

Początkowo w kolejce umieszczamy wartość 0, a następnie dopóki kolejka nie jest pusta to pobieramy wartość, którą najpierw sprawdzamy czy jest wielokrotnością n. Jeśli jest to natychmiast zwracamy wartość, ponieważ wszystkie kolejne wartości w kolejce są w porządku rosnącym. Jeśli jednak nie jest to wielokrotność to do kolejki dołączamy dla każdej cyfry z zestawu połączenie aktualnej wartości i cyfry. Oczywiście kolejne wartości powinny być dodawane wtedy i tylko wtedy, gdy nie przekraczają ustalonej wartości max. Jest to potrzebne, aby program nie poszukiwał wartościw nieskończoność.

Testowanie funkcji

Oto przykładowy fragment programu, który pozwala wczytać dane od użytkownika i zinterpretować wynik.

  1. int main() {
  2.   int n;
  3.   string zestaw;
  4.   cout << "Podaj liczbe:\n n = ";
  5.   cin >> n;
  6.   cout << "Uzyj cyfr (bez rozdzielenia):\n";
  7.   cin >> zestaw;
  8.   vector<int> cyfry;
  9.   for each (char c in zestaw)
  10.   {
  11.     if (!isdigit(c))
  12.       continue;
  13.     int q = c - '0';
  14.     if (find(cyfry.begin(), cyfry.end(), q) == cyfry.end())
  15.       cyfry.push_back(q);
  16.   }
  17.   int wynik = SzukajMinimalnejWielokrotnosci(n, cyfry);
  18.   if (wynik == -1) {
  19.     cout << "Nie udalo sie znalezc rozwiazania.." << endl;
  20.   }
  21.   else {
  22.     cout << "Szukana liczba to " << wynik;
  23.   }
  24.   system("pause");
  25.   return 0;
  26. }

Zadania

Zadanie 1

Napisz algorytm, który w pętli będzie sprawdzał kolejne wielokrotności n, aby wyznaczyć najmniejszą wielokrotność n złożoną z cyfr podanych w zestawie.