Josephus Number ( জোসেফাস নম্বর)

ধরা যাক  ৫ জন প্রতিযোগী আছে । এখন প্রতিবার এলিমিনেশন এর সময় ২য়  নম্বর প্রতিযোগীকে আউট করতে হবে এবং এভাবে সর্বশেষ যে প্রতিযোগী থাকবে সেই বিজয়ী হবে ।

                                                                      1  2  3 4 5

১ম এ ২ যাবে, তারপর ৪ , তারপর ১, তারপর ৫ । জয়ী ৩ যা Josephus  Number .

n=5  k=2

সর্বশেষ নম্বর এ হল জোসেফাস নম্বর । এই নম্বর বের করার সময় প্রতিবার n এর মান কমতে থাকে । তাই রিকার্শন
এর একটি সূত্র আছে এই নম্বর বের করার জন্য । সূত্রটি হলঃ

                                                        (josephus (n-1 , k ) + k-1) % n + 1


 base case হল n=1 .



josephus(int n, int k)
{
       if(n==1)
      {
            return 1;

     }
     else
    {

           return (josephus (n-1 , k ) + k-1) % n + 1;

    }


}

ব্যাখা ঃ

১ম এ josephus(5,2)  কল হবে । তারপর  josephus(4,2)-->josephus(3,2)-->josephus(2,2)--> josephus(1,2) তে n এর মান 1 তাই return 1 হবে । তখন josephus(1,2) =1

এরপর রিকার্শন এর নিয়ম অনুযায়ী রিটার্ন হওয়ার পর আগের ফাংশনগুলো তে যাবে । তাই josephus(2,2) তে যাবে এবং

josephus(2,2)= (josephus (1 , 2 ) + 2-1) % 2 + 1=(1+1)%2+1=1

এরপর  josephus(3,2) তে যাবে

josephus(3,2)= (josephus (2 , 2 ) + 2-1) % 3 + 1=(1+1)%3+1=3

josephus(4,2)= (josephus (3 , 2 ) + 2-1) % 4 + 1=(3+1)%4+1=1

josephus(5,2)= (josephus (4 , 2 ) + 2-1) % 5 + 1=(1+1)%5+1=3

সুতরাং  josephus(5,2) number হল  = 3

Josephus Number নিয়ে UVA তে অনেক প্রব্লেম আছে । কারো কোডিং এ প্রব্লেম হলে UVA 11351 Last Man Standing  অথবা  LightOj 1179 Josephus Problem এর সলুশন দেখতে পারো।

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here