LCM
প্রোগ্রামিং প্রবলেম সলভিংয়ে এলসিএম বেশ কমন। সাধারণত দুটি সংখ্যা দেয়া থাকে এবং এদের এলসিএম বের করতে হয়। এখানে যে প্রবলেমটি নিয়ে আলোচনা করা হয়েছে, এতে দুটি সংখ্যার ল.সা.গু(LCM) এবং সংখ্যা দুটির যেকোন একটি দেয়া আছে, অপর সংখ্যাটি বের করতে হবে। প্রথমে কিভাবে দুটি সংখ্যার এলসিএম নির্ণয় করতে হয় দেখা যাক -
(এলসিএম নির্ণয় করার জন্য একেকজন একেক নিয়ম অনুসরণ করে থাকে। আমরা নিচের নিয়মে করবো কারণ এতে গ.সা.গু নির্ণয় করাও শিখে ফেলা যাবে।)
১. সংখ্যা দুটির গ.সা.গু(GCD) নির্ণয় করতে হবে। ২. সংখ্যাদ্বয়ের গুণফলের পরমমানকে গ.সা.গু দিয়ে ভাগ দিলেই ল.সা.গু পাওয়া যাবে। এই কাজটি আহামরি কিছু না। অনেকেই আগে থেকেই জানো কিভাবে ল.সা.গু এবং গ.সা.গু বের করতে হয়।
ধর, সংখ্য্যা দুটি $a, b$ এবং গুণফল হল $m$। তাহলে, $lcm(a, b) = m/gcd(a, b)$
গসাগু(GCD) নির্ণয় করার জন্য ইউক্লিড বহু বছর আগে অসাধারণ একটি এলগরিদম লিখে গেছেন। ইউক্লিডীয় এলগরিদম সম্পর্কে জানতে এই লিঙ্কটি ফলো কর- http://en.wikipedia.org/wiki/Greatest_common_divisor
যাইহোক, আমাদের সমস্যায় ফিরে আসি। উপরের কনসেপ্টটিকে এভাবে লেখা যায়-
1
2
3
$a*b = lcm(a,b)* gcd(a,b)$
$a*b = c * gcd(a, b)$ এখানে $c = gcd(a, b)$, c এর মান দেয়া থাকবে
উপরের সমীকরণকে এভাবে লেখা যায়ঃ $b/gcd(a,b) = c/a$
আমরা সমস্যার সমাধান রিতীমত করে ফেলেছি!
সমস্যাটিতে $a$ এবং $c$ এর মান দেয়া থাকবে। আমাদের বের করতে হবে $b$ এর মান।
1
2
প্রবলেম কোড লেখার প্রক্রিয়া-
c/a এর মানকে লুপের ইনিশিয়াল ভেলু i=c/a তে এসাইন। এবার লুপ চালাতে থাকো। লুপ ঘুরবে গসাগু (c) এর সমান মান পর্যন্ত। লুপের ভেতরে মান ইনক্রিমেন্ট করবে c/a এর মান যত তত করে। যদি i/gcd(a, i) = c/a হয় তাহলে লুপ ব্রেক করো এবং i এর মানই হল আমাদের টার্গেট ভেলু b.
বুঝতে সমস্যা হলে শুরু থেকে আবার পড় লেখাটা। তাও যদি না বুঝ তাহলে নিচের কোডটি দেখ। আশাকরি ধারণা পরিষ্কার হবে।
1
2
3
4
5
target = c/a;
for (i = target; i <= c; i += target){
if (i / gcd(i, a) == target){
b = i;
}
পুরো কোড পেতে এখানে যাও । ঠিক এরকম একটা প্রবলেম UVA Online Judge এ দেয়া আছে। উপরের কোডটিও ঐ পবলেমটির সলভ। প্র্যাকটিস করতে চাইলে এই লিঙ্কে যাও।
নোট
$c/a$ এর মান পূর্ণ সংখ্যা না হলে এই সমস্যাটির কোন সমাধান নেই। হ্যাপি প্রবলেম সলভিং!