Showing posts with label Competitive Programming. Show all posts
Showing posts with label Competitive Programming. Show all posts

CECP004 - রাশিচক্র


রাশিচক্রের সাথে সবাই কমবেশি পরিচিত। মানুষের জন্ম তারিখের উপর ভিত্তি করে তার রাশি নির্ধারণ করা হয়। কারো জন্ম যদি একটি নির্দিষ্ট তারিখ রেঞ্জের মধ্যে হয়, তাহলে তাকে একটি নির্দিষ্ট রাশির জাতক/জাতিকা বলা হয়। যেমন, জন্ম যদি

১৬ এপ্রিল - ১৫ মে হয়, রাশি হবে Aries বা মেষ,
১৬ মে - ১৫ জুন হয়, রাশি হবে Taurus বা বৃষ,
১৬ জুন - ১৫ জুলাই হয়, রাশি হবে Gemini বা মিথুন,
১৬ জুলাই - ১৫ আগষ্ট হয়, রাশি হবে Cancer বা কর্কট,
১৬ আগষ্ট - ১৫ সেপ্টেম্বর হয়, রাশি হবে Leo বা সিংহ,
১৬ সেপ্টেম্বর - ১৫ অক্টোবর হয়, রাশি হবে virgo বা কন্যা,
১৬ অক্টোবর - ১৫ নভেম্বর হয়, রাশি হবে Libra বা তুলা,
১৬ নভেম্বর - ১৫ ডিসেম্বর হয়, রাশি হবে Scorpio বা বৃশ্চিক,
১৬ ডিসেম্বর - ১৫ জানুয়ারি হয়, রাশি হবে Sagittarius বা ধনু,
১৬ জানুয়ারি - ১৫ ফেব্রুয়ারি হয়, রাশি হবে Capricorn বা মকর,
১৬ ফেব্রুয়ারি - ১৫ মার্চ হয়, রাশি হবে Aquarius বা কুম্ভ,
১৬ মার্চ - ১৫ এপ্রিল হয়, রাশি হবে Pisces বা মীন।

Tûshar কিছুদিন হল রাশিচক্র সম্পর্কে জেনেছে। এখন সে সবাইকে তাদের জন্মতারিখ জিজ্ঞেস করে এবং এই তালিকা থেকে তার রাশি বের করে।

আপনাকে এমন একটি প্রোগ্রাম তৈরী করতে হবে যাতে তুষার একটি জন্মতারিখ ইনপুট হিসেবে দিলে, আউটপুট হিসেবে রাশির নাম পাবে।

ইনপুট

দিন-মাস-বছর এই ভাবে জন্মতারিখ ইনপুট দেওয়া হবে। যেমন, ০১ জানুয়ারি ২০০১ যদি কারো জন্মতারিখ হয় তাহলে ইনপুট হবে, 01-01-2001।

আউটপুট

নির্ভুল জন্মতারিখের জন্য উপরের তালিকায় দেওয়া রেঞ্জের রাশির নামটি আউটপুট দেওয়া হবে। যদি জন্মতারিখ ত্রুটিপূর্ণ হয় তাহলে আউটপুট হবে "Not Possible"।

sample input 1
15-09-1986

sample output 1
Leo

sample input 2
29-02-2016

sample output 2
Aquarius

sample input 3
31-09-1999

sample output 3
Not Possible


প্রব্লেম সেটার: হাসিবুল হাসান হাওলাদার

লিনিয়ার বা সিকোয়েন্সিয়াল সার্চ

লিনিয়ার বা সিকোয়েন্সিয়াল সার্চ একেবারে মৌলিক একটি সার্চ এলগোরিদম। নাম অনুযায়ীই এটি একটি ডেটা স্ট্রাকচারের উপাদানগুলিকে পর্যায় ক্রমে খুঁজে খুঁজে কাংক্ষিত উপাদানটি খুজে বের করে। অবিন্যস্ত ডেটা বা এমন ডেটা যা কোন নির্দিষ্ট ক্রমে সজ্জিত নয়, তার ক্ষেত্রে এটিই একমাত্র সার্চ টেকনিক তবে এটি বেশ সময় সাপেক্ষ।



লিনিয়ার সার্চের মূল ধারণাটি খুব সহজ। আমরা একদম প্রথম উপাদান থেকে খোজা শুরু করবো। এবং যতক্ষন কাংক্ষিত উপাদানটি খুজে পাওয়া না যায় ততক্ষণ খোজ চলতে থাকবে।
লিনিয়ার সার্চ

আমাদের পরিচিত ডেটা স্ট্রাকচার array দিয়েই আমরা উদাহরণটি দিই। ধরা যাক, ১২ টি ভিন্ন সংখ্যা একটি array তে রাখা আছে। আমরা এই array তে লিনিয়ার সার্চ চালিয়ে দেখবো যে এখানে 25 সংখ্যাটি আছে কি না। ধরি, এই array তে সংখ্যাটি নেই। সেই ক্ষেত্রে 0 নম্বর ইন্ডেক্স থেকে 11 নম্বর ইন্ডেক্স পর্যন্ত সার্চ চলবে।



আবার ধরা যাক একটি array তে ১৫ টি ইন্ডেক্স এ 1-15 পর্যন্ত সংখ্যাগুলো আছে। আমাদের সেখান থেকে 9 কে খুজে বের করতে হবে। এই ক্ষেত্রেও আমরা 0 নম্বর ইন্ডেক্স থেকে খোজা শুরু করবো, এবং 8 নম্বর ইন্ডেক্স পর্যন্ত সার্চ চালিয়ে গেলে আমরা আমাদের কাংক্ষিত সংখ্যা 9 খুজে পাবো।


আমাদের কাজের ধাপ হবেঃ

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

এইবার একটি সহজ কোড দেখি। ধরি array[20] একটি array যেখানে ২০ টি সংখ্যা আছে এবং আমাদের খুজে বের করতে হবে যে কত নম্বর ইন্ডেক্সে 75 সংখ্যাটি আছে।

#include<stdio.h>

int main()
{
    int i,array[20] = {2,3,5,6,33,45,6,34,57,55,75,89,4,6,7,86,54,32,99,78};

    for (i=0; i<20; i++)
    {
        if (array[i]==75)
        {
            printf("Found at index %d", i);
            break;
        }
     }
     if (i==20)
         printf("Not found in any index.");

    return 0;
}

একটি বাক্য থেকে শব্দ গণনা

ধরা যাক আমাদেরকে বলা হল যে, একটা ইংরেজি বাক্য দেওয়া আছে। আমাদের গুনে বের করতে হবে যে বাক্যটিতে কয়টি শব্দ আছে। আমরা চোখ দিয়ে তাকিয়ে শব্দ গুনে ফেলতে পারবো, কোন সমস্যা নয়। কিন্তু আমাদের যদি একটি প্রোগ্রাম লিখতে হয় এই গোনার কাজটি করার জন্য, তখন আমরা কি করব?

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

এইবার শব্দ খোজার পালা। আর এখানেই আমাদের দরকার লিনিয়ার বা সিকোয়েন্সিয়াল সার্চ সম্পর্কে ধারণা। যাদের এই ধারণাটা নাই তারা দয়া করে এখান থেকে পড়ে আসেন।

লিনিয়ার সার্চের মতই আমরা স্ট্রিং এর প্রথম ইন্ডেক্স থেকে খোজা শুরু করবো এবং শেষের নাল টার্মিনেটর ধারী ইন্ডেক্স পর্যন্ত খুঁজবো। এখন প্রশ্ন হল, আমরা কোন বৈশিষ্ট্য টা ধরে খুজবো? কিসের উপর ভিত্তি করে খুজলে আমরা শব্দের সঠিক সংখ্যা খুজে পাবো? আসুন আমরা একটা উদাহরণ দিই। ধরি,

