Showing posts with label Standard Template Library (STL). Show all posts
Showing posts with label Standard Template Library (STL). Show all posts

Thursday, June 28, 2018

Next Permutation

পার্মুটেশন কাকে বলে বা পার্মুটেশন কি সেটি বিস্তারিত জানার জন্য উইকির এই লিংকে  ঢুঁ দিয়ে এসো-

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

STL ব্যবহার করে পার্মুটেশনের সিউডো কোড এই রকম-

    do
    {
       //Here write code as your requirements          
    }while(next_permutation(a, a+n));


Code:  
/*  Next Permutation */

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    char a[3]={'a','b','c'};
    do
    {
        for(int i=0; i<3; i++)
        {
            printf("%c ", a[i]);
        }
        printf("\n");
    }while(next_permutation(a,a+3));
    return 0;
}


Reverse (Vector, String, Array)

মনেকর, প্রোগ্রামিং প্রতিযোগিতায় তোমাকে একটি স্ট্রিং দেয়া হলো- "london" এবং তোমাকে বলা হলো যে স্ট্রিংটিকে "nodnol" এইভাবে প্রকাশ করতে। কিংবা তোমাকে কিছু সংখ্যা দেয়া হল ১০, ২০, ১৫, ৫ এবং তোমাকে বলা হলো যে সংখ্যাগুলোকে ৫, ১৫, ২০, ১০ এইভাবে প্রকাশ করতে। তুমি এই প্রব্লেমটি কিভাবে সল্ভ করবে?? ডাটা স্ট্রাকচার ও এলগোরিদম  ব্যবহার করে অনেক বিশাল কোনো কোড লিখবে?? তুমি যদি reverse() Function সম্পর্কে জানো তাহলে তুমি মুহূর্তেই এই প্রব্লেম সল্ভ করতে পারো।


Vector এ reverse() Function: মনেকর, v একটি ভেক্টর। তাহলে ফাংশন কল দিবো এইভাবে-
reverse(v.begin(), v.end());

Array তে  reverse() Function: মনেকর, a একটি Array। তাহলে ফাংশন কল দিবো এইভাবে-
reverse(a, a+n);

String এ reverse() Function: মনেকর, s একটি String। তাহলে ফাংশন কল দিবো এইভাবে-
reverse(s.begin(), s.end());

Code:
/*  Reverse-Vector, String, Array  */

