Dice (III) : Solution
একটা n sides dice দেওয়া থাকবে। আমাদের বের করতে হবে, Dice এর প্রত্যেকটা side at least একবার করে পেতে হলে গড়ে(Expected) কয়বার Dice টাকে throw করতে হবে?
ধরি, n sides Dice throw এর এক পর্যায়ে আমরা Dice এর x টা side এখনো পাই নাই তাহলে অবশিষ্ট (n - x) টা sides already আমরা পেয়েছি।
আমরা না পাওয়া Dice এর x টা sides পেতে চাই।
ধরি, x টা sides পেতে Expected number of throw হলো f(x).
এখন আমরা dice টা যদি throw করি তাহলে দুইটা ঘটনা ঘটতে পারে :
১. যে sides গুলা আগে পেয়ে ছিলাম তার মধ্যে থেকে যেকোনো একটা আবার পেতে পারি, ফলে Expected number of throw এর কোনো Change হবে না।
যার Probability হলো = (n - x )/n
২. আর যদি নতুন একটা sides পাই যা আগে পাই নাই তাহলে Expected number of throw ১ কমে যাবে| নতুন Expected number of throw হবে f(x-1).
যার Probability হলো = x/n
যা উপরের ছবির মতো
সুতরাং আমরা লিখতে পারি Expected number of throw,
f(x) = (n-x)/n * f(x) + (x/n) * f(x-1) + 1
f(x) - (n-x)/n * f(x) = 1 + (x/n) * f(x-1)
f(x) * (1 - (n-x)/n) = 1 + (x/n) * f(x-1)
f(x) * (x/n) = 1 + (x/n) * f(x-1)
f(x) = (n/x) + f(x-1)
উপরের সমীকরণ অনুযায়ী যদি আমাদের n টা (n = 0, 1, 2, 3, 4......) sides এর একটা dice দেওয়া থাকে এর প্রত্যেকটা side একবার করে পেতে হলে Expected number of throw আমরা লিখতে পারি,
f(0) = 0
f(1) = 1/1
f(2) = 2/1 + 2/2
f(3) = 3/1 + 3/2 + 3/3
.
.
.
.
f(n) = n/1 + n/2 + n/3 + n/4 + ............... + n/n
Coding Part :
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, k = 1;
cin >> t;
while(t--)
{
int n;
cin >> n;
double ans = 0;
cout << showpoint << fixed << setprecision(10);
for(int i=1;i<=n;i++)
ans += (double)n/(double)i;
cout << "Case " << k++ << ": " << ans << "\n";
}
return 0;
}
Comments
Post a Comment