সি তে , বাইনারি সার্চ , স্ট্রিং , এবং মৌলিক সংখ্যা

বাইনারি সার্চ  ঃ

বাইনারি সার্চ।

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

সংখ্যাটি কি N (একটি সংখ্যা)-এর চেয়ে বড়, ছোট নাকি সমান?

আর সংখ্যাটি কিন্তু একটি নির্দিষ্ট সীমার মধ্যে হতে হবে (যেমন 1 থেকে 100, 10 থেকে 1000, -1000 থেকে 100000)।

এখন ধরা যাক, প্রথমজন যে সংখ্যাটি ধরেছে সেটি 1 থেকে 1000-এর ভেতর একটি সংখ্যা। তাহলে কিন্তু সর্বোচ্চ এক হাজার বার 'সংখ্যাটি কি N-এর সমান?' প্রশ্নটি করে সেটি বের করে ফেলা যায়। (সংখ্যাটি কি 1? সংখ্যাটি কি 2? ... সংখ্যাটি কি 999?, সংখ্যাটি কি 1000?)। এভাবে প্রশ্ন করতে থাকলে সংখ্যাটি অবশ্যই বের হবে। তবে ভাগ্য খারাপ হলে এক হাজার বার ওই প্রশ্নটি করতে হবে।

কিন্তু আমাদের তো এত সময় নেই। ধরা যাক, 1 থেকে 1000-এর ভেতর ওই সংখ্যাটি হচ্ছে 50। তাহলে আমাদের প্রথম প্রশ্ন হবে:

১) সংখ্যাটি কি 500-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।

২) সংখ্যাটি কি 250-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।

৩) সংখ্যাটি কি 125-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।

৪) সংখ্যাটি কি 62-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।

৫) সংখ্যাটি কি 31-এর চেয়ে বড়, ছোট নাকি সমান? বড়।

৬) সংখ্যাটি কি 46-এর চেয়ে বড়, ছোট নাকি সমান? বড়।

৭) সংখ্যাটি কি 54-এর চেয়ে বড়, ছোট নাকি সমান? ছোট।

৮) সংখ্যাটি কি 50-এর চেয়ে বড়, ছোট নাকি সমান? সমান।

আমরা মাত্র আটটি প্রশ্ন করেই সংখ্যাটি পেয়ে গেছি!

তোমরা নিশ্চয়ই পদ্ধতিটি বুঝে ফেলেছ? প্রতিবার প্রশ্ন করে সংখ্যাটি যে সীমার মধ্যে আছে তাকে অর্ধেক করে ফেলা হয়েছে। খেলা শুরুর সময় সীমাটি ছিল 1 থেকে 1000। তারপর সেটি হয়েছে 1 থেকে 500। তারপর 1 থেকে 250, 1 থেকে 125, 1 থেকে 62, 31 থেকে 62, 46 থেকে 62, 46 থেকে 54।

সংখ্যা খুঁজে বের করার এই পদ্ধতিকে বলে বাইনারি সার্চ। চলো আমরা তাহলে অ্যালগরিদমটি লিখার চেষ্টা করি:

বাইনারি সার্চ (low, high, N): (শুরুতে আমাদের তিনটি সংখ্যা জানতে হবে, সংখ্যাটির নিম্নসীমা (low), উচ্চসীমা (high) এবং সেই সংখ্যা (N))

ধাপ 1: mid = (low + high) / 2

ধাপ 2: যদি mid এবং N-এর মান সমান হয় তবে ধাপ 5-এ যাও।

ধাপ 3: যদি N, mid-এর চেয়ে বড় হয়, তাহলে low = mid + 1. ধাপ 1-এ যাও।

ধাপ 4: যদি N, mid-এর চেয়ে ছোট হয়, তাহলে high = mid - 1. ধাপ 1-এ যাও।

ধাপ 5: সংখ্যাটি পেয়ে গেছি (mid)।

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

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

int ara[] = {1, 4, 6, 8, 9, 11, 14, 15, 20, 25, 33 83, 87, 97, 99, 100};

এখন বলো তো low আর high-এর মান কত হবে? low = 1 এবং high = 100 ? ঠিকই ধরেছ কিন্তু এখানে একটু সমস্যা আছে। আমরা এখানে সব সংখ্যার মধ্যে খুঁজব না, বরং অ্যারের ইনডেক্সের মধ্যে খুঁজব। আর অ্যারের ইনডেক্সগুলো ক্রমানুসারে থাকে বলেই অ্যারেতে বাইনারি সার্চ করা যায়। এখানে ara-এর সর্বনিম্ন ইনডেক্স হচ্ছে 0 এবং সর্বোচ্চ ইনডেক্স হচ্ছে 15। তাহলে আমরা দুটি ভেরিয়েবলের মান নির্দিষ্ট করে দিই -

low_indx = 0;

high_indx = 15;

যে সংখ্যাটি খুঁজব ধরা যাক সেটি হচ্ছে 97।

num = 97;

তোমাদের অনেকেই হয়তো ভাবছ, num সংখ্যাটি যদি ara-তে না থাকে তখন কী হবে? সেটিও আমরা দেখব। সংখ্যাটি যদি খুঁজে পাওয়া না যায় তবে সেটি জানিয়ে দেওয়ার ব্যবস্থা রাখতে হবে আমাদের প্রোগ্রামে।

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

 while(1) {  
     mid_indx = (low_indx + high_indx) / 2;       
     if(num == ara[mid_indx]) {  
         /* num যদি ara[mid_indx]-এর সমান হয়, তবে সেটি আমরা পেয়ে গেছি */  
         break;  
     }       
     if(num < ara[mid_indx]) {       
         /* num যদি ara[mid_indx]-এর ছোট হয়, তবে আমরা low_indx থেকে mid_indx – 1 সীমার মধ্যে খুঁজব। */  
         high_indx = mid_indx – 1;  
     }  
     else {  
         /* num যদি ara[mid_indx]-এর বড় হয়, তবে আমরা mid_indx + 1 থেকে high_indx সীমার মধ্যে খুঁজব। */  
         low_indx = mid_indx + 1;  
     }  
 }  

বাইনারি সার্চের প্রোগ্রাম আমরা লিখে ফেললাম। খুবই সহজ-সরল প্রোগ্রাম। সংখ্যাটি খুঁজে না পাওয়া পর্যন্ত লুপটি চলতেই থাকবে, কারণ আমরা লিখেছি while(1) আর 1 সব সময় সত্যি। কিন্তু সংখ্যাটি যদি ara-তে না থাকে তবে লুপটি চলতেই থাকবে এবং আমাদের প্রোগ্রাম কখনো বন্ধ হবে না। সুতরাং একটা ব্যবস্থা করা দরকার। আচ্ছা, আমরা কীভাবে বুঝব যে সংখ্যাটি ara-তে নেই? তোমরা ইতিমধ্যে লক্ষ করেছ যে আমরা প্রতিবার সার্চের সীমাটা অর্ধেক করে ফেলি। এভাবে চলতে থাকলে একসময় ওই সীমার ভেতর একটি সংখ্যাই থাকবে। তখন low এবং high-এর মান সমান হবে। আর প্রতিবার যেহেতু হয় low-এর মান বাড়ছে নাহয় high-এর মান কমছে, সুতরাং যেবার low আর high সমান হবে, তার পরের বার low-এর মান high-এর মানের চেয়ে বেশি হবে। তখন আমরা বুঝব যে সংখ্যাটি খুঁজে পাওয়া যায়নি। সুতরাং যতক্ষণ low <= high ততক্ষণ লুপটি চলবে। লুপ থেকে বের হয়ে যদি দেখি low > high, তখন বুঝব যে সংখ্যাটি খুঁজে পাওয়া যায়নি, আর না হলে বুঝব সংখ্যাটি খুঁজে পাওয়া গেছে এবং-এর মান ara[mid_indx]।

তাহলে পুরো প্রোগ্রামটি এবারে লিখে ফেলা যাক:

 #include <stdio.h>  
 int main()  
 {  
     int ara[] = {1, 4, 6, 8, 9, 11, 14, 15, 20, 25, 33 83, 87, 97, 99, 100};  
     int low_indx = 0;  
     int high_indx = 15;  
     int mid_indx;  
     int num = 97;  
     while (low_indx <= high_indx) {  
         mid_indx = (low_indx + high_indx) / 2;  
         if (num == ara[mid_indx]) {  
             break;  
         }  
         if (num < ara[mid_indx]) {  
             high_indx = mid_indx – 1;  
         }  
         else {  
             low_indx = mid_indx + 1;  
         }  
     }  
     if (low_indx > high_indx) {  
         printf("%d is not in the array\n", num);  
     }  
     else {  
         printf("%d is found in the array. It is the %d th element of the array.\n", ara[mid_indx], mid_indx);  
     }  
     return 0;  
 }  
 প্রোগ্রাম: ৮.১  

এবার তোমাদের কাজ হবে বাইনারি সার্চের জন্য একটি আলাদা ফাংশন লেখা।

আর বাইনারি সার্চ কীভাবে কাজ করে, সেটি এখানে সুন্দর করে অ্যানিমেশনের মাধ্যমে বোঝানো হয়েছে:
http://video.franklin.edu/Franklin/Math/170/common/mod01/binarySearchAlg.html

 

 

 

 

 

 

স্ট্রিং (string)।

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

এক বা একাধিক character মিলে string তৈরি হয়। সোজা কথায় স্ট্রিং হচ্ছে ক্যারেক্টার টাইপের অ্যারে। তবে প্রোগ্রামিংয়ে এটির ব্যবহার এতই বেশি যে কোনো কোনো ল্যাঙ্গুয়েজে স্ট্রিংকে আলাদা একটি ডাটা টাইপ হিসেবে ধরা হয়। তবে সি-তে আমরা char টাইপের অ্যারে দিয়েই স্ট্রিংয়ের কাজ করব।

নিচের উদাহরণগুলো লক্ষ করো:

 char country[11] = {'B', 'a', 'n', 'g', 'l', 'a', 'd', 'e', 's', 'h', '\0'};    
 char country[] = {'B', 'a', 'n', 'g', 'l', 'a', 'd', 'e', 's', 'h', '\0'};    
 char country[] = "Bangladesh";    
 char *country = "Bangladesh";    

এভাবে আমরা স্ট্রিং ডিক্লেয়ার করতে পারি। চারটি ডিক্লারেশন আসলে একই জিনিস। সবার শেষে একটি Null character ('\0') দিলে কম্পাইলার বুঝতে পারে এখানেই স্ট্রিংয়ের শেষ। আবার তৃতীয় উদাহরণে অ্যারের উপাদানগুলো আলাদা করে লেখা হয়নি, একসঙ্গে লেখা হয়েছে। এ ক্ষেত্রে কম্পাইলার নিজেই Null character বসিয়ে নেবে। চতুর্থ উদাহরণটি একটু অদ্ভুত। এখানে যে জিনিসটা ব্যবহার করা হয়েছে তার নাম পয়েন্টার (pointer)। এ বইতে এরকম জিনিস আমরা মাঝে মাঝে ব্যবহার করলেও বিস্তারিত আলোচনায় যাব না।

এবারে প্রোগ্রাম লিখার পালা।

 #include <stdio.h>     
 int main()     
 {     
     char country[] = {'B', 'a', 'n', 'g', 'l', 'a', 'd', 'e', 's', 'h', '\0'};     
     printf("%s\n", country);     
     return 0;     
 }    
 প্রোগ্রাম: ৯.১    

এখানে লক্ষ করো যে printf-এর ভেতরে %s ব্যবহার করা হয়েছে স্ট্রিং প্রিন্ট করার জন্য। আর অ্যারেতে শেষের '\0'টা ব্যবহার না করলেও চলে আসলে। বর্তমানের কম্পাইলারগুলো এটি বুঝে নিতে পারে।

 #include <stdio.h>     
 int main()     
 {     
     char country[] = {'B', 'a', 'n', 'g', 'l', 'a', 'd', 'e', 's', 'h', ' ', 'i', 's', ' ', 'm', 'y', ' ', 'c', 'o', 'u', 'n', 't', 'r', 'y'};     
     printf("%s\n", country);     
     return 0;     
 }    
 প্রোগ্রাম: ৯.২    

প্রোগ্রামটি চালাও। তারপর নিচের প্রোগ্রামটি চালাও। আউটপুটে কি পার্থক্য দেখতে পাচ্ছ? পার্থক্যের কারণটা কী?

 #include <stdio.h>     
 int main()     
 {     
     char country[] = {'B', 'a', 'n', 'g', 'l', 'a', 'd', 'e', 's', 'h', '\0', 'i', 's', ' ', 'm', 'y', ' ', 'c', 'o', 'u', 'n', 't', 'r', 'y'};     
     printf("%s\n", country);        
     return 0;     
 }    
 প্রোগ্রাম: ৯.৩    

