Tweety na temat @MinorMatematyka

Pomoce dla klasy

Szukaj na tym blogu lub wpisz post nr 1-535

Algorytm zachłanny

Algorytm zachłanny


Algorytm zachłanny wyznacza rozwiązanie w każdym kroku dokonując zachłannego tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego przy tym nie zachowując sensu działań poprzednich,  dokonując decyzji lokalnie optymalnej, wyboru najlepszego.

Firma produkuje klocki w trzech rozmiarach dostępnych w opakowaniach A, B, C. W każdym opakowaniu znajdują się dwa klocki w kształcie kwadratu 1x1, kxk (A: k=2, B: k=3, C: k=4) i jeden prostokąt kx1. Firma otrzymała zamówienie na produkcję klocków tak, żeby można było z nich ułożyć kwadraty o wymiarach do 13x13. Obliczyć z ilu klocków będzie się składał kwadrat A13, B13, C13 tzn. ile klocków należy włożyć do opakowania A, B, C i jakie?

Wyznaczamy kolejne ilości klocków znajdujących się w opakowaniach A, B, C z których można zbudować kwadraty:
A:

Algorytm zachłanny



A1(1x1)=1 (1x1) = 1                                               
A2(2x2)=1 (2x2) = 1                                              
A3(3x3)=1 (2x2) + 2 (2x1) +1 (1x1) = 4                         
A4(4x4)=4 (2x2)= 4
A5(5x5)=4 (2x2) + 4 (2x1) + 4 (1x1) = 9           
A6(6x6)=9 (2x2)9
A7(7x7)=9 (2x2) + 6 (2x1) + 1 (1x1) = 16
A8(8x8)=16 (2x2) 
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:

Algorytm zachłanny




B1(1x1)=1 (1x1) = 1                                               
B2(2x2)=4 (1x1) = 4                                              
B3(3x3)=1 (3x3)                        
B4(4x4)=1 (3x3) + 2 (3x1) + 1 (1x1)= 4
B5(5x5)=1 (3x3) + 4 (3x1) + 4 (1x1) = 9           
B6(6x6)=4 (3x3)4
B7(7x7)=4 (3x3) + 4 (3x1) + 1 (1x1) = 9  
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:

Algorytm zachłanny



C1(1x1)=1 (1x1) = 1                                               
C2(2x2)=4 (1x1) = 4                                              
C3(3x3)=9 (1x1) = 9                         
C4(4x4)=1 (4x4) =  1
C5(5x5)=1 (4x4) + 2 (4x1) + 1 (1x1) = 4           
C6(6x6)=1 (4x4) + 4 (3x1) + 4 (1x1) = 9
C7(7x7)=1 (4x4) + 6 (3x1) + 9 (1x1) = 16    
C
8(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, ...

 n |  A |  B |  C |

 1 |  1 |  1 |  1 |
 2 |  1 |  4 |  4 |
 3 |  4 |  1 |  9 |
 4 |  4 |  4 |  1 |
 5 |  9 |  9 |  4 |
 6 |  9 |  4 |  9 |
 7 | 16 |  9 | 16 |
 8 | 16 | 16 |  4 |
 9 | 25 |  9 |  9 |
10 | 25 | 16 | 16 |
11 | 36 | 25 | 25 |
12 | 36 | 16 |  9 |
13 | 49 | 25 | 16 |
14 | 49 | 36 | 25 |
15 | 64 | 25 | 36 |
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

WESPRZYJ BLOGA ZRZUTKĄ


Czytelniku, miło kiedy komentujesz posty. Chętnie zapoznam się z Twoim sposobem  rozwiązania zadania. Aby ten blog stanowił dla Czytelników pewną wartość, nie mogę pozwolić, żeby każdy mógł tu pisać co tylko chce. Korzystanie z bloga oznacza akceptację Regulaminu.
Regulamin bloga
1. Myśl zanim coś napiszesz – zanim zechcesz skrytykować moje sposoby rozwiązania zadań zastanów się jak możesz z tego skorzystać. Jeszcze raz – nie twierdzę, że wszystko co napiszę będzie dla Ciebie pomocne. Niemniej niektóre wskazówki po Twojej modyfikacji mogą dobrze Ci służyć. Myśl samodzielnie.
2. Publikuję wskazówki, które mogą pomóc Ci zrozumieć jak można rozwiązywać zadania matematyczne.
3. W ramach kopiowania zdjęć z bloga skorzystaj z przycisków udostępniania dostępnych w postach na blogu.
4. Wszystkie komentarze na blogu są moderowane przez autora bloga.
5. Korzystanie z bloga w całości jest nieodpłatne.