Najmniej Kwadratów
Zadanie
Dany jest prostokąt o pewnych bokach a i b. Zadanie polega na znalezieniu jak najmniejszej ilości kwadratów, które będzie można wyciąć z tego prostokąta, a potem z nich go odtworzyć. Napisz program, który dla podanych boków prostokąta zwróci najmniejszą ilość kwadratów na który trzeba podzielić prostokąt.
Analiza zadania
Zadanie sprowadza się do wycinania jak największego kwadratu z obecnego prostokąta. W kolejnych krokach należy wybrać, który bok jest krótszy, a następnie odciąć wzdłuż dłuższego boku kwadrat o takim boku jak krótszy bok prostokąta. Kontynuując takie wycinanie dochodzi się do momentu, gdy obydwa boki są sobie równe. Wtedy można zwrócić jeden, ponieważ kwadrat dowolnej wielkości nie wymaga dalszego dzielenia na kwadraty.
Przykład
Weźmy przykładowo prostokąt 17×10. Jednym z poprawnych jego podziałów jest:
Podczas rozwiązywania należy pamiętać, że orientacja prostokąta nie ma wpływu na dalszy podział, ponieważ figurę zawsze można obrócić. W celu uzyskania takiego wyniku należało kolejno wycinać następujące kwadraty i odpowiednio aktualizować boki:
| Kwadrat | a | b | Odcinany | Komentarz |
|---|---|---|---|---|
| 1 | 17 | 10 | 10×10 | Usuwamy największy możliwy kwadrat i odejmujemy od a 17 |
| 2 | 7 | 10 | 7×7 | Tym razem a jest krótszym bokiem, więc odcinamy od b |
| 3 | 7 | 3 | 3×3 | Kwadraty są coraz mniejsze.. |
| 4 | 4 | 3 | 3×3 | ..i może być kilka tego samego rozmiaru |
| 5 | 1 | 3 | 1×1 | |
| 6 | 1 | 2 | 1×1 | |
| 7 | 1 | 1 | 1×1 | Oba boki są równe, więc można zwrócić wynik |
Zgodnie z przedstawionym wcześniej przykładem podziału potrzeba dokładnie 7 kwadratów, aby podzielić prostokąt 17×10.
Implementacja
Przedstawiona funkcja najmniejKwadratow() zwraca wartość na ile kwadratów trzeba podzielić prostokąt. Działa ona rekurencyjnie.
- int najmniejKwadratow(int a, int b) {
- if (a == b)
- return 1;
- if (a < b)
- swap(a, b);
- return 1 + najmniejKwadratow(a - b, b);
- }
Do rozwiązania tego zadania należy wyróżnić trzy kroki: sprawdzanie czy dany prostokąt jest kwadratem - jeśli tak to zwrócić natychmiast 1. Jeśli nie jest to wyróżnić dłuższy bok, a następnie usunąć jak największy kwadrat czyli zwrócić 1 i dodać to co zwrócić funkcja dla tych samych parametrów, ale z pomniejszonym dłuższym bokiem o krótszy.
Testowanie funkcji
Do przetestowania napisanego kodu można skorzystać z poniższego fragmentu programu. Od użytkownika zostaje wczytany rozmiar prostoką ta i w odpowiedzi dostaje wynik funkcji.
- int main () {
- int a, b;
- cout << "Podaj rozmiar kwadratu\n a = ";
- cin >> a;
- cout << " b = ";
- cin >> b;
- int wynik = najmniejKwadratow(a, b);
- cout << "Wycietych kwadratow: " << wynik;
- system("pause");
- return 0;
- }
Zadania
Zadanie 1
Napisz funkcję najmniejKwadratow(), która będzie wykrywać, że jest więcej kwadratów tego samego rozmiaru do usunięcia. Przykładowo jeśli do usunięcia będę kolejno 3 kwadraty 4×4 to powinny zostać one usunięte w tym samym kroku.