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ł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.
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.
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ń.
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ść.
Oto przykładowy fragment programu, który pozwala wczytać dane od użytkownika i zinterpretować wynik.
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.