توالی فیبوناچی

آخرین مطالب

امکانات وب

توالی فیبوناچی

اجرای دنباله فیبوناچی "سلام ، جهان!"برنامه نویسی هاسکل. این صفحه پیاده سازی های Haskell را از دنباله جمع می کند.

فهرست

1 تعریف ساده لوحانه
2 اجرای عملیات خطی
- 2. 1 با حالت
 - 2. 1. 1 دم بازگشتی
 - 2. 1. 2 monadic
 - 2. 2. 1 اجرای zipwith متعارف
 - 2. 2. 2 با مراجعه مستقیم مستقیم
 - 2. 2. 3 با اسکنل
 - 2. 2. 4 با onloldr
 - 2. 2. 5 با تکرار
 - 3. 1 با استفاده از ماتریس 2x2
 - 3. 2 فیبر سریع دیگر
 - 3. 3 سریعترین فیبر در غرب
 - 4. 1 با استفاده از فرمول بینه
 - 5. 1 شماره N-Step Fibonacci
 تعریف ساده لوحانه
 
 تعریف استاندارد را می توان مستقیماً بیان کرد:
```
فیبر 0 = 0 فیبر 1 = 1 فیبر n = فیبر (n-1) + فیبر (n-2) 
```
 این اجرای نیاز به افزودنیهای O (FIB N) دارد.
 
 اجرای عملیات خطی
 
 با حالت
 
 ترجمه هاسکل از پایتون آلگو
```
 A ، B = 0 ، 1 برای _ در Xrange (n): a ، b = b ، a + b retu a > 
```
 دم بازگشتی
 
 با استفاده از استدلال باتری برای عبور دولت
```
 فیبر n = go n (0,1) جایی که go !n (!a, !b) | n==0 = a | در غیر این صورت = go (n-1) (b, a+b) 
```
 وابسته به یکنواخت
```
وارد كردن control. monad. state فیبر n = تلنگر ارزیابی کردن (0,1) $ do فرم [0..(n-1)] $ _ > do (a,b) گرفتن قرار دادن (b,a+b) (a,b) گرفتن برگشت a 
```
 با استفاده از لیست نامحدود اعداد فیبوناچی
 
 می توان اولین شماره های فیبوناچی N را با اضافات O (n) محاسبه کرد. اگر فیبر لیست نامحدود اعداد فیبوناچی است ، می توان تعریف کرد
```
فیبر n = فیبر!!n 
```
 اجرای زیپ متعارف
```
فیبر = 0 : 1 : پستی (+) فیبر (دم فیبر) 
```
 با مراجعه مستقیم به خود
```
فیبر = 0 : 1 : بعد فیبر جایی که بعد (a : t@(b:_)) = (a+b) : بعد t 
```
 با اسکنل
```
فیبر = باحجاب کردن (+) 0 (1:فیبر) فیبر = 0 : باحجاب کردن (+) 1 فیبر 
```
 بازگشت را می توان با رفع جایگزین کرد:
```
فیبر = ثابت (باحجاب کردن (+) 0 . (1:)) فیبر = ثابت ((0:) . باحجاب کردن (+) 1) 
```
 رفع استفاده شده در اینجا باید از طریق اشتراک گذاری ، F = xs را اصلاح کند که در آن xs = f xs ، نه تکثیر کد ، رفع f = f (رفع f) ، برای جلوگیری از رفتار درجه دوم.
 
 با onloldr
```
فیبر = باز کردن ((a,b) > عادل (a,(b,a+b))) (0,1) 
```
 با تکرار
```
فیبر = نقشه مگس $ تکرار کردن ((a,b) > (b,a+b)) (0,1) 
```
 نسخه ای با استفاده از برخی از هویت ها
```
فیبر 0 = 0 فیبر 1 = 1 فیبر n | زوج n = f1 * (f1 + 2 * f2) | n `حالت` 4 == 1 = (2 * f1 + f2) * (2 * f1 - f2) + 2 | در غیر این صورت = (2 * f1 + f2) * (2 * f1 - f2) - 2 جایی که k = n `قسمت` 2 f1 = فیبر k f2 = فیبر (k-1) 
```
 $O(log^2 n)$
 
 به نظر می رسد این از تماس های FIB استفاده می کند.
 
 اجرای عملیات لگاریتمی
 
 با استفاده از ماتریس 2x2
 
 استدلال تکرار در بالا یک تحول خطی است ، بنابراین می توانیم آن را به عنوان ماتریس معرفی کنیم و قدرت n این ماتریس را با ضرب و موارد اضافی O (log n) محاسبه کنیم. به عنوان مثال ، با استفاده از اجرای ساده ماتریس در برنامه های افزودنی Prelud
```
فیبر n = سر (درخواست دادن (ماتریس [[0,1], [1,1]] ^ n) [0,1]) 
```
 این تکنیک برای هر عود خطی کار می کند.
 
 فیبر سریع دیگر
 
 (فرض می کند که دنباله با 1. شروع می شود)
```
فیبر = مگس . فیبر 2 - |بازگشت (فیبر n ، فیبر (n + 1)) فیبر 2 0 = (1, 1) فیبر 2 1 = (1, 2) فیبر 2 n | زوج n = (a*a + b*b, c*c - a*a) | در غیر این صورت = (c*c - a*a, b*b + c*c) جایی که (a,b) = فیبر 2 (n `قسمت` 2 - 1) c = a + b 
```
 سریعترین فیبر در غرب
 
 این توسط WLI کمک شده است (فرض می کند که دنباله با 1. شروع می شود)
```
وارد كردن داده ها فیبر 1 n = SND . تاشو فیبر (1, 0) . نقشه (انگشت پا . از مرکز) $ باز کردن دسته n جایی که باز کردن f x = مورد f x of هیچ چی > [] عادل (u, v) > باز کردن f v ++ [u] دسته 0 = هیچ چی دسته k = عادل (بی رحمانه (تلنگر (,)) (k `غوغا` 2)) فیبر (f, g) p | p = (f*(f+2*g), f^2 + g^2) | در غیر این صورت = (f^2+g^2, g*(2*f-g)) 
```
 نسخه حتی سریعتر ، بعداً توسط WLI در کانال IRC ارائه شده است.
```
وارد كردن داده ها وارد كردن data. bits فیبر :: در نظر گرفتن > عدد صحیح فیبر n = SND . foldl_ فیبر (1, 0) . قطره نه $ [تست تست n k | k اجازه دهید s = بیتس کردن n in [s-1,s-2..0]] جایی که فیبر (f, g) p | p = (f*(f+2*g), ss) | در غیر این صورت = (ss, g*(2*f-g)) جایی که ss = f*f+g*g foldl_ = تاشو -- ' 
```
 پیاده سازی های زمان ثابت
 
 اعداد فیبوناچی را می توان در زمان ثابت با استفاده از فرمول بینه محاسبه کرد. با این حال ، این فقط در محدوده شماره های نقطه شناور موجود در سیستم عامل شما کار می کند. اجرای فرمول Binet به گونه ای که نتایج دقیق را برای همه اعداد صحیح محاسبه می کند ، به طور کلی منجر به اجرای بسیار کارآمد در مقایسه با برنامه هایی نمی شود که در بالا از تعداد لگاریتمی عملیات استفاده می کنند (و در زمان خطی کار می کنند).
 
 فراتر از آن ، شما می توانید از شماره های نامحدود شناور با دقت نامحدود استفاده کنید ، اما نتیجه احتمالاً بهتر از اجرای زمان ورود به سیستم نخواهد بود.
 
 با استفاده از فرمول بینه
```
فیبر n = گرد $ پستان ** از مرکز n / SQ5 جایی که SQ5 = SQRT 5 :: دو برابر پستان = (1 + SQ5) / 2 
```
 تعمیم اعداد فیبوناچی
 
 تعداد توالی فیبوناچی سنتی با جمع بندی دو عدد قبلی آن تشکیل می شود ، با مقادیر شروع 0 و 1. تغییرات دنباله را می توان با استفاده از مقادیر شروع مختلف و جمع بندی تعداد متفاوتی از پیشینیان بدست آورد.
 
 اعداد n-step fibonacci
 
 $F^توالی اعداد n-step fibonacci با جمع بندی n پیشینیان ، با استفاده از صفر ( n-1) و یک 1 به عنوان مقادیر شروع: _k: = شروع 0 و mbox 0 leq k تشکیل می شود.<n-1 \ 1 & mboxk = n-1 \ sumlimits_^ F^_i & mbox \ end$
 
 توجه داشته باشید که جمع بندی در تعریف فعلی دارای پیچیدگی زمانی O (n) است ، با فرض اینکه ما تعداد محاسبه شده قبلاً از دنباله را به یاد می آوریم. ما می توانیم بهتر از. مشاهده کنید که در دنباله Tribonacci زیر ، شماره 81 را با جمع بندی 13 ، 24 و 44 محاسبه می کنیم:
 
 $F^<(3)> = 0,0,1,1,2,4,7,underbrace,81,149, ldots$
 
 شماره 149 به روشی مشابه محاسبه می شود ، اما می تواند به شرح زیر محاسبه شود:
 
 $149 = 24 + 44 + 81 = (13 + 24 + 44) + 81 - 13 = 81 + 81 - 13 = 2cdot 81 - 13$
 
 و از این رو ، تعریف معادل دنباله اعداد n-step fibonacci:
 
 $F^_k: = شروع 0 & mbox 0 leq k<n-1 \ 1 & mboxk = n-1 \ 1 & mbox k = n \ F^_k := 2F^_-F^_ & mbox \ end$
 
 (به مورد اضافی مورد نیاز توجه کنید)
 
 تبدیل این کار به طور مستقیم به هاکل به ما می دهد:
```
nfibs n = تکثیر (n-1) 0 ++ 1 : 1 : پستی (b a > 2*b-a) (افت n (nfibs n)) (nfibs n) 
```
 با این حال ، این نسخه کند است زیرا محاسبه NFIBS N به اشتراک گذاشته نمی شود. نامگذاری نتیجه با استفاده از یک اتصال دهنده و ساخت Lambda Pointfree منجر به:
```
nfibs n = اجازه دهید r = تکثیر (n-1) 0 ++ 1 : 1 : پستی ((-).(2*)) (افت n r) r in r 
```
 همچنین ببینید
 - موازی ساده لوحانه ، نسخه چندگانه
 - مقدمات فیبوناچی به طور موازی
 - بحث در کافه هاسکل
 - برخی از راه حل های خوب دیگر
 - در پروژه اویلر ، برخی از مشکلات شامل شماره های فیبوناچی است. برخی از راه حل ها در هاکل وجود دارد (هشدار اسپویلر: تا زمانی که مشکلات خود را به تنهایی حل نکرده اید ، به راه حل های مربوط به مشکلات اویلر نگاه نکنید.):
 - مشکل 2
 - مشکل 25
 - مشکل 104
 - مشکل 137