[o-o_i]

Jakby się komuś nudziło, to polecam zastanowić się nad zadaniem:
Jaś wchodzi po schodach. Jednym krokiem może przejść jeden albo dwa stopnie. Na ile różnych sposobów Jaś może wejść na schody o 10 stopniach? Na ile różnych sposobów Jaś może wejść na schody o n stopniach?
Nie bawimy się w rozróżnianie, którą nogą wstępuje itd.
Zadanie na chwilę myślenia, a odpowiedź naprawdę ciekawa :)
#matematykadyskretna #informatyka #algorytmy (?)

[M.....k]

@o-o_i: Masz do przebycia 10m. Pierwszy krok, który postawisz ma 1m, a każdy kolejny stawiasz o połowę krótszy. Po ilu krokach dotrzesz do mety? ( ͡° ͜ʖ ͡°)

[o-o_i]

@MrSzatanek: Za cholerę nie dotrę. Ale Jaś schody może pokonać ( ͡° ͜ʖ ͡°)

[nikitaskawraca]

@o-o_i: 10! I n!

[R.....N]

@o-o_i: Uwaga podaje odpowiedź

[deryt]

fibonaciego

@WektorWlasny: @o-o_i:
Rekurencją.
n schodów da się na f(n) sposobów

Liczymy f(n+1):
- jeśli pierwszy krok to 1, to następne n schodów można na f(n) sposobów
- jeśli pierwszy krok to 2, to następne na f(n-1) sposobów
Stąd f(n+1)=f(n)+f(n-1)
Dodatkowo f(1)=f(0)=1.
Stąd f jest fibonaciego.

[o-o_i]

@WektorWlasny: Opowiedz coś o tej funkcji tworzącej. Za nic w świecie bym nie wpadł na to, że można to rozwiązać inaczej niż na chłopski rozum.

[o-o_i]

@WektorWlasny: O ty nygusie xD

[o-o_i]

@WektorWlasny: Musiałem to kiedyś umieć, więc to dla mnie kwestia przypomnienia. Myślałem, że masz na ten temat coś do napisania od siebie ;)