تکرار اور پنراورتی فارمولہ کو سمجھنا

Iteration

Iteration ایک عمل کی تکرار ہے. جو طالب علم اسکول جاتا ہے وہ ہر روز گریجویشن تک اسکول جانے کے عمل کو دہراتا ہے۔ ہم سامان خریدنے کے لئے ماہ میں کم از کم ایک یا دو بار گروسری اسٹور پر جاتے ہیں۔ ہم ہر ماہ اس عمل کو دہراتے ہیں۔ ریاضی میں ، فبونیکی تسلسل ٹاسک ریپیٹیٹیشن کی خصوصیات کی بھی پیروی کرتا ہے۔ آئیے فیبونیکی تسلسل پر غور کریں جہاں پہلے دو نمبر 0 اور 1 ہیں ، باقی تمام اعداد پچھلے دو نمبروں کا مجموعہ ہیں۔

0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89

تشخیصی اقدامات

فبونیکی فارمولہ لکھا جاسکتا ہے ،

F (n) = F (n - 1) + F (n - 2)
فیبونیکی (0) = 0
فیبونیکی (1) = 1
فبونیکی (2) = فبونیکی (1) + فبونیکی (0) = 1 + 0 = 1
فیبونیکی (3) = فائبونیکی (2) + فیبونیکی (1) = 1 + 1 = 2
فیبونیکی (4) = فائبونیکی (3) + فائبونیکی (2) = 2 + 1 = 3
فیبونیکی (5) = فائبونیکی (4) + فائبونیکی (3) = 3 + 2 = 5
فیبونیکی (6) = فائبونیکی (5) + فائبونیکی (4) = 5 + 3 = 8

ذیل میں دیئے گئے الگورتھم نویں فبونیکی نمبر کی واپسی کرتا ہے۔

تکرار

جب بھی ہم ایک نیا فبونیکی نمبر (نویں نمبر) حاصل کرتے ہیں کہ نواں نمبر دراصل (این - 1) واں نمبر ہوتا ہے جب ہمیں مل جاتا ہے (این + 1) واں فبونیکی کو ہمارا اگلا نواں فبونیکی ہے۔ جیسا کہ ہم دیکھتے ہیں کہ مذکورہ بالا تکرار کے مراحل ہیں: اگر n = 2 تو
فبونیکی (2) = فبونیکی (2 - 1) + فبونیکی (2 - 2) = فبونیکی (1) + فبونیکی (0) = 1 + 0 = 1

اب ، ہم فیبونیکی (3) پیدا کرنا چاہتے ہیں ، یعنی n = 3۔

فبونیکی (3) = فبونیکی (3 - 1) + فبونیکی (3 - 2) = فبونیکی (2) + فبونیکی (1) = 1 + 1 = 2
اس کا مطلب یہ ہے کہ ، ہر بار ن موجودہ (n - 1) ویں اور (n - 2) ویں فیبونیکی کی قیمت میں بھی اضافہ کرتا ہے۔ لیکن ہر این کے لئے (n - 1) ویں اور (n - 2) ویں فبوناکسی کو ٹریک رکھنا تھک رہا ہے۔ کیسے ایسا طریقہ لکھنے کے بارے میں جو خود کو تکرار کے کام کو خود سے دہرانے کے لئے کہتا ہے؟

ایک ایسا طریقہ جو خود کو بلاتا ہے اس کا نام recursive method ہے۔ ایک بار بار چلنے والے طریقہ کار میں بیس کیس ہونا ضروری ہے جہاں پروگرام خود فون کرنا بند کردے۔ فبونیکی سیریز کے لئے ہمارا بنیادی کیس فبونیکی (0) = 0 اور فبونیکی (1) = 1 ہے۔ ورنہ ، فیبونیکی کا طریقہ خود کو دو بار - فبونیکی (این - 1) اور فبوناکسی (این - 2) کہتے ہیں۔ پھر یہ انھیں فیبونیکی (n) حاصل کرنے میں شامل کرتا ہے۔ نواں فبونیکی کی تلاش کے لurs ایک بار بار آنے والا طریقہ لکھا جاسکتا ہے -

