Ciąg Fibonacciego.

Kvothe · Post autor: **Kvothe** » 23 lis 2013, o 16:37

Witam, mam problem ze zrozumieniem.

Zad. Na ile sposobów można planszę 2xn pociąć na prostokąty o wymiarach 2x1. Wiem dlaczego odpowiedź to n-1. Nie rozumiem tylko, dlaczego napisano, że w tym zadaniu zastosowanie ma ciąg Fibonacciego.

matmatmm · Post autor: **matmatmm** » 23 lis 2013, o 17:13

Prawidłowa odpowiedź to nie \(\displaystyle{ n-1}\). Prawidłową odpowiedzią jest ciąg określony rekurencyjnie podobny do ciągu Fibonacciego.

Kvothe · Post autor: **Kvothe** » 23 lis 2013, o 17:25

W jaki sposób określić ten ciąg?

matmatmm · Post autor: **matmatmm** » 23 lis 2013, o 17:40

Wskazówka: Jeżeli wiemy na ile sposobów można rozciąć planszę \(\displaystyle{ 2\times n}\) oraz planszę \(\displaystyle{ 2\times (n+1)}\), to na ile sposobów można rozciąć planszę \(\displaystyle{ 2\times (n+2)}\)?

dalej idąca wskazówka:

Kvothe · Post autor: **Kvothe** » 23 lis 2013, o 18:15

Nie rozumiem, jeżeli mamy np. planszę o wymiarach 2x4 to można otrzymać kawałki 2x1, poprzez 3 cięcia. Nie ma innej możliwości. Dalej jeżeli mamy planszę 2x5, to te kawałki można otrzymać poprzez 4 cięcia. Dalej planszę 2x6 załatwia 5 cięć. Inaczej nie otrzymamy wymiaru 2x1. Nie widzę tej zależności.

matmatmm · Post autor: **matmatmm** » 23 lis 2013, o 18:36

Pytanie jest na ile sposobów można rozciąć. Na przykład planszę \(\displaystyle{ 2\times 4}\) można rozciąć na 5 sposobów, a planszę \(\displaystyle{ 2\times 5}\) na 8 sposobów.

Kvothe · Post autor: **Kvothe** » 23 lis 2013, o 18:40

Ogólnie rozciąć tak, ale w poleceniu jest: " na prostokąty o wymiarach 2x1".

matmatmm · Post autor: **matmatmm** » 23 lis 2013, o 18:50

Mam na myśli rozcinanie właśnie na takie prostokąty.

Kvothe · Post autor: **Kvothe** » 23 lis 2013, o 19:39

Hm, nie widzę w jaki sposób to możliwe, oto mój sposób myślenia:

Pierwszy przypadek:

Drugi przypadek:

Prowizoryczne rysunki w paincie, ale oddają to o co mi chodzi.

matmatmm · Post autor: **matmatmm** » 23 lis 2013, o 22:13

Jest więcej możliwości. Na przykład takie dwie:

Kod: Zaznacz cały

http://wstaw.org/w/2m1X/

Kvothe · Post autor: **Kvothe** » 23 lis 2013, o 23:32

Zatem w zadaniu chodzi o to na ile sposobów można np. planszę \(\displaystyle{ 2\times 4}\) pociąć trzema cięciami? Myślałem że ogólnie chodzi o to ile cięć trzeba wykonać. W takim przypadku rzeczywiście ciąg Fibonacciego jest tu użyteczny:

matmatmm pisze:Wskazówka: Jeżeli wiemy na ile sposobów można rozciąć planszę \(\displaystyle{ 2\times n}\) oraz planszę \(\displaystyle{ 2\times (n+1)}\), to na ile sposobów można rozciąć planszę \(\displaystyle{ 2\times (n+2)}\)?

Ilość sposobów na jakie można pociąć \(\displaystyle{ 2\times (n+2)}\) to suma ilości sposobów dwóch poprzednich wymiarów (jak w ciągu Fibonacciego).

Dzięki, już rozumiem o co chodzi.