২দশ প্রশ্নে যেকোনো সংখ্যা: অর্ধেক করার শক্তি
একজন শিক্ষার্থী ১ থেকে ১,০০০-এর মধ্যে একটি সংখ্যা ভাবে। অন্যজন শুধু জিজ্ঞেস করতে পারে "এটা কি ...-এর চেয়ে বড় না ছোট?" বেশিরভাগ নতুনের অনেক আন্দাজ লাগে, কিন্তু একটি বুদ্ধিমান কৌশল সবসময় সর্বোচ্চ ১০টি প্রশ্নে সংখ্যাটি খুঁজে পায়। শিক্ষার্থীরা অর্ধেক করার কৌশল (বাইনারি সার্চ) আবিষ্কার করে, তাকে ২-এর ঘাত আর লগারিদমের সাথে যুক্ত করে, আর তারপর তা দিয়ে অভিধানে একটি শব্দ আর সাজানো তালিকায় একটি নাম খোঁজে।
- ক্লাস ও বয়স
- ক্লাস ১১ · ১৬–১৭
- কাজের ধরন
- একক বা দলগত
- সময় লাগবে
- ৪৫ মিনিট
- কাঠিন্য
- সহজ
- আনুমানিক খরচ
- প্রায় বিনা খরচে
গাণিতিক ধারণা
- খোঁজার জায়গা অর্ধেক করা
- ২-এর ঘাত আর ২ ভিত্তিক লগারিদম
- সবচেয়ে খারাপ অবস্থায় ধাপের সংখ্যা
- সাজানো থাকলে খোঁজা কেন দ্রুত
শেখার উদ্দেশ্য
- বাইনারি সার্চ কৌশল আবিষ্কার আর ব্যাখ্যা করা।
- প্রশ্নের সংখ্যাকে log₂ n-এর সাথে যুক্ত করা।
- রৈখিক আর বাইনারি খোঁজা তুলনা করা।
- দৈনন্দিন খোঁজায় ধারণাটি প্রয়োগ করা।
বাস্তব জীবনের সাথে সম্পর্ক
কম্পিউটার লাখ লাখ রেকর্ডের মধ্যে এক সেকেন্ডের ভগ্নাংশে একটি খুঁজে পায়, কারণ তথ্য সাজানো রাখা হয় আর অর্ধেক করে খোঁজা হয়। প্রোগ্রামাররাও কোন লাইন থেকে ত্রুটি শুরু হয়েছে খুঁজতে অর্ধেক করার পদ্ধতি ব্যবহার করেন।
প্রয়োজনীয় উপকরণ
- কাগজ আর পেনসিল
- একটি অভিধান আর নামের একটি সাজানো তালিকা (যেমন ক্লাসের হাজিরা খাতা)
- লগ ফাংশনসহ ক্যালকুলেটর
ধাপে ধাপে নির্দেশনা
- জোড়ায় পাঁচ রাউন্ড খেলো, প্রশ্ন গুনে। সর্বোচ্চ কত প্রশ্ন লেগেছে লেখো।
- কৌশল শেয়ার করো। কোন কৌশল সবচেয়ে কম প্রশ্নের নিশ্চয়তা দেয়?
- অর্ধেক করার কৌশল ব্যবহার করো: সবসময় বাকি পরিসরের মাঝখান নিয়ে প্রশ্ন করো। আবার খেলো।
- একটি সারণি বানাও: k প্রশ্নের পরে কতগুলো সংখ্যা বাকি থাকতে পারে? (১,০০০, ৫০০, ২৫০, ...)
- সবচেয়ে ছোট k বের করো যাতে 2ᵏ ≥ 1,000। log₂ 1,000 ≈ ৯.৯৭ দিয়ে যাচাই করো।
- ১ থেকে ১০,০০,০০০-এর জন্য কত প্রশ্ন? বাংলাদেশের প্রত্যেক মানুষের জন্য?
- অভিধানে একটি শব্দ খুঁজতে একটি একটি পাতা উল্টে আর অর্ধেক করে খুঁজে সময় মাপো।
- ব্যাখ্যা করো অর্ধেক করার পদ্ধতি কাজ করতে তালিকা কেন সাজানো থাকতে হবে।
গাণিতিক ব্যাখ্যা
প্রতিটি ভালোভাবে বাছা প্রশ্ন সম্ভাবনাগুলো অর্ধেক করে, তাই k প্রশ্নের পরে সর্বোচ্চ 1,000 ÷ 2ᵏটি সংখ্যা বাকি থাকে। যেহেতু 2¹⁰ = ১,০২৪, যা ১,০০০-এর বেশি, দশটি প্রশ্ন সবসময় যথেষ্ট। সাধারণভাবে প্রশ্নের সংখ্যা হলো log₂ n-এর সমান বা তার চেয়ে বড় সবচেয়ে ছোট পূর্ণসংখ্যা। দশ লাখ সংখ্যার জন্য তা ২০, আর প্রায় ১৭ কোটি মানুষের জন্যও মাত্র ২৮। একটি একটি করে দেখলে (রৈখিক খোঁজা) n ধাপ লাগতে পারে। অর্ধেক করা শুধু তখনই কাজ করে যখন তালিকা সাজানো থাকে, তাই সাজানো (প্রজেক্ট ১) আর খোঁজা একসাথে চলে।
প্রত্যাশিত ফলাফল
খেলার রেকর্ড, অর্ধেক করার সারণি, রৈখিক আর বাইনারি খোঁজার সময়ের তুলনা আর এক অনুচ্ছেদের ব্যাখ্যা।
যে দক্ষতা গড়ে ওঠে
- কৌশলগত চিন্তা
- প্রসঙ্গে লগারিদম
- অ্যালগরিদম তুলনা
- স্পষ্ট ব্যাখ্যা
মূল্যায়নের মানদণ্ড
- অর্ধেক করার কৌশল সঠিকভাবে ব্যবহার হয়েছে।
- সারণি আর log₂-এর হিসাব সঠিক।
- তথ্য দিয়ে রৈখিক আর বাইনারি খোঁজা তুলনা করা হয়েছে।
- সাজানোর প্রয়োজন ব্যাখ্যা করা হয়েছে।
এক্সটেনশন চ্যালেঞ্জ
এমন একটি সংস্করণ খেলো যেখানে উত্তরদাতা একবার মিথ্যা বলতে পারে। এখন কত প্রশ্ন লাগবে? একটি কৌশল নকশা করো।
নিরাপত্তা ও অন্তর্ভুক্তি
বিশেষ কোনো নিরাপত্তার প্রয়োজন নেই।