পার্থক্যটা কী সেটি তোমরা প্রোগ্রাম দুটি কম্পিউটারে চালালেই বুঝবে। পার্থক্যের কারণ হচ্ছে দ্বিতীয় প্রোগ্রামে স্ট্রিংয়ের ভেতরে এক জায়গায় '\0' থাকায় কম্পাইলার ধরে নিচ্ছে ওখানে স্ট্রিংটা শেষ হয়ে গেছে।

এবারে আমরা একটি প্রোগ্রাম লিখব। একটি স্ট্রিংয়ের ভেতরের সব অক্ষরকে বড় হাতের অক্ষরে (অর্থাৎ capital letter বা uppercase character) রূপান্তর করা। তবে এর জন্য আমাদের একটি জিনিস জানতে হবে। প্রতিটি অক্ষরের বিপরীতে কম্পিউটার একটি সংখ্যার কোড ব্যবহার করে। সেই কোড অনুযায়ী, 'A'-এর মান হচ্ছে 65, 'B'-এর মান হচ্ছে 66, 'C'-এর মান হচ্ছে 67... এভাবে 'Z'-এর মান হচ্ছে 90। তেমনই 'a' হচ্ছে 97, 'b' হচ্ছে 98 ... এভাবে 'z' হচ্ছে 122। সুতরাং কোনো ক্যারেক্টার বড় হাতের কি না সেটি আমরা নির্ণয় করতে পারি এভাবে: if(ch >= 'A' && ch <= 'Z') অথবা if(ch >= 65 && ch <= 90)। তেমনই ছোট হাতের অক্ষরের জন্য: if(ch >= 'a' && ch <= 'z') অথবা if(ch >= 97 && ch <= 122)। এখন কোনো ক্যারেক্টার যদি ছোট হাতের হয়, তবে তাকে বড় হাতের অক্ষরে রূপান্তর করার উপায় কী? উপায় খুব সহজ। একটি উদাহরণ দেখো: char ch = 'c'; ch = 'A' + (ch – 'a'); এখানে যেটি হচ্ছে, প্রথমে ch থেকে 'a' বিয়োগ করা হচ্ছে মানে 'c' থেকে 'a' বিয়োগ (আসলে 99 থেকে 97 বিয়োগ হচ্ছে)। বিয়োগফল 2। এবারে 'A'-এর সঙ্গে যদি ওই 2 যোগ করে দিই তবে সেটি 'C' হয়ে যাবে! এখন প্রোগ্রামটি লিখে ফেলা যাক: 

 #include <stdio.h>     
 int main()     
 {     
     char country[] = {'B', 'a', 'n', 'g', 'l', 'a', 'd', 'e', 's', 'h'};     
     int i, length;     
     printf("%s\n", country);     
     length = 10;         
     for(i = 0; i < length; i++) {     
         if(country[i] >= 97 && country[i] <= 122) {     
             country[i] = 'A' + (country[i] - 'a');     
         }     
     }     
     printf("%s\n", country);     
     return 0;     
 }    
 প্রোগ্রাম: ৯.৪    

এখন তোমরা uppercase থেকে lowercase-এ রূপান্তরের প্রোগ্রামটি লিখে ফেলো। তারপরে আবার বইটি পড়া শুরু করো।

এখানে লক্ষ করো যে স্ট্রিংয়ে (ক্যারেক্টারের অ্যারেতে) মোট কয়টি উপাদান আছে সেটি আমি দেখেই লিখে ফেলেছি এবং সরাসরি বসিয়ে দিয়েছি length = 10।

এবার আমরা কোনো স্ট্রিংয়ের দৈর্ঘ্য মাপার জন্য একটি ফাংশন লিখব! এটি তেমন কঠিন কিছু নয়। একটি লুপের সাহায্যে স্ট্রিংয়ের প্রতিটি উপাদান পরীক্ষা করতে হবে এবং Null character ('\0') পেলে লুপ থেকে বের হয়ে যাবে অর্থাৎ, '\0' না পাওয়া পর্যন্ত লুপ চলতে থাকবে। আর লুপ যতবার চলবে স্ট্রিংয়ের দৈর্ঘ্যও তত হবে।

 #include <stdio.h>     
 int string_length(char str[])     
 {     
     int i, length = 0;     
     for(i = 0; str[i] != '\0'; i++) {     
         length++;     
     }     
     return length;    
 }     
 int main()     
 {     
     char country[100];     
     int length;     
     while(1 == scanf("%s", country)) {                
         length = string_length(country);     
         printf("length: %d\n", length);     
     }     
     return 0;     
 }    
 প্রোগ্রাম: ৯.৫    

ওপরের প্রোগ্রামটায় তোমরা দেখতে পাচ্ছ যে ইনপুট নেওয়ার জন্য scanf ফাংশন ব্যবহার করা হয়েছে এবং স্ট্রিং ইনপুট নেওয়ার জন্য %s ব্যবহৃত হয়েছে। scanf ফাংশনটি যতটি উপাদান ইনপুট হিসেবে নেয়, সেই সংখ্যাটি রিটার্ন করে। সাধারণত রিটার্ন ভ্যালুটি আমাদের দরকার হয় না, তাই scanf ব্যবহার করলেও আমরা ওই ভ্যালুটি রাখি না। যেমন দুটি ইন্টিজার ইনপুট নিতে গেলে আমরা লিখি: scanf("%d %d", &n1, &n2);। আমরা এটি চাইলে এভাবেও লিখতে পারতাম: value = scanf("%d %d", &n1, &n2);। তোমরা প্রিন্ট করলে দেখবে value-এর মান 2। while(1 == scanf("%s", country)) লাইনে যেটি ঘটছে তা হলো, যতক্ষণ একটি country-এর নাম scanf দিয়ে ইনপুট নেওয়া হচ্ছে, ফাংশনটি 1 রিটার্ন করছে, আর লুপের ভেতরের কন্ডিশন সত্য হচ্ছে (1 == 1), তাই লুপের কাজ চলতে থাকবে।

আরেকটি জিনিস খেয়াল করো যে country-এর আগে কোন & চিহ্ন ব্যবহার করা হয়নি। তোমরা &country লিখে দেখো প্রোগ্রামটি কী আচরণ করে। তবে %s ব্যবহারের একটি সমস্যা হচ্ছে স্ট্রিংয়ে কোনো হোয়াইটস্পেস ক্যারেক্টার (যেমন: স্পেস, ট্যাব ইত্যাদি) থাকা যাবে না, এমন কিছু পেলে scanf ওই ক্যারেক্টার পর্যন্ত একটি স্ট্রিং ধরে নেয়। যেমন, ইনপুট যদি হয় this is তবে scanf প্রথমে thisকেই স্ট্রিং হিসেবে নেবে, তারপরে যদি আবার scanf ফাংশন কল করা হয়, তবে isকে সে স্ট্রিং হিসেবে ইনপুট নিয়ে নেবে। এই সমস্যা এড়ানোর জন্য আমরা gets ফাংশন ব্যবহার করতে পারি। নিচের উদাহরণটি দেখো:

 #include <stdio.h>     
 int main()     
 {     
     char ara[100];     
     while(NULL != gets(ara)) {                     
         printf("%s\n", ara);     
     }     
     return 0;     
 }    
 প্রোগ্রাম: ৯.৬    

এই প্রোগ্রামটিও চলতে থাকবে যতক্ষণ না তুমি ctrl + z (মানে কি-বোর্ডে ctrl ও z একসঙ্গে) চাপো, লিনাক্সের জন্য ctrl + d। ctrl + z বা ctrl + d দিলে gets ফাংশনটি NULL রিটার্ন করে। আরেকটি জিনিস লক্ষ করো যে আমি char ara[100]; ডিক্লেয়ার করে শুরুতেই বলে দিয়েছি স্ট্রিংয়ের সর্বোচ্চ দৈর্ঘ্য হবে 100।

আরেকটি ব্যাপার। string_length ফাংশনের ভেতরে আসলে দুটি ভেরিয়েবল ব্যবহার না করলেও চলে। আমরা ফাংশনটি এভাবেও লিখতে পারি:

 int string_length(char str[])     
 {     
     int i;         
     for(i = 0; str[i] != '\0'; i++);             
     return i;     
 }     

এখন তোমাদের কাজ হবে string_length ফাংশনটি for লুপ ব্যবহার না করে while লুপ ব্যবহার করে লেখা।

আমাদের পরবর্তী প্রোগ্রামের লক্ষ্য হবে দুটি স্ট্রিং জোড়া দেওয়া বা concatenate করা। যেমন একটি স্ট্রিং যদি হয় "bangla" এবং আরেকটি স্ট্রিং যদি হয় "desh" তবে দুটি জোড়া দিয়ে "bangladesh" বানাতে হবে।

প্রথমেই স্ট্রিংগুলো ডিক্লেয়ার করে নেই: char str1[] = "bangla", str2[] = "desh", str3[12];

আমাদের লক্ষ হচ্ছে str3তে "bangladesh" রাখা। খুব সুবিধা হতো যদি আমরা এমন কিছু লিখতে পারতাম:

str3 = str1 + str2;

কিন্তু 'সি'-তে এভাবে দুটি অ্যারে বা স্ট্রিং যোগ করা যায় না। তাই একটি একটি করে str1-এর উপাদানগুলো str3তে কপি করতে হবে, তারপর str2-এর উপাদানগুলো str3তে কপি করতে হবে।

 #include <stdio.h>     
 int main()     
 {     
     char str1[] = "bangla", str2[] = "desh", str3[12];     
     int i, j, length1 = 6, length2 = 4;     
     for(i = 0, j = 0; i < length1; i++, j++) {     
         str3[j] = str1[i];     
     }         
     for(i = 0, j = 0; i < length2; i++, j++) {     
         str3[j] = str2[i];     
     }     
     str3[j] = '\0';     
     printf("%s\n", str3);     
     return 0;     
 }    
 প্রোগ্রাম: ৯.৭    

প্রোগ্রামটি চালাও। আউটপুট কী আসা উচিত? bangladesh। কিন্তু আউটপুট এসেছে desh। আসলে আমরা কিছু একটা ভুল করেছি। তোমাদের এখন সেই ভুলটি ঠিক করার চেষ্টা করা উচিত। অন্তত তিরিশ মিনিট চেষ্টার পরও যদি ভুল বের করতে না পারো তবে আবার বইটি পড়া শুরু করো।

 for(i = 0, j = 0; i < length1; i++, j++) {     
     str3[j] = str1[i];     
 }    

এখানে আমরা শুরুতেই i-এর মান 0 করেছি কারণ iকে আমরা str1-এর ইনডেক্স হিসেবে ব্যবহার করব। jকে ব্যবহার করব str3-এর ইনডেক্স হিসেবে তাই j-এর মানও 0 করা হয়েছে। তারপর একে একে str1-এর উপাদানগুলো str3তে কপি করছি এবং i ও j-এর মান 1 করে বাড়াচ্ছি (i++, j++)। লুপ শেষ হওয়ার পরে i ও j প্রত্যেকের মান হবে 6।

এখন পরের লুপে আমরা str2কে str3-তে কপি করব। এখন str2-এর ইনডেক্স হিসেবে যদি i ব্যবহার করি, তবে তার মান লুপের শুরুতেই আবার 0 করে দিতে হবে। আমরা সেটি করেছি। কিন্তু ভুল করেছি সেই সঙ্গে j-এর মান 0 করে দিয়ে। j-এর মান 0 করলে তো str2-এর প্রথম (0তম) উপাদান str3-এর প্রথম (0তম) উপাদান হিসেবে কপি হবে, কিন্তু আমরা তো সেটি চাই না। আমরা চাই str2-এর প্রথম উপাদান হবে str3-এর সপ্তম উপাদান। তাহলে j-এর মান 0 করা যাবে না। তাই দ্বিতীয় লুপটি হবে এমন:

 for(i = 0; i < length2; i++, j++) {     
     str3[j] = str2[i];     
 }    

আরেকটি ব্যাপার লক্ষ করো। দ্বিতীয় লুপ থেকে বের হবার পরে str3-এর শেষ ঘরে '\0' অ্যাসাইন করেছি (str3[j] = '\0';) যাতে স্ট্রিংটা যে ওখানেই শেষ, এটি কম্পাইলার বুঝতে পারে।