I love you.

হল আমাদের ইংরেজি বাক্য। আমরা জানি বাক্যের ২ টি শব্দের মধ্যে একটি ফাকা স্থান বা blank স্পেস থাকে। কাজেই আমরা যদি ফাকা স্থানের সংখ্যা বের করি তাহলে শব্দ হিসাব করাটা কিছুটা সহজ হবে। যেমন, উপরের উদাহরণ এ ২ কি ফাকা স্থান আছে। আর, ব্যাকরণগত ভাবে সঠিক যে কোন বাক্যের শেষে একটি ফুলস্টপ থাকবে এবং তার আগে একটি শব্দ থাকবে। তাই স্পেস সংখ্যার সাথে ১ যোগ করলেই আমরা পেয়ে যাবো শব্দ সংখ্যা।

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

আমি একটি শর্ত সাজেস্ট করি।

১. আমরা একেবারে শুরুর ইন্ডেক্স থেকে গননা শুরু করবো না। আমরা ১ নম্বর ইন্ডেক্স থেকে গননা শুরু করবো।
২. আমরা তিনটা জিনিসের দিকে নজর রাখবো। স্পেস, স্পেশাল ক্যারেকটার আর নাল টার্মিনেটর।

৩. এদের যে কোন একটাকে খুঁজে পেলে চেক করে দেখবো যে তার আগের ইন্ডেক্সে একটি এলফাবেট বা নাম্বার আছে কি না। যদি এলফাবেট থাকে তাহলে আমরা ধরে নিবো যে একটা শব্দ (হিসাবে সুবিধার জন্য আমরা ধরে নিচ্ছি যে সংখ্যা বা সংখ্যাযুক্ত শব্দও শব্দ) আমরা পেয়ে গেছি। আর যদি তা না হয় তাহলে আমরা পরবর্তি ইন্ডেক্সে সার্চ চালিয়ে যাবো।

কাজেই আমাদের কোড এর গঠন হবে,

#include<stdio.h>
#include<ctype.h>

int main()
{
    char str[128],  ch; /* স্ট্রিং ধারণের জন্য array */
    int i, word=0;

    /* ইনপুট অংশ শুরু */
    for (i =0;;)
    {
        ch=getchar();
        if (ch=='\n')
        {
            str[i]='\0';
            break;
         }
         str[i++]=ch;
    }
    /* ইনপুট অংশ শেষ */

    /* সার্চ শুরু */
    for (i =1; ; i++)
    {
        if (str[i]==' '||ispunct(str[i])||str[i]=='\0') /* স্পেস, স্পেশাল ক্যারেকটার ও নাল টার্মিনেটর চেক */
        {
            if (isalnum(str[i-1])) /* আগের ক্যারেকটার টি এলফাবেট বা ডিজিট কি না সেটা চেক */
            word++;

            if (str[i]=='\0')
            break;
        }
    }
    printf("Number of words = %d", word);

    return 0;
}

দেখুন তো আপনারা চিন্তা করে অন্য একটি উপায় বের করতে পারেন কি না!!!

মৌলিক সংখ্যা : সংখ্যার মৌলিকতা পরীক্ষা

ড্রাফট পোস্টঃ


প্রাইম নাম্বার হল তারা যারা কেবল ১ এবং সেই নাম্বার দ্বারা নিঃশেষে বিভাজ্য। সহজ ও সুন্দর সংগা।



কাজেই আসো আমরা একটা নাম্বার প্রাইম কি না তা বের করার যৌক্তিক পদক্ষেপ গুলো নির্ধারণ করি।

ধারনা ১:

আমরা সংখ্যাটিকে প্রথমে ২ দিয়ে ভাগ করা শুরু করতে পারি। এরপর ৩, তারপর ৪, এভাবে সেই সংখ্যাটির আগ পর্যন্ত সকল সংখ্যা দ্বারা ভাগ করে দেখতে পারি যে কোন ভাগ শেষ আসে কি না। যেহেতু ১ দ্বারা সকল সংখ্যা বিভাজ্য এবং যেকোন সংখ্যাই সেই সংখ্যা দ্বারা বিভাজ্য তাই আমরা ২ থেকে শুরু করে সংখ্যাটির আগের সংখ্যা দ্বারা ভাগ করে দেখতে পারি।

কাজেই আমাদের ইনপুট নাম্বার যদি হয় n তাহলে আমরা 2 থেকে শুরু করে n-1 পর্যন্ত ভাগ করব। এই জন্য আমাদের for স্টেটমেন্ট হবে:

for (i =2; i <n;i++)
{
    flag=1;
    if(n%i==0)
    {
        flag=0;
        break;
    }
}

এরপরে আমরা খুব সহজেই flag এর ভ্যালু চেক করে বলতে পারব যে সংখ্যাটি প্রাইম কি না। কারণ আমরা প্রথমেই ধরে নিয়েছি যে flag এর ভ্যালু  ১ এবং সংখ্যাটি i এক কোন মান দ্বারা বিভাজ্য না হলে flag এর মান ১ ই থাকবে।

এই ধারনা দ্বারা ১ থেকে ৩৫০০০০ এর মধ্যেকার সকল প্রাইম নাম্বার (২৯৯৭৭ টি) বের করতে সময় লেগেছে ১১.৮৬ সেকেন্ড। (সময় নির্ধারণঃ ideone)

ধারণা ২:

আমরা ধারণা ১ কে একটু ঘষামাজা করি।
১০/১০=১, ১০/৫=২;
৮/৮= ১, ৮/৪=২;
..........................
n/n =1, n/(n/2)=2;

তাই কোন সংখ্যা তার অর্ধেকের বেশি মানের কোন সংখ্যা দ্বারা নিঃশেষে বিভাজ্য হতে পারে না।

তাই সেই সংখ্যার অর্ধেকের বেশি মানের কোন সংখ্যা দ্বারা তাকে ভাগ করা অর্থহীন।

কাজেই আমরা ২ দ্বারা ভাগ করা শুরু করব এবং সংখ্যাটির অর্ধেক মানের সংখ্যা দ্বারা ভাগ করেই থেমে যাবো। আমাদের for স্টেটমেন্ট হবে:

for(i =2; i <=n/2; i++)
{
    flag =1;
    if(n%i==0)
    {
        flag=0;
        break;
    }
}

ধারণা ২ তে আমাদের ভাগের কাজ হবে ধারণা ১ এর প্রায় অর্ধেক। এই যুক্তি ব্যবহার করে ১-৩৫০০০০ এর মধ্যেকার সব প্রাইম নাম্বার (২৯৯৭৭ টি) বের করতে সময় লেগেছে ৫.৯৪ সেকেন্ড। (সময় নির্ধারণঃ ideone)

ধারণা ৩:

আমরা ধারনা ২ কে আরো একটু স্লিম করার চেষ্টা করি। কেমন?

* সংগা অনুসারে ২ বাদে আর কোন জোড় প্রাইম নাম্বার থাকা সম্ভব না।
* একটি জোড় সংখ্যা সব সময়ই ২ দ্বারা বিভাজ্য
* একটি জোড় ও একটি বিজোড় সংখ্যার গুনফল সব সময়ই একটি জোড় সংখ্যা।

কাজেই কোন সংখ্যা যদি ২ দ্বারা বিভাজ্য না হয় তাহলে তাকে কোন জোড় সংখ্যা দ্বারা ভাগ করে দেখা অর্থহীন।

