19 (1106256), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Дерево Фибоначчи с h = 6.131885113274610916151220171914119Деревья ФибоначчиТеорема 1. Число вершин в дереве Фибоначчи Fh высоты hравно m(h) = fh+2 – 1.Доказательство (по индукции).h = 0:m(0) = f2 – 1 = 0m(1) = f3 – 1 = 1.Шаг: по определению m(h) = m(h – 1) + m(h – 2) + 1.Имеем m(h) = (fh+1 – 1) + (fh – 1) + 1 = fh+2 – 1,так как fh + fh + 1 = f h + 220Деревья ФибоначчиТеорема 2. Пусть C1 и C2 таковы, что уравнениеr2 – C1r – C2 = 0имеет два различных корня r1 и r2 , r1 ≠ r2.Тогда дляan = α1r1n + α2r2nвыполняется соотношениеan = C1an-1 + C2an-2 .(*)Доказательство.

r1 и r2 – корни уравнения (*),тоr12 = C1r1 + C2r22 = C1r2 + C2.Имеем:C1an-1 + C2an-2 = C1(α1r1n-1 + α2r2n-1) + C2(α1r1n-2 + α2r2n-2) == α1r1n-2 (C1r1 + C2) + α2r2n-2 (C1r2 + C2) == α1r1n-2 r12 + α2r2n-2 r22 = α1r1n + α2r2n = an(**)Теорема доказана.21Деревья ФибоначчиТеорема 3. Пусть C1 и C2 таковы, что уравнениеr2 – C1r – C2 = 0имеет два корня r1 и r2 , r1 ≠ r2.(*)Тогдаиз an = C1an-1 + C2an-2 и начальных условий а0 и а1следует an =α1r1n + α2r2nдля n = 1, 2, ...Доказательство.

Нужно не только повторить в обратномпорядке вывод (**), но и подобрать такие α1 и α2, чтобыа0 = α1 + α2, а1 = α1r1 + α2r2(***)Рассматривая (***) как систему линейных уравненийотносительно α1 и α2, получим:α1 =a1 − a0 ⋅ r2,r1 − r2Теорема доказана.− a1 + a0 ⋅ r1α2 =r1 − r222Деревья ФибоначчиПрименим доказанные теоремы к числам Фибоначчи:fn = fn-1 + fn-2.Уравнение r2 – r – 1 = 0 имеет корни1− 51+ 5r2 =r1 =22Следовательно, согласно теореме 3nn1− 5 1+ 5  ,αf n = α1 ⋅ r + α 2 ⋅ r = α1 ⋅ +⋅2 2  2 f 0 = α1 + α 2 = 0,n1n21− 5 1+ 5  =1 + α2 ⋅ f1 = α1 ⋅ 2211,α 2 = −α1 =5523Деревья ФибоначчиОткудаn1 1+ 5 1 1− 5  −fn =⋅ ⋅ 5  2 5  2 nСогласно теореме 1m( h ) = f h + 21 1+ 5 −1 =5  2 1 1− 5 5  2 h+ 21 1− 5 −5  2 h+ 2−1h+2<11 1+ 5 m( h ) + 1 >5  2 h+ 224Деревья Фибоначчи1+ 5Обозначение γ =21 h+2m( h) + 1 > γ5(****)Логарифмируя обе части (****) , получаемh+2<откудаlog 2 (m + 1) log 2 5+log 2 γlog 2 γh < 1,44 ⋅ log 2 (m + 1) − 0,32Таким образом, мы доказали, что для деревьев Фибоначчи с числомвершин m количество сравнений в худшем случае не превышает1,44 ⋅ log 2 (m + 1) − 0,3225.

Характеристики

Список файлов лекций