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

Najmniejsza Wielokrotność z Danych Cyfr

https://mattomatti.com/a0239

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

C++C#
Python
  1. def SzukajMinimalnejWielokrotnosci(n, cyfry, max=1000000):
  2.   bufor = [0]
  3.   cyfry.sort()
  4.   while (len(bufor) != 0):
  5.     ostatni = bufor.pop(0)
  6.     if (ostatni != 0 and ostatni % n == 0):
  7.       return ostatni
  8.     ostatni *= 10
  9.     if (ostatni < max):
  10.       for x in cyfry:
  11.         bufor.append(ostatni + x)
  12.   return -1

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.

C++C#
Python
  1. n = int(input("Podaj liczbę\n n = "))
  2. zestaw = input("Użyj cyfr (bez rozdzielenia):\n")
  3. cyfry = []
  4. for c in zestaw:
  5.   if not c.isdigit():
  6.     continue
  7.   q = ord(c) - ord('0')
  8.   if not q in cyfry:
  9.     cyfry.append(q)
  10. wynik = SzukajMinimalnejWielokrotnosci(n, cyfry)
  11. if (wynik == -1):
  12.   print("Nie udało się znaleźć rozwiązanie")
  13. else:
  14.   print("Szukana liczba to", wynik)

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.