Zadanko na dziś brzmi:
Zadanie 4: Sprawa małej wagi
Tomek obserwuje mrówki w przedszkolnym terrarium. Znajdują się tam dwa gatunki mrówek: czerwone i czarne. Czarnych jest więcej niż czerwonych. Aczkolwiek Tomek zauważył, że co roku liczba czarnych mrówek się podwaja, a liczba czerwonych potraja. Teraz Tomek się zastanawia za ile lat liczba czerwonych mrówek przerośnie liczbę czarnych.
Wejście
W jedynym wierszu standardowego wejścia znajdują się dwie liczby naturalne a oraz b (1 ≤ a < b ≤ 100) oznaczające odpowiednio liczbę czerwonych i czarnych mrówek.
Wyjście
Na standardowym wyjściu należy podać liczbę pełnych lat po upływie których liczba czerwonych mrówek będzie większa od liczby mrówek czarnych.
Przykład
Dla danych wejściowych
8 18Poprawnym wynikiem jest
3Wyjaśnienie do przykładu. Po pierwszym roku liczba czerwonych mrówek będzie równa 24, a czarnych 36. Po drugim roku zarówno liczba czarnych jak i czerwonych mrówek będzie równa 72. Dopiero w trzecim roku liczba czerwonych mrówek przerośnie liczbę czarnych mrówek. Będzie ich odpowiednio 216 oraz 144.
Wszystkie instrukcje w naszych programach do tej pory wykonywane były jednokrotnie. Dzisiaj poznamy pętle, dzięki którym pewne instrukcje będą mogły być wykonywane wielokrotnie. Pętla while (ang. dopóki) wygląda w następujący sposób:
while (warunek)
{
// blok instrukcji
}Powyższy blok instrukcji będzie wykonywany dopóki warunek jest prawdziwy. Przebieg tego programu jest następujący. Sprawdzamy czy prawdziwy jest warunek. Jeśli nie, to kończymy. Jeśli jest prawdziwy to wykonujemy blok instrukcji i ponownie sprawdzamy czy warunek jest prawdziwy. Jeśli nie jest to kończymy. Jeśli jest prawdziwy to wykonujemy blok instrukcji i ponownie sprawdzamy czy warunek jest prawdziwy… Jak widać program może wykonywać się w ten sposób w “nieskończoność”. Mówimy wtedy, że program wpadł w nieskończoną pętlę. Zadaniem programisty jest napisanie programu w ten sposób, aby do tego nie dopuścić. Jeśli nasz program wpadnie w nieskończoną pętlę na konkursie, zostanie on wyłączony po przekroczeniu limitu czasu i otrzymamy werdykt “przekroczony limit czasu”. Jeśli program wpadnie w nieskończoną pętlę na naszym komputerze, możemy go wyłączyć w konsoli używając skrótu ctrl + c. Używając tego skrótu możemy wyłączyć program nawet jeśli nie wpadł on w nieskończoną pętlę 🙂
Zmodyfikujmy nasz program do wprowadzania kodu pin.
#include <iostream>
using namespace std;
int main()
{
const int poprawny_pin = 4242;
int pin;
cout << "Podaj pin: ";
cin >> pin;
while (pin != poprawny_pin)
{
cout << "Pin niepoprawny" << endl;
cout << "Podaj pin: ";
cin >> pin;
}
cout << "Pin podany poprawnie" << endl;
return 0;
}Powyższy program prosi o podanie pinu. Jeśli pin nie jest poprawny, to wyświetla komunikat o niepoprawnym pinie i prosi ponownie o podanie pinu i całość się powtarza aż do momentu, gdy użytkownik poda poprawny pin. Wtedy program wypisuje “Pin podany poprawnie” i program się kończy.
Istnieje inna wersja pętli while, zwana do ... while. Jest ona używana bardzo rzadko (na tyle rzadko, że nie mam pojęcia czy jeszcze kiedykolwiek pojawi się na tym blogu), ale chyba warto mieć świadomość jej istnienia. Wygląda ona następująco:
do
{
// blok instrukcji
} while (warunek);Zwróć uwagę, że w konstrukcji powyżej, jest użyty średnik, którego nie ma w konstrukcji while. Jedyna różnica między tą wersją a poprzednią, jest taka, że w wersji do ... while blok instrukcji jest zawsze wykonywany. Innymi słowy. W pętli do ... while blok instrukcji zostanie wykonany przynajmniej raz, podczas gdy w pętli while takiej gwarancji nie mamy. Albo jeszcze inaczej. W pętli while najpierw sprawdzany jest warunak a później wykonywany jest blok instrukcji (i tak w kółko) a w pętli do ... while na odwrót. Pojedyncze wykonanie bloku instrukcji w pętlach będę nazywał jedną (lub pojedynczą) iteracją.
Ostatnią pętlą o której powiemy, jest pętla for. Wygląda ona tak:
for (inicjalizacja zmiennej; warunek; zmiana wartości zmiennej)
{
// Blok instrukcji
}Wygląda to trochę skomplikowanie. Spróbujmy na przykładzie:
for (int i = 0; i < n; i++)
{
// Blok instrukcji
}Konstrukcja działa następująco. Wykonywana jest inicjalizacja zmiennej int i = 0; (w nowszych wersjach C++ możliwe jest zdefiniowanie zmiennej i w tym miejscu na co nie pozwalają niektóre archaiczne wersje języka C sprzed 1999 roku; choć nie powinno się zdarzyć aby na zawodach obowiązywał aż tak stary kompilator, to w szkółce młodego konkursowicza postaram się wam opowiadać o różnicach pomiędzy kompilatorami). Następnie sprawdzany jest warunek i < n. Jeśli nie jest on spełniony to kończymy. Jeśli jest, to wykonujemy blok instrukcji, po którym wykonujemy operację i++. Operacja ta polega na zwiększeniu zmiennej i o jeden i jest zwana inkrementacją. Następnie znowu sprawdzamy czy prawdziwy jest warunek i < n. Jeśli nie to kończymy. Jeśli tak, to znowu wykonujemy blok instrukcji i zwiększamy zmienną i o jeden. Zmienną i nazywamy zmienną sterującą pętlą.
Można łatwo zauważyć, że pętla wykona się dokładnie n razy. Ktoś mógłby zapytać dlaczego zaczynamy od i = 0 i kończymy na i < n, zamiast zacząć od i = 1 i kończyć na warunku i <= n. Wtedy też pętla wykonałaby się dokładnie n razy. Zaczęliśmy jednak od zera, bo tak się zaczyna w języku C++ i chcę was do tego przyzwyczaić. Głównym powodem dla którego tak jest, jest indeksowanie tablic w tym języku, które poznamy już niedługo. Dlaczego tablice indeksuje się od zera zrozumiemy jednak dopiero po notce poświęconej wskaźnikom. W tej chwili najlepiej po prostu uwierzyć na słowo, że tak będzie lepiej. Zwróćcie też uwagę na to, że jeśli weźmiemy resztę z dzielenia dowolnej liczby naturalnej przez n to w wyniku otrzymamy jakąś liczbę z zakresu od 0 do n-1. Jest to ciekawy związek z numerowaniem od zera, z którego wielokrotnie będziemy korzystać.
Tak naprawdę język programowania potrzebuje tylko jednego rodzaju pętli. Pętla for i pętla while są sobie tożsame. Zauważmy, że pętlę for możemy zapisać w następujący sposób:
int i = 0;
while (i < n)
{
// Blok instrukcji
i++;
}Natomiast pętlę while można zapisać w następujący sposób:
for (; warunek; )
{
// Blok instrukcji
}Zatem dlaczego uczymy się obu tych konstrukcji? Otóż będziemy z nich korzystać przy różnych okazjach. Pętli for używamy wtedy kiedy wiemy ile razy ma wykonywać się blok instrukcji. Jeśli ma wykonać się on 5 razy, 10 razy, 1000 razy, n razy, 2 *n razy… wtedy korzystamy z pętli for. Z pętli while korzystamy wtedy, kiedy nie wiemy ile razy wykona się blok instrukcji. Na przykład jeśli nie wiemy ile razy użytkownik poda nam zły pin. Oczywiście to tylko sugestia mająca na celu poprawienie czytelności naszego programu.
Wróćmy jeszcze na chwilę do pętli for, bo spotkaliśmy tam ciekawą instrukcję i++. Jest to oczywiście skrót instrukcji i = i + 1. O tyle charakterystyczny jest to skrót, że od niego nazwę wziął język C++ (jako że jest to język C tylko o jeden większy; w podobnym tonie (pun intended) nazwa języka C# wzięła swoją nazwę od #, który w muzyce oznacza pół tonu w górę). Takich skrótów w języku C++ jest więcej. Mamy oczywiście i--, które oznacza i = i - 1 (tak zwana dekrementacja) jak i cały zestaw postaci a (operacja)= b. Na przykład a += b, a -= b, a *= b czy nawet a %= b. Oznaczają one odpowiednio a = a + b, a = a - b, a = a * b oraz a = a % b. Są jeszcze operatory --i oraz ++i, które różnią się od i-- oraz i++ pewną subtelną różnicą, o której powiem innym razem.
Nauczyliśmy się już naprawdę sporo. Przejdźmy zatem do rozwiązania naszego zadania. Problem da się rozwiązać matematycznie. Na szczęście nie jesteśmy tego w stanie zrobić, bo nie poznaliśmy jeszcze logarytmów w szkółce młodego konkursowicza. Użyjemy zatem pętli!
#include <iostream>
using namespace std;
int main()
{
int a, b, rok;
cin >> a >> b;
rok = 0;
while (a <= b)
{
a *= 3;
b *= 2;
rok++;
}
cout << rok << endl;
return 0;
}Pętla while wykonuje się tak długo, jak a <= b. W bloku instrukcji pętli while zmiększamy 3-krotnie zmienną a oraz 2-krotnie zmienną b. W zmiennej rok liczymy ile razy wykonała się pętla while i wartość tej zmiennej później wyświetlamy na standardowym wyjściu.
