5. Mathematics for DSA
প্রোগ্রামিং সমস্যা সমাধানের জন্য গণিত অত্যন্ত গুরুত্বপূর্ণ। বিশেষ করে কম্পিটিটিভ প্রোগ্রামিং এবং ডাটা স্ট্রাকচার শেখার শুরুতে কিছু মৌলিক গাণিতিক বিষয় আয়ত্ত করা খুব জরুরি।
মৌলিক গাণিতিক কাজ (Basic Arithmetic Operations)
যোগ, বিয়োগ, গুণ এবং ভাগের পাশাপাশি প্রোগ্রামিংয়ে কিছু বিশেষ গাণিতিক অপারেশন বেশি ব্যবহৃত হয়।
Modulo Operation (%)
মডুলো অপারেশন একটি সংখ্যাকে অন্য সংখ্যা দিয়ে ভাগ করার পর অবশিষ্ট (remainder) কত থাকে তা বের করে।
- ব্যবহার: জোড়-বিজোড় সংখ্যা বের করা, কোনো সংখ্যার শেষ ডিজিট বের করা ইত্যাদি।
- উদাহরণ:
10 % 3 = 1
Power Calculation (সূচক)
কোনো সংখ্যার ওপর পাওয়ার বা সূচক হিসাব করা।
- অপ্টিমাইজেশন: O(n) থেকে O(log n) এ পাওয়ার হিসাব করার জন্য Binary Exponentiation ব্যবহৃত হয়।
GCD এবং LCM
GCD (Greatest Common Divisor)
দুটি বা ততোধিক সংখ্যার গরিষ্ঠ সাধারণ গুণনীয়ক (গ.সা.গু)।
- Algorithm: ইউক্লিডীয় অ্যালগরিদম (Euclidean Algorithm) ব্যবহার করে খুব দ্রুত GCD বের করা যায়।
LCM (Least Common Multiple)
দুটি বা ততোধিক সংখ্যার লঘিষ্ঠ সাধারণ গুণিতক (ল.সা.গু)।
- Formula: LCM(a, b) = (a * b) / GCD(a, b)
মৌলিক সংখ্যা (Prime Numbers)
সবসব সংখ্যা কেবল ১ এবং সেই সংখ্যা ছাড়া অন্য কিছু দিয়ে বিভাজ্য নয়।
- Primality Test: একটি সংখ্যা মৌলিক কিনা তা চেক করার জন্য O(√n) অ্যালগরিদম বেশ জনপ্রিয়।
- Sieve of Eratosthenes: ১ থেকে n পর্যন্ত সব মৌলিক সংখ্যা দ্রুত বের করার একটি শক্তিশালী পদ্ধতি।
ফ্যাক্টোরিয়াল (Factorial)
একটি সংখ্যা n এর ফ্যাক্টোরিয়াল হলো ১ থেকে n পর্যন্ত সব সংখ্যার গুণফল (n!)। এটি রিকার্সন বোঝার জন্য সবচেয়ে কমন উদাহরণ।
- উদাহরণ: 5! = 5 _ 4 _ 3 _ 2 _ 1 = 120
ফিবোনাচ্চি সংখ্যা (Fibonacci Numbers)
একটি বিশেষ ধারা যেখানে পরবর্তী সংখ্যাটি আগের দুটি সংখ্যার সমষ্টি।
- ধারা: 0, 1, 1, 2, 3, 5, 8, 13, 21...
- কমপ্লেক্সিটি: রিকার্সিভ পদ্ধতিতে O(2^n) লাগে, কিন্তু ডাইনামিক প্রোগ্রামিং ব্যবহার করলে O(n) এ আনা সম্ভব।
মৌলিক সংখ্যাতত্ত্ব (Basic Number Theory)
এছাড়াও আরও কিছু বিষয় জানা থাকলে সুবিধা হয়:
- Divisor counting: একটি সংখ্যার মোট কতটি ভাজক আছে।
- Modular Arithmetic: বড় বড় ক্যালকুলেশন হ্যান্ডেল করার জন্য খুব প্রয়োজনীয়।
TIP
গণিত কেবল ফর্মুলা নয়, এটি মূলত আপনার লজিক্যাল থিংকিং স্কিল তৈরি করে। তাই নিয়মিত ম্যাথ রিলেটেড প্রবলেম সলভ করুন।