Strona główna » Algorytmy » Artykuły » Najmniej Kwadratów
 

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:

Przykładowy podział prostokąta

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:

KwadratabOdcinanyKomentarz
1171010×10Usuwamy największy możliwy kwadrat i odejmujemy od a 17
27107×7Tym razem a jest krótszym bokiem, więc odcinamy od b
3733×3Kwadraty są coraz mniejsze..
4433×3..i może być kilka tego samego rozmiaru
5131×1 
6121×1 
7111×1Oba 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.

  1. static int najmniejKwadratow(int a, int b) {
  2.   if (a == b)
  3.     return 1;
  4.   if (a < b)
  5.     zamień(ref a, ref b);
  6.   return 1 + najmniejKwadratow(a - b, b);
  7. }

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.

  1. static void Main(string[] args) {
  2.   Console.Write("Podaj rozmiar kwadratu\n a = ");
  3.   int a = Convert.ToInt32(Console.ReadLine());
  4.   Console.Write(" b = ");
  5.   int b = Convert.ToInt32(Console.ReadLine());
  6.   int wynik = najmniejKwadratow(a, b);
  7.   Console.WriteLine("Wyciętych kwadratów: {0}", wynik);
  8.   Console.ReadKey();
  9. }

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.