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. }

• Kod źródłowy Implementacja

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.

• Kod źródłowy Zadanie 1