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

  1. static int SzukajMinimalnejWielokrotnosci(int n, List<int> cyfry, int max = 1000000)
  2. {
  3. Queue<int> bufor = new Queue<int>();
  4. cyfry.Sort();
  5. bufor.Enqueue(0);
  6. while (bufor.Count != 0)
  7. {
  8. int ostatni = bufor.Dequeue();
  9. if (ostatni != 0 && ostatni % n == 0)
  10. {
  11. return ostatni;
  12. }
  13. ostatni *= 10;
  14. if (ostatni < max)
  15. {
  16. foreach (int x in cyfry)
  17. {
  18. bufor.Enqueue(ostatni + x);
  19. }
  20. }
  21. }
  22. return -1;
  23. }

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. static void Main(string[] args)
  2. {
  3. Console.Write("Podaj liczbę\n n = ");
  4. int n = Convert.ToInt32(Console.ReadLine());
  5. Console.WriteLine("Użyj cyfr (bez rozdzielenia):");
  6. string zestaw = Console.ReadLine();
  7. List<int> cyfry = new List<int>();
  8. foreach(char c in zestaw)
  9. {
  10. if (!char.IsDigit(c))
  11. continue;
  12. int q = c - '0';
  13. if (!cyfry.Contains(q))
  14. cyfry.Add(q);
  15. }
  16. int wynik = SzukajMinimalnejWielokrotnosci(n, cyfry);
  17. if (wynik == -1) {
  18. Console.WriteLine("Nie udało się znaleźć rozwiązanie");
  19. } else {
  20. Console.WriteLine("Szukana liczba to {0}", wynik);
  21. }
  22. Console.ReadKey();
  23. }

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.