আমাদের পরবর্তী প্রোগ্রাম হবে দুটি স্ট্রিংয়ের মধ্যে তুলনা করা। অর্থাৎ দুটি স্ট্রিংয়ের মধ্যে ছোট, বড়, সমান নির্ণয় করা। সংখ্যার ক্ষেত্রে যেমন >, <, >=, <=, == চিহ্ন ব্যবহার করে তুলনা করা যায়, স্ট্রিংয়ের ক্ষেত্রে সেই ব্যবস্থা নাই। কিন্তু স্ট্রিংয়ের ক্ষেত্রে প্রায়ই আমাদের এই তুলনা করার দরকার পড়বে। যেমন ধরো, সর্টিংয়ের ক্ষেত্রে যেখানে ছোট থেকে বড় বা বড় থেকে ছোট ক্রমানুসারে সাজাতে হবে (alphabetical ordering)। স্ট্রিংয়ে ছোট-বড় আবার কী? বেশি কথা বলে ব্যাখ্যা না করে কিছু উদাহরণ দিই, তাহলেই বুঝতে পারবে। 'aaa'-এর চেয়ে 'aab' বড়। আবার 'ba' ও 'ca'-এর মধ্যে 'ca' বড়। এই প্রোগ্রামে আমরা একটি ফাংশন লিখব string_compare() যেটির কাজ হবে দুটি স্ট্রিংয়ের মধ্যে তুলনা করে প্রথমটি দ্বিতীয়টির চেয়ে বড় হলে 1 রিটার্ন করবে, ছোট হলে -1 আর দুটি সমান হলে 0 রিটার্ন করবে। ফাংশনের রিটার্ন টাইপ হবে ইন্টিজার এবং প্যারামিটার হবে দুটি char টাইপের অ্যারে। 

 int string_compare(char a[], char b[])    
 {    

 }    

আমাদের মূল কাজ হবে a-এর প্রথম উপাদানের সঙ্গে b-এর প্রথম উপাদান, a-এর দ্বিতীয় উপাদানের সঙ্গে b-এর দ্বিতীয় উপাদান এভাবে তুলনা করতে থাকা। যখনই a-এর কোনো উপাদান b-এর কোনো উপাদানের চেয়ে ছোট হবে, আমরা সঙ্গে সঙ্গে বলে দিতে পারি যে a, b-এর চেয়ে ছোট। সুতরাং -1 রিটার্ন করে ফাংশন থেকে বের হয়ে আসব। একইভাবে যখনই a-এর কোনো উপাদান b-এর কোনো উপাদানের চেয়ে বড় হবে, সঙ্গে সঙ্গে 1 রিটার্ন করে ফাংশন থেকে বের হয়ে আসব কারণ a, b-এর চেয়ে বড়। কিন্তু যদি সবগুলোই সমান হয়? তখন আমরা 0 রিটার্ন করব। তাতে বুঝব যে স্ট্রিং দুটি সমান।

 int string_compare(char a[], char b[])     
 {     
     int i, j;     
     for(i = 0; a[i] != '\0' && b[i] != '\0'; i++) {     
         if(a[i] < b[i]) {     
             return -1;     
         }     
         if(a[i] > b[i]) {     
             return 1;     
         }     
     }     
     if(string_length(a) == string_length(b)) {     
         return 0;     
     }     
     if(string_length(a) < string_length(b)) {     
         return -1;     
     }     
     if(string_length(a) > string_length(b)) {     
         return 1;     
     }     
 }     

স্ট্রিংয়ের বেসিক জিনিসগুলো নিয়ে আলোচনা করলাম। তবে মজার ব্যাপার হচ্ছে সি ল্যাঙ্গুয়েজে একটি হেডার ফাইল আছে, যার নাম string.h এবং ওইখানে বেশিরভাগ স্ট্রিং-সংক্রান্ত কাজের জন্য ফাংশন তৈরি করে দেওয়া আছে (যেমন: strcmp, strlen, strcpy ইত্যাদি)। তোমাদের দিয়ে কাজগুলো আমি আবার করালাম বলে দুঃখ পাওয়ার কোনো কারণ নেই, আমার ওপর রাগ করারও কিছু নেই। মৌলিক জিনিসগুলো শিখে রাখা সব সময়ই গুরুত্বপূর্ণ, যা তোমার প্রোগ্রামিং চিন্তাকে বিকশিত করবে।

এখন আমরা আরেকটি প্রোগ্রাম লিখব যেটি ইনপুট হিসেবে একটি স্ট্রিং নেবে (যেখানে অনেকগুলো শব্দ থাকবে)। এই স্ট্রিংয়ের সর্বোচ্চ দৈর্ঘ্য হবে 1000। শব্দগুলোর মাঝখানে এক বা একাধিক স্পেস থাকবে। আউটপুট হিসেবে প্রতিটি শব্দ আলাদা লাইনে প্রিন্ট করতে হবে। বিরামচিহ্নগুলো (punctuation) প্রিন্ট করা যাবে না এবং শব্দের প্রথম অক্ষর হবে বড় হাতের।

অনেক শর্ত দিয়ে ফেললাম। তবে প্রোগ্রামটি খুব কঠিন কিছু নয়। নিজে নিজে চেষ্টা করতে পারো। আর না পারলে এখন চলো দেখি কীভাবে সমাধান করা যায়।

প্রথম কথা হচ্ছে, ইনপুট নেব কীভাবে? বুঝতেই পারছ যে ইনপুটে যেহেতু স্পেস থাকবে, scanf("%s") ব্যবহার করা যাবে না। তাই আমরা gets() ব্যবহার করব। তার পরের কথা হচ্ছে একটি শব্দে কোন কোন ক্যারেক্টার থাকতে পারে? যেহেতু বলা নেই, আমরা ধরে নিই 'a' থেকে 'z', 'A' থেকে 'Z' আর '0' থেকে '9' থাকবে।

তার পরের প্রশ্ন হচ্ছে, আমরা কখন বুঝব বা আমাদের প্রোগ্রামকে কীভাবে বোঝাবো যে একটি শব্দ শুরু হয়েছে?-এর জন্য আমরা একটি ভেরিয়েবল রাখতে পারি। ভেরিয়েবলের নাম যদি দিই is_word_started তাহলে এর মান 0 হলে বুঝব শব্দ শুরু হয়নি, শব্দ শুরু হলে এর মান আমরা 1 করে দেব। আবার শব্দ শেষ হলে 0 করে দেব। যখন দেখব শব্দ শুরু হয়ে গেছে (is_word_started-এর মান 1) কিন্তু কোনো ক্যারেক্টারের মান 'a' – 'z' বা 'A' – 'Z', বা '0' – '9' এই রেঞ্জের মধ্যে নেই, তখনই বুঝব শব্দটি শেষ। তোমরা যদি এর আগে প্রোগ্রামটি চেষ্টা করার পরও লিখতে না পারো, এখন চেষ্টা করলে পারবে আশা করি। আমি এখন কোডটি লিখে দেব তবে সেটি দেখার আগে অবশ্যই নিজে করার চেষ্টা করতে হবে।

 #include <stdio.h>    
 #include <string.h>    
 int main()    
 {    
     char s[1002], word[100];    
     int i, j, length, is_word_started;    
     gets(s);    
     length = strlen(s);    
     is_word_started = 0;    
     for (i = 0, j = 0; i < length; i++) {    
         if (s[i] >= 'a' && s[i] <= 'z') {    
             if (is_word_started == 0) {    
                 is_word_started = 1;    
                 word[j] = 'A' + s[i] - 'a'; // first character is capital    
                 j++;    
             }    
             else {    
                 word[j] = s[i];    
                 j++;    
             }    
         }    
         else if (s[i] >= 'A' && s[i] <= 'Z') {    
             if (is_word_started == 0) {    
                 is_word_started = 1;    
             }    
             word[j] = s[i];    
             j++;    
         }    
         else if (s[i] >= '0' && s[i] <= '9') {    
             if (is_word_started == 0) {    
                 is_word_started = 1;    
             }    
             word[j] = s[i];    
             j++;    
         }    
         else {    
             if (is_word_started == 1) {    
                 is_word_started = 0;    
                 word[j] = '\0';    
                 printf("%s\n", word);    
                 j = 0;    
             }    
         }    
     }    
     return 0;    
 }     
 প্রোগ্রাম: ৯.৮    

প্রোগ্রামটি বুঝতে কি একটু সমস্যা হচ্ছে? সে পরে দেখা যাবে, আগে প্রোগ্রামটি চটপট কম্পিউটারে টাইপ করে ফেলো, কম্পাইল ও রান করো। যারা লিনাক্স ব্যবহার করছ তারা gets() ব্যবহারের কারণে কম্পাইলার থেকে একটি সতর্ক সংকেত (warning) পেতে পারো, পাত্তা দিয়ো না।

ইনপুট হিসেবে যেকোনো কিছু লিখতে পারো। যেমন: This is a test.। আউটপুট কী?

আউটপুট হচ্ছে এই রকম:

This
Is
A

কী মুশকিল! test গেল কোথায়?

এখন তোমার কাজ হবে test-এর নিখোঁজ হওয়ার রহস্যটা তদন্ত করা। তারপর আমি প্রোগ্রামটি ব্যাখ্যা করব।

তোমরা দেখো প্রোগ্রামে আমি স্ট্রিংয়ের দৈর্ঘ্য নির্ণয়ের জন্য strlen ফাংশন ব্যবহার করেছি। আর-এর জন্য আমাকে string.h হেডার ফাইলটি include করতে হয়েছে। ইনপুট হিসেবে স্ট্রিংটা নিলাম s-এ। আর word রাখার জন্য একটি অ্যারে ডিক্লেয়ার করে রেখেছি। তারপর আমি i = 0 থেকে length পর্যন্ত একটি লুপ চালিয়েছি s-এর ভেতরের প্রতিটি ক্যারেক্টার পরীক্ষা করার জন্য।

if (s[i] >= 'a' && s[i] <= 'z') দিয়ে পরীক্ষা করলাম এটি ছোট হাতের অক্ষর নাকি। যদি ছোট হাতের অক্ষর হয় তবে একটি শব্দের প্রথম অক্ষর কি না সেটি জানতে হবে। কারণ প্রথম অক্ষর হলে ওটাকে আবার বড় হাতের অক্ষরে রূপান্তর করতে হবে। সেই পরীক্ষাটা আমরা করেছি: if (is_word_started == 0) দিয়ে। এটি সত্য হওয়া মানে শব্দ শুরু হয়নি, এটিই প্রথম অক্ষর। তাই আমরা is_word_started-এর মান 1 করে দেব। আর word[j]তে s[i]-এর বড় হাতের অক্ষরটা নেব। তারপর j-এর মান এক বাড়াতে হবে। else if (s[i] >= 'A' && s[i] <= 'Z') এবং else if (s[i] >= '0' && s[i] <= '9') এই দুটি শর্তের ভেতরেই আমরা একই কাজ করি। s[i]কে word[j]তে কপি করি। তাই চাইলে দুটি শর্তকে একসঙ্গে এভাবেও লিখতে পারতাম: else if ((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= '0' && s[i] <= '9')) তার পরের else-এর ভেতরে ঢোকার মানে হচ্ছে আগের if এবং else if-এর শর্তগুলো মিথ্যা হয়েছে। তাই s[i]-এর ভেতরে যেই ক্যারেক্টার আছে সেটি word-এ রাখা যাবে না। এবং যদি word ইতিমধ্যে শুরু হয়ে গিয়ে থাকে, সেটি শেষ করতে হবে এবং wordটি প্রিন্ট করতে হবে। আর যদি word শুরু না হয়ে থাকে তাহলে কিছু করার দরকার নেই। 

 else {    
     if (is_word_started == 1) {    
         is_word_started = 0;    
         word[j] = '\0';    
         printf("%s\n", word);    
         j = 0;    
     }    
 }    

তোমরা কি test-রহস্য সমাধান করতে পেরেছ? তোমরা চেষ্টা করতে থাকো আর আমি এখন প্রোগ্রামটি অন্যভাবে লিখব (এর সঙ্গে test রহস্যের কোনো সম্পর্ক নেই সেটি বলে রাখলাম)।

এখন আমি যেটি করব, প্রোগ্রামটি এমনভাবে লিখব যাতে word অ্যারেটিই ব্যবহার করতে না হয়! একটু চিন্তা করে দেখো। আসলে তো এই অ্যারেটি নিয়ে আমরা কিছু করছি না প্রিন্ট করা ছাড়া। তাই এর আসলে কোনো দরকার নেই।

 #include <stdio.h>    
 #include <string.h>    
 int main()    
 {    
     char s[1002], ch;    
     int i, length, is_word_started;    
     gets(s);    
     length = strlen(s);    
     is_word_started = 0;    
     for (i = 0; i < length; i++) {    
         if (s[i] >= 'a' && s[i] <= 'z') {    
             if (is_word_started == 0) {    
                 is_word_started = 1;    
                 ch = 'A' + s[i] - 'a';    
                 printf("%c", ch);    
             }    
             else {    
                 printf("%c", s[i]);    
             }    
         }    
         else if ((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= '0' && s[i] <= '9')) {    
             if (is_word_started == 0) {    
                 is_word_started = 1;    
             }    
             printf("%c", s[i]);    
         }    
         else {    
             if (is_word_started == 1) {    
                 is_word_started = 0;    
                 printf("\n");    
             }    
         }    
     }    
     printf("\n");    
     return 0;    
 }    
 প্রোগ্রাম: ৯.৯    

