Strona główna » Algorytmy » Teoria Liczb » Obracanie Liczby
 

Obracanie Liczby

https://mattomatti.com/a0218

Cel

Znajdź wszystkie unikalne obroty liczby. Obrót liczby w lewo oznacza przeniesienie cyfry jedności na początek liczby. Można również obrócić w drugą stronę przenosząc pierwszą cyfrę na koniec. Dodatkową zaletą rozwiązania będzie posortowany wynik końcowy.

Przykład

Przykładowo obracają liczbę 123 w prawo otrzymamy kolejno 123, 312, 231, 123 itd., a w lewo byłoby odwrotnie tj. 123, 231, 312, 123, itd. Jeśli w liczbie występuje powtarzający się wzór cyfr np. liczba 1818 to ma ona tylko dwa unikalne obroty: 1818, 8181. Na podstawie tego łatwo zauważyć, że ilość unikalnych wyników w wyniku obrotu jest równa najdłuższej, niepowtarzącej się części liczby. Dla liczb złożonej z jednej cyfry tylko ona jest unikalnym obrotem.

Implementacja

Poniższy algorytm znajduje zbiór wszystkich unikalnych obrotów liczby dla podanej liczby a. Algorytm wykorzystuje obrót w prawo.

  1. static HashSet<int> ZnajdzObroty(int a) {
  2.   int dl = (int)Math.Log10(a) + 1;
  3.   int mn = (int)Math.Pow(10, dl - 1);
  4.   HashSet<int> wynik = new HashSet<int>();
  5.   for (int i = 0; i < dl; i++) {
  6.     a = (a % 10 * mn) + (a / 10);
  7.     wynik.Add(a);
  8.   }
  9.   return wynik;
  10. }

Algorytm początkowo określa z ilu cyfr składa się podana liczba oraz mnożnik mn, który zostanie wykorzystany do przekładania cyfry jedności na początek. Następnie w pętli przesuwamy tyle razy z ilu cyfr składa się liczba. Wszystkie znalezione wartości dorzucamy do zbioru wynikowego. Wykorzystują odpowiednią strukturę danych na koniec zwracana jest lista unikalnych obrotów. Dodatkowo jest ona posortowana.

Testowanie funkcji

Poniższy fragment kodu może wczytać od użytkownika liczbę, a następnie wypisać dla niej wszystkie unikalne obroty:

  1. static void Main(string[] args) {
  2.   Console.Write("Podaj liczbę do obrotu\n a = ");
  3.   int a = Convert.ToInt32(Console.ReadLine());
  4.   HashSet<int> wynik = ZnajdzObroty(a);
  5.   foreach (int x in wynik) {
  6.     Console.Write("{0} ", x);
  7.   }
  8. }

Zadania

Zadanie 1

Napisz algorytm do znajdowania wszystkich obrotów liczby wykorzystując obrót w lewo. Przykładowo dla liczby 123 kolejno powinny zostać wypisane:

  1. 123
  2. 231
  3. 312
  4. 123
  5. ..