Deməli, Siz $2^n$-er olmaq istəyirsiniz?#1577

Deməli, Siz $2^n$-er olmaq istəyirsiniz? (Həll təhlili)

$f (n, a)$ f(n, a) ilə oyunçunun $n$ suala cavab verməli olduğu və ilkin məbləğin $a$ -ya bərabər olduğu halda gözlənilən uduşun maksimum mümkün dəyərini işarə edək.

Əgər $n = 0$ n = 0 olarsa, oyunçu ilkin məbləğ ilə qalır, yəni $f (0, a) = a$ f(0, a) = a.

Düzgün cavab vermə ehtimalı $p$ -yə bərabərdir, burada $t \leq p \leq 1$ t \le p \le 1. Əgər oyunçu birinci suala düzgün cavab verirsə, ona $n - 1$ n - 1 sual qalır, mükafat məbləği isə ikiqat artaraq $2 a$ -ya bərabər olur. $1 - p$ 1 - p ehtimalı ilə səhv cavab verilir və bütün məbləğ itir. Deməli, birinci sualdan sonra gözlənilən uduş bərabərdir

p \cdot f (n - 1, 2 a) + (1 - p) \cdot 0 = p \cdot f (n - 1, 2 a)

p \cdot f(n - 1, 2a) + (1 - p) \cdot 0 = p \cdot f(n - 1, 2a)

Əgər bu dəyər cari məbləğ $a$ -dan böyükdürsə, oyuna davam etmək sərfəlidir; əks halda — dayanmaq lazımdır. Beləliklə, davam etmə qərarından sonra gözlənilən uduş bərabərdir

ma x (a, p \cdot f (n - 1, 2 a))

max(a, p \cdot f(n - 1, 2a))

$p$ ehtimalı $[t; 1]$ parçası üzərində bərabər paylandığı üçün

f (n, a) = \frac{1}{1 - t} \int_{t}^{1} ma x (a, p \cdot f (n - 1, 2 a)) d p

f(n, a) = \frac{1}{1 - t} \int_{t}^{1} max(a, p \cdot f(n - 1, 2a))\,dp

Əgər $t = 1$ t = 1 olarsa, düzgün cavab vermə ehtimalı vahidə bərabərdir, deməli oyunçu bütün $n$ suala cavab verməlidir və nəticədə $2^{n}$ 2^n uduş əldə edir.

Nümunə

Üçüncü testə baxaq, burada $n = 2, t = 0.6$ n = 2, t = 0.6. İlkin kapital $a = 1$ a = 1.

f (2, 1) = \frac{1}{0.4} \int_{0.6}^{1} ma x (1, p \cdot f (1, 2)) d p, f (1, 2) = \frac{1}{0.4} \int_{0.6}^{1} ma x (2, p \cdot f (0, 4)) d p, f (0, 4) = 4

f(2, 1) = \frac{1}{0.4} \int_{0.6}^{1} max(1, p \cdot f(1, 2))~dp, \\ f(1, 2) = \frac{1}{0.4} \int_{0.6}^{1} max(2, p \cdot f(0, 4))~dp, \\ f(0, 4) = 4

$f (1, 2)$ f(1, 2) dəyərini $f (0, 4)$ f(0, 4) vasitəsilə hesablayaq:

f (1, 2) = \frac{1}{0.4} \int_{0.6}^{1} ma x (2, p \cdot f (0, 4)) d p = 2.5 \cdot \int_{0.6}^{1} ma x (2, 4 p) d p = / n ə z ə r ə a l ı r ı q k i, 4 p > 2 o l d u g ˘ u ha l d a 0.6 \leq p \leq 1/ 2.5 \cdot \int_{0.6}^{1} 4 p d p = 2.5 \cdot [2 p^{2}]_{0.6}^{1} = 5 \cdot (1 - 0.36) = 5 \cdot 0.64 = 3.2

f(1, 2) = \frac{1}{0.4} \int_{0.6}^{1} max(2, p \cdot f(0, 4))~dp = 2.5 \cdot \int_{0.6}^{1} max(2, 4p)~dp = \\ / nəzərə alırıq ki,~4p > 2~olduğu halda~0.6 \le p \le 1 / \\ 2.5 \cdot \int_{0.6}^{1} 4p~dp = 2.5 \cdot \left[ 2 p^2 \right]_{0.6}^{1} = \\ 5 \cdot (1 - 0.36) = 5 \cdot 0.64 = 3.2

$f (2, 1)$ f(2, 1) dəyərini $f (1, 2)$ f(1, 2) vasitəsilə hesablayaq:

f (2, 1) = \frac{1}{0.4} \int_{0.6}^{1} ma x (1, p \cdot f (1, 2)) d p = 2.5 \cdot \int_{0.6}^{1} ma x (1, 3.2 p) d p = / n ə z ə r ə a l ı r ı q k i, 3.2 p > 1 o l d u g ˘ u ha l d a 0.6 \leq p \leq 1/ 2.5 \cdot \int_{0.6}^{1} 3.2 p d p = 2.5 \cdot [1.6 p^{2}]_{0.6}^{1} = 4 \cdot (1 - 0.36) = 4 \cdot 0.64 = 2.56

