Zadanie dla znudzonych. Trivial: Rachunek lambda Korzystając z funkcji Y = (λf. (λx. f (x x)) (λx. f (x x))) udowodnić, że (Y F) = (F (Y F)) oraz przekształcić funkcję rekurencyjną SILNIA = (λn. IF (= n 0) 1 (* n (SILNIA (− n 1)))) do postaci anonimowej, w której nie odwołujemy się do nazwy "SILNIA".

asdf: ostatnio probowalem rozwiązać równanie rekurencyjne, gdzie z funkcji rekurencyjnej f_n = f_n−1 + f_n−2 mozna bylo wyzanczyc nie odwołując się rekurencyjnie, podeslac? nawet mi wyszlo..

Trivial: Możesz

asdf: na mailu masz, co do tego fibonacciego to mam gdzies w notatkach, wieczorem kolo 20 Ci podesle bo szukalem, a nie moge znaleźć − wieczorem w akademiku poszukam, napisze jak znajde

asdf: troche teorii: a_n + c₁*a_n−1 + c₂*a_n−2 + ... c_k*a_n−k = 0 zaklada się, że rozwiązaniem jest a_i = rⁱ, gdzie r = const. Np. a_n = rⁿ, wtedy: rⁿ + c*rⁿ⁻¹ + ... + c_k*r^n−k = 0, a z tego wynika: r^n−k(r^k + c₁r^k−1 + c₂r^k−2 + ... + c_k) = 0 −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− przykład: F_n = F_n−1 + F_n−2 F₀ = 0, F₁ = 1; zgadujemy, że F_n = rⁿ rⁿ = rⁿ⁻¹ + rⁿ⁻² rⁿ⁻²(r² − r − 1) = 0 √Δ = √5

	1 − √5
r1 =
	2

	1 + √5
r2 =
	2

otrzymujemy: F_n = α*r₁ⁿ + β*r₂ⁿ (zamiast pisać c₁ itd..)

	1−√5		1+√5
Fn = α(		)n + β(		)n
	2		2

F₀ = α + β, F₀ = 0 ⇒ α+β = 0

	1−√5		1+√5
F1 = α(		)n + β(		)n,
	2		2

	1−√5		1+√5
F1 = 1 ⇒ α(		)n + β(		)n = 1
	2		2

z pierwszego równania: α = −β podstawienie do drugiego:

	1−√5		1+√5
−β(		) + β(		) = 1
	2		2

	β		β√5		β		β√5
−		+		+		+		= 1
	2		2		2		2

2β√5
	= 1
2

	√5
β = −
	5

	√5
α =
	5

z tego wynika równanie:

	√5		1−√5		√5		1+√5
Fn =		(		)n −		(		)n
	5		2		5		2

PATIIIIII: CZY MÓGŁBY MI KTOŚ POMÓŻ POMOCY https://matematykaszkolna.pl/forum/203251.html

Trivial: asdf, wszystko pięknie. Policz mi proszę z tego wzoru dziesiąty wyraz ciągu.

asdf: od tego jest już komputer http://www.wolframalpha.com/input/?i=sqrt%285%29%2F5+*+%28+++%281%2Bsqrt%285%29%29%2F2++%29%5E10+-+sqrt%285%29%2F5*%28++++%281-sqrt%285%29+%29%2F2+++%29%5E10 tak chyba postac powinna wyglądać a tu masz dla 100: http://www.wolframalpha.com/input/?i=sqrt%285%29%2F5+*+%28+++%281%2Bsqrt%285%29%29%2F2++%29%5E100+-+sqrt%285%29%2F5*%28++++%281-sqrt%285%29+%29%2F2+++%29%5E100 a ktora forma obliczen zabiera więcej pamięci i czasu? rekurencyjna czy ta?

asdf: dla n = 1000 wolfram się wysypuje

asdf: nie wierzylem, puki nie sprawdzilem: http://www.wolframalpha.com/input/?i=sqrt%285%29%2F5+*+%28+++%281%2Bsqrt%285%29%29%2F2++%29%5En+-+sqrt%285%29%2F5*%28++++%281-sqrt%285%29+%29%2F2+++%29%5En+and+n+%3D+8 czyli działa f(n) = 21, n = 8

Trivial: Komputer szybciej (a przynajmniej dokładniej) policzy z postaci rekurencyjnej (z pewnymi optymalizacjami). Postać rekurencyjną zapisujemy macierzowo:

fn+1 fn		fn + fn−1 fn		1 1 1 0	fn fn−1
	=		=

Czyli

fn+1 fn		1 1 1 0		f1 f0		1 1 1 0		1 0
	=		n		=		n

Trivial: Ostatnia postać ma złożoność Θ(lgn). Postać rekurencyjna: Θ(n) Postać "dokładna": Θ(lgn). ← ale bardzo słabe stałe ukryte (lub niedokładny wynik) Z kolei jeśli chcesz liczyć wszystkie wyrazy ciągu to postać rekurencyjna jest najszybsza (po przepisaniu na pętle for, czy co tam chcesz).

asdf: to po co to się wyprowadza?

Trivial: A czemu nie? Wiem że liczenie prosto z definicji rekurencyjnej (bez spamiętywania) ma

	1+√5
złożoność Θ(φn), gdzie φ =		. Taki tam zbieg okoliczności. W ogóle to
	2

masz błąd w tym swoim wzorku (odwrotnie minusy)

asdf: wiem − na kodzie w wolframie poprawiłem, a zapomnialem napisac tutaj