এখন প্রোগ্রামটি বুঝতে চেষ্টা করো এবং বিভিন্ন ইনপুট দিয়ে পরীক্ষা করে দেখো। যেমন:

This is test number 9.9

স্ট্রিং-সংক্রান্ত সমস্যাগুলো দেখতে জটিল মনে হলেও আসলে সহজ। আর এ ধরনের সমস্যা সমাধানের যত চর্চা করবে দক্ষতা তত বাড়বে।

 

 

 

 

 

 

 

 

 

 

মৌলিক সংখ্যা।

মৌলিক সংখ্যা (Prime Number) গণিতবিদদের কাছে যেমন প্রিয়, তেমনই প্রোগ্রামারদেরও অনেক প্রিয় একটি বিষয়। তোমাদের বিভিন্ন সময়ে এই মৌলিক সংখ্যাসংক্রান্ত নানা সমস্যার সমাধান করতে হবে। মৌলিক সংখ্যা জিনিসটি যে গুরুত্বপূর্ণ সেটি বোঝার আরেকটি উপায় হলো, এই বইতে বিষয়টির জন্য আমি একটি পৃথক অধ্যায় বরাদ্দ করেছি। মৌলিক সংখ্যা হচ্ছে সেসব সংখ্যা যারা 1-এর চেয়ে বড় পূর্ণসংখ্যা এবং সেটি কেবল 1 এবং ওই সংখ্যাটি দ্বারাই নিঃশেষে বিভাজ্য হবে। খুবই সহজ-সরল জিনিস। এখন কোনো সংখ্যা মৌলিক কি না সেটি বের করার জন্য একটি প্রোগ্রাম লিখে ফেলা যাক।

 #include <stdio.h>   
 int is_prime(int n)   
 {   
     int i;   
     if (n < 2) {  
         return 0;  
     }  
     for(i = 2; i < n; i++) {   
         if(n % i == 0) {   
             return 0;   
         }   
     }   
     return 1;   
 }   

 int main()   
 {    
     int n;   
     while(1) {   
         printf("Please enter a number (enter 0 to exit): ");   
         scanf("%d", &n);   
         if(n == 0) {   
             break;   
         }    
         if(1 == is_prime(n)) {   
             printf("%d is a prime number.\n", n);   
         }   
        else {   
            printf("%d is not a prime number.\n", n);   
        }    
     }   
     return 0;   
 }  
 প্রোগ্রাম: ১০.১  

মৌলিক সংখ্যা নির্ণয়ের জন্য আমরা একটি ফাংশন লিখেছি যেটির প্যারামিটার হচ্ছে একটি ইন্টিজার নম্বর n। ফাংশনে আমরা nকে 2 থেকে n-1 পর্যন্ত সংখ্যাগুলো দিয়ে ভাগ করার চেষ্টা করেছি একটি লুপের সাহায্যে। যদি এর মধ্যে কোনো সংখ্যা দিয়ে n নিঃশেষে বিভাজ্য হয়, তবে আমরা সঙ্গে সঙ্গেই বলে দিতে পারি যে সেটি মৌলিক সংখ্যা নয় এবং ফাংশনটি 0 রিটার্ন করে। আর যদি সব সংখ্যা দিয়ে ভাগ করার পরও দেখা যায় যে কোন সংখ্যাই nকে নিঃশেষে ভাগ করতে পারেনি, তখন আমরা এই সিদ্ধান্তে আসতে পারি যে n একটি মৌলিক সংখ্যা। আর তখন ফাংশন থেকে 1 রিটার্ন করি। আমরা মৌলিক সংখ্যা নির্ণয় করা শিখে গেলাম! আমি প্রোগ্রামটি লিখার সময় যে পথ অবলম্বন করেছি সেটি হচ্ছে খুব সহজ-সরল পথ। প্রোগ্রামটিকে মোটেও ইফিশিয়েন্ট (efficient) বানানোর চেষ্টা করিনি। তোমরা খুব সহজেই ব্যাপারটি বুঝতে পারবে। প্রোগ্রামে ইনপুট হিসেবে 2147483647 দাও। এটি যে মৌলিক সংখ্যা সেটি বের করতে বেশ সময় লাগে। কারণ তখন 2147483647কে 2 থেকে 2147483646 পর্যন্ত সব সংখ্যা দিয়ে ভাগ করার ব্যর্থ চেষ্টা করা হয়। প্রোগ্রামটিকে আরও ইফিশিয়েন্ট করতে হবে।

একটি বুদ্ধি তোমাদের মাথায় এর মধ্যেই নিশ্চয়ই এসে গেছে। সেটি হচ্ছে 2 থেকে n-1 পর্যন্ত সব সংখ্যা দিয়ে ভাগ করার চেষ্টা না করে 2 থেকে n/2 পর্যন্ত সংখ্যাগুলো দিয়ে ভাগ করার চেষ্টা করলেই হয়। তাহলে প্রোগ্রামের গতি দ্বিগুণ হয়ে যাবে। এখন তোমরা আরেকটি বিষয় লক্ষ করো। কোন সংখ্যা যদি 2 দিয়ে নিঃশেষে বিভাজ্য না হয়, তবে সেটি অন্য কোন জোড় সংখ্যা দিয়ে নিঃশেষে বিভাজ্য হওয়ার প্রশ্নই আসে না। তাই 2 বাদে অন্য জোড় সংখ্যাগুলো (4, 6, 8, …) দিয়ে ভাগ করার চেষ্টা করাটা আসলে বোকামি। জোড় সংখ্যা দিয়ে বিভাজ্যতার পরীক্ষাটা আমরা ফাংশনের শুরুতেই করে নিতে পারি। এখন আমাদের ফাংশনটির চেহারা দাঁড়াবে এই রকম:

 int is_prime(int n)   
 {   
   int i;   
   if (n < 2) {  
     return 0;  
   }  
   if(n == 2) {   
     return 1;   
   }    
   if(n % 2 == 0) {   
     return 0;   
   }   
   for(i = 3; i <= n / 2; i = i + 2) {   
     if(n % i == 0) {   
       return 0;   
     }   
   }   
   return 1;   
 }  

প্রথমে আমরা পরীক্ষা করেছি n-এর মান 2 কি না। যদি 2 হয় তবে বলে দিয়েছি যে n মৌলিক সংখ্যা। তারপরে আমরা পরীক্ষা করেছি n জোড় সংখ্যা কি না। যদি জোড় হয়, তবে n মৌলিক সংখ্যা না, কেবল 2ই একমাত্র জোড় মৌলিক সংখ্যা যেটির পরীক্ষা আমরা একেবারে শুরুতেই করে ফেলেছি। তারপর আমরা 3 থেকে n / 2 পর্যন্ত সব বেজোড় সংখ্যা দিয়ে nকে ভাগ করার চেষ্টা করেছি। এখন তোমরা বিভিন্ন ইনপুট দিয়ে প্রোগ্রামটি পরীক্ষা করে দেখো। 2147483647 দিয়ে পরীক্ষা করলে বুঝতে পারবে যে প্রোগ্রামের গতি আগের চেয়ে বেড়েছে কিন্তু তার পরও একটু সময় লাগছে। আমার কম্পিউটারে চার সেকেন্ডের মতো সময় লাগছে। কিন্তু এত সময় তো দেওয়া যাবে না। তোমাদের যাদের গাণিতিক বুদ্ধিশুদ্ধি বেশি, তারা একটু চিন্তা করলেই প্রোগ্রামটির গতি বাড়ানোর একটি উপায় বের করে ফেলতে পারবে। সেটি হচ্ছে n-এর উৎপাদক বের করার জন্য আসলে n / 2 পর্যন্ত সব সংখ্যা দিয়ে পরীক্ষা করার দরকার নেই। n-এর বর্গমূল পর্যন্ত পরীক্ষা করলেই হয়। n = p x q হলে, p বা q যেকোনো একটি সংখ্যা অবশ্যই n-এর বর্গমূলের সমান বা তার ছোট হবে। বর্গমূল নির্ণয়ের জন্য আমরা math.h হেডার ফাইলের sqrt() ফাংশনটি ব্যবহার করব। আমাদের প্রোগ্রামটি দাঁড়াচ্ছে এই রকম:

 #include <stdio.h>   
 #include <math.h>   
 int is_prime(int n)   
 {   
     int i, root;  
     if(n == 2) {   
         return 1;   
     }     
     if(n % 2 == 0) {   
         return 0;   
     }   
     root = sqrt(n);   
     for(i = 3; i <= root; i = i + 2) {   
         if(n % i == 0) {   
             return 0;   
         }   
     }   
     return 1;   
 }   

 int main()   
 {    
     int n, m;   
     while(1) {   
         printf("Please enter a number (enter 0 to exit): ");   
         scanf("%d", &n);   
         if(n == 0) {   
             break;   
         }    
         if(1 == is_prime(n)) {   
             printf("%d is a prime number.\n", n);   
         }   
         else {   
             printf("%d is not a prime number.\n", n);   
         }   
     }   
     return 0;   
 }  
 প্রোগ্রাম: ১০.২  

এখন তোমরা প্রোগ্রামটি চালিয়ে বিভিন্ন ইনপুট দিয়ে পরীক্ষা করে দেখো। একটি কথা বলে দিই। প্রোগ্রামটায় একটি বাগ আছে (মানে ভুল আছে)। সেটি খুঁজে বের করে ঠিক করে ফেলো।

প্রাইম নম্বর বের করতে পেরে তোমরা নিশ্চয়ই বেশ খুশি? কিন্তু আমাদের চেষ্টা এখানেই থেমে থাকবে না। আমরা এখন দেখব আরেকটি চমৎকার পদ্ধতি, গ্রিক গণিতবিদ ইরাতোসথেনেস (Eratosthenes) আজ থেকে দুই হাজার বছরেরও আগে এই পদ্ধতি আবিষ্কার করেছিলেন। এজন্য-এর নাম হচ্ছে সিভ অব ইরাতোসথেনেস (Sieve of Eratosthenes)।

পদ্ধতিটি ব্যাখ্যা করা যাক। ধরো, আমরা 2 থেকে 40 পর্যন্ত সব মৌলিক সংখ্যা বের করব। শুরুতে সব সংখ্যা লিখে ফেলি: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 , 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40. এখন দেখো, তালিকার প্রথম সংখ্যা হচ্ছে 2। এবারে 2-এর সব গুণিতক (2 বাদে, মানে 2-এর চেয়ে বড়গুলো আরকী) বাদ দিয়ে দাও। তাহলে থাকবে: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19 , 21, 23, 25, 27, 29, 31, 33, 35, 37, 39. এখন তালিকার দ্বিতীয় সংখ্যা 3-এর সব গুণিতক (3-এর চেয়ে বড়গুলো) বাদ দাও। 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37. এখন তালিকার তৃতীয় সংখ্যা 5-এর সব গুণিতক (5 বাদে) বাদ দাও। 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. পরবর্তী সংখ্যা হচ্ছে 7 কিন্তু সেটির গুণিতক খোঁজার চেষ্টা করা বৃথা। কারণ তালিকার সর্বোচ্চ সংখ্যা 37-এর বর্গমূল 7-এর চেয়ে ছোট। সুতরাং 7-এর যে গুণিতকগুলো তালিকায় ছিল সেগুলো ইতিমধ্যে তালিকা থেকে বাদ পড়েছে। কারণটি বুঝতে সমস্যা হচ্ছে? দেখো 7-এর গুণিতকগুলো ছিল 14, 21, 28, 35। 7-এর সঙ্গে যেসব সংখ্যা গুণ করে ওই গুণিতকগুলো পাওয়া যায় সেগুলো সবই 7-এর চেয়ে ছোট সংখ্যা এবং তাদের গুণিতকগুলো আমরা ইতিমধ্যেই বাদ দিয়ে দিয়েছি।

