Strona główna » Po Godzinach » Zagadki » Otwarte czy Zamknięte?
 

Otwarte czy Zamknięte?

https://mattomatti.com/a0067

Zagadka

W pewnym biurowcu znajduje się 100 par drzwi. Dyrektor zarządził, że otwieraniem oraz zamykaniem poszczególnych pomieszczeń będzie się zajmował specjalny robot. Na początku każdego dnia robot otwiera drzwi, a wieczorem wszystkie zamyka. Do wewnętrznej sieci firmy włamał się haker, który zmienił algorytm otwierania drzwi. Od teraz robot podchodząc do drzwi otwiera je jeśli są zamknięte, albo zamyka jeśli otwarte. Maszyna początkowo przeszła wszystkie drzwi po kolei (otwierając je), a następnie podszedł do co drugich drzwi (licząc od początku), potem co 3 (też od początku) itd. Pracę zakończył podchodząc do co setnych drzwi.

Nad ranem został wezwany informatyk, aby jak najszybszciej otworzył zamknięte drzwi. Z tego powodu potrzebne jest określenie, które pomieszczenia, tj. o jakich numerach, są już otwarte i ile ich będzie łącznie?

Rozwiązanie

Odpowiedź Będzie 10 takich pomieszczeń. Ich numery są kwadratami liczb naturalnych czyli są to pomieszczenia: 1, 4, 9, 16, 25, 36, 49, 64, 81 oraz 100.

Analiza zadania

Podstawowym problemem do zastanowienia się w zadaniu jest to jak określić ile razy robot łącznie otworzy/zamknie drzwi. Po pierwsze warto zauważyć, że jeśli robot podejdzie parzystą ilość razy to drzwi dalej pozostaną zamknięte, więc drzwi zostaną otwarte tylko pod warunkiem, że robot podejdzie nieparzystą ilość razy!

Rozpatrzmy przypadek podany w zadaniu, ale tylko dla 10 par drzwi. Na tej podstawie postaramy się wysnuć pewne wniosku. W kolejnych wierszach X oznacza, że dane drzwi zostały otwarte/zamknięte. Kolejne kolumny to kolejne drzwi.

 12345678910
1XXXXXXXXXX
2 X X X X X
3  X  X  X 
4   X   X  
5    X    X
6     X    
7      X   
8       X  
9        X 
10         X

Spójrzmy teraz na kolejne kolumny. W każdej kolumnie X oznacza, że liczba będąca nagłówkiem kolumny dzieli się przez nagłówek danego wiersza. Przykładowo liczba 6 dzieli się na 1, 2, 3 oraz 6. W ten sposób z tabelki można odczytać licząc X w danej kolumnie czy dana para drzwi będzie otwarta czy zamknięta. Jednak rysowanie tabelki 100×100 i jej wypełnianie nie jest najwygodniejszym pomysłem.

Zastanówmy się jednak ile dzielników ma liczba n? Na pewno każda liczba większa od 1 jest podzielna przez samą siebie oraz 1. Oznacza to, że nie zmieni to stanu w jakim znalazły się drzwi. Wykreślmy je w takim razie z tabelki:

 2345678910
1---------
2- X X X X
3 -  X  X 
4  -   X  
5   -    X

Nie rozpatrując liczby 1, ponieważ robot podejdzie do nich na pewno tylko raz, można zauważyć, że w niektórych kolumnach pozostała nieparzysta liczba X, a w niektórych parzysta. Nieparzysta ilość pozostała w przypadku liczb 4 oraz 9. Nie jest to przypadkowe. Jeśli jakaś liczba a jest dzielnikiem n to a pewno istnieje liczb b taka, że a·b = n. Oznacza to, że dzielniki występują "parami". Jednak czasem może się zdarzyć przypadek, że a = b. Z punktu widzenia zadania to jest jeden i ten sam dzielnik czyli tylko jedno podejście do drzwi. Tego typu warunek spełniają jedynie kwadraty liczb naturalnych.

Z analizy mamy następujący wniosek: nieparzystą ilość dzielników mają jedynie kwadraty liczb naturalnych. Z tego względu wszystkie pomieszczenia o numerach będących kwadratami zostaną otwarte, a wszystkie pozostałe pomieszczenia pozostaną zamknięte.

Implementacja

Napisz program, który wczyta od użytkownika ile jest drzwi w budynku. Funkcja ma wypisać wszystkie numery pomieszczeń, które zostaną zamknięte oraz ile takich pomieszczeń jest łącznie. Zakładamy, że algorytm otwierania drzwi jest identyczny z tym z zadania.

Zadanie

Zgodnie z analizą zadania przedstawioną wcześniej należy znaleźć wszystkie numery, które są kwadratami liczb naturalnych. Program będzie działał w pętli i wyliczał kolejne kwadraty, aż osiągnie wartość, która nie jest prawidłowym numerem pomieszczenia.

C++
C#
  1. int ktoreOtwarte(int n) {
  2.   int a = 1;
  3.   while (a*a <= n) {
  4.     cout << a*a << " ";
  5.     a++;
  6.   }
  7.   return a - 1;
  8. }

Testowanie funkcji

W celu wczytania argumentu od użytkownika, a następnie wypisanie wyniku można skorzystać z poniższego fragmentu kodu.

C++
C#
  1. int main () {
  2.   int n;
  3.   cout << "Ile jest drzwi w biurowcu?\n n = ";
  4.   cin >> n;
  5.   cout << "Otwarte zostana drzwi:\n";
  6.   int w = ktoreOtwarte(n);
  7.   cout << endl << "lacznie otwartych par: " << w;
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Napisz algorytm, który znajdzie, które pomieszczenia zostaną otwarte zgodnie z algorytmem w przedstawionym w zagadce. W swoim rozwiązaniu nie korzystaj z operacji mnożenia.