কিছু প্রোগ্রামিং সমস্যা

প্রোগ্রামিং সমস্যা

এই অ‌ধ্যায়ে আমরা কয়েকটি সহজ সমস্যা দেখব ও সমাধানের চেষ্টা করব।
আমাদের প্রথম সমস্যা হচ্ছে, বিভিন্ন ধরনের আকৃতি তৈরি করা। নিচের ছবিগুলো দেখো।
তোমাদের চারটি প্রোগ্রাম লিখতে হবে এই চার ধরনের আকৃতি তৈরি করার জন্য। কেবল printf ফাংশন ব্যবহার করলেই হবে না, লুপ ব্যবহার করতে হবে। তাহলে লুপ বা নেস্টেড লুপ, এবং 'c' ও ' ' (স্পেস ক্যারেক্টার) প্রিন্ট করে তোমরা প্রোগ্রামগুলো লিখে ফেলতে পারো। আরও খেলাধুলা করার ইচ্ছা হলে আরও নানান রকম আকৃতি তৈরির চেষ্টা করতে পার।
প্যালিন্ড্রোম (palindrome) কী জিনিস, তোমরা জান? কোনো শব্দকে উল্টাভাবে (মানে শেষ থেকে শুরু) লিখলে যদি সেটি আর নতুন শব্দটি একই রকম হয় তবে সেটি একটি প্যালিন্ড্রোম। যেমন: madam। এটিকে শেষ থেকে শুরু পর্যন্ত লিখলেও madam হবে। এখন একটি প্রোগ্রাম লিখব যেটিতে কোনো শব্দ ইনপুট দিলে সেটি প্যালিন্ড্রোম কি না বলে দেবে।
এজন্য আমরা কী করতে পারি? প্রথমে শব্দটি স্ট্রিং হিসেবে একটি অ্যারেতে ইনপুট নেব। তারপর আরেকটি অ্যারেতে সেটি উল্টাভাবে রাখব। তারপর যদি দুটি একই স্ট্রিং হয়, তবে সেটি প্যালিন্ড্রোম। তাহলে প্রোগ্রামটি লিখে ফেলি:
#include <stdio.h> #include <string.h> int main() { char word[80], reverse_word[80]; int i, j, len; scanf("%s", word); len = strlen(word); for(i = 0, j = len - 1; i < len; i++, j--) { reverse_word[i] = word[j]; } reverse_word[i] = '\0'; printf("%s\n", reverse_word); if (0 == strcmp(word, reverse_word)) { printf("%s is a palindrome.\n", word); } else { printf("%s is not a palindrome.\n", word); } return 0; } প্রোগ্রাম: ১৩.১
কী মজা! আমি প্রোগ্রামটি লিখে দিলাম। তবে আমি এখানে বেশ কিছু বোকামি করেছি, যার মধ্যে অন্যতম হচ্ছে একটি অতিরিক্ত অ্যারে ব্যবহার করা। সুতরাং তোমাদের এখন প্রোগ্রামটি এমনভাবে লিখতে হবে, যাতে কেবল একটি অ্যারে ব্যবহার করেই কাজ হয়। আর তখন strcmp ফাংশনটিরও দরকার হবে না। প্রোগ্রামটি লিখতে সময় বেশি লাগতে পারে, লাগুক, অসুবিধা নেই। তবে লিখতে হবে ঠিকঠাক, এটিই হলো কথা।
তোমরা তো ফ্যাক্টরিয়াল (factorial) জিনিসটির সঙ্গে পরিচিত? এটি একটি গাণিতিক অপারেশন যা কোনো ধনাত্মক পূর্ণসংখ্যার ক্ষেত্রে ব্যবহার করা যায়। n একটি ধনাত্মক পূর্ণ সংখ্যা হলে-এর ফ্যাক্টরিয়ালকে প্রকাশ করা হয় n! দিয়ে এবং n! = n * (n – 1) * (n – 2) * … * 3 * 2 * 1। যেমন 4! = 4 * 3 * 2 * 1 = 24। আবার 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720। 1! = 1। 0! = 1 (0-এর ক্ষেত্রে ব্যতিক্রমটি লক্ষ করো, কিছু বিশেষ সুবিধার জন্য 0-এর ফ্যাক্টরিয়ালের মান 1 ধরা হয়)। এখন তোমরা কোনো ধনাত্মক পূর্ণসংখ্যার ফ্যাক্টরিয়াল বের করার প্রোগ্রামটি লিখে ফেলো। সহজ প্রোগ্রাম, একটি লুপ ব্যবহার করেই করা যায়। এখন বিভিন্ন সংখ্যা দিয়ে প্রোগ্রামটি টেস্ট করে দেখো ফ্যাক্টরিয়াল ঠিকঠাক বের করতে পারে কি না। প্রোগ্রামে তুমি যদি ডাটা টাইপ int ব্যবহার করে থাক তবে 12-এর চেয়ে বড় কোনো পূর্ণ সংখ্যার ফ্যাক্টরিয়ালের মান ঠিকমতো দেখাবে না (ক্যালকুলেটরে করে মিলিয়ে দেখতে পারো)। কারণ হচ্ছে 12-এর চেয়ে বড় কোনো পূর্ণ সংখ্যার জন্য সেই সংখ্যার ফ্যাক্টরিয়ালের মান রেঞ্জের বাইরে চলে যায়।
এখন তোমাদের একটি মজার সমস্যা সমাধান করতে হবে। কোনো পূর্ণসংখ্যা n (যেখানে 1 < n < 100, মানে n-এর মান 2 থেকে 99 পর্যন্ত হতে পারে)-এর ফ্যাক্টরিয়ালকে মৌলিক সংখ্যার গুণফল হিসেবে প্রকাশ করলে কোন মৌলিক সংখ্যা কতবার আছে সেটি বের করতে হবে। যেমন, আমরা জানি, 5! = 120 = 2 * 2 * 2 * 3 * 5। এখানে 2 আছে 3 বার, 3 আছে 1 বার আর 5 আছে 1 বার। তাই ইনপুট 5 হলে আউটপুট হবে: 5! = (2, 3), (3, 1), (5, 1)। তোমরা কি একটি ব্যাপার বুঝতে পারছ যে শুরুতে n-এর ফ্যাক্টরিয়ালের মান বের করে তারপর মৌলিক উৎপাদকে ভাঙতে গেলে একটি ঝামেলা হয়ে যাবে? কারণ n-এর মান সর্বোচ্চ হতে পারে 99 আর ইন্টিজারে তো 12-এর চেয়ে বড় কোনো সংখ্যার ফ্যাক্টরিয়ালের মান রাখা যায় না। আসলে এই প্রোগ্রামের জন্য n!-এর মান বের করার কোনো দরকার নেই। শুধু একটু গাণিতিক যুক্তি-বুদ্ধি খাটাও। আর 2 থেকে 99 পর্যন্ত মৌলিক সংখ্যাগুলো একটি অ্যারেতে রেখে নাও। প্রোগ্রামটি ঠিকভাবে করতে তোমাদের অনেকেরই দু-তিন দিন সময় লেগে যেতে পারে, এতে হতাশ হওয়ার কিছু নেই।
এখন আমরা একটি প্রোগ্রাম লিখব। যার উদ্দেশ্য হবে কোনো অ্যারেতে কিছু সংখ্যা থাকলে সেগুলোকে ছোট থেকে বড় ক্রমে সাজানো। যেমন, কোনো অ্যারে যদি এমন হয়: int ara[] = {3, 1, 5, 2, 4}, তবে আমাদের প্রোগ্রাম সেই অ্যারের সংখ্যাগুলো এমনভাবে সাজাবে, যাতে ara[] = {1, 2, 3, 4, 5} হয়।
প্রোগ্রামটি একটু পরে লিখব, তার আগে ঠিক করে নেই যে সেটি কীভাবে কাজ করবে। তোমার কাছে পাঁচটি সংখ্যা আছে: 3, 1, 5, 2, 4। ছোট থেকে বড় ক্রমে সাজাতে হবে। তুমি প্রথমে কী করবে? প্রথমে সবচেয়ে ছোট সংখ্যাটি খুঁজে বের করে তাকে শুরুতে লিখবে: 1। তখন বাকি থাকে চারটি সংখ্যা: 3, 5, 2, 4। এখন এই চারটির মধ্যে সবচেয়ে ছোট সংখ্যাটি 1-এর পরে লিখবে: 1, 2। বাকি রইল 3, 5, 4। এদের মধ্যে সবচেয়ে ছোট 3। তাই তুমি লিখবে : 1, 2, 3। এখন বাকি 5, 4। এই দুটি সংখ্যার মধ্যে সবচেয়ে ছোট 4। সেটি তুমি 3-এর পরে লিখবে: 1, 2, 3, 4। এখন বাকি একটি সংখ্যা, 5। সেটি তুমি 4-এর পরে লিখবে। 1, 2, 3, 4, 5। তোমার সাজানোর কাজ হয়ে গেল। একে সর্টিং (sorting) বলে। বিভিন্ন উপায়ে এটি করা যায়। তবে আমরা একটি সহজ-সরল উপায়ে করলাম।
আমরা যেভাবে কাজটি করেছি, সেটি উইকিপিডিয়াতে চমৎকার একটা অ্যানিমেশনের সাহায্যে দেখানো হয়েছে। অ্যানিমেশনটি একবার দেখলে বোঝা কঠিন, তাই আমার পরামর্শ হচ্ছে কমপক্ষে চার-পাঁচবার এটি দেখো।
এখন প্রোগ্রামটি লিখব কীভাবে?
প্রথমে একটি অ্যারেতে সংখ্যাগুলো রাখো: int ara1[] = {3, 1, 5, 2, 4}; এখন আরেকটি অ্যারে নাও:

int ara2[5]; অ্যারেটি এখনো খালি। তাই একটি ভেরিয়েবলে ইনডেক্স 0 লিখে রাখো। int index_2 = 0; এখন একটি একটি করে ara2তে সংখ্যাগুলো রাখতে হবে। তার জন্য একটি লুপ দরকার। for(index_2 = 0; index_2 < 5; index_2++) // মানে 0 থেকে 4 পর্যন্ত প্রতিটি ঘরে আমরা সংখ্যা বসাব। এই লুপের ভেতরে আরেকটি লুপ দরকার যেটি দিয়ে আমরা ara1-এর সবচেয়ে ছোট সংখ্যা খুঁজে বের করব। minimum = 100000; // এমন একটি বড় সংখ্যা অ্যাসাইন করলাম যেটি ara1-এর যেকোনো সংখ্যার চেয়ে বড়। for (i = 0; i < 5; i++) {  if (ara1[i] < minimum) {   minimum = ara1[i];  } } এখন ara1-এর ক্ষুদ্রতম সংখ্যাটি minimum এ চলে এল। সেটি এখন ara2 তে রাখি: ara2[index_2] = minimum। সবশেষে ara2-এর সব সংখ্যা প্রিন্ট করে দেখব। এবারে চলো, পুরো প্রোগ্রামটি লিখে কম্পাইল ও রান করে দেখি আউটপুট কী আসে। 

#include <stdio.h> int main() { int ara1[] = {3, 1, 5, 2, 4}; int ara2[5]; int i, minimum, index_2; for (index_2 = 0; index_2 < 5; index_2++) { minimum = 10000; for (i = 0; i < 5; i++) { if (ara1[i] < minimum) { minimum = ara1[i]; } } ara2[index_2] = minimum; } for (i = 0; i < 5; i++) { printf("%d\n", ara2[i]); } return 0; } প্রোগ্রাম: ১৩.২

কী সুন্দর প্রোগ্রাম! আউটপুট কী? আউটপুটও খুব সুন্দর, একে একে পাঁচটি 1।

1 1 1 1 1

কিন্তু আমরা তো এমন আউটপুট চাইনি। কোথাও গোলমাল হয়েছে। এখন আমার কোডে দেখো তো কোনো ভুল বের করা যায় কি না।

একটি ঝামেলা হয়েছে। ভেতরের লুপে (যেখানে সবচেয়ে ছোট সংখ্যা বের করা হয়) কিন্তু সব সময়ই minimum-এর মান 1 আসবে, কারণ 1 হচ্ছে ওই পাঁচটির মধ্যে সবচেয়ে ছোট সংখ্যা। এজন্য দ্বিতীয় অ্যারেতে পাঁচটি সংখ্যাই 1 হয়ে যাচ্ছে। তাই আমরা যখন minimum বের করব, তখন অ্যারের যেই ঘরে সবচেয়ে ছোট সংখ্যা পাব সেই ঘরের মান একটি অনেক বড় সংখ্যা দিয়ে দেব। এজন্য একটি ভেরিয়েবল রাখি minimum_index। আর লুপটি এখন এমন হবে:

minimum = 10000; for (i = 0; i < 5; i++) { if (ara1[i] < minimum) { minimum = ara1[i]; minimum_index = i; } }

এখন minimum-এর মান আমরা পেয়ে গেছি এবং সেই সঙ্গে এটিও জানি যে এটি আসলে আছে ara1[minimum_index] ঘরে। ara1[minimum_index] = 10000;

তাহলে প্রোগ্রামটি ঠিক করে আবার চালাই:

#include <stdio.h> int main() { int ara1[] = {3, 1, 5, 2, 4}; int ara2[5]; int i, minimum, index_2, minimum_index; for (index_2 = 0; index_2 < 5; index_2++) { minimum = 10000; for (i = 0; i < 5; i++) { if (ara1[i] < minimum) { minimum = ara1[i]; minimum_index = i; } } ara1[minimum_index] = 10000; ara2[index_2] = minimum; } for (i = 0; i < 5; i++) { printf("%d\n", ara2[i]); } return 0; } প্রোগ্রাম: ১৩.৩

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

রোবট নিয়ে এখন আমরা একটি প্রোগ্রাম লিখব। কোনো একটি N x N গ্রিডে একটি রোবট আছে। শুরুতে তার একটি অবস্থান আছে। আমরা সেটিকে কিছু কমান্ড দেব, এক ঘর ডানে, বাঁয়ে, ওপরে ও নিচে যাওয়ার কমান্ড 

।
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (0, 7) (0, 8) (1, 0)
(1, 2)
(2, 0) (2, 1) R (2, 2) (2, 3)
(3, 0)
(3, 2)
(4, 0)
(5, 0)
(6, 0)
(7, 0)
(8, 0)
(8, 8)
গ্রিডটি দেখো। ওপরের একেবারে বাঁ দিকের ঘর হচ্ছে (0, 0)। ওপরের একেবারে ডানদিকের ঘর হচ্ছে (0, 8)। নিচের একেবারে বাঁ দিকের ঘর হচ্ছে (8, 0)। নিচের একেবারে ডান দিকের ঘর হচ্ছে (8, 8)। ধরা যাক, এই মুহূর্তে রোবটটি আছে (2, 2) ঘরে। এক ঘর ওপরে যেতে বললে সে যাবে (1, 2) ঘরে। নিচে যেতে বললে যাবে (3, 2) ঘরে। ডানে আর বাঁয়ে যেতে বললে যথাক্রমে (2, 3) ও (2, 1) ঘরে যাবে। কমান্ডগুলো হচ্ছে U (up), D (down), L (left), R (right), S (stop)। এখন তোমাকে যদি শুরুর অবস্থান আর কমান্ডগুলো বলে দিই, তাহলে রোবটের শেষ অবস্থান (stop করার পর অবস্থান) বের করতে হবে।
তোমরা কি প্রোগ্রামটি নিজে লিখার জন্য কিছুক্ষণ চেষ্টা করবে?
তোমরা নিশ্চয়ই বুঝতে পারছ যে একটি 2-D অ্যারে দরকার হবে এই প্রোগ্রামে। আসলে কিন্তু এখানে অ্যারের কোনোই দরকার নেই। এটি সাধারণ যোগ-বিয়োগের প্রোগ্রাম। মনে করি, শুরুর অবস্থান হচ্ছে (x, y)। এখন U কমান্ড দিলে একঘর ওপরে যাবে, তখন x-এর মান এক কমে যাবে, y-এর মানের কোনো পরিবর্তন হবে না। D কমান্ড দিলে এক ঘর নিচে যাবে, তখন x-এর মান এক বেড়ে যাবে, y-এর মানের কোনো পরিবর্তন হবে না। R কমান্ড দিলে y-এর মান এক বাড়বে, x-এর মান অপরিবর্তিত থাকবে। L কমান্ড দিলে y-এর মান এক কমবে, x-এর মান অপরিবর্তিত থাকবে। তাহলে আমাদের পুরো প্রোগ্রামটি দাঁড়াবে এই রকম:
#include <stdio.h> int main() { int x, y; char c; printf("Please enter the initial position: "); scanf("%d %d", &x, &y); while (1) { scanf("%c", &c); if (c == 'S') { break; } else if (c == 'U') { x--; } else if (c == 'D') { x++; } else if (c == 'R') { y++; } else if (c == 'L') { y--; } } printf("Final position of the robot is: %d, %d\n", x, y); return 0; } প্রোগ্রাম: ১৩.৪
আউটপুট কী হবে সেটি নির্ভর করবে তোমার ইনপুটের ওপর। যেমন: Please enter the initial position: 2 2 D R D R S Final position of the robot is: 4, 4
বেশ সহজ সরল প্রোগ্রাম। কিন্তু এখন যদি বলি যে গ্রিডে কিছু কিছু ঘরে যাওয়া নিষেধ এবং ওই ঘরগুলোতে যেতে বললে রোবটটি কিছুই করবে না (অর্থাৎ ওই কমান্ডকে উপেক্ষা করবে), তখন আমরা প্রোগ্রামটি কীভাবে লিখব? যেমন একটি উদাহরণ দিই। ধরা যাক, (0, 4) ঘরটি নিষিদ্ধ (blocked)। যদি রোবটের অবস্থান হয় (0, 3) ঘরে এবং তাকে 'R' কমান্ড দেওয়া হয়, তখন তার অবস্থানের কোনো পরিবর্তন হবে না। কারণ এক ঘর ডানে (মানে (0, 4) ঘরে) যাওয়া সম্ভব নয়।
এই সমস্যার সমাধান করতে যে প্রোগ্রামটি লিখতে হবে, তাতে কিন্তু একটি 2-D অ্যারে ব্যবহার করতে হবে। এই অ্যারের সাহায্যে আমরা বুঝব যে কোন ঘরে যাওয়া যাবে আর কোন ঘরে যাওয়া যাবে না। সেটি কীভাবে? খুবই সহজ। যেসব ঘরে যাওয়া যাবে অ্যারের ওই ঘরগুলোতে 1 আর যেসব ঘরে যাওয়া যাবে না সেগুলোতে 0 রাখব।
প্রথমে 10 x 10 গ্রিডের জন্য একটি 2-D অ্যারে ডিক্লেয়ার করি: int grid[10][10];
তারপর শুরুতে ধরে নিই সব ঘরে যাওয়া যাবে।
for (i = 0; i < 10; i++) { for (j = 0; j < 10; j ++) { grid[i][j] = 1; } }
এখন কোন কোন ঘরগুলোতে যাওয়া যাবে না তা ব্যবহারকারীর কাছ থেকে ইনপুট নিই:
printf("Please enter the number of blocked cells: "); scanf("%d", &n); printf("Now enter the cells: "); for (i = 0; i < n; i++) { scanf("%d %d", &x, &y); grid[x][y] = 0; }
এখন কোনো ঘরে যাওয়া যাবে কি না, সেটি বোঝার জন্য একটি শর্ত পরীক্ষা করলেই হবে।
if (grid[x][y] == 1) { যদি সত্য হয়, তবে (x, y) ঘরে যাওয়া যাবে। }
এখন তোমরা সম্পূর্ণ প্রোগ্রামটি নিজে নিজে লিখে ফেলো