Tweety na temat @MinorMatematyka

Łączna liczba wyświetleń

Nowość! Snapchat: matematycznyswi

Snapchat: matematycznyswi

Szukaj na tym blogu lub wpisz post nr 1-516

czwartek, 2 maja 2013

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    
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, ...

 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    
Autor: o
Etykiety: ,

Liczba komentarzy:
Reakcje: 
Lokalizacja: Ślesin, Polska

Brak komentarzy:

Prześlij komentarz

Subskrybuj: Komentarze do posta (Atom)

Regulamin bloga

Czytelniku, miło kiedy komentujesz posty. Chętnie zapoznam się także z innym Twoim punktem widzenia w podanym rozwiązaniu zadania. Jednak, aby ten blog stanowił dla Czytelników pewną wartość, nie mogę pozwolić, żeby każdy mógł tu pisać co tylko chce.

Blog wymaga wiele czasu pracy, godzin pracy, których nie widać i jako jego autor chcę się na nim dobrze czuć. Niniejszy Regulamin określa zasady korzystania z bloga www.matematyczny-swiat.pl. Korzystanie z bloga oznacza akceptację Regulaminu.



$1

Sprawy organizacyjne

1. Jeżeli uważasz, że w jakimś temacie czujesz się bardziej kompetentny, to napisz jak to wygląda z Twojego punktu widzenia.

2. 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.

3. Ten blog to miejsce, w którym publikuję wskazówki, które mogą pomóc Czytelnikom zrozumieć i nauczyć się rozwiązywać zadania matematyczne.

4. Dozwolone jest kopiowanie zdjęć z bloga na portale społecznościowe lub inne blogi z bezwzględnym podaniem aktywnego linka do bloga. Niedozwolone jest kopiowanie zdjęć i treści bez podania aktywnego linka.

5. Pamiętaj, żeby w ramach kopiowania zdjęć z bloga korzystać z przycisków udostępniania dostępnych w postach na blogu.

6. Zdjęcia w postach na blogu są mojego autorstwa i własnością intelektualną, a zdjęcia kopiowane na mój blog są zawsze z podaniem źródła.

7. Blog posiada jednego autora. Autorem bloga jest Robert Karolewski.

8. Zabrania się, przerabiania, przystosowywania, usuwania logotypu lub dokonywania jakichkolwiek innych zmian w zdjęciach na potrzeby własnej publikacji i przypisywanie im autorstwa. Dopuszczalne jest na własne potrzeby bez ich publikacji.

9. Wszystkie zdjęcia na blogu mojego autorstwa zawierają logotyp Minor Matematyczny Świat.
10. Przykłady w zadaniach prezentowane na blogu są przygotowane przeze mnie i moją własnością intelektualną. Na blogu również dostępne są przykładowe zadania z jakimi można spotkać się na różnym poziomie nauczania.
11. Rozwiązania wszystkich zadań z arkuszy maturalnych posiadają logotyp wobec tego, że są to moje przykładowe odpowiedzi.

12. Niniejszy regulamin obowiązuje również na wszystkich moich portalach społecznościowych.

13. Korzystanie z bloga w całości jest nieodpłatne i dostępne dla wszystkich Czytelników.


$2

Komentarze

14. Wszystkie komentarze na blogu są publikowane automatycznie i moderowane przez autora bloga.

a) Jeśli komentarze są obraźliwe zarówno w stosunku do mnie jak i do innych Czytelników, to zostaną usunięte lub ukryte.

b) Jeśli komentarze są niezwiązane z tematem wpisu, to zostaną usunięte lub ukryte.

c). Jeśli komentarze są spamem. Za spam uznaję linki do innych stron, podpisywanie się adresem www, dodawanie adresu strony pod komentarzem, reklama, to zostaną usunięte lub ukryte.


Osoby, które nie będą stosowały się do powyższych zasad $2 mają gwarancję, że ich komentarz pojawi się chwilę na blogu. W skrajnych przypadkach Twoje konto zostanie zablokowane.