পুনরাবৃত্তি এবং পুনরাবৃত্তির সূত্র বোঝা

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
ফিবোনাচি ()) = ফিবোনাচি (৫) + ফিবোনাচি (৪) = ৫ + ৩ = ৮

নীচে প্রদত্ত অ্যালগরিদমটি নবম ফিবোনচি নম্বরটি প্রদান করে।

পুনরাবৃত্তি

প্রতিবার আমরা একটি নতুন ফিবোনাচি নম্বর পাই (নবম সংখ্যা) যে নবম সংখ্যাটি আসলে (এন - 1) তম সংখ্যা হয় যখন আমরা আমাদের পরবর্তী নবম ফিবোনাচি হিসাবে (এন + 1) তম ফিবোনাচি পাই। আমরা উপরে উল্লিখিত পুনরাবৃত্তির পদক্ষেপগুলি দেখতে পাই: যদি n = 2 হয়
ফিবোনাচি (2) = ফিবোনাচি (2 - 1) + ফিবোনাচি (2 - 2) = ফিবোনাচি (1) + ফিবোনাচি (0) = 1 + 0 = 1

এখন, আমরা ফিবোনাচি (3) উত্পন্ন করতে চাই, এটি এন = 3।

ফিবোনাচি (3) = ফিবোনাচি (3 - 1) + ফিবোনাচি (3 - 2) = ফিবোনাচি (2) + ফিবোনাচি (1) = 1 + 1 = 2
এর অর্থ, প্রতিটি সময় এন বর্তমান (n - 1) তম এবং (এন - 2) তম ফাইবোনাকির মান বৃদ্ধি করে। তবে প্রতিটি এন এর জন্য (এন - 1) তম এবং (এন - 2) তম ফিবোনাচি ট্র্যাক করে রাখা ক্লান্তিকর। কীভাবে এমন একটি পদ্ধতি লেখার বিষয়ে যা নিজে থেকে পুনরাবৃত্তির কাজটি নিজেই পুনরুত্থিত করতে কল করে?

একটি পদ্ধতি যা নিজেকে কল করে তার নাম পুনরাবিপন্ন পদ্ধতি হিসাবে দেওয়া হয়। পুনরাবৃত্তির পদ্ধতির একটি বেস কেস থাকতে হবে যেখানে প্রোগ্রামটি কল করা বন্ধ করে দেয়। ফিবোনাচি সিরিজের জন্য আমাদের বেস কেসটি ফিবোনাচি (0) = 0 এবং ফিবোনাচি (1) = 1. অন্যথায়, ফিবোনাচি পদ্ধতিটি নিজেকে দুটিবার কল করে - ফাইবোনাকি (এন - 1) এবং ফাইবোনাকি (এন - 2)। তারপরে এটি ফাইবোনাকি (এন) পেতে তাদের যুক্ত করে। নবম ফিবোনাচি সন্ধানের জন্য একটি পুনরাবৃত্ত পদ্ধতি হিসাবে রচনা করা যেতে পারে -

আমরা যদি মনোযোগ সহকারে লক্ষ্য করি তবে পুনরাবৃত্তি স্ট্যাকের সম্পত্তি অনুসরণ করে। এটি সমস্যার সমাধান পেতে আরও ছোট ছোট সমস্যাগুলি সমাধান করে। N> 1 এর জন্য, এটি শেষ লাইনটি কার্যকর করে। সুতরাং, যদি এন = 6, ফাংশনটি কল করে এবং ফিবোনাচি (6 - 1) এবং ফিবোনাচি (6 - 2) যুক্ত করে। ফিবোনাচি (6 - 1) বা ফাইবোনাকি (5) কল করে ফাইবোনাকি (5 - 1) এবং ফাইবোনাকি (5 - 2) যুক্ত করে। এই পুনরাবৃত্তি অবধি চলমান অবধি অবধি চলবে যতক্ষণ না 6 তার বেস কেস মান পর্যন্ত পৌঁছায় যা ফিবোনাচি (0) = 0 বা ফিবোনাচি (1) = 1। এটি একবার বেস কেটে গেলে এটি দুটি বেস মান যুক্ত করে এবং ফাইবোনাকির মান না পাওয়া পর্যন্ত উপরে যায় ( 6)। নীচে পুনরাবৃত্তি একটি গাছ উপস্থাপন করা হয়।

পুনরাবৃত্তি ট্রি

আমরা দেখতে পাচ্ছি, পুনরাবৃত্তি কতটা শক্তিশালী হতে পারে। কোডের একক লাইন উপরের গাছটি তৈরি করছে (উপরের কোডের শেষ লাইনটি বেস কেসগুলি সহ)। পুনরাবৃত্তি একটি স্ট্যাক বজায় রাখে এবং বেস কেসে না পৌঁছা পর্যন্ত এটি গভীরতর হয়। ডায়নামিক প্রোগ্রামিং (ডিপি): পুনরাবৃত্তি বোঝা এবং কোড করা সহজ তবে সময় এবং মেমরির ক্ষেত্রে এটি ব্যয়বহুল। নীচে পুনরাবৃত্তি গাছটি দেখুন। ফাইব (4) দিয়ে শুরু হওয়া বাম সাবট্রি এবং ফাইব (4) দিয়ে শুরু হওয়া ডান সাবট্রি হুবহু একই। তারা একই ফলাফল উত্পন্ন করে যা 3 হয় তবে একই কাজটি দুটিবার করছে। যদি এন একটি বড় সংখ্যা হয় (উদাহরণ: 500000) তবে পুনরাবৃত্তি একটি প্রোগ্রামকে খুব ধীর করতে পারে কারণ এটি একাধিকবার একই সাব টাস্ককে কল করবে।

পুনরাবৃত্তি গাছ বৃত্তাকার

এই সমস্যাটি এড়াতে ডায়নামিক প্রোগ্রামিং ব্যবহার করা যেতে পারে। ডায়নামিক প্রোগ্রামিংয়ে আমরা একই ধরণের ভবিষ্যতের টাস্ক সমাধান করতে পূর্বে সমাধান হওয়া সাবটাস্ক ব্যবহার করতে পারি। এটি আসল সমস্যা সমাধানের জন্য কাজ হ্রাস করার একটি উপায়। আসুন একটি অ্যারে ফাইব [] থাকুন যেখানে আমরা পূর্বে সমাধান হওয়া সাবটাস্ক সমাধানগুলি সঞ্চয় করি store আমরা ইতিমধ্যে জানি যে fib [0] = 0 এবং fib [1] = 1। আসুন এই দুটি মান সংরক্ষণ করি store এখন, ফাইব [2] এর মান কত? হিসাবে fib [0] = 0 এবং fib [1] = 1 সংরক্ষণ করা হয়েছে ইতিমধ্যে আমাদের কেবল fib [2] = fib [1] + fib [0] বলতে হয় এবং এটি সবই। আমরা একইভাবে fib [3], fib [4], fib [5], ……, fib [n] উত্পন্ন করতে পারি। পূর্বে সমাধান হওয়া সাবটাস্কগুলিকে মূল সাবসেসটি সমাধান না করা অবধি পরবর্তী সাবটাস্ক পাওয়ার জন্য ডাকা হচ্ছে, ফলে অপ্রয়োজনীয় গণনা হ্রাস হয়।