#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main()
{
    vector <int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    for(int i=0; i<(int)v.size(); i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
    reverse(v.begin(), v.end()); //Reverse elements of vector
    printf("After reverse vector:\n");
    for(int i=0; i<(int)v.size(); i++)
    {
        printf("%d ", v[i]);
    }
    string s="abcd";
    printf("\n%s", s.c_str());
    reverse(s.begin(), s.end()); //Reverse characters of string
    printf("\nAfter reverse string:\n%s\n", s.c_str());
    int a[5]={1,2,3,4,5};
    for(int j=0; j<5; j++)
    {
        printf("%d", a[j]);
    }
    reverse(a, a+5); //Reverse elements of array
    printf("\nAfter reverse array:\n");
    for(int j=0; j<5; j++)
    {
        printf("%d", a[j]);
    }
    return 0;
}


Map

ম্যাপ Array এর মতোই একটি কন্টেইনার যাতে প্রতিটি এলিমেন্টের জন্য একটি Mapped Value ও একটি Key Value থাকে। দুটি এলিমেন্টের Mapped Value একই হতে পারে কিন্তু Key Value কখনই একই হবে না। 

এখন কন্সেপচুয়াল থিওরির বাইরে গিয়ে ম্যাপকে প্রোগ্রামিং প্রব্লেম কেন্দ্রিক আরো সহজভাবে তুলে ধরছি। আমরা Array তে বিভিন্ন Index এ ডাটা স্টোর করি। Index এর Value সাধারণত Integer হয়। যদি Index এর value integer না হয়ে String হত; কত  ইন্টারেষ্টিং হতো তাই না !!!! ম্যাপ দিয়ে তুমি ঠিক এই কাজটি করতে পারো। ম্যাপে Index double, long, Character ও হতে পারে।

এখন মনেকর, তোমার শিক্ষক তোমাকে রাঙামাটি জেলার আজকের তাপমাত্রা জিজ্ঞাসা করল। তুমি মুহূর্তের মধ্যে সেটি বের করতে পারবে? জানি তোমার উত্তর হবে না। কিন্তু তুমি যদি ম্যাপ ব্যবহার করে "বান্দরবান" নামের Index এ ২৮, "রাঙামাটি" নামের Index এ ২৬, "খাগড়াছড়ি" নামের Index এ ৩০ এভাবে সবকটি জেলার তাপমাত্রা আগে থেকে স্টোর করতে তাহলে প্রোগ্রামটি এক্সেকিউট করে ইনপুটে রাঙামাটি দিলেই মুহূর্তের মধ্যেই রাঙামাটি জেলার তাপমাত্রা তুমি জেনে যেতে। ম্যাপ  অনেক মজার টপিক তাই না !!!! 

ম্যাপ ডিক্লেয়ার করতে হয় এইভাবে-
map<data type1, data type2> variable;
map<string, int> m;

ম্যাপে ডাটা Initialization করা যায় এইভাবে-
m["Bandarban"]=28;
m["Rangamati"]=26;
m["Khagrachhari"]=30; 

ম্যাপ প্রোগ্রামিং এ অনেক ব্যবহৃত হয়। আমরা ভবিষ্যতে বিভিন্ন কোডিং এ ম্যাপের ব্যবহার দেখবো।

Code: 
/*  Map */

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
int main()
{
    string s;
    map<string, int> m;
    m["abc"]=5;
    m["def"]=10;
    m["ijk"]=20;
    printf("%d\n", m["def"]);
    getline(cin, s, '\n');
    if(m.find(s)==m.end()) //if find() function checks until end and string does not match
    {
        printf("Not found");
    }
    else
    {
        printf("%d", m[s]);
    }
    return 0;
}


Set

সেট অনেক ইন্টারেষ্টিং ডাটা স্ট্রাকচার। Set এ কোন Data Duplication নেই, একটি ডাটা কোন  সেটে বার বার Insert করলেও সেটি একবারই সেই সেট এ স্টোর হয়। আবার Set এ Insert করা ডাটা সমূহ Ascending অর্ডারে সর্টেড অবস্থায় থাকে। অতএব বুঝতেই পারছো সেট অনেক কাজের জিনিস !!!!

সেট কিভাবে ডিক্লেয়ার করবে তা জানাই এবার। সেট ডিক্লেয়ার করতে হয় এইভাবে-
set <data type> variable name;
set<int> s;

ডিক্লারেশন করার পর এখন S নামের সেটটিতে কিছু ডাটা Insert করব।
s.insert(10);
s.insert(20);
s.insert(10);
s.insert(5);

এখন একটি মজার প্রোগ্রামিং প্রব্লেম নিয়ে আলোচনা করি। মাঝে মাঝে প্রোগ্রামিং প্রতিযোগিতায় অনেকগুলো সংখ্যা দিয়ে বলা থাকে কতটি মৌলিক সংখ্যা আছে তা বের কর। তুমি যদি সেট সম্পর্কে জানো তাহলে সেটি তুমি মুহূর্তেই বের করতে পারো। শুধু একটির পর একটি ইনপুট নিবে এবং সেগুলোকে সেটে Input করবে। এরপর সেটের size() বের করলেই তোমাকে দেয়া প্রব্লেমটি সল্ভ হয়ে গেলো।

Code:   
/*  Set  */

#include<cstdio>
#include<set>
using namespace std;
int main()
{
    int a;
    set<int> s;
    set<int>::iterator i;
    for(int j=0; ; j++)
    {
        scanf("%d", &a);
        if(a==0)
        {
            break;
        }
        s.insert(a);
    }
    for(i=s.begin(); i!=s.end(); i++)
    {
        printf("%d ", *i);
    }
    return 0;
}


Wednesday, June 27, 2018

Priority Queue

প্রায়োরিটি কিউ সম্পর্কে জানার আগে কিউ সম্পর্কে জেনে এসো-
Queue Tutorial Link

প্রায়োরিটি কিউ সম্পূর্ণ কিউ এর মতোই শুধু পার্থক্য হচ্ছে- কিউ তে যে ডাটা আগে push করা হয় সেটি আগে থাকে, কিন্তু প্রায়োরিটি কিউ তে push কৃত ডাটা সমূহের মধ্যে যেটির value বড় সেটি Top এ থাকবে। Top এর ডাটাটি Pop করা হলে, অবশিষ্ট ডাটা সমূহের মধ্যে যেটির value বড় সেটি Top এ থাকবে।

প্রায়োরিটি কিউ ডিক্লেয়ার করতে হয় এই ভাবে- 
priority_queue< data type > variable name;
priority_queue< int > pq;

প্রায়োরিটি কিউ তে ডাটা Push করার নিয়ম-
pq.push(20);
pq.push(30);

প্রায়োরিটি কিউ তে Top ডাটার value জানতে- pq.top(); ব্যবহার করা হয়।  

প্রায়োরিটি কিউ থেকে ডাটা Pop  বা  Remove করা যায় এই ভাবে- pq.pop();

Code: 
/*  Priority Queue */

#include<cstdio>
#include<queue>
using namespace std;
int main()
{
    priority_queue<int> pq;
    pq.push(20);
    pq.push(30);
    pq.push(10);
    while(!pq.empty())
    {
        printf("%d ",pq.top());
        pq.pop();
    }
    return 0;
}


Queue

বাস বা  ট্রেনে ওঠার জন্য দীর্ঘ সারির সাথে আমরা সবাই পরিচিত। বাসে উঠার জন্য যে ব্যক্তি প্রথমে দাঁড়ান, তিনিই প্রথমে বাস ওঠার সুযোগ পান। এভাবে দ্বিতীয় জন, তৃতীয় জন, চতুর্থ জন বাসে ওঠেন। ঠিক এইভাবেই কিউ ডাটা স্ট্রাকচার কাজ করে। অনেক ইন্টারেস্টিং, তাই না ???


আমি এই পোষ্টে STL এর মাধ্যমে কিভাবে Queue ব্যবহার করতে হয় তা নিয়ে আলোচনা করব। Queue ডিক্লেয়ার  করতে হয় এই ভাবে-
queue< data type > variable;
queue< int > q;

Queue ডিক্লেয়ার করা হল, এবার জানব Queue তে কিভাবে ডাটা Push করতে হয় বা Insert করতে হয়। Push কৃত ডাটা  Queue এর পেছন দিয়ে প্রবেশ করে। উপরের q নামের কিউটিতে আমরা ডাটা পুশ করব। 
q.push(10);
q.push(50); 
q.push(70); 

কিউতে যেসব ডাটা থাকে, তার মধ্যে যেটি ফ্রন্টে থাকে সেটিই দরকার হয় বিভিন্ন অপারেশন এ। তাই ফ্রন্টে কোন ডাটা আছে তা আমাদের জানতে হবে। q.front() এভাবে আমরা q নামের কিউটির  ফ্রন্টে কোন ডাটা আছে তা সহজেই জানতে পারি।  

এবার আমরা Queue থেকে ডাটা Pop করব বা Remove করবQueue থেকে ডাটা Pop করা যায় সামনে থেকে। যে ডাটাটি Queue তে সবার সামনে বা Front এ থাকবে সেটিই আগে Pop হবে ডাটা Pop করবো এইভাবে - q.pop();

Queue এর ডাটা স্ট্রাকচার সাধারনত FIFO অর্থাৎ First In First Out মডেল Follow করেফলে যে ডাটাটি সবার আগে Push করা হয় সেটি সবার আগে Pop করা হয়

Code:
    
/*  Queue */

#include<cstdio>
#include<queue>
using namespace std;
int main()
{
    queue<int> q;
    q.push(10);
    q.push(50);
    q.push(70);
    while(!q.empty())
    {
        printf("%d ", q.front());
        q.pop();
    }
    return 0;
}


Sunday, June 24, 2018

String Stream

মনেকর তোমাকে একটি সংখ্যার স্ট্রিং দেয়া হলো। এবার বলা হলো এই বিশাল স্ট্রিং কে ইন্টিজার সংখ্যায় কনভার্ট করতে। কিভাবে করবে ???? স্ট্রিং স্ট্রিম ব্যবহার  করে তুমি সহজেই তা করতে পারো। স্ট্রিং স্ট্রিম খুব মজার ডাটা স্ট্রাকচার।
প্রোগ্রামিং প্রতিযোগিতায় অনেক বিশাল লিমিটের কোনো সংখ্যা নিয়ে কাজ করতে বলা হলে সংখ্যাটি স্ট্রিং হিসেবে ইনপুট নিয়ে পরবর্তীতে স্ট্রিং স্ট্রিম ব্যবহার করে স্ট্রিংটিকে সংখ্যায় কনভার্ট করা যায় সহজেই।
নিচে স্ট্রিং স্ট্রিম নিয়ে কোড দেয়া হলো-
/*  String Stream   */
     
    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        string s;
        cin>>s;
        int number;
        stringstream ss(s); // here ss is stringstream type variable
        ss>>number;
        printf("%d", number);
        return 0;
    }

