মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 1
পাঠ 6: রিকার্সিভ অ্যালগোরিদম- রিকার্শন
- উৎপাদক ফাংশন
- চ্যালেঞ্জ: পুনরাবৃত্তিমূলক উৎপাদক
- রিকার্সিভ উৎপাদক
- চ্যালেঞ্জ: রিকার্সিভ উৎপাদক
- রিকার্সিভ অ্যালগোরিদমের বৈশিষ্ট্য
- একটি শব্দ প্যালিনড্রোম শব্দ কিনা তা রিকার্শন ব্যবহার করে নির্ধারণ করা
- চ্যালেঞ্জ: একটি স্ট্রিং কি একটি প্যালিনড্রোম?
- একটি সংখ্যার ঘাত হিসাব করা
- চ্যালেঞ্জ: রিকার্সিভ ঘাতসমূহ
- সিয়েরপিন্সকি গ্যাসকেট
- প্রকল্প: রিকার্সিভ কলা
© 2023 Khan Academyব্যবহারের শর্তাদিগোপনীয়তার নীতিমালাকুকি নোটিশ
সিয়েরপিন্সকি গ্যাসকেট
এতদিন পর্যন্ত যতগুলো পুনরাবৃত্তির জন্য উদাহরণ দেখেছি তার প্রতিটিতে শুধুমাত্র একবার পুনরাবৃত্তির ফাংশনটি কল করতে দেখেছি। কিন্তু কিছু কিছু সময় তোমাকে বেশ কয়েকটি পৌনঃপুনিকতা কল করা প্রয়োজন পড়বে। খুব ভাল একটি উদাহরণ এখানে দেওয়া হল, গাণিতিকভাবে তৈরি করা অসীম একটি প্যাটার্ন যেটা আমাদের কাছে সিয়েরপিন্সকি গ্যাসকেট নামে পরিচিত:
তুমি এখানে দেখতে পারছ যে, বর্গাকার অঞ্চলে নির্দিষ্ট একটি প্যাটার্নে অঙ্কন করা ছোট ছোট বর্গের একটি সমষ্টি। এটা কীভাবে আঁকাতে হয় তা এখানে দেখান হল। সম্পূর্ণ বর্গ এলাকাটি নিয়ে কাজ করা শুরু করা যাক এবং বর্গটিকে চারটি ভাগে বিভক্ত করা যাক, এরকমভাবে:
এখানে তিনটি বর্গ নেওয়া যাক যার প্রতিটি বর্গের মধ্য দিয়ে একটি × থাকবে—উপরের বাম এবং ডানপাশের বর্গ আর নিচের ডানপাশের বর্গ— আর বর্গগুলো সমান চারটি সমান ভাগে বিভক্ত থাকবে:
এরকমভাবে কাজটি করতে থাক। প্রতিটি বর্গকে একটি × ব্যবহার করার মাধ্যমে চারটি ভাগে বিভক্ত কর এবং প্রতিটি বর্গের উপরের বাম ও ডানপাশের অংশ এবং নিচের ডানপাশের অংশে একটি × রাখ কিন্তু প্রতিটি বর্গের নিচের বামপাশের অংশে কখনই কিছু আঁকানোর করার দরকার নেই।
বর্গগুলো যখন আর ছোট করা সম্ভব হবে না, ভাগ করা বন্ধ করে দাও। যদি তুমি প্রতিটি বর্গ একটি × দিয়ে পূর্ণ করবে এবং বাকি থাকা অন্য বর্গগুলোর কথা ভুলে যাও তাহলে তুমি একটি সিয়েরপিন্সকি গ্যাসকেট পাবে। এখানে আরও একবার দেখানো হল:
সংক্ষেপে, একটি বর্গে কীভাবে সিয়েরপিন্সকি গ্যাসকেট অঙ্কন করতে হয় তা এখানে দেখান হল:
- Determine how small the square is. If it's small enough to be a base case, then just fill in the square. You get to pick how small "small enough" is.
- Otherwise, divide the square into upper left, upper right, lower right, and lower left squares. Recursively "solve" three subproblems:
- Draw a Sierpinski gasket in the upper left square.
- Draw a Sierpinski gasket in the upper right square.
- Draw a Sierpinski gasket in the lower right square.
Notice that you need to make not just one but three recursive calls. That is why we consider drawing a Sierpinski gasket to exhibit multiple recursion.
You can choose any three of the four squares in which you recursively draw Sierpinski gaskets. The result will just come out rotated by some multiple of 90 degrees from the drawing above. (If you recursively draw Sierpinski gaskets in any other number of the squares, you don't get an interesting result.)
The program below draws a Sierpinski gasket. Try commenting and uncommenting some of the recursive calls to get rotated gaskets:
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।