মডিউল ১৯ঃ 2D Array এবং Recursion দিয়ে Problem Solving

---

মডিউল ১৯-১: মিরর এরে

প্রবলেম স্টেটমেন্টঃ

ইনপুটে রো এবং কলাম দেওয়া থাকবে। তারপর একটি 2D এরে দেওয়া থাকবে। সেই 2D এরের মিরর রিভার্স ( প্রতিটি রো রিভার্স করে ) প্রিন্ট করতে হবে।

সল্যুশনঃ

প্রথমে রো এবং কলাম ইনপুট নিব। তারপর 2D এরে ডিক্লেয়ার করব। তারপর নেস্টেড লুপ চালিয়ে 2D এরে ইনপুট নিব। তারপর যেই নেস্টেড লুপ চালিয়ে আমরা 2D এরে প্রিন্ট করতাম সেখানে অল্প একটু মডিফাই করতে হবে। নেস্টেড লুপের ইনার লুপটি উল্টো করে প্রিন্ট করে দিলেই দেখব সবগুলো রো উল্টো করে প্রিন্ট হচ্ছে।

Code:

#include <stdio.h>
int main()
{
    int row, col;
    scanf("%d %d", &row, &col);   // রো এবং কলাম ইনপুট নেওয়া হচ্ছে।
    int a[row][col];               // ইনপুট নেওয়া রো এবং কলাম দিয়ে 2D এরে ডিক্লেয়ার করা হচ্ছে।
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            scanf("%d", &a[i][j]); // 2D এরে ইনপুট নেওয়া হচ্ছে নেস্টেড লুপ দিয়ে।
        }
    }
    for (int i = 0; i < row; i++)      // নেস্টেড লুপের আউটার লুপ
    {
        for (int j = col - 1; j >= 0; j--) // নেস্টেড লুপের ইনার লুপ। রো উল্টো করে প্রিন্ট করার জন্য এই লুপটি উল্টো চালানো হয়েছে।
        {
            printf("%d ", a[i][j]);    // প্রিন্ট করা হচ্ছে।
        }
        printf("\n");
    }
    return 0;
}

---

মডিউল ১৯-২ঃ প্রিন্ট ডিজিটস ইউজিং রিকারশন

প্রবলেম লিংকঃ D. Print Digits using Recursion

প্রবলেম স্টেটমেন্টঃ

ইনপুটে প্রথমে টেস্টকেস দেওয়া থাকবে। প্রতিটি টেস্টকেসে একটি করে সংখ্যা ইনপুট থাকবে। প্রতিটি সংখ্যার সবগুলো ডিজিট একটি একটি করে বাম থেকে প্রিন্ট করতে হবে রিকারশন ব্যাবহার করে।

সল্যুশনঃ

প্রথমে টেস্টকেস ইনপুট নিব। তারপর টেস্টকেস এর জন্য লুপ চালিয়ে প্রতিবার একটা করে সংখ্যা ইনপুট নিব। সংখ্যা ইনপুট নেওয়ার পর আমরা সংখ্যাটিকে রিকারশন ফাংশনের মধ্যে দিয়ে দিব। ফাংশনের মধ্যে শুরুতে সংখ্যাকে ১০ দিয়ে মড করলে আমরা লাস্ট ডিজিটটি পেয়ে যাব। আমাদের প্রিন্ট করতে হবে ফার্স্ট ডিজিট থেকে তাই আমরা লাস্ট ডিজিট বের করার পর প্রিন্ট না করে আগে রিকারশন ফাংশনকে কল করে দিব। আর যেহেতু লাস্ট ডিজিট এর কাজ হয়ে গেছে তাই আমরা ফাংশনে সংখ্যাটিকে ১০ দিয়ে ভাগ করে পাঠাব। আমরা ধরে নিব সেই রিকারশন ফাংশন ফার্স্ট থেকে ডিজিট প্রিন্ট করে দিবে। রিকারশন ফাংশনকে কল করার পর আমরা মাত্র বের করা লাস্ট ডিজিট প্রিন্ট করে দিব। এক্ষেত্রে বেস কেস হবে যখন সংখ্যাটি ১০ দিয়ে ভাগ করতে করতে শূন্য হয়ে যাবে।

