Strona główna » Algorytmy » Artykuły » Znajdź Liczbę
?
 

Znajdź Liczbę

Zagadka

Znajdź liczbę mniejszą od 3000, która przy dzieleniu przez 2 daje resztę 1, przez 3 resztę 2, ..., przez 9 resztę 8. Jaka to liczba? Uzasadnij swój wybór i zastanów się jak najprościej ją obliczyć?

Rozwiązanie

Odpowiedź

Poprawną odpowiedzią jest liczba 2519.

Wyjaśnienie

Sprawdzanie wszystkich warunków dla każdej z liczb to bardzo długi i monotonny proces. Z tego powodu warto przyjrzeć się dokładniej warunkom określonym w zadaniu. Po pierwsze wiadomo, że przy dzieleniu przez 2 otrzymujemy resztę 1. To powinno dać wskazówkę, że poszukujemy liczby nieparzystej. Wiadomo też, że przy dzieleniu przez 3 daje resztę 2. W celu szybkiego zawężenia poszukiwań przyjrzyjmy się, że liczba podzielona przez 5 da resztę 4. W takim razie ostatnia cyfra to 4, albo 9. Wiemy jednak, że liczba jest nieparzysta, więc zostawiamy 9.

Znamy już cyfrę jedności liczby: 9. To ogranicza liczbę potencjalnych liczb do około 300. Licza będzie podzielna przez 4 jeśli jej dwie ostatnie cyfry są podzielne przez 4. W zadaniu przy dzieleniu przez 4 mamy otrzymać resztę 3, więc jak dwie ostatnie cyfry podzielimy przez 4 to musimy otrzymać 3. Spośród wszystkich 10 możliwości pasuje: 19, 39, 59, 79 i 99. (W tej chwili liczba możliwych rozwiązań zmniejszyła się o połowę.) Jeśli liczba jest podzielna przez 9 to suma jej cyfr też, więc wiadomo, że suma cyfr po podzieleniu przez 9 musi dać w tym zadaniu 8. Skorzystamy też z faktu, że liczba jest maksymalnie 4 cyfrowa. Dla każdej cyfry początkowej 0, 1, 2 i odpowiedniej końcówki wyliczymy drugą od lewej cyfrę c na podstawie warunku podzielności przez 9. Dla każdej liczby sprawdzamy warunek czy po podzieleniu przez 7 otrzymamy resztę 6.

Dla przypomnienia jeśli chcemy sprawdzić czy liczba dzieli się przez 7 skreślamy jej ostatnie trzy cyfry, a od tak powstałej liczby odejmujemy liczbę skreśloną, jeśli ta różnica dzieli się przez siedem to i liczba jest podzielna przez 7.

1cKońcówkaCzy liczba podzielona przez 7 daje resztę 6?
0719(0·27 + 7·9 + 1·3 + 9)/7 = 75/7 = 10 r. 5
0539(0·27 + 5·9 + 3·3 + 9)/7 = 63/7 = 9 r. 0
0359(0·27 + 3·9 + 5·3 + 9)/7 = 51/7 = 7 r. 2
0179(0·27 + 1·9 + 7·3 + 9)/7 = 39/7 = 5 r. 4
0899(0·27 + 8·9 + 9·3 + 9)/7 = 108/7 = 15 r. 3
1619(1·27 + 6·9 + 1·3 + 9)/7 = 93/7 = 13 r. 2
1439(1·27 + 4·9 + 3·3 + 9)/7 = 81/7 = 11 r. 4
1259(1·27 + 2·9 + 5·3 + 9)/7 = 69/7 = 9 r. 6
1079(1·27 + 0·9 + 7·3 + 9)/7 = 57/7 = 8 r. 1
2699(2·27 + 6·9 + 9·3 + 9)/7 = 144/7 = 20 r. 4
2519(2·27 + 5·9 + 1·3 + 9)/7 = 111/7 = 15 r. 6
2339(2·27 + 3·9 + 3·3 + 9)/7 = 99/7 = 14 r. 1
2159(2·27 + 1·9 + 5·3 + 9)/7 = 87/7 = 12 r. 3
2879(2·27 + 8·9 + 7·3 + 9)/7 = 156/7 = 22 r. 2
2699(2·27 + 6·9 + 9·3 + 9)/7 = 144/7 = 20 r. 4

Potencjalnymi kandydatami są tutaj tylko dwie liczby: 1259 oraz 2159. Obie spełniają warunek, że przy dzieleniu otrzymujemy resztę 2. Jednak okazuje się, że 1259 mod 8 = 3, a 2159 mod 8 = 7. Szukana liczba została znaleziona poprzez eliminację lczb, które nie spełniają określonej reguły dzielenia.

Implementacja

Założenia

Celem jest napisanie funkcji szukajLiczby(), która znajdzie najmniejszą liczbę, która spełni wszystkie zadane warunki dla danego dzielnika i reszty. Jako argumenty program wczytuje ilość n takich par, a następnie n takich par. Jeśli w zakresie zmiennej nie udało się znaleźć takiej wartości to program powinien zwrócić 0.

Rozwiązanie

  1. int szukajLiczby(vector<int> lista) {
  2.   int liczba = 0;
  3.   while (liczba + 1 < INT_MAX) {
  4.     liczba++;
  5.     bool ok = true;
  6.     for (int i = 0; i < lista.size(); i += 2) {
  7.       if (liczba % lista[i] != lista[i + 1]) {
  8.         ok = false;
  9.         break;
  10.       }
  11.     }
  12.     if (ok) {
  13.       return liczba;
  14.     }
  15.   }
  16.   return 0;
  17. }

Poszukiwania liczby odbywają się w pętli, aż do osiągnięcia górnego zakresu zmiennej, albo do przerwania poprzez zwrócenie znalezionej wartości. Dla każdej kolejnej liczby program sprawdza dla każdej pary (dzielnik, reszta) czy wymagany warunek jest spełniony. Jeśli nie jest to program przerywa wewnętrzną pętlę i przechodzi do następnej liczby. Jednak jeśli pętla nie zostanie przerwana to zmienna ok pozostanie ustawiona na prawdę i jeśli tak będzie to zwrócona zostanie aktualnie rozpatrywana liczba. W przypadku, gdy zostanie osiągnięty górne ograniczenie zmiennej zwrócona zostanie wartość 0.

Testowanie funkcji

Poniższy fragment kodu wczytuje n warunków, a następnie wypisuje odpowiedni komunikat w zależności od zwróconej wartości.

  1. int main () {
  2.   int n, dzielnik, reszta;
  3.   cout << "Ile warunkow?\n n = ";
  4.   cin >> n;
  5.   vector<int> lista;
  6.   while (n-- > 0) {
  7.     cin >> dzielnik >> reszta;
  8.     lista.push_back(dzielnik);
  9.     lista.push_back(reszta);
  10.   }
  11.   int wynik = szukajLiczby(lista);
  12.   if (wynik == 0) {
  13.     cout << "Nie znaleziono rozwiazania";
  14.   } else {
  15.     cout << "Liczba to " << wynik << endl;
  16.   }
  17.   system("pause");
  18.   return 0;
  19. }