String

স্ট্রিং নিয়ে কারসাজি........ 

যাদের Character Array সম্পর্কে ধারণা আছে তারা স্ট্রিং খুব সহজেই বুঝতে পারবে। আমি এই পোস্টে স্ট্রিংয়ের ডেফিনিশনে যাবো না; স্ট্রিং নিয়ে কিছু টুকিটাকি আলোচনা করবো যা তোমাকে যে কোনো প্রোগ্রামিং প্রতিযোগিতায় অনেক এগিয়ে রাখবে। 

char a[100];
int n;
scanf("%d", &n);
gets(a);

উপরের মতো করে scanf() দিয়ে ইনপুট নেয়ার পর gets() দিয়ে Character Array তে ইনপুট নেয়ার ক্ষেত্রে সমস্যায় পড়তে হয়। নিচের নিয়মে এই সমস্যা এড়ানো যায়।
scanf("%d", &n);
getchar();  ->এভাবে scanf() ও gets() এর মাঝে getchar() দিতে হবে। 
gets(a);

space সহ সম্পূর্ণ স্ট্রিং কিভাবে ইনপুট নিবো??? এটি একটি কমন ইস্যুপ্রোগ্রামিং প্রতিযোগিতায় অনেক সময় space সহ স্ট্রিং ইনপুট নিতে হয়। তরুণ প্রতিযোগীদের এটি অনেক ভোগায়।
string s;