اگر ہم غور سے دیکھیں تو ، تکرار اسٹیک کی خاصیت کی پیروی کرتی ہے۔ یہ کسی چھوٹے مسئلے کو حل کرتا ہے تاکہ کسی مسئلے کا حل نکالا جاسکے۔ n> 1 کے ل it ، یہ آخری لائن پر عملدرآمد کرتا ہے۔ لہذا ، اگر این = 6 ، فنکشن فون کرتا ہے اور فیبونیکی (6 - 1) اور فبوناکشی (6 - 2) شامل کرتا ہے۔ فبوناکی (6 - 1) یا فبونیکی (5) کال کرتی ہے اور فیبونیکی (5 - 1) اور فبوناکسی (5 - 2) شامل کرتی ہے۔ یہ تکرار اس وقت تک جاری رہتا ہے جب تک 6 اس کی بنیاد کیس کی قیمت تک نہیں پہنچتا ہے جو فیبونیکی (0) = 0 یا فبوناکسی (1) = 1 ہے۔ جب یہ بیس کیس سے ٹکرا جاتا ہے تو اس میں دو بنیادی اقدار شامل ہوجاتی ہیں اور اس وقت تک اوپر جاتے ہیں جب تک کہ اسے فیبونیکی کی قدر نہیں ملتی ہے۔ 6)۔ نیچے تکرار کی ایک درخت کی نمائندگی ہے۔

تکرار درخت

جیسا کہ ہم دیکھ سکتے ہیں ، تکرار کتنی طاقتور ہوسکتی ہے۔ کوڈ کی صرف ایک لائن ہی درخت کو اوپر بنا رہی ہے (اوپر والے کوڈ کی آخری سطر بشمول بیس کیسز) تکرار ایک اسٹیک کو برقرار رکھتی ہے اور جب تک یہ بیس کیس تک نہ پہنچ پائے اس کی گہرائی میں جاتا ہے۔ متحرک پروگرامنگ (DP): تکرار کرنا سمجھنے اور سمجھنے میں آسان ہے لیکن وقت اور میموری کے لحاظ سے یہ مہنگا پڑ سکتا ہے۔ نیچے تکرار درخت پر ایک نظر ڈالیں۔ فائیب (4) سے شروع ہونے والی بائیں ذیلی ندی اور فب (4) سے شروع ہونے والی دائیں سب ٹری بالکل یکساں ہیں۔ وہ ایک ہی نتیجہ پیدا کرتے ہیں جو 3 ہے لیکن وہ ایک ہی کام دو بار کر رہے ہیں۔ اگر این بڑی تعداد میں ہے (مثال کے طور پر: 500000) تو پھر تقرری ایک پروگرام کو بہت سست بنا سکتی ہے کیونکہ یہ ایک ہی سب ٹاسک کو متعدد بار کال کرے گا۔

تکرار درخت چکر لگایا

اس مسئلے سے بچنے کے لئے متحرک پروگرامنگ استعمال کی جاسکتی ہے۔ متحرک پروگرامنگ میں ہم پہلے حل شدہ سب ٹاسک کا استعمال اسی قسم کے مستقبل کے کام کو حل کرنے کے ل. کرسکتے ہیں۔ اصل مسئلہ کو حل کرنے کے لئے کام کو کم کرنے کا یہ ایک طریقہ ہے۔ آئیے ایک سرنی فب [] رکھتے ہیں جہاں ہم پہلے حل شدہ سب ٹاسک حل حل کرتے ہیں۔ ہم پہلے ہی جان چکے ہیں کہ fib [0] = 0 اور fib [1] = 1. آئیے ان دو اقدار کو ذخیرہ کریں۔ اب ، فائب [2] کی قدر کیا ہے؟ چونکہ fib [0] = 0 اور fib [1] = 1 پہلے ہی ذخیرہ ہوچکا ہے ہمیں صرف fib [2] = fib [1] + fib [0] کہنا ہے اور بس اتنا ہی ہے۔ ہم اسی طرح سے fib [3]، fib [4]، fib [5]، ……، fib [n] پیدا کرسکتے ہیں۔ پہلے حل شدہ سب ٹاسکس کو اگلی سب ٹاسک حاصل کرنے کے لئے کہا جارہا ہے جب تک کہ اصل کام حل نہ ہوجائے ، اس طرح بے کار حساب کو کم کردیتا ہے۔