শীতের সকালে সুন্দর রোদের আলো থাকে । সেই আলো তির্যকভাবে পড়ে ঘাসের ডগায় জমে থাকা শিশিরের উপর । শিশির থেকে সেই আলো বিচ্ছুরিত হয়ে ফিরে আসে আমাদের চোখে এবং মুখে । তখনকার চাঙ্গা অনূভব সবার মধ্যে সর্বদা বজায় থাকুক - এই প্রত্যাশায় চল বন্ধুরা আমরা শুরু করি আমদের নবজীবনের গান ।
শুরুতেই বলে নেই আজকের সমস্যার Topics হল Probability/Expected Value । সমস্যার সারসংক্ষেপ নিচে প্রদান করা হল ।
১। Rimi integers সম্পর্কে নতুন একটা জিনিস জানল আর তা হল
- any positive integer greater than 1 can be divided by its
divisors.
২। Integer এর property কে নিয়ে সে খেলা শুরু করল ।
৩। সে যে কুন একটা number N নিল এবং এইটার নাম দিল D .
৪। In each turn he randomly chooses a divisor of D (1 to D).
৫। Then he divides D by the number to obtain new D.
৬। He repeats this procedure until D becomes 1.
What is the expected number of moves required for N to become 1.
Solution hints :
1. Suppose we want to calculate E(N) where N is a number,k is the number of it’s distinct prime factors and p is the number of primes < n
E(N)=1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak)) + ((p-k)/p) * E(N)
2. It means after one step we can choose a correct prime numbers(from the factors of N) or one of the wrong ones from (p-k) ones
3. Such a recurrence can be changed to
E(N) – ((p-k)/p) * E(N) = 1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak))
E(N)*(k/p) = 1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak))
4. We can apply dynamic programming then.
U can Alo try UVA ACM 11762
শুরুতেই বলে নেই আজকের সমস্যার Topics হল Probability/Expected Value । সমস্যার সারসংক্ষেপ নিচে প্রদান করা হল ।
১। Rimi integers সম্পর্কে নতুন একটা জিনিস জানল আর তা হল
- any positive integer greater than 1 can be divided by its
divisors.
২। Integer এর property কে নিয়ে সে খেলা শুরু করল ।
৩। সে যে কুন একটা number N নিল এবং এইটার নাম দিল D .
৪। In each turn he randomly chooses a divisor of D (1 to D).
৫। Then he divides D by the number to obtain new D.
৬। He repeats this procedure until D becomes 1.
What is the expected number of moves required for N to become 1.
Solution hints :
1. Suppose we want to calculate E(N) where N is a number,k is the number of it’s distinct prime factors and p is the number of primes < n
E(N)=1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak)) + ((p-k)/p) * E(N)
2. It means after one step we can choose a correct prime numbers(from the factors of N) or one of the wrong ones from (p-k) ones
3. Such a recurrence can be changed to
E(N) – ((p-k)/p) * E(N) = 1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak))
E(N)*(k/p) = 1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak))
4. We can apply dynamic programming then.
U can Alo try UVA ACM 11762
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন