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

3662 روز از زمان راه اندازی

هفته اول: دنباله فیبوناچی و نسبت طلایی

هفته گذشته، چند دستور ساده را در پایتون معرفی کردیم و از آنها برای محاسبه چند عدد کامل اول، تنها با استفاده از چند خط کد استفاده کردیم.

در این آموزش ما به یکی دیگر از مسائل ریاضی ساده ای که می توان با پایتون کاوش کرد نگاه خواهیم کرد: دنباله فیبوناچی. نسبت طلایی ظاهری غیرمنتظره خواهد داشت!

استفاده از فایل های پایتون

Last time, we wrote our Python commands directly into the shell, by typing at the prompt (>>>). این برای دستورات ساده خوب است، اما به سرعت دست و پا گیر می شود. مخصوصاً اگر مثل من هنگام وارد کردن کد اشتباه کنید. همچنین، وقتی پایتون را ترک می کنید، ممکن است خطوط ارزشمند کد شما فراموش شود! از این پس برنامه های خود را در فایل های پایتون نگه می داریم.

In the menu of IDLE, go to File > New Window. In the new window, type print "Hello everyone!" , and now save the file, by going to File >صرفه جویی. من همه فایل هایم را در پوشه کد/Pi3/، در فهرست اصلی خود ذخیره می کنم. ممکن است بخواهید یک دایرکتوری جدید ایجاد کنید. یک نام فایل مناسب را انتخاب کنید، به عنوان مثال، hello. py. توجه داشته باشید که تمام فایل های پایتون با پسوند . py خاتمه می یابد.

You can run your program (i.e. execute the commands in the python file, in the order in which they appear) by pressing F5 in IDLE, or selecting the menu option Run >ماژول را اجرا کنید. اکنون باید پیام تبریک خود را در پوسته پایتون مشاهده کنید.

همچنین می توانید برنامه خود را مستقیماً از خط فرمان با تایپ python hello. py اجرا کنید

از این به بعد پیشنهاد می کنم دستورات پایتون خود را (Ctrl-S) در فایل ها ذخیره کنید و با F5 در IDLE اجرا کنید. در پایان این صفحه، چند نمونه فایل پایتون را پیوست کرده ام که ممکن است بخواهید آنها را بررسی کنید.

دنباله فیبوناچی

دنباله اعداد فیبوناچی است

0، 1، 1، 2، 3، 5، 8، 13، 21، 34، 55، 89، و غیره.

می توانید ببینید که مقدار بعدی در لیست با جمع کردن دو مقدار قبلی با هم پیدا می شود. به عنوان مثال، 13 = 8 + 5، 21 = 13 + 8، 34 = 21 + 13، و غیره. از نظر ریاضی، می توانیم دنباله را با یک رابطه عود تعریف کنیم:

F(n+1) = F(n) + F(n-1)

و دو مقدار اولیه، F(0) = 0 و F(1) = 1.

لئوناردو اهل پیزا، معروف به فیبوناچی، این دنباله را در کتاب Liber Abaci خود در سال 1202 به ریاضیات اروپایی معرفی کرد. تصور می شود که حتی پیش از این در ریاضیات هندی بوجود آمده باشد.

بیایید به یک کد ساده - از آموزش رسمی پایتون - نگاه کنیم که دنباله فیبوناچی را تولید می کند.

# سری فیبوناچی: # مجموع دو عنصر بعدی a را مشخص می کند، b = 0، 1 در حالی که b<10: print b a, b = b, a+b

من این دستورات را در fib. py ضمیمه این صفحه قرار داده ام. اجرای fib. py را در IDLE امتحان کنید. آیا خروجی مورد انتظارتان را دریافت می کنید؟

این مثال چند دستور جدید پایتون را معرفی می کند که در اینجا توضیح داده شده است. بیایید به ترتیب به هر خط نگاهی بیندازیم:

• نماد # به ما امکان می دهد "نظر" بنویسیم. یک نظر فقط متن قابل خواندن انسانی است ، که کامپیوتر از آن چشم پوشی می کند. اضافه کردن نظرات به کد شما ایده بسیار خوبی است ، به خصوص اگر - مانند من - شما یک حافظه کوتاه دارید.
• a ، b = 0 ، 1 این خط معادل دو خط ، a = 0 و b = 1 است ، همزمان اجرا می شود. کاما اجازه می دهد تا دو خط در یک نوشته شود (اما برای ظرافت در زیر مشاهده کنید)
• در حالی که ب<10: This is another type of loop statement, similar to the for i in range(10): syntax we saw in tutorial 0. When the program reaches this line, Python will check whether the value of b is less than 10. If so, it will run the indented statements once, and will then retu again to the while statement. If b is still less than 10, then it will run the indented statements again . and so on. It will only stop this process when b is found not to be less than 10.
• چاپ B این مقدار B را به خروجی چاپ می کند
• a ، b = b ، a+b این وسوسه انگیز است که این را به عنوان دو جمله تفسیر کنید ، یکی پس از دیگری اجرا شود ، یعنی ابتدا مقدار b را به A اختصاص دهید ، و سپس مقدار A+B را به متغیر b اختصاص دهید. اما این درست نیست. در واقع ، این یک تکلیف چندگانه است. تفسیر صحیح این است که یک جفت مقادیر ، از B و A+B درست کنید. سپس آنها را همزمان به A و B اختصاص دهید. به این ترتیب ، مقدار A تا مرحله آخر جایگزین نمی شود. همان نتیجه را می توان با سه خط کد بدست آورد:

a_old = a a = b b = a_old + b

یک روش تکراری

روش های بسیاری دیگر برای محاسبه دنباله فیبوناچی وجود دارد. یک احتمال کد زیر است:

# Fibonacci Series # روش تکراری ، با مقادیر ذخیره شده در یک لیست fiblist = [0،1] برای i در محدوده (10): fiblist. Append (fiblist [i] + fiblist [i + 1])

این یک روش تکراری است ، مانند مثال قبلی - از یک حلقه استفاده می کند. تفاوت اصلی این است که من مقادیر را در یک لیست نگه می دارم و مقادیر جدید را "ضمیمه" می کنم.

آیا می بینید که چگونه می توانیم عناصر فردی لیست را بازیابی کنیم؟در اینجا ، Fiblist [0] به اولین عنصر لیست ("HEAD") ، Fiblist [1] به دوم و غیره اشاره دارد.

یک روش بازگشتی

اعداد فیبوناچی از نظر ریاضی (بالاتر) با (i) رابطه عود f (n + 1) = f (n) + f (n-1) و (ii) موارد پایه f (1) = 1 ، f (0) تعریف شده اند.= 0. به جای استفاده از یک روش تکراری ، با یک حلقه ، ممکن است در عوض یک عملکرد "بازگشتی" را تعریف کنیم که به این تعریف ریاضی نزدیکتر است.

def fibrec (n): اگر n<2: retu n else: retu fibRec(n-1) + fibRec(n-2)

ببینید که چگونه عملکرد خود را بارها و بارها صدا می کند؟این نمونه ای از یک روش بازگشتی است. با فراخوانی مکرر خود ، عود به سمت پایین پیش می رود تا اینکه به پرونده پایه برسد.

نسبت طلایی

حال بیایید در مورد نسبت عناصر پی در پی دنباله ، یعنی f (n+1) / f (n) فکر کنیم. به نظر می رسد که این نسبت به سمت یک مقدار ثابت تمایل دارد ، زیرا تعداد فیبوناچی ها بزرگتر می شوند. علاوه بر این ، این ارزش خاص در سنین بالا برای ریاضیدانان بسیار مشهور است. به عنوان نسبت طلایی شناخته می شود و توسط

سعی کنید نسبت اصطلاحات پی در پی در لیست اعداد فیبوناچی را با بیانیه ای مانند: محاسبه کنید:

gratio = [fiblist [i] / float (fiblist [i-1]) برای i در محدوده (2 ، لن (fiblist))] چاپ gratio

چی میبینی؟چقدر می توانید به مقدار دقیق نسبت طلایی نزدیک شوید؟(این کد ممکن است در انتهای صفحه در gratio. py یافت شود).

نمایش گرافیکی

اعداد فیبوناچی را می توان به صورت گرافیکی به عنوان طول بازوها در یک مارپیچ یا به عنوان مربع هایی که مستطیل را کاشی می کنند ، همانطور که در زیر نشان داده شده است ، نشان داد. در هفته های آینده ، من نحوه ترسیم چنین الگوهای را با استفاده از ماژول Pygame نشان خواهم داد.

نسبت طلایی در نوع خاصی از مستطیل یافت می شود. هنگامی که یک مستطیل در کنار یک مربع قرار می گیرد ، همانطور که نشان داده شده است ، آنها یک مستطیل دوم درست می کنند. نسبت طلایی زمانی اتفاق می افتد که دو مستطیل مشابه باشند ، به این معنی که نسبت طول سمت آنها همان است ، a/b = (a+b)/a. این نسبت نسبت طلایی است.

فرمول بینه

در واقع یک فرمول ریاضی ساده برای محاسبه شماره فیبوناچی n وجود دارد که نیازی به محاسبه اعداد قبلی ندارد. این نسبت طلایی است:

به این فرمول بینه گفته می شود. ما می توانیم با استفاده از یک تابع فرمول Binet را در پایتون پیاده سازی کنیم:

def fibbinet (n): phi = (1 + 5 ** 0. 5) /2. 0 Retu int (دور ((phi ** n - ( 1-phi) ** n) / 5 ** 0. 5))

توجه داشته باشید که ** به معنای "افزایش به قدرت" است ، و افزایش به قدرت نیمی (0. 5) از نظر ریاضی معادل گرفتن ریشه مربع است.(راه دیگر برای گرفتن ریشه مربع استفاده از ماژول ریاضی است که ابتدا باید در پایتون بارگذاری شویم: واردات ریاضی به ما اجازه می دهد تا از Math. sqrt (5) استفاده کنیم).

این کد ممکن است کمی ناخوشایند به نظر برسد. به عنوان مثال ، چگونه می توانیم مطمئن باشیم که ریشه مربع قبل از تقسیم گرفته می شود؟در اینجا ، ما به این واقعیت متکی هستیم که پایتون (مانند اکثر زبانها) اظهارات را به ترتیب ثابت خاص از تقدم اجرا می کند. افزایش به قدرت بر تقسیم می شود ، که (مانند ضرب) بر افزودن و تفریق برتری دارد. برای ترتیب مقدمات عملیات مشترک اینجا را ببینید. در جایی که یک سفارش متفاوت مورد نیاز است ، باید از براکت ها استفاده کنیم (مانند مثال فوق).

کد پایتون برای همه این روش ها را می توان در fibonacci. py یافت ، که در پایین این صفحه ضمیمه شده است. نمونه هایی از روش های دیگر برای محاسبه اعداد فیبوناچی را می توان در Rosettacode و در برنامه های سواد پیدا کرد

چالش ها

1. در تصویر بالا ، شش مربع در داخل یک مستطیل نصب شده و هیچ فضایی باقی نمی گذارد. به عبارت دیگر ، مستطیل با مربع کاشی می شود. آیا می توانید یک مربع دیگر برای تهیه مستطیل جدید اضافه کنید؟چقدر بزرگ است؟حالا یک مربع دیگر اضافه کنید. چقدر بزرگ؟اندازه مربع ها چگونه با توالی فیبوناچی ارتباط دارد؟

2. در تصویر بالا ، دو مربع با همان اندازه وجود دارد. اما اگر فقط می توانید از مربع های اندازه های مختلف (اعداد کامل) استفاده کنید ، آیا می توانید یک مستطیل کاشی کنید؟اگر چنین است ، آیا می توانید نتیجه بگیرید که چگونه؟[اگر به یک اشاره نیاز دارید ، pi3challenge@sheffield. ac. uk] این بسیار سخت است.

هفته آینده ما یاد خواهیم گرفت که چگونه از پایتون برای تولید دیسک های زیبا فیبوناچی مانند این استفاده کنیم (با استفاده از کدی که توسط پیتر درلین نوشته شده است) < SPAN> کد پایتون برای همه این روش ها را می توان در fibonacci. py یافت ، که در پایین این صفحه ضمیمه شده است. بشرنمونه هایی از روش های دیگر برای محاسبه اعداد فیبوناچی را می توان در Rosettacode و در برنامه های سواد پیدا کرد