আরো পরিষ্কারভাবে বোঝার জন্য উইকিপিডিয়ার এই অ্যানেমেশনটি দেখতে পারো (এখানে 2 থেকে 120 পর্যন্ত সংখ্যাগুলোর মধ্যে মৌলিক সংখ্যাগুলো বের করা হয়েছে):

 
এবারে ইমপ্লিমেন্ট করার পালা। আমরা তালিকা রাখার জন্য একটি অ্যারে ব্যবহার করব। ধরা যাক, তার নাম হচ্ছে ara। অ্যারেটি এমনভাবে তৈরি করতে হবে, যাতে কোনো একটি সংখ্যা n-এর অবস্থা (অর্থাৎ সেটি মৌলিক কি না) ara[n] দিয়ে প্রকাশ করা যায়। যদি ara[n]-এর মান 1 হয়, তবে n মৌলিক সংখ্যা আর ara[n]-এর মান 0 হলে n মৌলিক সংখ্যা নয়। ইমপ্লিমেন্টেশনের আগে অ্যালগরিদমটা লেখা যাক:
ধাপ ১: ধরা যাক, অ্যারেতে nটি উপাদান আছে। শুরুতে অ্যারের সব উপাদানের মান 1 বসাই।
ধাপ ২: অ্যারের প্রতিটি উপাদানের জন্য সেটির মান 1 কি না তা পরীক্ষা করি। যদি 1, হয় তবে তৃতীয় ধাপে যাই।
ধাপ ৩: ওই সংখ্যাকে 2 থেকে m পর্যন্ত ক্রমিক সংখ্যাগুলো দিয়ে গুণ করি এবং গুণফল যত হবে, অ্যারের তত নম্বর উপাদানে শূন্য (0) বসাই। অর্থাৎ সেটি যে মৌলিক নয় তা চিহ্নিত করি। এখানে m-এর মান এমন হবে যেন ঐ সংখ্যার সঙ্গে m-এর গুণফল n-এর চেয়ে ছোট বা সমান হয়।

এখন তোমরা কোডটি লিখার চেষ্টা করো। কমপক্ষে তিন ঘণ্টা নিজে চেষ্টা করার পর এবারে আমার কোড দেখো।

 #include <stdio.h>   
 #include <math.h>   
 const int size = 40;   
 int ara[size];   

 void print_ara()   
 {   
     int i;   
     for(i = 2; i < size; i++) {   
         printf("%4d", ara[i]);   
     }   
     printf("\n");   
     for(i = 2; i < size; i++) {   
         printf("----");   
     }   
     printf("\n");   
     for(i = 2; i < size; i++) {   
         printf("%4d", i);   
     }   
     printf("\n\n\n");    
 }   

 void sieve()   
 {   
     int i, j, root;   
     for(i = 2; i < size; i++) {   
         ara[i] = 1;   
     }   
     root = sqrt(size);   
     print_ara();   
     for(i = 2; i <= root; i++) {      
         if(ara[i] == 1) {   
             for(j = 2; i * j <= size; j++) {   
                 ara[i * j] = 0;          
             }   
             print_ara();   
         }   
     }   
 }   

 int is_prime(int n)   
 {   
     int i;   
     if(n < 2) {   
         return 0;   
     }   
     return ara[n];   
 }   

 int main()   
 {    
     int n, m;   
     sieve();   
     while(1) {   
         printf("Please enter a number (enter 0 to exit): ");   
         scanf("%d", &n);   
         if(n == 0) {   
             break;   
         }   
         if(n >= size) {   
             printf("The number should be less than %d\n", size);   
             continue;   
         }   
         if(1 == is_prime(n)) {   
             printf("%d is a prime number.\n", n);   
         }   
         else {   
             printf("%d is not a prime number.\n", n);   
         }   
     }      
     return 0;   
 }  
 প্রোগ্রাম: ১০.২  

প্রতিবার অ্যারের অবস্থা বোঝানোর জন্য আমি একটি ফাংশন ব্যবহার করেছি, print_ara()। তোমরা দেখো এবারে ইনপুট নেওয়ার আগেই আমরা sieve() ফাংশন কল করে অ্যারেটি তৈরি করে ফেলেছি। তারপর যতবারই ইনপুট নাও, কোনো চিন্তা নেই, ইনপুট যদি n হয় তবে ara[n]-এর মান পরীক্ষা করলেই চলে, মান যদি 1 হয় তবে n মৌলিক সংখ্যা, যদি 0 হয় তবে n মৌলিক সংখ্যা নয়। কত পর্যন্ত সংখ্যা হিসাব করতে চাও সেটি size-এ বসিয়ে দিলেই হবে। এখন এই প্রোগ্রামে গতি নিয়ে কোনো সমস্যা নেই। খুবই ফাস্ট (fast)। কিন্তু আর কোনো সমস্যা তোমাদের চোখে পড়ছে? তোমরা কি বুঝতে পারছ যে প্রোগ্রামটি অনেক বেশি মেমোরি খরচ করে? ধরো, আমরা যদি 100 কোটি পর্যন্ত সংখ্যা মৌলিক কি না সেটি বের করতে চাই, তাহলে তো আমাদের 100 কোটির একটি অ্যারে দরকার হবে। 'সময় বাঁচাব না মেমোরি' সমস্যায় প্রোগ্রামারদের প্রায়ই পড়তে হয়। আমাদের সমস্যার ক্ষেত্রে আমরা একটি মাঝামাঝি সমাধানে পৌঁছতে পারি। n-এর সর্বোচ্চ মান যত হবে তার বর্গমূলটিকে size-এর মান হিসেবে নিতে পারি। তোমাকে যদি বলা হয়, n-এর মান সর্বোচ্চ 100000000 (দশ কোটি) পর্যন্ত হতে পারে তাহলে তুমি এর বর্গমূল অর্থাৎ 10000 পর্যন্ত সংখ্যাগুলোর জন্য sieve ফাংশন ব্যবহার করে মৌলিক সংখ্যাগুলো বের করবে। তারপর কী করবে? নাহ্, আর কিছু বলা যাবে না, তোমরাই চিন্তা করে ঠিক করো কী করবে। আরেকটি কথা বলে দেওয়া দরকার। একটি ইন্টিজার কিন্তু চার বাইট জায়গা দখল করে, যেখানে একটি ক্যারেক্টার করে এক বাইট। সুতরাং ইন্টিজারের পরিবর্তে তোমরা ক্যারেক্টারের অ্যারে ব্যবহার করে মেমোরি খরচ চার ভাগের এক ভাগে নামিয়ে আনতে পারো। আমাদের তো আসলে ইন্টিজার অ্যারের দরকার নেই, কারণ অ্যারেতে কেবল দুই ধরনের মান থাকবে 0 বা 1।

সি প্রোগ্রামিংয়ে ভেক্টর নিয়ে কিছু কথা (জোবায়ের ভাই এর লিখা )

ভেক্টরঃ

অ্যারে আমাদের সবারই বিশেষভাবে পরিচিত, এবং সবার খুবই প্রিয় একটা ডাটা-স্ট্রাকচার হল অ্যারে। কোন কোডে অ্যারে ব্যবহার করতে পারলেই কেমন যেন শান্তি শান্তি লাগে… অ্যারের সবচেয়ে আকর্ষনীয় ফিচার মনে হয় তার ইন্ডেক্সিং (মানে র‍্যান্ডম অ্যাকসেস)। কিন্তু যতই দিন যায়, সব কেমন যেন কঠিন হয়ে যায়… তাইতো আজকাল অ্যারে নিয়েও মাঝে মাঝে ঝামেলায় পড়তে হয়, বিশেষতঃ যখন কিনা অ্যারের আকার আকৃতি রানটাইমে পরিবর্তন করার দরকার হয়। কারন, অ্যারে একবার ডিক্লেয়ার করলে রানটাইমে C++ এ তা আর ছোট-বড় করা যায় না। আর এখানেই ভেক্টরের আবির্ভাব।
ভেক্টরকে বলা যেতে পারে একটা ডায়নামিক অ্যারে, দরকার মত যেটার সাইজ বাড়ানো কমানো যায়। আবার অ্যারের মত মাল্টি ডাইমেনশন এবং ইন্ডেক্সিং সুবিধাগুলো ব্যবহার করা যায়।

কিভাবে ব্যবহার করবো?

ভেক্টর C++ STL এর একটা কন্টেইনার ক্লাস। অর্থাৎ এটাও একটা টেমপ্লেট ক্লাস, যার কারনে এটাকে অন্য টেমপ্লেটের সাথে সহজেই ব্যবহার করা যায়। তবে সবার প্রথমে দরকার স্ট্যান্ডার্ড হেডার vector ইনক্লুড করাঃ

1 2	#include <vector> using namespace std;

এর পরের কাজ হল ভেক্টর ডিক্লারেশন, সেটাও আবার কয়েকভাবে করা যায়, তবে সাধারন স্টাইল হলঃ vector < type > Var; এখানে type হতে পারে যে কোন টাইপ, অন্য কোন ইউজার ডিফাইনড টাইপ, টেমপ্লেট ক্লাস টাইপ, বেসিক টাইপগুলো। ভেক্টর ডিক্লেয়ার করার সাধারন সিন্ট্যাক্সগুলো নিচে দেখানো হলঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// constructing vectors #include <iostream> #include <vector> using namespace std; int main () {     // constructors used in the same order as described above:     vector<int> first;                                // empty vector of ints     vector<int> second (4,100);                       // four ints with value 100     vector<int> third (second.begin(),second.end());  // iterating through second     vector<int> fourth (third);                       // a copy of third           // the iterator constructor can also be used to construct from arrays:     int myints[] = {16,2,77,29};     vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );     cout << "The contents of fifth are:";     for (unsigned i=0; i < fifth.size(); i++) cout << " " << fifth[i]; cout << endl;           return 0; }

ভেক্টর ডিক্লেয়ার করার সময় [] আর () অপারেটরের মধ্যে পার্থক্যটা খেয়াল করা উচিতঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14

#include <iostream> #include <vector> using namespace std; int main () {     // use of [] and ()     vector<int> v1[100]; // creates an array of vectors, i.e. 100 vectors     vector<int> v2(100); // creates 1 vector of size 100     // creating a 2D array 100x2 where each element is a vector,     // so in total, it is a 3D structure, as vector itself is 1D     vector<int> v3[100][2];     return 0; }

উপরের কোডে যেমন দেখা গেল… চাইলেই আমরা ভেক্টরের অ্যারে তৈরি করতে পারি (এটা ভেক্টরের অন্যতম একটা গুরুত্বপূর্ন ব্যবহার)। কিন্তু এছাড়াও ভেক্টরে দিয়ে মাল্টিডাইমেনশনাল স্ট্রাকচার তৈরি করা যায়, যেখানে প্রতিটা ডাইমেনশনই ডায়নামিকঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <iostream> #include <vector> using namespace std; int main () {     // multidimentional vector     vector< vector< int > > V2D;     // the above is basically a vector where each element is a vector,     // we can also increase the level of nesting if needed.     // demonstrate a triangular structure..     vector< int > temp;     for(int i = 0; i < 10; i++) {         temp.clear();         for(int j = 0; j <= i; j++) {             temp.push_back(i+1);         }         V2D.push_back(temp);     }     return 0; }

হুম, তো আমরা খালি একটা ভেক্টরের মধ্যে আরেকটা ভেক্টর পুশ করলাম, ফলাফল 2D ভেক্টর। আগেই বলা হয়েছে, ভেক্টর একটা টেমপ্লেট ক্লাস, তাই, যে কোন টাইপ নিয়ে এটা বানানো যায়। যেমন চাইলেই আমরা কিউএর একটা ভেক্টর বানাতে পারিঃ vector< queue > Vq;

ভেক্টর অ্যাকসেসঃ

ভেক্টর দুইভাবে অ্যাকসেস করা যায়, ইটারেটরের সাহায্যে, ইন্ডেক্সিং-এর সাহায্যে। ইটারেটরের সাহায্যে করলে কিঞ্চিত ফাস্ট হয়, ভেক্টরের ইটারেটর একটা র‍্যান্ডম অ্যাকসেস ইটারেটর।

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <iostream> #include <vector> using namespace std; int main () {     vector< vector< int > > V2D;           // creating a 2D triangular structure     for(int i = 0; i < 10; i++) {         vector< int > temp;         for(int j = 0; j <= i; j++) {             temp.push_back(i);         }         V2D.push_back(temp);     }     // using iterator     cout << "using iterator:\n";     vector< vector< int > > :: iterator outer;     vector< int > :: iterator inner;     for(outer = V2D.begin(); outer != V2D.end(); outer++) {         for(inner = outer->begin(); inner != outer->end(); inner++) {             cout << *inner << ' ';         }         cout << '\n';     }     // using index     cout << "\nusing indexes:\n";     for(unsigned i = 0; i < V2D.size(); i++) {         for(unsigned j = 0; j < V2D[i].size(); j++) {             cout << V2D[i][j] << ' ';         }         cout << '\n';     }     return 0; }

সাধারনত কেউ ভেক্টরে ইটারেটর ব্যবহার করে না, কারন ইন্ডেক্সের ব্যবহার অনেক সহজ, এবং অধিকাংশ C++ কোডারের পয়েন্টারের প্রতি আজন্মের ভয়। কিন্তু ইটারেটরের ব্যবহার আরো বেশি সিগ্নিফিক্যান্ট, এবং অর্থবহ। অবশ্য কিভাবে ব্যবহার করতে হবে সেটা কোডারের ব্যক্তিগত ইচ্ছা। যার যেটায় সুবিধা সেটাই ব্যবহার করা উচিত। উপরের কোডে ভ্যালুগুলো চাইলে অ্যারের মত করে মডিফাইও করা যাবে, যেমন, V2D[i][j] = 100; লিখে দিলেই ওই পজিশনটার মান ১০০ হয়ে যাবে।

