Algorytm zachłanny
Wyznaczamy kolejne ilości klocków znajdujących się w opakowaniach A, B, C z których można zbudować kwadraty:
A:
A3(3x3)=1 (2x2) + 2 (2x1) +1 (1x1) = 4
A4(4x4)=4 (2x2)= 4
A9(9x9)=16 (2x2) + 8 (2x1) + 1 (1x1) = 25
A10(10x10)=25 (2x2)
A11(11x11)=25 (2x2) + 10 (2x1) + 1 (1x1) = 36
A12(12x12)=36 (2x2)
A13(13x13)=36 (2x2) + 12 (2x1) + 1 (1x1) = 49
A14(14x14)=49 (2x2)
A15(15x15)=49 (2x2) + 14 (2x1) + 1 (1x1) = 64
A16(16x16)=64 (2x2)
A17(17x17)=64 (2x2) + 16 (2x1) + 1 (1x1) = 81
A18(18x18)=81 (2x2)
A19(19x19)=81 (2x2) + 18 (2x1) + 1 (1x1) = 100
A20(20x20)=100 (2x2)
B:
B3(3x3)=1 (3x3)
B4(4x4)=1 (3x3) + 2 (3x1) + 1 (1x1)= 4
B8(8x8)=4 (3x3) + 8 (3x1) + 4 (1x1) = 16
B9(9x9)=16 (3x3) = 9
B10(10x10)=9 (3x3) + 6 (3x1) + 1 (1x1) = 16
B11(11x11)=9 (3x3) + 12 (3x1) + 4 (1x1) = 25
B12(12x12)=16 (3x3)
B13(13x13)=16 (3x3) + 8 (3x1) + 1 (1x1) = 25
B14(14x14)=16 (3x3) + 16 (3x1) + 4 (1x1) = 36
B15(15x15)=25 (3x3)
B16(16x16)=25 (3x3) + 10 (3x1) + 1 (1x1) = 36
B17(17x17)=25 (3x3) + 20 (3x1) + 4 (1x1) = 49
B18(18x18)=36 (3x3)
B19(19x19)=36 (3x3) + 12 (3x1) + 1 (1x1) = 49
B20(20x20)=36 (3x3) + 24 (3x1) + 4 (1x1) = 64
C:
C3(3x3)=9 (1x1) = 9
C4(4x4)=1 (4x4) = 1
C8(8x8)=4 (4x4) = 4
C9(9x9)=4 (4x4) + 4 (3x1) + 1 (1x1) = 9
C10(10x10)=4 (4x4) + 8 (3x1) + 4 (1x1) = 16
C11(11x11)=4 (4x4) + 12 (3x1) + 9 (1x1) = 25
C12(12x12)=9 (4x4)
C13(13x13)=9 (4x4) + 6 (3x1) + 1 (1x1) = 16
C14(14x14)=9 (4x4) + 12 (3x1) + 4 (1x1) = 25
C15(15x15)=9 (4x4) + 18 (3x1) + 9 (1x1) = 36
C16(16x16)=16 (4x4)
C17(17x17)=16 (4x4) + 8 (3x1) + 1 (1x1) = 25
C18(18x18)=16 (4x4) + 16 (3x1) + 4 (1x1) = 36
C19(19x19)=16 (4x4) + 24 (3x1) + 9 (1x1) = 49
C20(20x20)=25 (4x4)
Co najważniejsze, algorytm ten jest na tyle zachłanny, że w wynikach ilości klocków z których można ułożyć kwadraty bazuje na liczbach kwadratowych 1, 4, 9, 25, 36, 49, ...
14 | 49 | 36 | 25 |
16 | 64 | 36 | 16 |
17 | 81 | 49 | 25 |
18 | 81 | 36 | 36 |
19 | 100 | 49 | 49 |
20 | 100 | 64 | 25 |
Post nr 130
Brak komentarzy:
Prześlij komentarz