f(2, 1) = \frac{1}{0.4} \int_{0.6}^{1} max(1, p \cdot f(1, 2))~dp = 2.5 \cdot \int_{0.6}^{1} max(1, 3.2p)~dp = \\ / nəzərə alırıq ki,~3.2p > 1~olduğu halda~0.6 \le p \le 1 / \\ 2.5 \cdot \int_{0.6}^{1} 3.2p~dp = 2.5 \cdot \left[ 1.6 p^2 \right]_{0.6}^{1} = \\ 4 \cdot (1 - 0.36) = 4 \cdot 0.64 = 2.56

Alqoritmin realizasiyası

integral funksiyası

I (a, k) = \frac{1}{1 - t} \int_{t}^{1} ma x (a, k p) d p

I(a, k) = \frac{1}{1 - t} \int_{t}^{1} max(a, kp)\,dp

inteqralının dəyərini verilmiş $a$ və $k$ həqiqi ədədləri üçün hesablayır. $t = 1$ t = 1 olduqda $p$ təxmin etmə ehtimalı vahidə bərabərdir, buna görə $I (a, k)$ I(a, k) inteqralının dəyəri $ma x (a, k)$ max(a, k)-ya bərabər qəbul edilir.

Aşağıda sahəsi $\int_{t}^{1} ma x (a, k p) d p$ \int_{t}^{1} max(a, kp)\,dp inteqralının dəyərinə bərabər olan sahə göstərilib:

$y = a$ y = a və $y = k p$ y = kp düz xətlərinin kəsişmə nöqtəsini tapaq:

a = k p, b u r a d an p = a / k

a = kp,~buradan~p = a/k

$t e m p = a / k$ temp = a / k qəbul edək. $\int_{t}^{1} ma x (a, k p) d p$ \int_{t}^{1} max(a, kp)\,dp inteqralının dəyərinə $\int_{t}^{t e m p} a d p$ \int_{t}^{temp} a\,dp + $\int_{t e m p}^{1} k p d p$ \int_{temp}^{1} kp\,dp cəmi kimi baxaq. $t e m p$ nöqtəsinin $t$ və $1$ nöqtələrinə nisbətən vəziyyətindən asılı olaraq $I (a, k)$ I(a, k) inteqralının dəyərini hesablayırıq.

Əgər $t \leq t e m p \leq 1$ t \le temp \le 1 olarsa, onda $\int_{t}^{t e m p} a d p$ \int_{t}^{temp} a\,dp + $\int_{t e m p}^{1} k p d p$ \int_{temp}^{1} kp\,dp =

a \cdot (t e m p - t) + k \cdot (1 - t e m p \cdot t e m p) /2

a \cdot (temp - t) + k \cdot (1 - temp \cdot temp) / 2

Əgər $t e m p \leq t$ temp \le t olarsa, onda $\int_{t}^{t e m p} a d p$ \int_{t}^{temp} a\,dp + $\int_{t e m p}^{1} k p d p$ \int_{temp}^{1} kp\,dp = $\int_{t}^{1} k p d p$ \int_{t}^{1} kp\,dp = $k \cdot (1 - t \cdot t) /2$ k \cdot (1 - t \cdot t) / 2.
Əgər $t e m p > 1$ temp > 1 olarsa, onda $\int_{t}^{t e m p} a d p$ \int_{t}^{temp} a\,dp + $\int_{t e m p}^{1} k p d p$ \int_{temp}^{1} kp\,dp = $\int_{t}^{1} a d p$ \int_{t}^{1} a\,dp = $a \cdot (1 - t)$ a \cdot (1 - t).

double integral(double a, double k)
{
  double s = 0, temp = a / k;
  if (t == 1) return max(a,k);
  if (temp > 1) return a * (1 - t);
  if (temp >= t) s = a * (temp - t);
  else temp = t;
  s += k * (1 – temp * temp) / 2;
  return s / (1 - t);
}

C++

f funksiyası $f (n, a) = {I (a, f (n - 1, 2 a)), n > 0 a, n = 0$ f(n, a) = \begin{cases} I(a, f(n - 1, 2a)), n > 0 \\ a, n = 0 \end{cases} dəyərini rekursiv olaraq hesablayır.

double f(int n, int a)
{
  if (!n) return a;
  double k = f(n - 1,2 * a);
  return integral(a,k);
}

Proqramın əsas dövrü. Giriş məlumatlarını oxuyuruq və $f (n, 1)$ f(n, 1) dəyərini çap edirik.

while(scanf("%d %lf",&n,&t),n + t)
  printf("%.3lf\n",f(n,1));