পুশব্যাক, পপব্যাক, সাইজ, এম্পটি

আগের কোডটায় আমরা দেখলাম পুশব্যাক দিয়ে ভেক্টরে ভ্যালু ইন্সার্ট করা হচ্ছে, তাই আর নতুন করে সেটা দেখনোর কিছু নাই, push_back() ফাংশনের সাহায্যে ভেক্টরের শেষে একি ধরনের একটা আইটেম অ্যাড করা যায়, আর pop_back() দিয়ে ভেক্টরের শেষ থেকে একটা আইটেম হাওয়া করে দেওয়া যায়। অন্যান্য STL মেম্বারের মত ভেক্টরের size() আর empty() ফাংশন দুইটাও আইডেন্টিক্যাল। নিচের কোডে এগুলোর ব্যবহার দেখানো হলঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <iostream> #include <vector> using namespace std; int main () {     vector< int > simple;     for(int i = 1; i < 10; i++) {         simple.push_back(i*100);         cout << "inserting: " << simple.back() << endl;     }     cout << "-------------------\n";     while(!simple.empty()) {         cout << "size: " << simple.size();         cout << " last element: " << simple.back() << endl;         simple.pop_back();     }     cout << "vector empty\n";     return 0; }

রিসাইজ, ইরেজ, ক্লিয়ার এবং রিসাইজ নিয়ে কিছু কাহিনীঃ

ভেক্টরের সাইজ মডিফায় করা যায় এরকম কিছু মেম্বার হল resize(), erase(), clear(), এদের মধ্যে clear() এর ব্যবহার অন্য যে কোন কন্টেইনার ক্লাসের মতই, সব এলিমেনত ডিলিট করে দেয়, ফলাফম সাইজ ০ হয়ে যায়। আর resize() ফাংশন দিয়ে ভেক্টরের সাইজ পরিবর্তন করা যায়। erase() এর কাজ কোন এলিমেন্ট বা একটা রেঞ্জ ডিলিট করা যায়। erase() এর দুইটা ফরম্যাট আছে, erase(iterator pos), erase(iterator first, iterator last), অর্থাৎ কোন ভ্যালুর সাপেক্ষে ডিলিট করা যায় না, তার ইটারেটর পজিশন দিতে হবে, আর দ্বিতীয় ধরনে ভেক্টরের [first, last) এই রেঞ্জের সব আইটেম ডিলিট করে দিবে। বলাই বাহুল্য, আজগুবি ইটারেটর দিলে রানটাইম এররর খেয়ে বসে থাকতে হবে…

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <iostream> #include <vector> using namespace std; int main () {     unsigned int i;     vector<unsigned int> myvector;     // set some values (from 1 to 10)     for (i=1; i<=10; i++) myvector.push_back(i);     // erase the 6th element     myvector.erase (myvector.begin()+5);     // erase the first 3 elements:     myvector.erase (myvector.begin(),myvector.begin()+3);     cout << "myvector contains:";     for (i=0; i<myvector.size(); i++)         cout << " " << myvector[i];     cout << endl;     // clear all     myvector.clear();     cout << "size: " << myvector.size() << endl;     // resize and then check size     myvector.resize(10);     cout << "size: " << myvector.size() << endl;     return 0; }

কিছু বিষয়ে এখানে সতর্ক হতে হবে, যেমনঃ resize() ফাংশনটা ভেক্টরের আগের অবস্থাত কোন তোয়াক্কা না করেই তার সাইজ চেঞ্জ করবে, ফলে কিছু এলিমেন্ট বাদও পড়তে পারে, আবার কিছু জায়গা খালিও থাকতে পারে। কিন্তূ ভেক্টরের সাইজ চেক করলে নতুন সাইজ এ পাওয়া যাবে, যদিও, সেটা হয়তো একটা খালি ভেক্টর ছিল। তাই, resize() এর পরে push_back() ব্যবহার করলে কোডার যাই আশা করুক না কেন, সে রিসাজকৃত স্পেসের পরেই পুশ করবে। যেমন, মনে করি, ভেক্টরে ছিল ১৮ টা আইটেম, আমি সেটাকে রিসাইজ করলাম ৫০ এ। তখন push_back() করলে সে ১৯ তম পজিশনে করবে না, করবে ৫১ তম পজিশনে (মানে ইন্ডেক্স ৫০)। একই ভাবে যদি ১২ রে রিসাইজ করতাম, তাহলেও সে ১৯ এ না করে ১৩ তে পুশ করতো। সাধারনত clear() এর অল্টারনেট হিসাবে resize() ব্যবহার করা যায়, তবে এর সাথে push_back() ব্যবহার না করাই ভাল। নিচের কোডঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#include <iostream> #include <vector> using namespace std; int main () {     int n, a;     vector< int > v;     while(cin >> n) {         v.resize(n);         for(a = 0; a < n; a++) {             cin >> v[a];         }         for(a = 0; a < n; a++) {             cout << v[a] << endl;         }     }     return 0; }

erase() এর ব্যাপারেও একটা কথা আছে, তা হল, এর কমপ্লেক্সিটি লিনিয়ার, তাই রান্ডম ইনসার্ট আর ডিলিটের জন্য ভেক্টর সুবিধাজনক না। x.clear() করা আর x.erase(x.begin(), x.end()) একই কথা। তাই কোডে খুব বেশি clear না মারাই ভাল।

ভেক্টরের ইটারেটর পাব কিভাবে?

উপরের কোডগুলোতে প্রায়ই দেখা গেছে begin() আর end() নামের দুটি ফাংশন। এরা যথা ক্রমে ভেক্টরের শুরু আর শেষের ইটারেটর রিটার্ন করে। মনে রাখতে হবে, STL এর যে কোন মেম্বারই একটা কমন রুল ফলো করে, তা হল, এখানে রেঞ্জ ডিফাইন করা হয় [first, last) দিয়ে, তার মানে last টা ইনক্লুডেড না। একই ভাবে end() ইটারেটর হল লাস্ট আইটেমের পরের ইটারেটর টা। এদের উলটা ফাংশন ২টা হলঃ rbegin(), rend(), যথাক্রমে রিভার্স বিগিন আর রিভার্স এন্ড ইটারেটর রিটার্ন করে।

অনেক হল…

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <iostream> #include <vector> using namespace std; const int MAX = 100; typedef pair< int, int > Edge; // to, weight int main () {     int n, e, i, j, u, v, w;     vector< Edge > G[MAX]; // adjacency list for MAX vertices     while(cin >> n >> e) {         // n nodes in range [0,n), e edges         for(i = 0; i < n; i++) G[i].clear(); // forget previous info         for(i = 0; i < e; i++) {             // directed edge from u to v with cost w             cin >> u >> v >> w;             G[u].push_back(Edge(v, w));         }         // now show the graph         for(i = 0; i < n; i++) {             cout << "Degree of " << i << ": " << G[i].size() << endl;             cout << "Adjacents:\n";             for(j = 0; j < (int)G[i].size(); j++) {                 cout << ' ' << G[i][j].first << "(" << G[i][j].second << ")\n";             }             cout << endl;         }     }     return 0; }

রেফারেন্সঃ

ভেক্টরের কারনে কাজ অনেক সহজ হয়ে যায়, তবে ভেক্টর কিছুটা স্লো আর বেশি মেমরি নেয়। যারা অপ্টিমাইজেশন পছন্দ করেন তাদের জন্য এটা খুব একটা মজার কিছু না।
ডিটেইলসঃ http://www.cplusplus.com/reference/stl/vector/

বিভাগ:ডাটা স্ট্রাকচার, প্রোগ্রামিং Tags: c++, data structure, programming, stl

C++ STL :: pair

অক্টোবর 1, 2010 zobayer2009 8 comments

কিছু কথাঃ

যারাই কিনা সি/সি++ নিয়ে বেশকিছুদিন নাড়াচাড়া করছেন, তারা প্রায় সবাই সি এর একটা দারুন জিনিস স্ট্রাকচার-এর সাথে পরিচিত, আর, আরেকটু অ্যাডভান্সডরা তো মনে হয় অলরেডি সি++ এর ক্লাস নামের জিনিসটা মোয়া বানিয়ে ফেলেছে।
সি একটা ফাটাফাটি ল্যাঙ্গুয়েজ আর সি++ এর কথা তো বলাই বাহুল্য। যারা অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং এর সুবাতাস পেয়েছেন তারা এটা আরো ভাল করে জানেন। আমরা জানি, সি++ এ কিছু প্রিমিটিভ ডাটা টাইপ ডিফাইন করা আছে, যাদের উপরে আমরা খুব সহজেই বিভিন্ন অপারেশন চালাতে পারি, কিন্তু মাঝে মাঝে এই রকমের ডাটা টাইপের ব্যবহার আমাদের কে ঝামেলায় ফেলতে পারে। যেমন, মনে করা যাক আমাকে একটা 2D গ্রিডের কিছু পয়েন্ট স্টোর করতে হবে। শুধু int টাইপের অ্যারে দিয়ে এটা মেইনটেইন করাটা বেশ মুশকিলের ব্যাপার। কিন্তু যদি এরকম একটা ডাটা টাইপ থাকতো ‘point’ নামে, যা কিনা (x, y) আকারে কো-অর্ডিনেট রাখতে পারতো!!! সি এ সেই ব্যাবস্থা করেই দেয়া আছে, যেন প্রোগ্রামাররা চাইলেই ইচ্ছা মতো ডাটা টাইপ বানিয়ে নিতে পারেন, আর সি++ এটাকে আরেক ডিগ্রি এগিয়ে নিয়ে গেছে। এখানে প্রোগ্রামার চাইলে তার বানানো ডাটা টাইপের আচার আচরণও বলে দিতে পারেন।
কিন্তু, প্রশ্ন হল, এটা কন্টেস্ট প্রোগ্রামিং এর জন্য কতটা সুইটেবল?

পেয়ার কি?

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

1	struct point { int x, y; } P[128];

অর্থাৎ, P[] হল একটা পয়েন্ট টাইপের অ্যারে, এখন এটাকে সর্ট করতে হবে। কাজ তো সোজাই, অ্যালগোরিদমের হেডারটা ইনক্লুড করে sort() মেরে দিলেই হয়… কিন্তু আসলে এটা এত সিম্পল না, কারন, sort() একটা টেমপ্লেট ফাংশন, মানে যে কোন ডাটাটাইপের জন্য কাজ করবে, কিন্তু তার আগে তাকে ডাটাটাইপের ভাবগতি জানাতে হবে। আমি ‘struct point’ দিয়ে কি বুঝাতে চাই, এটা তার বুঝার কোন কারনই নাই যদি না আমি বলে দেই। তার মানে খালি sort() কে ডাকলেই চলবে না, তার সাথে অপারেটর ওভারলোড বা কম্পেয়ার ফাংশন লিখে বুঝিয়ে দিতে হবে যে আমি আসলে কি চাই। আর এখানেই std::pair এর প্লাস পয়েন্ট।
std::pair জিনিশটা তেমন কিছুই না, জাস্ট দুইটা ভ্যালু কে একসাথে করে রাখে, যেখানে ভ্যালু দুইটা যে কোন টাইপের হতে পারে, ডিফারেন্ট টাইপেরও হতে পারে। পেয়ার ক্লাসটা ডিফাইন করা থাকে std <utility> নামের হেডারে।

1 2	#include <utility> using namespace std;

pair ক্লাসের ডেফিনিশনঃ

1 2 3 4 5 6 7

template <class T1, class T2> struct pair {     T1 first;     T2 second;     pair(): first(T1()), second(T2()) {}     pair(const T1 &x, const T2 &y): first(x), second(y) {}     template <class U, class V> pair(const pair<U, V> &p): first(p.first), second(p.second) {} };

যাদের টেমপ্লেট সম্পর্কে আইডিয়া নাই, তাদের জন্য অল্প কথায়, টেমপ্লেট একটা সিস্টেম যেখানে কোন অ্যাকচুয়াল টাইপের জন্য ডিজাইন থাকে না, বরং যে কোন টাইপের জন্য তার একটা ইন্সট্যান্স তৈরি করা যায়। টেমপ্লেট শিখতে হলে এই পেজটি দেখা যেতে পারে।
pair এর সুবিধা হল, এটা টেমপ্লেট টাইপ, তাই STL algorithm এর ফাংশন গুলার জন্য সাধারনতঃ pair অবজেক্ট গুলার আলাদা করে কোন পরিচয় দেওয়ার দরকার পড়ে না। যেমন আগের প্রবলেমে জাস্ট sort() কল দিলেই চলে, সে অটমেটিক প্রথমে পেয়ারের প্রথম মেম্বার, তার পর ২য় টা, তার পর ৩য় টা, এভাবে বাকি গুলা কম্পেয়ার করে দেখবে। প্রোগ্রামারকে এর জন্য কিছুই বলতে হবে না।

