বাইনারি সার্চ ঃ
নিচের উদাহরণগুলো লক্ষ করো:
এবারে প্রোগ্রাম লিখার পালা।
প্রোগ্রামটি চালাও। তারপর নিচের প্রোগ্রামটি চালাও। আউটপুটে কি পার্থক্য দেখতে পাচ্ছ? পার্থক্যের কারণটা কী?
This
Is
A
বাইনারি সার্চ।
একটি
সহজ খেলা দিয়ে শুরু করা যাক। এটি খেলতে দুজন দরকার। একজন মনে মনে একটি
সংখ্যা ধরবে। আর দ্বিতীয়জন কিছু প্রশ্ন করে সেই সংখ্যাটি বের করবে। তবে
'তোমার সংখ্যাটি কত?' - এমন প্রশ্ন কিন্তু সরাসরি করা যাবে না। প্রশ্নটি
হচ্ছে:
সংখ্যাটি কি 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
আর বাইনারি সার্চ কীভাবে কাজ করে, সেটি এখানে সুন্দর করে অ্যানিমেশনের মাধ্যমে বোঝানো হয়েছে:
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, …) দিয়ে ভাগ করার চেষ্টা করাটা আসলে বোকামি। জোড় সংখ্যা দিয়ে বিভাজ্যতার পরীক্ষাটা আমরা ফাংশনের শুরুতেই করে নিতে পারি। এখন আমাদের ফাংশনটির চেহারা দাঁড়াবে এই রকম:
একটি বুদ্ধি তোমাদের মাথায় এর মধ্যেই নিশ্চয়ই এসে গেছে। সেটি হচ্ছে 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-এর চেয়ে ছোট বা সমান হয়।
এখন তোমরা কোডটি লিখার চেষ্টা করো। কমপক্ষে তিন ঘণ্টা নিজে চেষ্টা করার পর এবারে আমার কোড দেখো।
প্রাইম নম্বর বের করতে পেরে তোমরা নিশ্চয়ই বেশ খুশি? কিন্তু আমাদের চেষ্টা এখানেই থেমে থাকবে না। আমরা এখন দেখব আরেকটি চমৎকার পদ্ধতি, গ্রিক গণিতবিদ ইরাতোসথেনেস (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।