কাজেই, আমরা নাম্বারটিকে প্রথমে ২ দ্বারা ভাগ করে দেখব, এবং এর পরে যদি সংখ্যাটি ২ দ্বারা বিভাজ্য না হয় তাহলে শুধু বিজোড় সংখ্যা দ্বারা ভাগ করব। এবং অবশ্যই এই ভাগ চলবে সংখ্যাটির অর্ধেক মানে সংখ্যা পর্যন্ত।

কাজেই আমাদের লজিক হবে:


flag=1;
if (n==2)
    flag=1;
else if (n%2==0)
    flag=0;
else
    for (i = 3; i <=n/2; i += 2)
    {
        if(n%i==0)
        {
            flag=0;
            break;
        }
    }

ধারণা ৩ এ ভাগের কাজ হবে ধারণা ২ এর অর্ধেক। এই ধারনা ব্যবহার করে ১-৩৫০০০০ পর্যন্ত সব প্রাইম নাম্বার (২৯৯৭৭ টি) বের করতে সময় লেগেছে ২.৯৮ সেকেন্ড। (সময় নির্ধারণঃ ideone)

ধারণা ৪:

ইউক্লিড এর প্রস্তাবনা অনুসারে, যে কোন পূর্ণসংখ্যা হয় প্রাইম অথবা তার থেকে ছোট দুই বা ততোধিক প্রাইমের গুণফল। অর্থাৎ, যেকোন সংখ্যা তার চেয়ে ছোট একটি প্রাইম দ্বারা বিভাজ্য হবে যদি সেটি নিজে প্রাইম না হয়।

এখন একটা মজার জিনিস দেখি। ধরা যাক, ১০০ সংখ্যাটি প্রাইম কি না তা আমরা বের করবো। কাজেই ১০০ থেকে ছোট কোন প্রাইম দ্বারা যদি এটি বিভাজ্য না হয় তাহলেই এটি প্রাইম হবে। সবচে ছোট প্রাইম ২। ১০০/২=৫০। ৫০ এর কাছাকাছি প্রাইম হচ্ছে ৪৭। তাই ২ থেকে ৪৭ পর্যন্ত সংখ্যা দ্বারা যদি ১০০ বিভাজ্য না হয় তাহলেই ১০০ প্রাইম।

মজার জিনিসটা হচ্ছে, কোন সংখ্যা যদি প্রাইম না হয় তবে তা তার বর্গমূলের সমান বা তার চেয়ে ছোট কোন না কোন প্রাইম দ্বারা বিভাজ্য। আলোচ্চ্য ১০০ এর ক্ষেত্রে, ১০০ এর বর্গমূল ১০। তাই ২ থেকে ১০ এর মধ্যে কোন সংখ্যা দ্বারা যদি এটি বিভাজ্য না হয় তাহলেই এটি প্রাইম।

১০০ এর কাছাকাছি প্রাইমটি হচ্ছে ৯৭। ২, ৩, ৫, ৭  এই চারটি প্রাইমের কোনটি দ্বারাই ৯৭ বিভাজ্য নয়।

কাজেই,
আমরা যদি কোন সংখ্যার বর্গমূল বের করি এবং ২ থেকে শুরু করে সেই বর্গমূল পর্যন্ত সবগুলো সংখ্যা দিয়ে প্রদত্ত সংখ্যাটিকে ভাগ করে দেখি যে ভাগশেষ শূন্য নয়, তবেই সেটি প্রাইম নম্বর।

আমরা এখন ধারণা ৩ এর সাথে এই ধারণাটা যুক্ত করবো।

অর্থাৎ,


if (n==2)
    flag=1;
else if (n%2==0)
    flag=0;
else
{
    flag=1;
    m= (int) sqrt( (double) n);
    for (i = 3; i <=m; i+=2)
    {
        if (n%i==0)
        {
            flag=0;
            break;
        }
    }
}

এখন flag এর ভ্যালু চেক করলেই বোঝা যাবে যে n প্রাইম কি না।

এই ক্ষেত্রে সময় ধারনা ৩ এর চেয়েও কম লাগবে। এবং সেই কমটাও অনেক অনেক কম।

ধারণা ৪ ব্যবহার করে ১-৩৫০০০০ পর্যন্ত সবগুলো প্রাইম (২৯৯৭৭ টি) বের করতে সময় লেগেছে ০.০২ সেকেন্ড। (সময় নির্ধারণঃ ideone)

কারো ইচ্ছা থাকলে এই ধারণা ৪ টি ব্যবহার করে ১০০০০০ পর্যন্ত যতগুলো প্রাইম নম্বর আছে তা বের করে দেখতে পারো যে কোন ধারণায় কতটা সময় লাগে আউটপুট আসতে।

সার্চ পদ্ধতি সমূহ

তথ্য খুজে বের করা কম্পিউটার বিজ্ঞানের একটি অন্যতম গুরুত্বপূর্ণ কাজ। সাধারণত প্রাথমিক একটি তথ্য সরবরাহ করা হয়, যাকে 'key' বলা হয়, এবং তার সাথে সম্পর্কিত অন্যান্য তথ্য খুঁজে বের করতে হয়। এই কাজের জন্য প্রথমেই যে কাজটি করতে হয় তা হচ্ছে একটি তথ্য তালিকা থেকে খুঁজে দেখা হয় যে প্রদত্ত key টি উক্ত তালিকায় আছে কি না। কোন সিস্টেমে বিশাল আকারের ডেটা জমা থাকলে তা থেকে একটি নির্দিষ্ট তথ্য খুঁজে বের করার জন্য কি পদ্ধতি ব্যবহার করা হবে তা নির্ভর করে জমা রাখা মোট তথ্যের আকার ও বিন্যাসের উপর ভিত্তি করে। সার্চিং পদ্ধতি কখনো কখনো বেশ সরল আবার কখনো বা খুবই জটিল হয়ে থাকে।



কিভাবে ডেটা সাজানো আছে এবং কোন পদ্ধতিতে ডেটা সার্চ করা হচ্ছে, তার উপর প্রোগ্রামের পারফর্মেন্স অনেকাংশে নির্ভর করে। আজকের আলোচনায় আমরা মৌলিক কিছু সার্চ টেকনিক সম্পর্কে সাধারণ আলোচনা করবো।

সাধারণ সার্চ টেকনিক সমূহ

এই সার্চ টেকনিকগুলো সম্পর্কে জানা ও বোঝার জন্য array, relational operator, logical operator এবং C প্রোগ্রাম কন্ট্রোল স্টেটমেন্ট সমূহ সম্পর্কে জ্ঞান থাকতে হবে।

n সংখ্যক তথ্য বিশিষ্ট একটি তালিকার কথা কল্পনা করি যেখানে প্রত্যেকটি তথ্যই একটি key হতে পারে। আমাদের লক্ষ্য হবে এই তালিকা থেকে যে কোন একটি নির্দিষ্ট key কে যতটা কম সম্ভব সময়ের মধ্যে খুজে বের করা। একটি তালিকা থেকে এভাবে খুঁজে বের করার জন্য আমাদের সতর্কতার সাথে লক্ষ্য করতে হবে যে, তালিকাটিতে ডেটা কিভাবে সাজানো রয়েছে, অর্থাৎ কোন ধরনের ডেটা স্ট্রাকচার ব্যবহার করা হয়েছে। প্রাথমিক ভাবে আমাদের সবার পরিচিত array ডেটা স্ট্রাকচারে তথ্য রাখা হয়েছে বলেই ধরে নিই। array তে কোন তথ্য দুইভাবে সাজানো থাকতে পারে। সুবিন্যস্ত  (sorted) এবং অবিন্যস্ত (unsorted)। আমরা প্রথমে এই দুই ক্ষেত্রে কিভাবে সার্চ করা হবে সেটা দেখবো। সাজানোর পদ্ধতি বা সর্টিং টেকনিক সম্পর্কে আলোচনার জন্য এইখানে দেখুন।