কিভাবে ব্যবহার করে?

pair নিয়ে কাজ করতে চাইলে <utility> হেডার ইনক্লুড করা উচিৎ, অবশ্য যে কোন STL হেডার ইনক্লুড করলেই pair ব্যবহারের সুবিধা পাওয়া যায়। আর pair টাইপের অবজেক্ট সহজে ক্রিয়েট করার জন্য <utility> হেডারের make_pair() ফাংশন ব্যবহার করা যায়। আর pair-এর ১ম আর ২য় এলিমেন্টকে যথাক্রমে .first আর .second মেম্বার দিয়ে অ্যাক্সেস করা যায়। নিচে একটা উদাহরন দেখানো হলঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include <iostream> #include <string> #include <utility> using namespace std; int main() {     // simple constructions     pair< int, int > px, py;     pair< int, int > p1(23, 43);     pair< int, int > p2 = pair< int, int >(234, 534);     px = p1;     py.first = p2.first * px.second, py.second = p2.second * px.first;     cout << "py: (" << py.first << ", " << py.second << ")\n";           // bit more complex     pair< pair< int, int >, pair< int, int > > p3;     p3 = pair< pair<int, int>, pair< int, int > > (px, py);     cout << "p3: ((";     cout << p3.first.first << ", " << p3.first.second << "), (";     cout << p3.second.first << ", " << p3.second.second << "))\n";           // using make_pair()     pair< double, pair< string, int > > p4;     p4 = make_pair(3.14159, make_pair("pi", 5) );     cout << "this is " << p4.second.first << ", value: " << p4.first;     cout << " precision: " << p4.second.second << " digits\n";     return 0; }

pair নিয়ে সবচেয়ে বেশি যে কথাটা শোনা যায় তা হল, মানুষজন নাকি .first.second.second.first…. এরকম চেইন লিখতে লিখতে টায়ার্ড হয়ে যায়। কিন্তু একটু কাজ করেই এইটাকে সহজ করে ফেলা যায়, যেমন, নিচের কোডে pair কে #define করে নেওয়া হয়েছেঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <iostream> using namespace std; #define pii pair< int, int > #define ppi pair< pii, int > #define ff first #define ss second int main() {     ppi p1;     pii p2;     cin >> p2.ff >> p2.ss;     p1 = ppi( p2, p2.ss * p2.ff );     cout << "entry: " << p1.ff.ff << ", " << p1.ff.ss << endl;     cout << "product: " << p1.ss << endl;     return 0; }

অন্যান্য STL কন্টেইনারের ডাটা টাইপ হিসাবেও pair ব্যবহার করা যায়। যেমন, বি.এফ.এস. অ্যালগরিদমে প্রায়ই কিউতে একজোড়া নাম্বার রাখতে হতে পারে, অথবা ডায়াকস্ট্রার অ্যালগরিদমে পুরা একটা এজকে প্রাইওরিটি কিউতে রাখার ব্যাবস্থা করতে হয়। এটাও খুব সহজেই করা যায়ঃ

1 2 3 4 5 6 7 8

#include <queue> using namespace std; #define pii pair< int, int > #define edge pair< int, pii > // edge.first is weight, edge.second is a pair indicating endpoints queue< pii > Q; priority_queue< edge, vector< edge >, greater< edge > > PQ;

সতর্কতাঃ

