روش تعیین تعداد عمل جمع برای بدست آرودن عدد n ام در سری فیبوناچی؟؟؟؟

[sobhan1990]

سلام
روز همگی بخیر

چطور میشه تعداد عمل جمع برای بدست آوردن عدد n ام در سری فیبو ناچی رو بدست بیاریم؟
یعنی برای بدست آوردن مثلا عدد 100 اُم سری فیبوناچی به چند عمل جمع نیاز داریم؟

البته من به اثباتش بیشتر از جوابش نیاز دارم.

ممنون میشم اگر راهنمایی کنید.

[mortezamsp]

شب شمام بخیر.
بستگی به روشت داره . روش های مختلف با پیچیدگی های مختلف از log n هست تا نمایی .

مثلا اگه از روش آرایه داینامیکش بخوای ، تعداد عمل جمع میشه n-1
ولی برای روش بازگشتی عادی f(n)=f(n-1)+f(n-1) باید از معادلات همگن استفاده کرد . من این چیزا یادم رفته ولی میدونم تعداد عمل جمع تو این روش اینطوریه :

p(n) = 1 + p(n-1) + p(n-2)



0	0

1	0

2	1

3	2

4	4

5	7

6	12

7	20

8	33

البته این یه معادله بازگشتیه و برای تبدیلش به غیربازگشتی __یه چیزایی داشتم مثل معادلات لژاندر یا حل بکمک سری که من یادم نیست __ باید از روش های معادلات برید .

[mortezamsp]

http://cplusplus.blogsky.com/1388/08/27/post-46/

[nima898]

در هر مرحله يك بار عمل جمع انجام ميشه ( غير از مرحله اول)
ميشه 99 بار براي n=100