Code:

#include <stdio.h>
void fun(int n)
{
    if (n == 0) return;              // বেস কেস। যখন সংখ্যাটি ১০ দিয়ে ভাগ করতে করতে শূন্য হয়ে যাবে।
    int x = n % 10;                  // লাস্ট ডিজিট বের করে রাখা হচ্ছে।
    fun(n / 10);                     // রিকারশন ফাংশনকে কল করা হচ্ছে।
    printf("%d ", x);                // ফাংশন কল হওয়া শেষে লাস্ট ডিজিটটি প্রিন্ট করা হচ্ছে।
}
int main()
{
    int test;
    scanf("%d", &test);              // টেস্টকেস ইনপুট নেওয়া হচ্ছে।
    for (int t = 0; t < test; t++)   // টেস্টকেস এর উপর লুপ চালানো হচ্ছে।
    {
        int n;
        scanf("%d", &n);             // সংখ্যা ইনপুট নেওয়া হচ্ছে।
        fun(n);                       // রিকারশন ফাংশনকে কল করা হচ্ছে।
        if (n == 0)                   // যদি সংখ্যাটি জিরো হয় তাহলে ফাংশন থেকে কিছু প্রিন্ট হবে না। কারন বেস কেসে আমরা জিরো দিয়ে করেছি।
        {
            printf("0");              // ইনপুটে জিরো থাকলে জিরো প্রিন্ট করে দিচ্ছি সরাসরি।
        }
        printf("\n");
    }
    return 0;
}

---

মডিউল ১৯-৩ঃ কাউন্ট Length of String using Recursion

প্রবলেম স্টেটমেন্টঃ

ইনপুটে একটি স্ট্রিং দেওয়া থাকবে। সেই স্ট্রিং এ কয়টি character আছে তা কাউন্ট করতে হবে রিকারশনের মাধ্যমে।

সল্যুশনঃ

প্রথমে স্ট্রিংটি ইনপুট নিব। তারপর রিকারশন ফাংশনে স্ট্রিং দিয়ে দিব এবং ইন্ডেক্স হিসেবে ০ দিব। আমরা ০ ইন্ডেক্স থেকে character কাউন্ট করা শুরু করছি। রিকারশন ফাংশন শুরুতে রিকারশন ফাংশনকেই কল করে দিবে এবং ইন্ডেক্স এর সাথে ১ যোগ করে দিব কারন আমরা পরবর্তী ইনডেক্স নিয়ে কাজ করতে চাই। তারপর আমরা ধরে নিব রিকারশন ফাংশন পরবর্তী ইন্ডেক্স থেকে লাস্ট ইন্ডেক্স পর্যন্ত কয়টি ক্যারেক্টার আছে তা কাউন্ট করে দিয়ে দিবে। সেই কাউন্টটা আমরা একটি ভেরিয়েবলে স্টোর করব। তারপর যেই ইন্ডেক্সে ছিলাম তা নিয়ে কাজ করতে হবে। এক্ষেত্রে function থেকে যে মান পেয়েছি তার সাথে এক যোগ করে রিটার্ন করতে হবে। এক্ষেত্রে বেস কেস হবে স্ট্রিং যখন শেষ হয়ে যাবে অর্থাৎ ইন্ডেক্সটি যখন নাল ক্যারেক্টারে থাকবে।

Code:

#include <stdio.h>

int fun(char s[], int i)
{
    // base case
    if (s[i] == '\0')   // স্ট্রিং যখন শেষ হয়ে যাবে অর্থাৎ ইন্ডেক্সটি যখন নাল ক্যারেক্টারে থাকবে।
    {
        return 0;       // নাল ক্যারেক্টারে থাকলে আমরা ০ রিটার্ন করছি। কারন এখানে কোন ক্যারেক্টার নেই।
    }
    int ans = fun(s, i + 1);   // রিকারশন ফাংশনকে কল করে স্ট্রিং দিয়ে দিচ্ছি এবং ইন্ডেক্সের সাথে ১ যোগ করে দিচ্ছি যাতে পরবর্তী ইন্ডেক্স নিয়ে কাজ করা হয়। কাজ করে যে কাউন্ট রিটার্ন করবে তা স্টোর করছি আরেকটি ভেরিয়েবলে।

    return ans + 1;     // ans এর সাথে নিজের ইন্ডেক্সের ক্যারেক্টার এর জন্য ১ যোগ করে রিটার্ন করছি
}
int main()
{
    char s[205];
    scanf("%s", s);
    int cnt = fun(s, 0);   // রিকারশন ফাংশনকে কল করে ফাংশন থেকে রিটার্ন আসা কাউন্ট ভেলু স্টোর করে রাখা হচ্ছে।
    printf("%d\n", cnt);   // কাউন্ট প্রিন্ট করা হচ্ছে।
    return 0;
}

---

মডিউল ১৯-৪: কাউন্ট ভাওয়েলস

প্রবলেম লিংকঃ I. Count Vowels

প্রবলেম স্টেটমেন্টঃ

ইনপুটে একটি স্ট্রিং দেওয়া থাকবে। সেই স্ট্রিং এ কয়টি ভাওয়েলস আছে তা কাউন্ট করতে হবে রিকারশনের মাধ্যমে।

সল্যুশনঃ

প্রথমে স্ট্রিংটি ইনপুট নিব। তারপর রিকারশন ফাংশনে স্ট্রিং দিয়ে দিব এবং ইন্ডেক্স হিসেবে ০ দিব। আমরা ০ ইন্ডেক্স থেকে ভাওয়েলস কাউন্ট করা শুরু করছি। রিকারশন ফাংশন শুরুতে রিকারশন ফাংশনকেই কল করে দিবে এবং ইন্ডেক্স এর সাথে ১ যোগ করে দিব কারন আমরা পরবর্তী ইনডেক্স নিয়ে কাজ করতে চাই। তারপর আমরা ধরে নিব রিকারশন ফাংশন পরবর্তী ইন্ডেক্স থেকে লাস্ট ইন্ডেক্স পর্যন্ত ভাওয়েল কাউন্ট করে দিয়ে দিবে। সেই কাউন্টটা আমরা একটি ভেরিয়েবলে স্টোর করব। তারপর যেই ইন্ডেক্সে ছিলাম তা নিয়ে কাজ করতে হবে। প্রথমেই আমরা যদি ক্যারেক্টারটি আপার কেসে থাকে তাহলে লোয়ার কেসে কনভার্ট করে নিব। তারপর চেক করে দেখব ক্যারেক্টারটি ভাওয়েল কিনা। ভাওয়েল হলে কাউন্ট এর সাথে ১ যোগ করে রিটার্ন করে দিব। আর ভাওয়েল না হলে কাউন্ট রিটার্ন করে দিব। এক্ষেত্রে বেস কেস হবে স্ট্রিং যখন শেষ হয়ে যাবে অর্থাৎ ইন্ডেক্সটি যখন নাল ক্যারেক্টারে থাকবে।

Code:

#include <stdio.h>

int fun(char s[], int i)
{
    // base case
    if (s[i] == '\0')   // স্ট্রিং যখন শেষ হয়ে যাবে অর্থাৎ ইন্ডেক্সটি যখন নাল ক্যারেক্টারে থাকবে।
    {
        return 0;       // নাল ক্যারেক্টারে থাকলে আমরা ০ রিটার্ন করছি। কারন এখানে কোন ভাওয়েল নেই।
    }
    int ans = fun(s, i + 1);   // রিকারশন ফাংশনকে কল করে স্ট্রিং দিয়ে দিচ্ছি এবং ইন্ডেক্সের সাথে ১ যোগ করে দিচ্ছি যাতে পরবর্তী ইন্ডেক্স নিয়ে কাজ করা হয়। কাজ করে যে কাউন্ট রিটার্ন করবে তা স্টোর করছি আরেকটি ভেরিয়েবলে।
    if (s[i] >= 'A' && s[i] <= 'Z')   // যদি ক্যারেক্টারটি আপার কেসে থাকে তাহলে লোয়ার কেসে কনভার্ট করে নিচ্ছি।
    {
        s[i] = s[i] + 32;
    }
    if (s[i] == 'a' || s[i] == 'e' || s[i] == 'o' || s[i] == 'u' || s[i] == 'i') // ভাওয়েল কিনা চেক করছি।
    {
        return ans + 1;     // ভাওয়েল হলে কাউন্ট এর সাথে ১ যোগ করে রিটার্ন করছি।
    }
    else
    {
        return ans;         // আর না হলে কাউন্ট রিটার্ন করে দিচ্ছি।
    }
}
int main()
{
    char s[205];
    fgets(s, 205, stdin);   // এফগেটস দিয়ে স্ট্রিং ইনপুট নিচ্ছি। কারন স্ট্রিং এর মধ্যে স্পেস থাকবে।
    int cnt = fun(s, 0);    // রিকারশন ফাংশনকে কল করে ফাংশন থেকে রিটার্ন আসা কাউন্ট ভেলু স্টোর করে রাখা হচ্ছে।
    printf("%d\n", cnt);    // কাউন্ট প্রিন্ট করা হচ্ছে।
    return 0;
}