অন্যান্য সব STL অবজেক্টের মত, এখানেও একটা ব্যাপার খেয়াল করতে হবে তা হলঃ উপরের উদাহরন গুলাতে দেখা যায় কন্সট্রাকশন শেষ করার সময় মাঝে মাঝে পর পর দুইটা > ব্যবহার করতে হয়, (যেমন প্রাইওরিটি কিউ এর উদাহরনে শেষে ……greater< edge > >, এখানে শেষ ২টা > এর মাঝখানে একটা স্পেস ব্যবহার করা হয়েছে, এটা কিন্তু সৌন্দর্য বর্ধনের জন্য না। এটা না দিলে অনেক সময় কম্পাইলারের মাথা গরম হয়ে যায়। কারন সি++ এ >> আরো কয়েকটা অপারেটরের কাজ করে। আর যেসব যায়গায় দেখা যায় pair ইউজ করলে আরো ঝামেলা হয়, সেখানে নরমাল স্ট্রাকচার ব্যবহার করাটাই বেশি ভাল। এটা জেনে রাখা ভাল, আর জানলেই যে বসাতে হবে এমনও কোন কথা নাই।

ব্যবহারঃ

সাধারনতঃ STL এর টেমপ্লেট ক্লাসগুলোর ওভারলোডিং সুবিধা নেওয়ার জন্য এবং ছোটো খাটো স্ট্রাকচারের শর্টহ্যান্ড হিসাবে pair ব্যবহার করা হয়ে থাকে। এছাড়া std::map এ হাশিং এর সময় pair ব্যবহার করা হয়। প্রোগ্রামিং প্রবলেমগুলাতে গ্রাফ আর জিওমেট্রিক রিপ্রেজেন্টেশনে pair অনেক ব্যবহার করা হয়।
আশা করি যারা আগ্রহি হবে তারা এটাকে নিয়ে আরো কিছুক্ষন ঘাটাঘাটি করবে, কারন ঘাটাঘাটি খোচাখুচি করাই প্রোগ্রামিং শেখার সবচেয়ে ভাল টেকনিক।
বিস্তারিতঃ http://www.cplusplus.com/reference/std/utility/pair/

বিভাগ:ডাটা স্ট্রাকচার, প্রোগ্রামিং Tags: c++, data structure, pair, programming, stl

C++ STL :: priority_queue

অগাষ্ট 17, 2010 zobayer2009 3 comments

প্রায়োরিটি কিউঃ

সব ডাটা-স্ট্রাকচারই যে ধোয়া তুলসি পাতা, এইটা বলা যায় না, বিশেষতঃ যখন “জোর যার মুল্লুক তার” টাইপের এই ডাটা-স্ট্রাকচারটা প্রায়ই ব্যবহার করতে হয়, C++ STL এর priority_queue, এটা একটা বাইনারি হিপ ডাটা-স্ট্রাকচার (ডিফল্টঃ ম্যাক্স হিপ)। সহজ বাংলায়, হিপ হল এমন একটা ট্রি ডাটা-স্ট্রাকচার যেখানে সবচেয়ে বড় (ম্যাক্স হিপ) বা সবচেয়ে ছোট (মিন হিপ) এলিমেন্টটা সবসময় রুটে থাকবে। তাই, যদি এমন একটা ঘটনা ঘটে যে, একদল লোক লাইন দিছে কাঙ্গালি ভোজে, এমন টাইমে মাস্তান টাইপের এক ফকির আসছে, আর লোকজন ভয় পেয়ে তাকে লাইনের সামনে দাঁড়া করায় দিবে, তখন প্রায়রিটি কিউ ছাড়া উপায় নাই, অর্থাৎ খালি আগে আসলেই হবে না, যথেষ্ট পরিমানে ভাব নিয়ে আসতে হবে।
এইটা খুব সহজেই করা যায়, বার বার চেক করে যে নেক্সট কার প্রায়রিটি বেশি, কিন্তু এইভাবে করাটা আন-এফিসিয়েন্ট, তার চেয়ে হিপের মত একটা ট্রি ডাটা-স্ট্রাকচার ব্যবহার করে অনেক কম সময়ে এই কাজ করা যায়, আর সেই কাজটাকে আর সহজ করে দেওয়ার জন্যই আছে priority_queue, queue এর মত এটাও একটা অ্যাডাপ্টার ক্লাস, তার মানে হল, যে সব STL কন্টেইনার front(), push_back(), pop_back() এই অ্যাকসেস দেয়, তাদেরকে priority_queue এর ইন্টারনাল কন্টেইনার হিসাবে ব্যবহার করা যাবে। আর এটা ব্যবহার করতে চাইলে std <queue> হেডারটা প্রোগ্রামে ইনক্লুড করতে হবেঃ

1 2	#include <queue> using namespace std;

কনস্ট্রাকশনঃ

priority_queue বেশ কয়েকভাবে বানানো যায়, বাই ডিফল্ট এটা ম্যাক্স হিপ ইম্পলিমেন্ট করে আর এলিমেন্ট কম্পেয়ার (ছোট-বড় বুঝার জন্য) করার জন্য <queue> এর less<type_t> ক্লাস ব্যাবহার করে। চাইলে এটাকে অন্য কোন কন্টেইনার যেমন vector কে ইন্টারনাল কন্টেইনার হিসাবে ডিফাইন করে দেওয়া যায়, আর বিল্ট ইন বা ওভারলোডেড টেমপ্লেট টাইপ ছাড়াও এটা বানানো যায়, সেক্ষেত্রে ডাটার নিজের ডিফল্ট কম্পেয়ারিজন ক্লাস ব্যবহার করতে হবেঃ < কে ওভারলোড করে, অথবা এক্সপ্লিসিট কম্পেয়ারিজন ক্লাসে () কে ওভারলোড করে। আর, মিন হিপ বানানোও সহজ, <queue> এ ডিফাইন করা greater<type_t> ক্লাস ব্যবহার করে খুব সহজেই করা যায়। যেমনঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

// constructing priority queues #include <iostream> #include <queue> using namespace std; class mycomparison {     bool reverse; public:     mycomparison(const bool& revparam=false) { reverse = revparam; }     bool operator() (const int& lhs, const int&rhs) const {         if (reverse) return (lhs>rhs);         else return (lhs<rhs);     } }; int main () {     int myints[]= {10,60,50,20};           // default construction     priority_queue<int> first;     priority_queue<int> second (myints,myints+3);           // using greater<> to create min heap     priority_queue< int, vector<int>, greater<int> > third (myints,myints+3);           // using "mycomparison" comparison class     priority_queue< int, vector<int>, mycomparison > fourth;           typedef priority_queue<int,vector<int>,mycomparison> mypq_type;     mypq_type fifth (mycomparison());     mypq_type sixth (mycomparison(true));           return 0; }

কমপ্লেক্সিটিঃ ইনিশিয়াল এলিমেন্টের সাপেক্ষে লিনিয়ার, ইনিশিয়ার এলিমেন্ট অ্যাসাইন না করলে কন্সট্যান্ট।

পুশ, পপ, টপঃ

priority_queue এর এলিমেন্ট কে অ্যাকসেস করার জন্য ৩ টা ফাংশন ডিফাইন করা আছে, push(), pop() আর top(). কিউতে কোন এলিমেন্ট অ্যাড করতে চাইলে push() ফাংশনটা ব্যবহার করতে হয়, top() হিপের বর্তমান রুটকে রিটার্ন করে, আর pop() সেটা ট্রি থেকে ডিলিট করে। অর্থাৎ top() আর pop() একত্রে ম্যাক্স হিপের জন্য extract_max() আর মিন হিপের জন্য extract_min() [see: Introduction To Algorithms — CLRS — MIT Press] এর কাজ করে। নিচে উদাহরণ দেওয়া হলঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

// priority_queue::push/pop/top #include <iostream> #include <queue> #include <ctime> #include <cstdlib> using namespace std; int main () {     priority_queue<int> mypq;     srand(time(NULL));           cout << "Pushing some random values...\n";     for(int n, i = 0; i < 10; i++) {         n = rand();         cout << " " << n;         mypq.push(n);     }     cout << endl;           cout << "Popping out elements...\n";     while (!mypq.empty()) {         cout << " " << mypq.top();         mypq.pop();     }     cout << endl;     return 0; }

কমপ্লেক্সিটিঃ push() লগারিদমিক, top() কন্সট্যান্ট, কিন্তু pop() লগারিদমিক।

কিউ এর সাইজ চেক করাঃ

priority_queue এর বর্তমান এলিমেন্ট কতগুলা আছে বা, কিউ খালি কিনা এটা টেস্ট করার জন্য ২ টা ফাংশন ডিফাইন করা আছে, size() আর empty(). কিউ থেকে top() আর pop() ব্যবহার করার আগে অবশ্যই কিউ খালি কিনা চেক করা উচিৎ, তা না হলে রান টাইম এরর জেনারেট হতে পারে। আর, কিউ খালি কিনা এটা empty() মেথড দিয়েই চেক করা উচিত, soze()==0 দিয়ে নয়। STL এর সব কন্টেইনার ক্লাসেই এদের ব্যবহার একি রকমঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

// priority_queue ::size/empty #include <iostream> #include <queue> using namespace std; int main () {     priority_queue<int> myints;     cout << "0. size: " << (int) myints.size() << endl;           for (int i=0; i<10; i++) myints.push(i);     cout << "1. size: " << (int) myints.size() << endl;           myints.pop();     cout << "2. size: " << (int) myints.size() << endl;           while(!myints.empty()) myints.pop();     cout << "3. size: " << (int) myints.size() << endl;           return 0; }

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

ব্যবহারঃ

বাইনারি হিপ তৈরিতে, ডায়াকস্ট্রা আর প্রিম অ্যালগরিদমে ব্যবহার করা হয়, টেমপ্লেট ক্লাস হওয়ায় যে কোন ডাটা টাইপের জন্য খুব দ্রুত কোড ইমপ্লিমেন্ট করা যায়।
বিস্তারিতঃ http://www.cplusplus.com/reference/stl/priority_queue/

বিভাগ:ডাটা স্ট্রাকচার, প্রোগ্রামিং Tags: c++, data structure, priority queue, programming, stl

C++ STL :: queue

জুলাই 30, 2010 zobayer2009 ১টি মন্তব্য

কিঊঃ

আগে আসলে আগে পাবেন, এই রকমের একটা ডাটা স্ট্রাকচার হল কিউ, যাকে আমরা বলি ফার্স্ট ইন ফার্স্ট আউট (FIFO)। এটা C++ STL এর সবচেয়ে বেশি ব্যবহৃত কন্টেইনার ক্লাস। queue এর সামনের দিক থেকে ডাটা এক্সট্র্যাক্ট করা হয়, আর ইনসার্ট করা হয় তার বিপরীত দিক থেকে। তাই, যে সব STL কন্টেইনার push_back() আর pop_front() সাপোর্ট করে সেগুলো দিয়ে কিউ ইমপ্লিমেন্ট করা যায়, যেমন list আর deque. অবশ্য queue এর ডিফল্ট কন্টেইনার হল deque, যদি কিছু বলে না দেয়া হয়। stack এর মত queue ও একটা অ্যাডাপ্টার ক্লাস।
queue ব্যবহার করতে চাইলে std <queue> হেডারটা প্রোগ্রামে ইনক্লুড করতে হবেঃ

1 2	#include <queue> using namespace std;

কন্সট্রাকশনঃ

অন্যান্য কন্টেইনার ক্লাসের মত queue এর সাধারণ কন্সট্রাক্টর queue< type_t > myqueue; এই ধরনের। এছাড়া এক্সপ্লিসিট কন্টেইনার ডিক্লেয়ার করেও queue কন্সট্রাক্ট করা যায়, যেমনঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

// constructing queues #include <deque> #include <list> #include <queue> using namespace std; int main () {     deque< int > mydeck(3,100); // deque with 3 elements     list< int > mylist(2,200); // list with 2 elements           // implicit declaration     queue< int > first; // empty queue     queue< int > second(mydeck); // from a mydeck     queue< int > third(second); // from another queue           // explicit declaration     queue< int, list< int > > fourth; // empty queue     queue< int, list< int > > fifth(mylist); // from mylist     queue< int, deque< int > > sixth; // empty queue     queue< int, deque< int > > seventh(mydeck); // from mydeck           // initialization with operator=     queue< int > eighth = first; // initialized with first     return 0; }

কমপ্লেক্সিটিঃ কন্সট্রাক্টরের সাপেক্ষে কন্সট্যান্ট, অর্থাৎ কন্টেইনারের উপরে নির্ভর করে।

পুশ আর পপঃ

queue এ ডাটা ইন্সার্ট আর এক্সট্র্যাক্ট করার জন্য ২ টা মেম্বার ফাংশন আছে, push() আর pop()। push() এর কাজ হল queue এর শেষে এলিমেন্ট ইন্সার্ট করা আর pop() এর সাহায্যে queue এর সামনে থেকে কোন এলিমেন্ট বের করে দেয়া। যেমনঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

// queue::push/pop #include <iostream> #include <queue> using namespace std; int main() {     queue< int > Q;           // push 5 integers     for(int i=1; i<=5; i++) Q.push(i);           // pop 5 integers     // will be popped in the same order they were pushed     for( ; !Q.empty() ; )     {         cout << Q.front() << endl;         Q.pop();     }           return 0; }

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

ফ্রন্ট আর ব্যাক

queue তে এলিমেন্ট এক্সেসের জন্য ২ টা ফাংশন হল front() আর back(); front() দিয়ে queue এর ফার্স্ট এলিমেন্ট এক্সেস করা যায়, আর back() দিয়ে লাস্ট ইন্সার্ট করা এলিমেন্ট কে পাওয়া যায়। front() আর back() এর এলিমেন্ট কে স্ট্যান্ডার্ড অপারেটর গুলর সাহায্যে মডিফাই করা যায়। যেমনঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

// queue::front/back #include <iostream> #include <queue> using namespace std; int main () {     queue<int> myqueue;           myqueue.push(77);     myqueue.push(16);     cout << "myqueue.front() = " << myqueue.front() << endl;     cout << "myqueue.back() = " << myqueue.back() << endl;           // modify front element     myqueue.front() -= myqueue.back();     cout << "myqueue.front() is now " << myqueue.front() << endl;           // modify back element     myqueue.back() += myqueue.front();     cout << "myqueue.back() is now " << myqueue.back() << endl;     return 0; }

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

কিউ কি খালি?

queue এ এই মুহূর্তে কত গুলা এলিমেন্ট আছে সেটা জানা যায় size() ফাংশনের মাধ্যমে, আর empty() ফাংশন টা boolean, queue খালি থাকলে true দেয়, না হলে false; queue খালি কি না, সেটা চেক করা হয় empty() দিয়ে, কখনই size() এর ভ্যালু ০ কিনা এটা দেখে queue খালি কিনা, সেই টেস্ট করা উচিৎ না, আর queue তে pop() করার আগে আবশ্যই দেখে নিতে হবে queue এ কোন এলিমেন্ট আছে কিনা, তা না হলে run-time error হতে পারে। নিচের কোডে size() আর empty() এর প্রয়োগ দেখানো হলঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// queue::size/empty #include <iostream> #include <queue> using namespace std; int main () {     queue<int> Q;           // just push some elements     for(int i = 0; i < 5; i++) Q.push(i*i);           cout << "Queue has " << Q.size() << " elements" << endl;           Q.pop(); // not a good way, first check for Q.empty()           if(!Q.empty()) Q.pop(); // this is the porper way           while(!Q.empty()) Q.pop(); // pop all element           if(Q.size()==0) cout << "Q is empty" << endl; // not a good way     if(Q.empty()) cout << "Q is empty" << endl; // this is the proper way           return 0; }

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

ব্যবহারঃ

FIFO ডাটা স্ট্রাকচার হিসাবে, BFS ট্রাভার্সাল, বিভিন্ন গ্রাফ এলগরিদমে queue ইম্পলিমেন্ট করা হয়।
বিস্তারিতঃ http://www.cplusplus.com/reference/stl/queue/

বিভাগ:ডাটা স্ট্রাকচার, প্রোগ্রামিং Tags: c++, data structure, programming, queue, stl

C++ STL :: stack

জুলাই 29, 2010 zobayer2009 12 comments

স্ট্যাকঃ

STL কন্টেইনারদের মধ্যে সম্ভবত সবচেয়ে সিম্পল ডাটা স্ট্রাকচার হল stack, এটা একটা লাস্ট ইন ফার্স্ট আউট (LIFO) ডাটা স্ট্রাকচার, মানে হল যে সবার শেষে আসবে, সে সবার আগে ভাগবে… সোজা কথায় এই কন্টেইনারের শুধুমাত্র একটা দিকেই ডাটা ইন্সার্ট বা এক্সট্র্যাক্ট করা হয়। আর STL এ stack তার ডিফল্ট ইন্টার্নাল ডাটা স্ট্রাকচার হিসাবে ব্যবহার করে STL এরই deque কন্টেইনার, তবে চাইলে vector বা list ও ব্যবহার করা যেতে পারে। যে সব কন্টেইনার push_back() আর pop_back() মেথড ২ টা সাপোর্ট করে সেগুলোকেই stack এর কন্টেইনার ক্লাস হিসাবে ব্যবহার করা যায়। stack আসলে একটা অ্যাডাপ্টার ক্লাস, অর্থাৎ, এটা তৈরি করা হয় এর ইন্টারনাল কন্টেইনারের স্পেসিফিক কিছু ফাংশনকে এলিমেন্ট একসেসের অনুমতি দিয়ে।
stack ব্যবহার করতে চাইলে সর্বপ্রথম কাজটা হল std <stack> হেডারটা প্রোগ্রামে ইনক্লুড করাঃ

1 2	#include <stack> using namespace std;

কন্সট্রাক্টরঃ

অন্যান্য STL কন্টেইনার ক্লাসের মত stack এরও সাধারণ কন্সট্রাক্টর stack< type_t > myStack; এই রকমের, তবে আরো অনেকভাবে ডিক্লেয়ার করা যায়। যেমনঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

// constructing stacks #include <list> #include <vector> #include <deque> #include <stack> using namespace std; int main () {     // using default container deque     stack< int > first; // empty stack     deque< int > mydeque(3, 100); // deque with 3 elements     stack< int > second(mydeque); // from mydeque     stack< int > third(second); // from another stack second     // explicit container declarations     stack< int, deque< int > > fourth; // empty stack using deque     deque< int > newdeque(10, 100); // deque with 10 elements     stack< int, deque< int > > fifth(newdeque); // from newdeque     stack< int, vector< int > > sixth;  // empty stack using vector     vector< int > myvector(2, 200); // vector with 2 elements     stack< int, vector< int > > seventh(myvector); // from myvector     stack< int, list< int > > eighth; // empty srack using list     list< int > mylist(4, 100); // list with 4 elements     stack< int, list< int > > ninth(mylist); // from mylist     // can refer to some other stack     stack< int > tenth = first; // declaration time initialization     return 0; }

কমপ্লেক্সিটিঃ কন্টেইনার কন্সট্রাকশনের সাপেক্ষে কন্সট্যান্ট, অতএব কি ধরণের কন্টেইনার ব্যবহার করা হচ্ছে তার উপরে নির্ভর করে।

এলিমেন্ট একসেসঃ

stack ক্লাসের এলিমেন্ট গুলাকে একসেস করার জন্য ৩ টা মেম্বার ফাংশন আছেঃ

1. top()
2. push()
3. pop()

push() ফাংশনটার কাজ stack এর শেষে কোন এলিমেন্ট ইন্সার্ট করা, আর pop() দিয়ে লাস্ট এলিমেন্ট টা বের করে দেয়া। top() এর সাহায্যে কারেন্টলি stack এ সবার উপরের এলিমেন্ট কে পাওয়া যায়। top() এলিমেন্টকে স্ট্যান্ডার্ড অপারেটরদের সাহায্যে মডিফাই করা যায়।
আর, stack এর এলিমেন্ট কাউন্ট করার জন্য ২ টা ফাংশন আছেঃ

1. size()
2. empty()

size() ব্যবহার করে জানতে পারি এই মুহূর্তে stack এ কতগুলো এলিমেন্ট আছে, আর empty() একটা boolean ফাংশন, stack খালি থাকলে এটা true দেয়, না হলে false, stack এ pop() মেথডটা ব্যবহার করতে চাইলে আগে অবশ্যই চেক করে নিতে হবে stack এ কিছু আছে কিনা, তা না হলে run-time error হতে পারে।
নিচে এই ফাংশন গুলার কাজ দেখানো হলঃ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

// stack::push/pop/top/size/empty #include <iostream> #include <stack> using namespace std; int main () {     stack< int > mystack;     // lets push and pop some values     for (int i=0; i<5; i++) mystack.push(i);     cout << "Popping out elements...";     while (!mystack.empty())     {         cout << " " << mystack.top();         mystack.pop();     }     cout << endl;     // changing the value of top     mystack.push(100);     mystack.top() += 1000;     cout << "Now top is: " << mystack.top() << endl;     mystack.pop();     // not a good way to check if stack is empty     if(mystack.size() == 0) cout << "Stack is empty" << endl;     // better we do this     if(mystack.empty()) cout << "Stack is empty" << endl;     return 0; }

কমপ্লেক্সিটিঃ প্রতিটা ফাংশনের কম্পলেক্সিটি কন্সট্যান্ট।

ব্যবহারঃ

সাধারণত এক্সপ্রেশন / গ্রামার প্রসেসিং, রিকারসিভ এলগরিদমের নন রিকারসিভ প্রয়োগ, DFS ট্রাভার্সাল, LIFO অপারেশনে stack ব্যবহার করা হয়। STL এর stack একটা টেমপ্লেট ক্লাস, তাই যে কোন ডাটা টাইপের জন্য খুব দ্রুত stack ইম্পলিমেন্ট করা যায় STL ব্যবহার করে।
বিস্তারিতঃ http://www.cplusplus.com/reference/stl/stack/