মনেকর, s একটি স্ট্রিং। এখন সি++ এ cin দিয়ে s স্ট্রিং space সহ ইনপুট নিলে, s স্ট্রিং এ প্রথম স্পেস এর আগের অংশ স্টোর হবে; সম্পূর্ণ স্ট্রিং স্টোর হবে না। getline() function ব্যবহার করে আমরা এই সমস্যাটি সমাধান করতে পারি। getline() দিয়ে s স্ট্রিংটি ঠিক এই ভাবে ইনপুট নিতে হবে- getline(cin, s, '\n');
char a[100];
আবার মনেকর, a একটি character array। scanf() দিয়ে character array টিতে space সহ ইনপুট নিলেও একই সমস্যায় পড়তে হবে, প্রথম space এর আগের অংশটুকু character array টিতে স্টোর হবে। এই ক্ষেত্রে ইনপুট নিতে হবে এই ভাবে- cin.getline(a, 99);

প্রোগ্রামিং প্রতিযোগিতায় cin, cout এর ব্যবহার সীমিত রাখাই ভাল। Character Array a কে দেখানোর জন্য printf() ব্যবহার করা গেলেও স্ট্রিং s কে দেখানোর জন্য শুধু printf() ব্যবহার করলে চলবে না। স্ট্রিং s কে printf() এর মাধ্যমে দেখাতে হবে এইভাবে-
printf("%s", s.c_str()); 

লুপ ছাড়াই কপি!!! একটি Character Array থেকে অন্য Character Array তে ডাটা ট্রান্সফারের জন্য আমাদের লুপ এর সাহায্য নিতে হয়। স্ট্রিং এ এইসব ঝক্কি-ঝামেলা  নেই।
string s1, s2;
স্ট্রিং s1 থেকে s2 তে ডাটা ট্রান্সফার করবো এইভাবে- 
s2=s1;
স্ট্রিং এ কতটি ক্যারেক্টার আছে তা size() ও length() দিয়ে সহজেই বের করা যায়।

Code:
 

/*  String Input */

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int main()
{
    char a[100], b[100];
    int num1, num2;
    string s1, s2, s3;
    /*when we get any string using white space, variable:a will store string before
    white space & string after white space will be stored into variable:b*/
    printf("Enter a:");
    scanf("%s", a);
    printf("Enter b:");
    scanf("%s", b);
    printf("%s\n%s\n", a,b);
    /*When we use get function after any integer input, enter button pressed by user
    stored as string to solve is problem, we use getchar() function between two input*/
    scanf("%d", &num1);
    gets(a);
    printf("%d %s\n", num1, a);
    scanf("%d", &num2);
    getchar();
    gets(b);
    printf("%d %s\n", num2, b);
    /*When we get any string using cin, it also stores before white space*/
    /*cin>>s1;
    cout<<s1;*/
    getline(cin, s2, '\n');  //This is used to get a line as string
    /*Definition: getline(cin, string_variable, delimiter_char)
    this is used for string type variable, not for char array */
    cout<<s2; //we can't use printf() function here
    /*We get input in char array as string using white space by following method*/
    cin.getline(a, 15);  //Definition: cin.getline(char_array, size-1)
    printf("%s\n", a); //we can use cout as well
    int l1=s2.size();
    printf("%d\n", l1);
    int l2=s2.length();
    printf("%d", l2);
    s3=s2; //we directly store string one variable to another
    cout<<s3;
    /*We can get char_array as input & convert it into string by following*/
    char c[100];
    scanf("%s", c);
    string s4= string(c);
    cout&lt<s4;
    printf("\n%s", s3.c_str());  //we can print string by printf() by this method
    return 0;
}

 স্ট্রিং ম্যানিপুলেশন  নিয়ে নিচের কোডটি দেখতে পারো-

/*  String Manipulation */

#include<cstdio>
#include<string>
using namespace std;
int main()
{
    string s1, s2, s3;
    s1="abcdefgh";
    printf("%s\n", s1.c_str());
    s2=s1.substr(3);
    printf("%s\n", s2.c_str());
    s3=s1.substr(4,3);
    printf("%s\n", s3.c_str());
    s2[1]='P';
    printf("%s\n", s2.c_str());
    return 0;
}