লিনিয়ার সার্চ ও বাইনারী সার্চ



১. লিনিয়ার সার্চ বা সিকোয়েন্সিয়াল সার্চ


এই সার্চ পদ্ধতি একেবারেই সরল ও সোজাসুজি পদ্ধতি। একটি array এর প্রথম ইন্ডেক্স থেকে সার্চ শুরু করবো এবং যতক্ষন পর্যন্ত key এর সাথে মিল পাওয়া না যাবে ততক্ষণ সার্চ চালিয়ে যাবো। এই ক্ষেত্রে সর্বোচ্চ শেষ ইন্ডেক্স পর্যন্ত সার্চ করার প্রয়োজন হতে পারে, যদি key টি শেষ ইন্ডেক্সে থাকে অথবা key টি আদৌ array তে না থেকে থাকে।

বর্ণনা থেকেই বোঝা যাচ্ছে যে বড় ডেটার ক্ষেত্রে এটি মন্থর গতির সার্চ। তবে সময় সাপেক্ষ হলেও অবিন্যস্ত  array এর ক্ষেত্রে এটিই একমাত্র সরাসরি সার্চ টেকনিক। এই বিষয়ে বিস্তারিত জানার জন্য এখানে দেখুন।


২. বাইনারি সার্চ


সুবিন্যস্ত array এর ক্ষেত্রে এই সার্চ টেকনিক ব্যবহার করা যায়। ধরা যাক একটি array এর সকল তথ্য ঊর্ধ্বক্রমে সাজানো আছে। অর্থাৎ প্রথম ইন্ডেক্সে সবচে ছোট আর শেষ ইন্ডেক্সে সবচে বড় মানের তথ্যটি আছে। এইখানে সার্চ শুরু করা হয় array এর মধ্য ইন্ডেক্স থেকে। যদি মধ্য ইন্ডেক্সের তথ্যের মান key এর চেয়ে কম হয় তাহলে সার্চ করা হয় array এর ডান পাশের অর্ধেকের মধ্য ইন্ডেক্সটি। আর যদি মান key এর চেয়ে বেশি হয় তাহলে সার্চ করা হয় array এর বাম পাশের অর্ধেকের মধ্য ইন্ডেক্সটি।

এভাবে প্রতিবারে array এর সার্চ এলাকা অর্ধেক হতে থাকে। তাই এটি লিনিয়ার সার্চ অপেক্ষা দ্রুতগতির। তবে এটি কেবলমাত্র সুবিন্যস্ত তথ্যের ক্ষেত্রে কাজ করে। অবিন্যস্ত তথ্যের উপর বাইনারি সার্চ চালানোর জন্য তাকে প্রথমে বিন্যস্ত করে বা সর্ট করে নেবার দরকার পরে। বিস্তারিত জানার জন্যে এখানে দেখুন।

কিছু উচ্চতর সার্চ টেকনিক


নিম্নবর্ণিত সার্চ টেকনিক দুটি array অপেক্ষা জটিল ও উচ্চতর ডেটা স্ট্রাকচারে সার্চিং এর জন্য ব্যবহার করা হয়। এইগুলো ব্যবহারের পূর্বে হ্যাশ টেবিল, ট্রি, কিউ ইত্যাদি ডেটা স্ট্রাকচার সম্পর্কে সুস্পষ্ট ধারনা গ্রহন আবশ্যক।

৩. হ্যাশ সার্চ


হ্যাশ টেবিলে সার্চ করা খুবই দ্রুতগতির। key এর হ্যাশ ভ্যালু বের করে হ্যাশ ইন্ডেক্স সার্চ করতে থাকলেই দ্রুত তথ্য খুজে পাওয়া যায়, অথবা বোঝা যায় যে তথ্যটি তালিকাতে নেই।

বিস্তারিত জানার জন্য এখানে দেখুন।

৪. বাইনারি ট্রি সার্চ


বাইনারি ট্রি সার্চও হ্যাশ সার্চের মতই তবে এটি সাধারণত তুলনামূলক ভাবে মন্থর, বিশেষ করে যদি ট্রি এর সজ্জা ঠিকমতো ব্যালেন্স করা না থাকে।

ট্রির রুট থেকে সার্চ শুরু হয়। যদি রুটের ভ্যালু বড় হয় তাহলে বাম সাব ট্রিতে সার্চ করতে হবে আর যদি রুটের ভ্যালু ছোট হয় তাহলে ডান সাবট্রিতে সার্চ করতে হয়। এই উপায়ে ততক্ষণ সার্চ করতে হবে যতক্ষন পর্যন্ত না key খুজে পাওয়া না যায়, অথবা আর সাবট্রি অবশিষ্ট না থাকে।

বিস্তারিত জানার জন্য এখানে দেখুন।

C স্ট্রিং লাইব্রেরী : STRING.H

C হেডার ফাইল: string.h
C++ হেডার ফাইল: cstring.h


এই লাইব্রেরীতে C স্ট্রিং ও array ম্যানিপুলেশন এর জন্য কিছু ফাংশন ডিফাইন করা আছে। এছাড়াও, NULL ম্যাক্রো (null pointer) এবং size_t ডেটা টাইপও এই লাইব্রেরীতেই ডিফাইন করা। যদিও এই হেডার ছাড়াই এই ম্যাক্রো আর ডেটা টাইপ ব্যবহার করা যায়, তবে নিচে উল্লিখিত ফাংশনসমূহ ব্যবহারের জন্য অবশ্যই এই হেডার ব্যবহার করতে হবে।

ফাংশন সমূহঃ

কপি ফাংশন:


  • memcpy : একটি মেমরি ব্লকে যা আছে তা অন্য একটি মেমরি ব্লকে কপি করার জন্য
  • memmove : একটি মেমরি ব্লকে যা আছে তা অন্য একটি মেমরি ব্লকে সরিয়ে নেওয়ার জন্য
  • strcpy : সম্পূর্ণ স্ট্রিং কপি করার জন্য
  • strncpy : স্ট্রিং থেকে নির্দিষ্ট সংখ্যক ক্যারেকটার কপি করার জন্য


সংযুক্তিকরণ (concatenation) ফাংশনঃ


  • strcat : দুটি পূর্ণাঙ্গ স্ট্রিংকে যুক্ত করার জন্য
  • strncat : একটি স্ট্রিং এর সাথে অপর একটি স্ট্রিং এর নির্দিষ্ট সংখ্যক ক্যারেকটার যুক্ত করার জন্য


তুলনাকরণ (Comparison) ফাংশন:


  • memcmp : দুটি মেমরি ব্লকের মধ্যে তুলনা করার জন্য 
  • strcmp : দুটি পূর্ণাঙ্গ স্ট্রিং এর মধ্যে তুলনা করার জন্য
  • strcoll : দুটি পূর্ণাঙ্গ স্ট্রিং এর মধ্যে তুলনা করার জন্য (locale ব্যবহার করে)
  • strncmp : দুটি সস্ট্রিং এর নির্দিষ্ট সংখ্যক ক্যারেকটার এর মধ্যে তুলনা করার জন্য
  • strxfrm : locale ব্যবহার করে স্ট্রিং এর রূপান্তর এর জন্য


