Ile kwadratów na obrazku?

Zadanie

Najpierw narysowano kwadrat, a następnie podzielono na 16 mniejszych. Ile teraz można wskazać kwadratów na poniższym obrazku? Co jeśli zostałby podzielony na większą liczbę równych kwadracików?

Odpowiedź

Na rysunku znajduje się dokładnie 30 kwadratów. (Wskazówka: 16 elementów 1×1, 9 elementów 2×2, 4 elementy 3×3 oraz 1 element 4×4)

Rozważanie dla dowolnego przypadku

Niezależnie od ilości kwadratów n na jaką został podzielony obrazek wiadomo, że zawsze jest n małych elementów 1x1 oraz jeden duży złożony ze wszystkich małych. W celu wyznaczenia ile będzie kwadratów 2×2 należy zauważyć, że nie można takiego kwadratu wybrać w ostatniej kolumnie oraz wierszu. Oznacza to, że jeśli kwadrat został podzielony na a×a to jest dokładnie (a - 1)·(a - 1) elementów 2×2. Analizując dla większych elementów można zauważyć, że elementów k×k jest (a - k + 1)².

Przeanalizujmy przedstawiony sposób rozumowania w tabelce:

Element	1×1	2×2	3×3	..	(a - 1)×(a - 1)	a×a
Liczba	a2	(a - 1)2	(a - 2)2	..	22	1

Łączna liczba kwadratów na rysunku złożonego z a² wynosi tyle co suma wartości w drugim wierszu: a² + (a - 1)² + (a - 2)² + .. + 2² + 1. Tu z kolei na podstawie wyznaczonego wzoru możliwe jest wyprowadzenie wzoru dla dowolnego przypadku: a(2a² + 3a + 1)/6.

Przykład

Rozpatrzmy przykład kiedy duży kwadrat podzielona na 25 małych kwadracików.

Powyższemu rysunkowi odpowiada następująca tabelka:

Element	1×1	2×2	3×3	4×4	5×5
Liczba	5·5 = 25	4·4 = 16	3·3 = 9	2·2 = 4	1·1 = 1

Z tego wynika, że dla kwadratu o rozmiarze 5×5 można znaleźć dokładnie 55 różnych kwadratów.

Prostokąt, nie kwadrat

Zadanie

Napisz program, który dla podanej siatki o rozmiarze a×b wyznaczy ile jest różnych kwadratów do zaznaczenia. Podczas rozwiązywania zadań nie należy używać żadnego wzoru.

Przykład

W podanym przykładzie można zaznaczyć 20 różnych kwadratów. (Wskazówka: 12 elementów 1×1, 6 elementów 2×2 oraz 2 elementy 3×3)

Rozwiązanie

Zauważmy, że jeśli a < b to w podanym prostokącie nie będzie można znaleźć kwadratu o rozmiarze większym niż a×a. Rozumowanie dotyczące ilości elementów o rozmiarze k×k jest bardzo podobne, ale należy pamiętać, że tym razem będzie ich (a - k + 1)(b - k + 1) pod warunkiem, że taki kwadrat można wpisać. Ponownie rozwiązanie można wygodnie przedstawić w tabelce:

Implementacja

Funkcja ileKwadratow() wylicza dla podanej wielkości siatki a×b ile jest możliwych kwadratów do zaznaczenia. Pomijane są przypadki, gdy kwadrat nie mieści się na siatce.

1. int ileKwadratow(int a, int b) {
2.   int min = a < b ? a : b;
3.   int ile = 0;
4.   for (int i = 0; i < min; i++)
5.     ile += (a - i)*(b - i);
6.   return ile;
7. }

(2.) Na początku należy wyznaczyć maksymalny rozmiar kwadratu, który można wpisać w podany rozmiar siatki. Następnie (3.) inicjalizujemy zmienną, a następnie (4. - 5.) sumujemy wartości dla kolejnych wielkości kwadratów. Na koniec (6.) zwracamy wyliczoną sumę.

Testowanie funkcji

W celu przeprowadzenia obliczeń i przetestowania powyższego kodu można skorzystać z poniższego fragmentu kodu:

1. int main () {
2.   int a, b;
3.   cout << "Podaj rozmiar siatki a x b\n a = ";
4.   cin >> a;
5.   cout << " b = ";
6.   cin >> b;
7.   int ile = ileKwadratow(a, b);
8.   cout << "Na siatce jest " << ile << " kwadratow";
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja