সি/সি++

ব্যাকট্র্যাকিং: পারমুটেশন জেনারেটর

[পুরানো লেখা, নতুন করে গুছিয়ে লিখে আবার প্রকাশ করা হলো] ব্যাকট্র্যাকিং একধরণের ব্রুটফোর্স টেকনিক। ব্রুটফোর্সের মতই এটা সম্ভাব্য সবধরণের বিন্যাস-সমাবেশ থেকে ফলাফল খুজে নিয়ে আসে। যেমন ধর তোমাকে ঢাকা থেকে চট্টগ্রামার যাবার সবথেকে ছোটো পথ খুজে বের করতে বলা হলো। তুমি ডায়াক্সট্রার দেয়া অ্যালগোরিদম ব্যবহার না করে উত্তরা থেকে শাহবাগে যাবার যত পথ আছে সবগুলো খুজে বের করলে এবং তারপর তারমধ্যে থেক...
Read More

কোডের এক্সিকিউশন টাইম নির্ণয়

অনেক সময় আমাদের পুরো কোডের বা কোনো নির্দিষ্ট ফাংশনের এক্সিকিউশন টাইম বের করা দরকার হয়। সব ল্যাংগুয়েজেই টাইমার ফাংশন আছে যা ব্যবহার করে এক্সিকিউশন টাইম বের করা যায়। সি/সি++ দিয়ে শুরু করি। [crayon-5bca167906548913877439/] clock() রিটার্ন করে প্রোগ্রাম চালু করার পর সিস্টেম clock tick সংখ্যা। CLOCKS_PER_SEC একটি বিল্টইন ম্যাক্রো যা দিয়ে ভাগ করে আমরা সেকেন্ডে সময় নির্ণয় করতে পারি। পাইথনে ti...
Read More

সিপিপি তে সর্ট এবং স্টেবল সর্ট ফাংশনের পার্থক্য

সিপিপি তো সর্ট আর স্টেবল সর্ট নামের দুটি পৃথক ফাংশন আছে। এই পোস্টের উদ্দেশ্য এদুটির পার্থক্য দেখানো,কিভাবে ব্যবহার করতে হয় শিখানো না। আজকে codeforces কনটেস্টে জিনিসটা মাথায় না থাকার কারণে একদম সহজ প্রবলেমে বিশাল ধরা খেয়েছি। প্রবলেমটির লিংক: http://www.codeforces.com/problemset/problem/63/A এখানে বলা হয়েছে নিচের মত নামের লিস্ট দেয়া হবে: 6 Jack captain Alice woman Charlie man Teddy...
Read More

গ্রাফ থিওরিতে হাতেখড়ি – ৩ (ভ্যারিয়েবলে গ্রাফ স্টোর-২)

আগের পর্ব সবগুলো পর্ব এই পর্বে গ্রাফ স্টোর করার ২য় পদ্ধতি অ্যাডজেসেন্সি লিস্ট নিয়ে লিখব। এ পদ্ধতিতে গ্রাফ স্টোর করে কম মেমরি ব্যবহার করে আরো efficient কোড লেখা যায়। এ ক্ষেত্রে আমরা ডায়নামিক্যালি মেমরি অ্যালোকেট করব,ভয়ের কিছু নেই সি++ এর standard template library(STL) ব্যবহার করে খুব সহজে কাজটা করা যায়। আগের লেখার শেষের দিকে STL এর উপর কয়েকটি টিউটোরিয়ালের লিংক দিয়েছি, আশা করছি ভেক্টর কিভ...
Read More

গ্রাফ থিওরিতে হাতেখড়ি – ২ (ভ্যারিয়েবলে গ্রাফ স্টোর-১)

আগের পোস্টে আমরা দেখেছি গ্রাফ থিওরি কি কাজে লাগে,আর এলিমেন্টারি কিছু টার্ম শিখেছি। এখন আমরা আরেকটু ভিতরে প্রবেশ করবো। প্রথমেই আমাদের জানা দরকার একটা গ্রাফ কিভাবে ইনপুট নিয়ে স্টোর করে রাখা যায়। অনেকগুলো পদ্ধতির মধ্যে দুটি  খুব কমন: ১. অ্যাডজেসেন্সি ম্যাট্রিক্স(adjacency matrix) ২. অ্যাডজেসেন্সি লিস্ট(adjacency list) অ্যাডজেসেন্ট(adjacent) শব্দটার অর্থ "কোন কিছুর পাশে"। যেমন তোমার...
Read More

গ্রাফ থিওরিতে হাতেখড়ি – ১

(গ্রাফ অ্যালগরিদম বইটি অনলাইনে পাওয়া যাচ্ছে রকমারি.কম এ। এছাড়াও নীলক্ষেতে হক, মানিক এবং রানা লাইব্রেরিতে বইটি পাওয়া যাচ্ছে) তুমি কি জানো পৃথিবীর প্রায় সব রকমের প্রবলেমকে কিছু রাস্তা আর শহরের প্রবলেম বানিয়ে সলভ করে ফেলা যায়? গ্রাফ থিওরির যখন জন্ম হয় তখন তোমার আমার কারোই জন্ম হয়নি, এমনকি পৃথিবীতে কোন কম্পিউটারও ছিলোনা! সেই সতেরো দশকের শেষের দিকে লিওনার্দ অয়লার গ্রাফ থিওরি আবিষ্কার করেন কনিসবা...
Read More