সার্চিং ফাংশনঃ


  • memchr : কোন একটি মেমরি ব্লকে একটি নির্দিষ্ট ক্যারেকটার এর অবস্থান বের করার জন্য
  • strchr : কোন স্ট্রিং এ একটি নির্দিষ্ট ক্যারেকটার এর প্রথম আবির্ভাবের অবস্থান বের করার জন্য
  • strcspn : কোন একটি স্ট্রিং এর শুরু থেকে একটি নির্দিষ্ট ক্যারেকটার পর্যন্ত দৈর্ঘ্য বের করার জন্য
  • strpbrk : কোন স্ট্রিং এ একাধিক ক্যারেকটার এর অবস্থান বের করার জন্য
  • strrchr : কোন স্ট্রিং এ কোন নির্দিষ্ট ক্যারেকটার এর সর্বশেষ আবির্ভাবের অবস্থান বের করার জন্য
  • strspn : কোন স্ট্রিং এএর শুরু থেকে একটি নির্দিষ্ট ক্যারেকটার সমাবেশ পর্যন্ত দৈর্ঘ্য বের করার জন্য
  • strstr : সাব স্ট্রিং (substring) এর প্রথম অবস্থান বের করার জন্য
  • strtok : একটি স্ট্রিং কে ক্ষুদ্র ক্ষুদ্র অংশে বিভক্ত করার জন্য


অন্যান্যঃ


  • memset : একটি মমেমরি ব্লক একটি নির্দিষ্ট ক্যারেকটার কন্সট্যান্ট দ্বারা পূর্ণ করার জন্য
  • strerror : এরর মেসেজ এর প্রতি পয়েন্ট করা পয়েন্টার লাভের জন্য
  • strlen : একটি স্ট্রিং এর দৈর্ঘ্য বের করার জন্য

CECP015 - রেজাল্ট শীট


একটি রেজাল্ট শীট তৈরী করতে হবে যেখানে স্টুডেন্ট এর নাম এবং এক অথবা এক এর অধিক সাবজেক্ট নম্বর ইনপুট নিবে।

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

ইনপুট

প্রথম লাইন এ দুইটি সংখ্যা ইনপুট হবে যার প্রথম টি স্টুডেন্ট সংখ্যা এবং দ্বিতীয়টি সাবজেক্ট সংখ্যা। তারপরের স্টুডেন্ট সংখ্যক লাইনে, স্টুডেন্ট নাম ও একটি করে স্পেস দিয়ে নাম্বার ইনপুট হবে। স্টুডেন্ট সংখ্যা ১ থেকে ১০০০ এবং সাবজেক্ট সংখ্যা ১ থেকে ১৫ হতে পারে।

আউটপুট

যতগুলো স্টুডেন্ট আছে তাদের জন্য আলাদা আলাদা লাইন হবে। প্রতিটি লাইন এ একটি করে স্টুডেন্ট এর নাম তারপর একটি করে স্পেস রেখে, সাবজেক্ট নাম্বার এবং সবশেষে সেই স্টুডেন্ট এর প্রাপ্ত নম্বর এর যোগফল।

প্রব্লেম সেটার: সাগর সরকার



C এর উপাদান সমূহঃ ভ্যারিয়েবল

C প্রোগ্রামিং কে যদি রান্না বান্নার সাথে তুলনা করি তাহলে ভ্যারিয়েবল আর ফাংশন হল বাটি, কড়াই, চুলা এইসব।

ভ্যারিয়েবল প্রায় আক্ষরিক অর্থেই বাটির মত। বাটিতে যেমন কিছু রাখা যায়, ঠিক তেমনি ভ্যারিয়েবল এও কোন না কোন ডেটা রাখা যায়।

"ডেটা জমা রাখা এবং প্রয়োজনের সময় সেই ডেটা ব্যবহারের জন্য সরবরাহ করাই ভ্যারিয়েবল এর কাজ"।

ভ্যারিয়েবল এর কিছু বৈশিষ্ট্য নিম্নরূপঃ

* ভ্যারিয়েবল এর একটা নাম থাকতে হয়। নাম করনের উদ্দেশ্য হল, কোন ডেটা কোন ভ্যারিয়েবল এ আছে তা বুঝানো। ভ্যারিয়েবল এর নাম করনের কিছু নিয়ম আছে যা সামনে আলোচনা করা হবে। এখন এইটুকুই জেনে রাখা হোক যে ভ্যারিয়েবল এর নাম থাকা আবশ্যক।

* ভ্যারিয়েবল এর একটা ডেটা টাইপ থাকতে হয়। কমন সেন্স ব্যবহার করলেই এইটা বোঝা যায়। চুলায় পানি গরম করার জন্য যেমন প্লাস্টিকের বাটি ব্যবহার যায় না, ঠিক তেমনি এক ডেটা টাইপের ভ্যারিয়েবলে অন্য ডেটা টাইপ নিয়ে কাজ করা যায় না। যে ডেটা টাইপের ডেটা নিয়ে কাজ করতে হবে, সেই ডেটা টাইপের ভ্যারিয়েবল ডিক্লেয়ার করতে হবে।

* ভ্যারিয়েবল ডিক্লেয়ার ও ডিফাইন করার পর ভ্যারিয়েবলটির জন্য মেমরিতে একটি জায়গা নির্ধারণ করে দেওয়া হয়, যে জায়গায় ডেটা টাইপ অনুযায়ী ডেটা জমা রাখা যায়।

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

* কম্পিউটার এর মেমরিতে প্রত্যেকটি বাইট (byte) এর একটি ঠিকানা থাকে, যাকে মেমরি এড্রেস বলে। যেহেতু ডিক্লেয়ারেশন এর পরে ভ্যারিয়েবল এর জন্য মেমরিতে জায়গা নির্ধারণ করা হয় তাই সেই জায়গারও একটি ঠিকানা বা মেমরি এড্রেস থাকবে। কোন ভ্যারিয়েবল এর জন্য নির্ধারিত স্থান এর ঠিকানাকে সেই ভ্যারিয়েবল এর মেমরি এড্রেস বলে। ভ্যারিয়েবল এর নামে আগে '&' চিহ্নটি ব্যবহার করে ভ্যারিয়েবল এর মেমরি এড্রেস বুঝানো হয়। যেমন: ধরা যাক number একটি ইন্টিজার টাইপের ভ্যারিয়েবল। কাজেই কম্পিউটার মেমরিতে এই ভ্যারিয়েবল এর ঠিকানা হবে &number।

* ভ্যারিয়েবল এর ধরন নির্ধারণ করা একটু কঠিন। কারন এর সর্বজন স্বীকৃত কোন প্রকারভেদ নাই। তবে শেখার সুবিধার জন্য নিচের শ্রেণীবিভাগ মনে রাখা যেতে পারে:

১. একক সাধারণ ভ্যারিয়েবলঃ মৌলিক ডেটা টাইপ দিয়ে ডিক্লেয়ার করা একক ভ্যারিয়েবল সমূহ।

২. সাধারণ ভ্যারিয়েবল এর সমাবেশঃ মৌলিক ডেটা টাইপ দিয়ে ডিক্লেয়ার করা array

৩. বিশেষ একক ভ্যারিয়েবলঃ পয়েন্টার ভ্যারিয়েবল

৪. বিশেষ ভ্যারিয়েবল এর সমাবেশঃ পয়েন্টার array, স্ট্রাকচার ভ্যারিয়েবল, ইউনিয়ন

কম্পিউটার এ যে কোন ডেটাই কম্পিউটার এর মেমরির একটি নির্দিষ্ট ঠিকানায় থাকে। ডেটার ধরণ যাই হোক না কেন ঠিকানাটি সব সময়ই একটি সংখ্যা। অনেক সময় এটি অনেক বড় একটি সংখ্যা। তাই এটি মনে রাখা ও ব্যবহার করা বেশ অসুবিধাজনক। সেই জন্যেই ভ্যারিয়েবল ব্যবহার করা হয়।

ভ্যারিয়েবল হচ্ছে কম্পিউটার এর মেমরিতে একটি নির্দিষ্ট স্থানের নাম যেখানে আমরা কোন ডেটা জমা রাখতে পারি। অর্থাৎ,
** ভ্যারিয়েবল হচ্ছে একটি নাম
** ভ্যারিয়েবল এ ডেটা জমা রাখা যায়।

যেহেতু ভ্যারিয়েবল একটি নাম, সেহেতু এর নাম করনের কিছু নিয়ম কানুন আছে। কিছু নিয়ম পালন করা বাধ্যতামূলক, কিছু নিয়ম হচ্ছে নামটিকে অধিক গ্রহণযোগ্য করে তোলার জন্য। ☺☺☺

প্রথমেই বাধ্যতামূলক নিয়মগুলো জেনে নিই।

১। ভ্যারিয়েবল এর নাম রাখার জন্য আলফা-নিউমেরিক ক্যারেকটার সমূহ ও স্পেশাল ক্যারেক্টার এর মধ্যে শুধুমাত্র আন্ডার স্কোর '_' ব্যবহার করা যাবে। অর্থাৎ নামে লেটার, নাম্বার ও আন্ডার স্কোর ছাড়া অন্য কিছু ব্যবহার করা যাবে না।

২। শুধু লেটার দিয়ে নামকরন করা গেলেও, শুধু নাম্বার দিয়ে ভ্যারিয়েবল এর নাম রাখা যাবে না। লেটার ও নাম্বার মিলিয়ে নাম রাখা যাবে, তবে সেই ক্ষেত্রে নামটি নাম্বার দিয়ে শুরু হতে পারবে না। যেমন,

asdf রাখা যাবে, কিন্তু 1234 রাখা যাবে না; আবার as12 রাখা যাবে কিন্তু 12as রাখা যাবে না।

৩। আন্ডার স্কোর দিয়ে নাম শুরু করা যাবে। যেমন,

_asdf রাখা যাবে, _12as রাখা যাবে;

৪। ভ্যারিয়েবল এর নাম করনে কোন প্রকার স্পেস ব্যবহার করা যাবে না। যেমন,

student info নামটি ভ্যালিড নাম নয়। বোধগম্য করা জন্য যদি কোন সেপারেটর ব্যবহার করতে হয় তাহলে আন্ডার স্কোর ব্যবহার করা যাবে। যেমন,

student_info একটি ভ্যালিড ভ্যারিয়েবল এর নাম।

৫। নামের দৈর্ঘ্য সর্বোচ্চ কত হতে পারবে তা কম্পাইলার এর উপর নির্ভর করবে। তবে স্ট্যান্ডার্ড অনুযায়ী কম্পাইলারের ৩১ অক্ষর পর্যন্ত কমপক্ষে সাপোর্ট করার কথা।

এইবার আসি নামকে অধিক ব্যবহার উপযোগী করে তোলার কিছু নিয়ম। এগুলো বাধ্যতামূলক নয়।

৬। নাম যথাসম্ভব সংক্ষিপ্ত হলে ভাল হয়। এতে ভ্যারিয়েবলকে বার বার লিখা সহজ হয়।

৭। নামকে প্রাসঙ্গিক করলে কোডে তার প্রয়োগ বোঝা সহজ হয়।

৮। যদিও নাম সম্পূর্ণ ছোট হাতের অক্ষর, সম্পূর্ণ বড় হাতের অক্ষর বা মিশ্র হতে পারে, তবুও সম্পূর্ণ বড় হাতের অক্ষরে না রাখাই ভাল। প্রচলিত প্রথা অনুযায়ী সম্পূর্ণ বড় হাতের অক্ষরে নাম রাখা হয় প্রিপ্রসেসর ডিরেক্টিভ #define দিয়ে ডিফাইন করা জিনিসের। তবে, রাখলে কোন ভুল হবে না।


বিশেষ বিশেষ ভ্যারিয়েবল এর ক্ষেত্রে আরো কিছু নিয়ম কানুন আছে। যেমনঃ

→ array ভ্যারিয়েবল এর নাম এর সাথে [ ] থাকে। এই ব্র‍্যাকেট এর মধ্যে array এর ইন্ডেক্স সংখ্যা থাকে। কাজেই একটি array যার নাম number এবং যার ইন্ডেক্স সংখ্যা ১০, তার পুরো নামটি হয় number[10]। আবার এই array তেই যদি ৫ নম্বর ইন্ডেক্সটিকে আমরা চিহ্নিত করতে চাই তাহলে তার নাম হবে number[5]। এইক্ষেত্রে মনে হতে পারে যে ভ্যারিয়েবল এর নাম করনের সময় [ ] কেও নামে রাখা হয়েছে। কিন্তু আসলে ব্যাপারটা সে রকম নয়।

→ pointer এর নাম রাখার সময় নামের আগে * যোগ করা হয়। যেমন, পয়েন্টার p এর নাম লিখার সময় লিখা হয় *p। এখানে তার নাম p এবং * দ্বারা বোঝানো হয় যে এটি একটি পয়েন্টার।

ডেটা টাইপ পোস্টটা যারা পড়েছেন তারা দেখেছেন যে C ভাষায় কোন ডেটাকে পাচটি মৌলিক ডেটা টাইপ বা তাদের থেকে উদ্ভূত বা লব্ধ কোন একটা ডেটা টাইপের অন্তর্ভুক্ত হিসেবে চিন্তা করা হয়। এটি প্রোগ্রামিং এর কাজকে অনেক সাবলীল করে তোলে।

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

ভ্যারিয়েবল এর নাম করনের সাথে সাথেই তার ডেটা টাইপও উল্লেখ করতে হয়।

অনেকটা চাইনিজ বা জাপানিজ দের নাম রাখার মত। জানেন তো যে তাদের নামের প্রথম অংশটা তাদের বংশের নাম?

আজকে আমরা যেটা জানবো সেটা হচ্ছে ভ্যারিয়েবল ডিক্লেয়ারেশন, ইনিশিয়ালাইজেশন ও ডেফিনিশন।

ভ্যারিয়েবল ডিক্লেয়ারেশন হচ্ছে একটি ঘোষনার মাধ্যমে জানিয়ে দেওয়া যে, অমুক ডেটা টাইপের অমুক নামের একটি ভ্যারিয়েবল তৈরী করা হল। ডিক্লেয়ার করার নিয়ম হচ্ছে,

data_type variable_name;

তারমানে হচ্ছে যদি আমরা number নামের একটি ইন্টিজার টাইপের ভ্যারিয়েবল ডিক্লেয়ার করতে চাই, তাহলে আমাদের ডিক্লেয়ারেশন স্টেটমেন্ট হবে,

int number;

সহজ, তাই না?

একই ধরনের কয়েকটি ভ্যারিয়েবলকে একবারে ডিক্লেয়ার করা যায়। এই ক্ষেত্রে ডেটা টাইপের নামের পরে স্পেস দিয়ে ভ্যারিয়েবল এর নাম সমূহ কমা দিয়ে আলাদা করে লিখতে হয়। যেমন, কারো সিজিপিএ একটি দশমিক সংখ্যা। যদি প্রথম সেমিস্টার এর জিপিএ কে first_gpa, ফাইনাল সেমিস্টার এর জিপিএ কে final_gpa, আর গড় জিপিএ কে cgpa নামের ভ্যারিয়েবলে রাখতে চাই, তাহলে সহজেই এই ডিক্লেয়ারেশন স্টেটমেন্ট লিখা যায়,

float first_gpa, final_gpa, cgpa;

এই স্টেটমেন্ট দ্বারা একই সাথে তিনটি ফ্লোটিং পয়েন্ট টাইপের ভ্যারিয়েবল ডিক্লেয়ার করা হয়ে গেলো।

