Dzisiaj zajmiemy się następującym zadaniem:
Problem 2: Pokrycie dywanowe
Po wybudowaniu muru z pierwszego zadania, Tomek zaczął układać klocki na środku przedszkola. Znalazł na dywanie czerwony prostokąt i zastanawia się ile klocków będzie potrzebował, aby go całego przykryć za pomocą kwadratowych klocków. Prostokąt ma wymiary a x b. Natomiast klocki mają wymiar c x c. Tomek układa klocki w ten sposób że boki klocków są prostopadłe do boków prostokąta. Tomkowi nie przeszkadza to, że być może klocki będą zajmować większą powierzchnię niż prostokąt. Pomóż Tomkowi i policz ile klocków będzie musiał przynieść z pudełka, aby wypełnić cały prostokąt.
Wejście
Na standardowym wejściu znajdują się trzy liczby naturalne a, b oraz c (1 ≤ a, b, c ≤ 1000) oznaczające odpowiednio, długość pierwszego boku prostokąta, długość drugiego boku prostokąta i długość boku klocka.
Wyjście
Na standardowe wyjście należy wypisać jedną liczbę naturalną – liczbę klocków potrzebną Tomkowi do przykrycia prostokąta.
Przykład
Dla danych wejściowych
5 7 2Poprawną odpowiedzią jest
12Wyjaśnienie do przykładu:
Pewnie zastanawiacie się dlaczego zaczynam tak bezpośrednio. Żadnego wstępu, żadnego dzień dobry, tylko od razu zaczynamy od zadania. Taki zabieg ma na celu po pierwsze, dać Wam czas na samodzielne rozwiązanie zadania, po drugie pokazanie, że to czego za chwilę Was nauczę, faktycznie się przydaje!
W pierwszej notce dowiedzieliśmy się czym jest zmienna, nauczyliśmy się ją deklarować oraz wczytywać do niej wartość podaną z klawiatury. Dzisiaj poznamy kolejne rzeczy, które możemy z nią robić. Najczęstszą operacją jaką będziemy wykonywać na zmiennych, będzie przypisanie do nich wartości. Popatrzmy na następujący program.
#include <iostream>
using namespace std;
int main()
{
int a;
a = 17; // Od tego miejsca, wartość zmiennej a to 17
cout << a << endl;
return 0;
}Linijka int a; to znana nam z pierwszej notki deklaracja zmiennej a. Zaraz pod nią przypisujemy wartość 17 do tej zmiennej, a następnie wypisujemy tę zmienną za pomocy znanego nam z pierwszej notki, strumienia cout. Aby się przekonać że faktycznie na ekranie zostanie wypisana wartość 17, spróbujemy teraz program skompilować.
Od tego momentu będę zakładał, że czytelnik korzysta z systemu Linux. Osoby, które korzystają z systemu Windows mogą za darmo zainstalować Linuxa używając programu Oracle VM Virtual Box. Jeśli nie chcecie tego robić, możecie skorzystać z programu CodeBlocks lub internetowego kompilatora np. ideone. Pewne kwestie w programowaniu łatwiej jest zrozumieć korzystając z linuksowej konsoli (na przykład co robi return 0 w kodzie powyżej lub czym tak naprawdę jest standardowe wejście/wyjście). Tych kwestii nie będzie dużo i będą pojawiać się jedynie na początku kursu.
Utwórzmy w naszym katalogu domowym folder o nazwie szkółka. W katalogu tym utwórzmy plik zmienna.cpp i otwórzmy go w edytorze tekstu (na potrzeby tej szkółki, za edytor tekstu będziemy rozumieli program, umożliwiający edycję tekstu, ale nie jego formatowanie; zatem Microsoft Word, Open Office Writer i inne tego typu programy się nie liczą; proszę nie pytać jakie traumatyczne przeżycia w mojej karierze doprowadziły do tego, że postanowiłem to wyjaśnienie tutaj umieścić). Wklejmy powyższy program i zapisz plik. Otwórz okno konsoli i przejdź do katalogu szkółka:
cd ~/szkółkaTeraz możemy skompilować nasz program:
g++ -o zmienna zmienna.cppJeśli otworzysz katalog, zobaczysz, że powstał w nim nowy plik o nazwie zmienna (możesz też to zobaczyć w konsoli wpisując w niej polecenie ls albo dir). g++ to nazwa programu, -o zmienna oznacza, że chcemy, aby nasz program nazywał się zmienna (nazwa pliku, który się właśnie utworzył) i w końcu zmienna.cpp to nazwa pliku z kodem źródłowym. Teraz nasz program możemy uruchomić wpisując:
./zmiennaJeśli wszystko wykonaliśmy poprawnie, powinniśmy zobaczyć na ekranie:
17Pierwsze przypisanie wartości do zmiennej, nazywamy inicjalizacją. Zanim zmienną zainicjalizujemy, posiada ona bliżej nie określoną wartość (usuń linijkę z przypisaniem z powyższego kodu, zapisz go, skompiluj ponownie program i uruchom; zobacz co dostałeś na ekranie; ja otrzymałem 32534; uruchom program ponownie; czy dostałeś taką samą wartość; u mnie wyświetliła się inna). Inicjalizować zmienne możemy już w momencie ich deklaracji. Wygląda to następująco:
#include <iostream>
using namespace std;
int main()
{
int a = 17;
cout << a << endl;
return 0;
}Na zmiennych całkowitoliczbowych możemy wykonywać operacje arytmetyczne. Są to na przykład: dodawanie, odejmowanie i mnożenie. Dodajemy wartości przy użyciu operatora +, odejmujemy przy użyciu operatora - a mnożymy przy użyciu operatora *.
#include <iostream>
using namespace std;
int main()
{
int a;
a = 2 + 2 * 2;
cout << a << endl;
return 0;
}Język C++ zwraca uwagę na kolejność wykonywania działań, dlatego powyższy program wypisze na ekranie 6, a nie 8. Jeśli chcielibyśmy uzyskać 8, musielibyśmy posłużyć się nawiasami. Do tego służą nawiasy okrągłe (). W szkole na matematyce stosowaliśmy również nawiasy kwadratowe (dla zwiększenia czytelności), ale w C++ używamy wyłącznie okrągłych. Możemy za to używać ich tyle razy ile chcemy.
#include <iostream>
using namespace std;
int main()
{
int a;
a = (2 + 2) * 2;
cout << a << endl;
return 0;
}Z operacją dzielenia nie jest tak prosto w przypadku liczb całkowitych. Wiemy przecież, że na przykład 7 / 3 nie da się wykonać w liczbach całkowitych (7 nie jest podzielne przez 3). Chociaż jeśli cofniemy się do 3 klasy podstawówki, być może przypomnimy sobie, że tam właśnie nauczyliśmy się dzielić 7 przez 3. Pisaliśmy wtedy 7 / 3 = 2 r. 1. Co czytaliśmy jako: siedem dzielone na trzy daje 2, reszty 1. I tak samo działa dzielenie w C++. Poniższy kod wypisze na ekranie liczbę 2:
#include <iostream>
using namespace std;
int main()
{
int a;
a = 7 / 3;
cout << a << endl;
return 0;
}Aby dowiedzieć się jaka jest reszta z dzielenia liczby 7 na 3, musimy użyć operatora modulo %. Operator ten ma zaskakująco dużo zastosowań w programowaniu i będziemy do niego wielokrotnie wracać.
Oprócz dodawania liczb, możemy również dodawać do siebie zmienne. Na przykład w ten sposób:
#include <iostream>
using namespace std;
// Program do liczenia średniej arytmetycznej
int main()
{
int a, b, srednia;
cin >> a >> b;
srednia = (a + b) / 2;
cout << srednia << endl;
return 0;
}Jest to pierwszy nasz program w którym użyliśmy więcej niż jednej zmiennej! Zmienne mogliśmy zadeklarować w trzech osobnych linijkach, ale możemy również to zrobić w jednej linijce, oddzielając zmienne od siebie przecinkami. Dokładnie tak jak powyżej. Przyjrzyjmy się miejscu, w którym przypisujemy wartość zmiennej srednia. Zawsze w momencie w którym przypisywana jest wartość do zmiennej, najpierw obliczana jest prawa strona równości, a następnie jej wynik przypisywany jest do zmiennej, która znajduje się po lewej stronie równości. Ponieważ program działa w takiej właśnie kolejności, możliwa jest następująca konstrukcja:
#include <iostream>
using namespace std;
int main()
{
int x = 4;
x = x + 1;
cout << x << endl;
return 0;
}Chociaż z matematycznego punktu widzenia, zapis x = x + 1 nie ma sensu, to tutaj oznacza on: weź wartość zmiennej x, dodaj do niej 1 i wynik zapisz w zmiennej x. Jest on zatem całkowicie logiczny i program wypisze na ekranie wartość 5.
Mamy już wystarczającą wiedzę do rozwiązania naszego zadania. Jeśli jeszcze nie rozwiązałeś naszego zadania (a chcesz to zrobić) to jest to ostatni moment, aby pomyśleć nad zadaniem samodzielnie.
W zadaniu pewien prostokąt próbujemy pokryć kwadratami i pytamy się ile kwadratów potrzebujemy. Możemy na chwilę zastanowić się nad zadaniem prostszym. Gdybym miał odcinek o długości 7 i próbował go pokryć odcinkami o długości 2… to ile odcinków bym potrzebował? Nie trudno zauważyć że 4. Jak to jednak policzyć? Można wziąć 7, podzielić na 2, a następnie zaokrąglić w górę. Jak to zrobić w języku C++? Wiemy, że w C++ dzielenie dwóch liczb jest zaokrąglane w dół. Czy zatem wystarczy dodać jeden? Nie. Bo jeśli 6 podzielimy na 2 i dodamy 1 to uzyskamy 4. A 3 odcinki długości 2 wystarczą aby pokryć odcinek długości 6.
Potrzebujemy użyć pewnej sztuczki. Mianowicie jeśli chcemy poznać wynik a / b zaokrąglony w górę, musimy najpierw do a dodać b-1. Wzór wygląda tak: (a + b - 1) / b. Zobaczmy na przykładzie że działa. Jeśli a = 7 i b = 2 to wtedy (7 + 2 - 1) / 2 = 8 / 2 = 4. I takiego wyniku oczekiwaliśmy. A jeśli a = 6 i b = 2 to wtedy (6 + 2 - 1) / 2 = 7 / 2 = 3. Jeśli ktoś by chciał przeprowadzić formalny dowód poprawności tego wzoru to musiałby rozważyć dwa przypadki. Jeśli b dzieli a oraz jeśli b nie dzieli a.
Wracając do naszego zadania. Możemy policzyć ile odcinków długości c potrzeba aby pokryć jeden bok prostokąta, ile odcinków długości c potrzeba aby pokryć drugi bok prostokąta, a następnie te wartości przez siebie przemnożyć. Wybrałem to zadanie na dzisiejszą notkę, bo wymaga ona 4 operacji, jakie poznaliśmy dzisiaj. Brakuje już tylko modulo. Program można zapisać w następujący sposób:
#include <iostream>
using namespace std;
int main()
{
int a, b, c, wynik;
cin >> a >> b >> c;
wynik = (a + c - 1) / c * (b + c - 1) / c;
cout << wynik << endl;
return 0;
}Krzyś dał Tomkowi 5 jabłek. Tomek oddał Kasi 3 jabłka. Pytanie: ile jabłek ma Tomek? Odpowiedź: nie wiadomo, bo nie wiemy ile Tomek miał jabłek na początku. Morał: zawsze pamiętaj o inicjalizowaniu zmiennych.