---

মডিউল ১৯-৫: ফেক্টরিয়াল

প্রবলেম লিংকঃ J. Factorial

প্রবলেম স্টেটমেন্টঃ

ইনপুটে একটি সংখ্যা দেওয়া থাকবে। সেই সংখ্যার ফেক্টরিয়াল প্রিন্ট করতে হবে।

সল্যুশনঃ

প্রথমে সংখ্যাটি ইনপুট নিব। কোন সংখ্যার ফেক্টরিয়াল হচ্ছে ১ থেকে ওই সংখ্যা পর্যন্ত গুনফল।

5! = 1 x 2 x 3 x 4 x 5

4! = 1 x 2 x 3 x 4

এরকম।

এখানে খেয়াল করলে দেখতে পাব 5! কে 5 x 4! এভাবে লিখা যায়। কারন 4! হচ্ছে 1 x 2 x 3 x 4 যার সাথে 5 গুন করলে 1 x 2 x 3 x 4 x 5 হয়ে যায় অর্থাৎ 5!

যেকোন ফেক্টরিয়ালকে এভাবে লিখা যায়ঃ n! = n x (n-1)!

এটি আমরা এখন রিকারশন দিয়ে করব। আমরা রিকারশন ফাংশনকে বলব n-1 এর ফেক্টরিয়াল বের করে আনতে। আমরা ধরে নিব সে n-1 এর ফেক্টরিয়াল বের করে নিয়ে আসবে। তারপর আমরা জাস্ট ওটার সাথে n গুন করে দিব। তাহলেই n! চলে আসবে।

Code:

#include <stdio.h>
long long int fact(long long int n)
{
    // base case
    if (n == 0)         // বেস কেস হিসেবে ০ দেওয়া হয়েছে। আমরা n থেকে ১ পর্যন্ত গুন করতে হবে। তাই ০ তে আসলে আমরা গুন করা থামিয়ে দিব।
    {
        return 1;       // ১ রিটার্ন করা হচ্ছে, কারন বেস কেসে আসা মানে হচ্ছে আমাদের ফেক্টরিয়াল বের করা শেষ। তাই তার সাথে ১ গুন করে রিটার্ন করে দিচ্ছি। গুনফল এর সাথে ১ গুন করায় গুনফলের কোন পরিবর্তন হচ্ছে না। এখানে আমরা ০ রিটার্ন করি নি কারন গুনফলের সাথে ০ গুন করলে সম্পূর্ণ গুনফল ০ হয়ে যাবে।
    }
    long long int ans = fact(n - 1);   // রিকারশন ফাংশনকে বলছি n-1 এর ফেক্টরিয়াল বের করে আনতে। আমরা ধরে নিব সে n-1 এর ফেক্টরিয়াল বের করে নিয়ে আসবে।
    return ans * n;     // তারপর সেই n-1 এর ফেক্টরিয়াল এর সাথে আমরা n কে গুন করে রিটার্ন করে দিচ্ছি যা আমাদের আন্সার।
}
int main()
{
    long long int n;        // সংখ্যাটি ইনপুট নিচ্ছি।
    scanf("%lld", &n);
    long long int ans = fact(n);    // রিকারশন ফাংশনকে কল করছি এবং ফাংশনের রিটার্ন করা আন্সার স্টোর করছি।
    printf("%lld", ans);    // আন্সার প্রিন্ট করছি।
    return 0;
}