C স্ট্যান্ডার্ড এ কোন কোড ব্লকের শুরুতে ভ্যারিয়েবলকে ডিক্লেয়ার করতে বলা হয়েছে। এই বাক্যটার মানে কি এবং তা কতটুকু মানতে হয় তা আমরা আস্তে আস্তে শিখবো। আপাতত আমরা এইটুকুই জেনে নিই যে প্রোগ্রামের মেইন ফাংশনের শুরুতেই আমরা ভ্যারিয়েবল ডিক্লেয়ারেশন এর কাজটা করে ফেলবো।

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

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

যেমনঃ number নামের একটি ইন্টিজার ভ্যারিয়েবলকে ডিক্লেয়ার করে তাতে প্রাথমিক ভাবে 0 জমা রাখার জন্য স্টেটমেন্ট গুলো হবেঃ

int number; //ডিক্লেয়ারেশন স্টেটমেন্ট
number = 0; // ইনিশিয়ালাইজেশন

'=' কে বলা হয় এসাইনমেন্ট অপারেটর যা সম্পর্কে পরবর্তিতে আলোচনা করা হবে। এখন এইটুকুই জেনে রাখা ভাল যে,

= চিহ্নের বাম পাশে ভ্যারিয়েবল রেখে আর ডানপাশে মানানসই ডেটা রেখে সেমিকোলন দিয়ে স্টেটমেন্ট শেষ করলেই ডেটা টি ঐ ভ্যারিয়েবল এ জমা হয়ে যায়। = চিহ্নের বামে ভ্যারিয়েবল ছাড়া অন্য কিছু থাকতে পারবে না।

ইনিশিয়ালাইজ কেন করা হয় তা যখন দরকার পড়বে তখনই বুঝতে পারবে। তবে এখন এইটুকুই জেনে রাখা দরকার যে,

ডিক্লেয়ারেশন এর পর পরই ভ্যারিয়েবল কে ইনিশিয়ালাইজ করার অভ্যাস থাকা ভাল।

আমরা চাইলে একই সাথে ডিক্লেয়ারেশন ও ইনিশিয়ালাইজেশন করতে পারি। এবং বাস্তবে সেটাই করা হয় সাধারণত। সেটা করা হয় এই ভাবে।

int number;
number=0;

এর পরিবর্তে একবারে লেখা হয়,

int number=0;

এই স্টেটমেন্ট এ প্রথমে number নামে একটি ভ্যারিয়েবল ডিক্লেয়ার হয়েছে, তারপর তাতে 0 জমা রাখা হয়েছে।

একই সাথে ডিক্লেয়ারেশন আর ইনিশিয়ালাইজেশন করাকেই ডেফিনিশন বলা হয়ে থাকে।

C এর উপাদান সমূহঃ ক্যারেকটার সেট ও ডেটা টাইপ

আর সব ভাষার মত C প্রোগ্রামিং ল্যাংগুয়েজও একটি ভাষা। কাজেই এর বর্ণমালা, সংখ্যা ও যতিচিহ্ন থাকবে এটাই স্বাভাবিক। C রোমান বর্ণমালা, যতিচিহ্ন  ও আরবী সংখ্যা পদ্ধতি ব্যবহার করে। 😜😜😜

C ভাষায় প্রোগ্রাম লিখতে হলে a থেকে z পর্যন্ত অক্ষর, 0 থেকে 9 পর্যন্ত অংক আর সচরাচর ব্যবহৃত যতিচিহ্ন সমূহকে ব্যবহার করা যায়। তবে অক্ষরের চেয়ে ব্যাকরণই বিভিন্ন ভাষার মধ্যে পার্থক্য তৈরী করে। কাজেই ইংরেজিতে ব্যবহৃত অক্ষর ও সংখ্যা C ভাষায় ব্যবহৃত হলেও তাদের প্রয়োগ আলাদা এবং C ভাষার নিজস্ব।

C তে প্রোগ্রামিং করার জন্য ৩ ধরনের ক্যারেকটার ব্যবহার করা যায়। ১) আলফা-নিউমেরিক ২) স্পেশাল ক্যারেক্টার বা যতিচিহ্নাদি ও ৩) ফাকা স্থান। আলফা-নিউমেরিক ক্যারেকটার আবার দুই ধরনের। a) alphabet বা বর্ণমালা ও b) ডিজিট বা অংক। তাহলে আমরা C ভাষায় ব্যবহারের জন্য ৪ ধরনের ক্যারেকটার পেলাম।

¢ Alphabet: a-z ও A-Z পর্যন্ত
¢ Digits: 0-9 পর্যন্ত
¢ Special Characters : .,! " ' : ;? % & () {} []= ইত্যাদি
¢ white space: space, TAB, new line (\n) ইত্যাদি

এই সব দিয়ে প্রোগ্রাম লিখা হয়। কিন্তু একটি প্রোগ্রামে আসলে কি লিখা হয়? কি কাজ করা হয়?

একটি C প্রোগ্রাম, প্রোগ্রামারের লক্ষ্য অনুযায়ী কম্পিউটার কে বিভিন্ন কাজ করার নির্দেশনা দেয়। আর এতে প্রোগ্রামার ও কম্পিউটার এর মধ্যে তথ্যের আদান প্রদান হয়। তথ্যের ক্ষুদ্র ক্ষুদ্র অংশকে ডেটা বলা হয়।

কাজেই দেখতে পাচ্ছি যে C প্রোগ্রামিং এর অর্থই হচ্ছে ডেটা নিয়ে কাজ করা। C প্রোগ্রামে ডেটাকে তিন উপায়ে শ্রেণীবদ্ধ করা হয়।

১। মৌলিক বা Fundamental শ্রেণীকরণঃ এই শ্রেনীতে 5 ধরনের ডেটা আছে। এই ধরনগুলোকে মৌলিক ডেটা টাইপ বলে। এরা হচ্ছেঃ

** ক্যারেকটার ডেটা: একে কিওয়র্ড char দ্বারা নির্দেশ করা হয়। C ভাষার ব্যবহৃত সকল ক্যারেকটারই char শ্রেনীর অন্তর্ভূক্ত।

** ইন্টিজার ডেটাঃ একে কিওয়র্ড int দ্বারা নির্দেশ করা হয়। শুন্য সহ সকল ধনাত্মক ও ঋণাত্মক পূর্ণসংখ্যা এই শ্রেণীভুক্ত।

** ফ্লোটিং পয়েন্ট ডেটাঃ একে কিওয়র্ড float দ্বারা নির্দেশ করা হয়। ৬ দশমিক স্থান পর্যন্ত সকল ধনাত্মক ও ঋণাত্মক সংখ্যা এই শ্রেনী ভুক্ত।

** ডাবল প্রিসিশান ফ্লোটিং পয়েন্ট ডেটাঃ একে কিওয়র্ড double দ্বারা নির্দেশ করা হয়। ১৪ দশমিক স্থান পর্যন্ত সকল ধনাত্মক ও ঋণাত্মক সংখ্যা সঠিক ভাবে হিসাব করার জন্য এই শ্রেনী।

** ভয়েড (void) ডেটাঃ একে কিওয়র্ড void দ্বারা নির্দেশ করা হয়। যে ধরনের ডেটা উপরের কোন শ্রেনীতেই পড়ে না, তারা এই শ্রেণীভুক্ত। মূলতঃ ফাংশনের রিটার্ন টাইপ ছাড়া এই ডেটা টাইপ ব্যবহৃত হয় না।

২। উদ্ভূত বা লব্ধ বা derived শ্রেণীকরণঃ মৌলিক ডেটা টাইপ গুলো থেকেই এই শ্রেনীর ডেটা টাইপের উৎপত্তি। কাজেই এদের নাম ও কাজ মৌলিক ডেটা টাইপ হতে আলাদা হলেও এরা মূলত তাদেরই পরিবর্তিত রূপ। যেমনঃ

** Array
** String বা NULL terminated Character Array
** Pointer
** Function ইত্যাদি

৩। প্রোগ্রামারের নিজের তৈরী বা user-defined শ্রেণী: এই শ্রেনীতে সেই সব ডেটা টাইপ রয়েছে যাদেরকে প্রোগ্রামার নিজের প্রয়োজনে মৌলিক ও লব্ধ ডেটা টাইপের উপর ভিত্তি করে নিজেই তৈরী করেছেন। কাজেই দেখা যাচ্ছে এরাও আসলে মৌলিক ডেটা টাইপেরই পরিবর্তিত রূপ মাত্র। যেমনঃ

** Structure
** union
** enumerations ইত্যাদি।

Data type যে কোন প্রোগ্রামিং ল্যাংগুয়েজ এর অত্যন্ত গুরুত্বপূর্ণ একটি বিষয়।

ভয়েড ছাড়া বাকি চারটি মৌলিক data type দ্বারাই variable 'declare' করা যায়। Variable ডিক্লেয়ারেশন এর সাথে সাথে কম্পাইলার কম্পিউটার এর মেমোরিতে variable এর জন্য জায়গা নির্ধারণ করে।

Data type এখানেই গুরুত্বটা বহন করে। এক এক ডেটা টাইপের ডেটা মেমরিতে রাখতে এক এক রকম জায়গা লাগে। Data type ই কম্পাইলারকে বলে দেয় যে কোন variable এর জন্য ঠিক কতটুকু জায়গা মেমোরিতে নির্দিষ্ট করে রাখা হবে।

যেমন ১ টি ক্যারেকটার রাখতে যতটুকু জায়গা লাগে, ১ টি ইন্টিজারের জন্য তার থেকে বেশি পরিমান জায়গা লাগে। আবার ফ্লোটিং পয়েন্ট ডেটার জন্য আরো বেশি জায়গা লাগে।

ANSI স্ট্যান্ডার্ড অনুযায়ী যে কোন কম্পাইলারকে
কমপক্ষে
char এর জন্য 8 bit বা 1 byte,
int এর জন্য 16 bit বা 2 byte,
float এর জন্য 32 bit বা 4 byte,
এবং
double এর জন্য 64 bit বা 8 byte

জায়গা মেমোরিতে নির্দিষ্ট করে রাখতে হবে। এইটা কমপক্ষে রাখতে হবে, তার মানে যদি কোন অপারেটিং সিস্টেম অনুমতি দেয় তাহলে কম্পাইলার ইচ্ছা করলে একটা নির্দিষ্ট data type এর জন্য ANSI স্ট্যান্ডার্ড এর চেয়ে বেশি জায়গাও বায়না করতে পারে।

যেমন 32-bit ও 64-bit অপারেটিং সিস্টেমে কম্পাইলার int type এর variable এর জন্য 32 bit বা 4 byte জায়গা রাখে।

কাজেই আমরা দেখতে পাচ্ছি যে, একই data type এর অবস্থা একেক অপারেটিং সিস্টেম বা কম্পাইলার এ একেক রকম। এই জন্য আমরা যে প্রোগ্রামিং এনভায়রনমেন্ট এ কাজ করব সেই এনভায়রনমেন্ট এ কোন Data type এর size কত তা জানাটা জরুরী হয়ে পরে।

এই জন্য sizeof অপারেটর ব্যবহার করা হয়।

sizeof অপারেটর একটি কম্পাইল টাইম অপারেটর। এটি প্রোগ্রাম কম্পাইল করার সময়ই কাজ করে ঐ এনভায়রনমেন্ট এ কোন ডেটা টাইপের সাইজ কত তা বের করে। যেমন নিচের কোডটি আপনার সিস্টেমে কম্পাইল করে সহজেই আপনি জেনে নিতে পারেন যে আপনার সিস্টেমে কোন ডেটা টাইপের সাইজ কতঃ

#include<stdio.h>

int main()
{

 printf("Size of Different data types in this system:\n\n");
 printf("Data Type\tSize\n\n");
 printf("char\t\t%d-bits/%d byte\n", 8*sizeof(char), sizeof(char));
 printf("int\t\t%d-bits/%d byte\n", 8*sizeof(int), sizeof(int));
 printf("float\t\t%d-bits/%d byte\n", 8*sizeof(float), sizeof(float));
 printf("double\t\t%d-bits/%d byte", 8*sizeof(double), sizeof(double));
 return 0;
}

টেস্ট কেস : ইহা কি এবং ইহার কাজ কি?

কম্পিটিটিভ প্রোগ্রামিং এ যারা আমার মত নতুন তারা একটা জিনিস সহজে বুঝতে পারেন না আর সেটা হল Test Case।

টেস্ট কেস জিনিসটা খুব ঝামেলার কিছু না। আপনাকে প্রব্লেম স্টেটমেন্ট এ যে সমস্যাটা সমাধান করতে বলেছে সেটাই মোট কতগুলো ইনপুট দিয়ে চেক করা হবে, সেটা হল টেস্ট কেস সংখ্যা। একটা উদাহরণ দেওয়া যাক।

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

মোট কথা, টেস্ট কেস সংখ্যা হচ্ছে কত গুলো ইনপুট এর জন্য প্রোগ্রামটা টেস্ট করে দেখা হবে সেটা। টেস্ট কেসের সমান সংখ্যক ইনপুট ও আউটপুট হবে।

মূলত যে সব প্রব্লেমে টেস্ট কেসের কথা থাকে তার ক্ষেত্রে প্রোগ্রামের একেবারে শুরুতেই, ভ্যারিয়েবল ডিক্লেয়ারেশন এর পরেই টেস্ট কেস সংখ্যা ইনপুট নিতে হয়। এর পর একটা লুপের মধ্যে মূল সমস্যাটার ইনপুট,  সমাধান ও আউটপুট করতে হয়। এই লুপটা টেস্ট কেস সংখ্যার সমান সংখ্যক বার চলবে। উপরের যোগের সমস্যাটা যদি আমরা কোডিং করি তাহলে দেখা যাবে যেঃ

#include<stdio.h>

int main()
{
    int a, b, i, sum, T;

    scanf("%d", &T); /* টেস্টকেস ইনপুট নেওয়া হল*/

    for (i =1; i <=T; i++) /* টেস্ট কেসে লুপ */
    {
/* মূল সমস্যার কাজ শুরু এখানে */
        scanf("%d%d", &a, &b);
        sum= a+b;
        printf("%d\n", sum);
/* মূল সমস্যার কাজ শেষ এখানে */
    }
    return 0;
}

এই কাজটা while স্টেটমেন্ট দিয়েও করা যায়। যেমন,
#include<stdio.h>

int main()
{
    int a, b, sum, T;

    scanf("%d", &T); /* টেস্টকেস ইনপুট নেওয়া হল*/

    while (T--) /* টেস্ট কেসে লুপ */
    {
/* মূল সমস্যার কাজ শুরু এখানে */
        scanf("%d%d", &a, &b);
        sum= a+b;
        printf("%d\n", sum);
/* মূল সমস্যার কাজ শেষ এখানে */
    }
    return 0;
}

কাজেই টেস্ট কেস এর জন্য আমাদের একটা লুপ নিতে হবে যার মধ্যে প্রব্লেম স্টেটমেন্ট এ উল্লিখিত সমস্যার সমাধান এর কোড (ইনপুট, প্রসেসিং এবং আউটপুট)  থাকবে।

আশা করি এবার অনুশীলন করার মত জ্ঞান সবার হয়েছে। কয়েকবার অনুশীলন করলেই ব্যাপার টা পরিষ্কার হয়ে যাবে।