полином n-ой степени, численный поиск корней

[Cash]

Цитата:

если игрок угадал максимум, то он получает рубль, если нет - ничего не получает и ничего не отдает. Правильная постановка

Если честно, особой разницы не вижу, кроме того, что хотел бы найти того, кто бы мне такую игру предложил
А в своих рассуждениях обнаружил существенный изъян.
Отвергая число, немного меньшее $1/2$ мы все-таки совершаем ошибку.
Например, если вышло $0.7$ и осталось 2 броска, то согласившись в 49% мы выигрыш забираем сразу. А при отказе 51% нам еще не гарантирован. Задача становится интересной

[Shadow]

Давайте сначала для $n=3$
Сравните ваше первое предложение, соглашаться при $\frac{1}{\sqrt 2}= 0.707106781$
с числом 0.689897949, что является корнем уравнения $5x^2-2x-1=0$.
Хоть компютерной сумуляцией (не менее 1000000 игр)

[Евгений Машеров]

В методе Прони возникает, да. Но 50-я степень там это значит, что ищется сумма 25 экспонент. Что означает, что ничего не найдём... Задача приобретает крайне неприятную численную неустойчивость.

[Cash]

Ну вроде признал уже, что не прав
При двух оставшихся бросках порогом будет корень уравнения
$x^2=1-x^2-\frac{(1-x)^2}{2}$
То есть если выпал $x$ - в $x^2$ случаях мы сразу срываем банк,
и в $\frac{(1-x)^2}{2}$ мы ошибочно берем 2-й, а не 3-й максимум.

-- Чт окт 27, 2011 16:24:34 --

Соответственно при $k$ оставшихся бросках получаем уравнение (если не запутался)
$x^k = 1-x^k - \sum\limits_{i=2}^k \frac {C_k^i}{i} x^{k-i}(1-x)^i$

[svv]

Евгений Машеров
С одной стороны вроде бы плохо, что алгоритм обязан "кровь из носу" выдать Вам 25 экспонент, даже если их там нет.
С другой стороны, по крайней мере в моей практике, "шумовые" экспоненты бывало легко отличить по очень малым коэффициентам и запредельно высоким частотам (мы искали разложение по комплексным экспонентам).
Около 50 экспонент реально и достаточно устойчиво получались в такой ситуации. Ультразвуковой пьезоизлучатель возбуждался коротким импульсом и дальше "звенел" на всех модах, и все они благодаря пьезоэффекту давали вклад в напряжение, измеряемое на обкладках. Анализируя этот сигнал, можно было методом Прони определять резонансные частоты -- полюсы передаточной функции на комплексной плоскости.

[Shadow]

Cash в сообщении #496450 писал(а):

Соответственно при $k$ оставшихся бросках получаем уравнение (если не запутался)
$x^k = 1-x^k - \sum\limits_{i=2}^k \frac {C_k^i}{i} x^{k-i}(1-x)^i$

Я только сейчас заметил это. Если верно, то ваше решение окажется лучше моего. Решал так:
1. Нахождение порога для $n$ "бросков"
2. Определения вероятност успеха при $x$ выше порога
$C_1=0$
$f(1,x)=1-x$
$C_n$ корень уравнения $x^{n-1}=f(n-1,x)$
$f(n,x)=xf(n-1,x)+\int\limits_x^1 x^{n-1}dx$, т.е

$f(n,x)=xf(n-1,x)+\frac{1-x^n}{n}$
Задача скорее всего для "програмирование". В оффтоп результаты до $n=200$

(Оффтоп)

002   0.500000000
003   0.689897949
004   0.775845068
005   0.824589583
006   0.855949208
007   0.877807017
008   0.893910042
009   0.906265292
010   0.916044161
011   0.923976127
012   0.930539111
013   0.936059280
014   0.940766832
015   0.944828868
016   0.948369620
017   0.951483370
018   0.954242956
019   0.956705545
020   0.958916631
021   0.960912866
022   0.962724113
023   0.964374944
024   0.965885767
025   0.967273665
026   0.968553055
027   0.969736182
028   0.970833516
029   0.971854061
030   0.972805606
031   0.973694918
032   0.974527910
033   0.975309767
034   0.976045058
035   0.976737821
036   0.977391643
037   0.978009718
038   0.978594898
039   0.979149742
040   0.979676549
041   0.980177393
042   0.980654145
043   0.981108503
044   0.981542010
045   0.981956067
046   0.982351956
047   0.982730847
048   0.983093810
049   0.983441831
050   0.983775812
051   0.984096587
052   0.984404924
053   0.984701532
054   0.984987068
055   0.985262141
056   0.985527316
057   0.985783117
058   0.986030032
059   0.986268517
060   0.986498997
061   0.986721867
062   0.986937499
063   0.987146239
064   0.987348413
065   0.987544325
066   0.987734263
067   0.987918495
068   0.988097274
069   0.988270840
070   0.988439416
071   0.988603216
072   0.988762438
073   0.988917273
074   0.989067900
075   0.989214487
076   0.989357194
077   0.989496175
078   0.989631573
079   0.989763524
080   0.989892160
081   0.990017602
082   0.990139969
083   0.990259372
084   0.990375918
085   0.990489709
086   0.990600839
087   0.990709403
088   0.990815487
089   0.990919176
090   0.991020550
091   0.991119686
092   0.991216657
093   0.991311532
094   0.991404380
095   0.991495265
096   0.991584247
097   0.991671387
098   0.991756741
099   0.991840364
100   0.991922306
101   0.992002619
102   0.992081351
103   0.992158548
104   0.992234255
105   0.992308513
106   0.992381365
107   0.992452849
108   0.992523005
109   0.992591868
110   0.992659475
111   0.992725858
112   0.992791052
113   0.992855088
114   0.992917996
115   0.992979806
116   0.993040546
117   0.993100244
118   0.993158927
119   0.993216620
120   0.993273348
121   0.993329135
122   0.993384004
123   0.993437978
124   0.993491079
125   0.993543327
126   0.993594743
127   0.993645347
128   0.993695157
129   0.993744192
130   0.993792471
131   0.993840010
132   0.993886827
133   0.993932937
134   0.993978357
135   0.994023102
136   0.994067187
137   0.994110626
138   0.994153434
139   0.994195624
140   0.994237209
141   0.994278203
142   0.994318618
143   0.994358465
144   0.994397758
145   0.994436507
146   0.994474724
147   0.994512419
148   0.994549604
149   0.994586288
150   0.994622481
151   0.994658194
152   0.994693436
153   0.994728215
154   0.994762542
155   0.994796424
156   0.994829871
157   0.994862891
158   0.994895492
159   0.994927681
160   0.994959467
161   0.994990857
162   0.995021859
163   0.995052479
164   0.995082725
165   0.995112603
166   0.995142120
167   0.995171283
168   0.995200098
169   0.995228571
170   0.995256709
171   0.995284516
172   0.995311999
173   0.995339164
174   0.995366015
175   0.995392559
176   0.995418801
177   0.995444746
178   0.995470398
179   0.995495763
180   0.995520845
181   0.995545650
182   0.995570182
183   0.995594444
184   0.995618443
185   0.995642181
186   0.995665664
187   0.995688894
188   0.995711878
189   0.995734617
190   0.995757116
191   0.995779380
192   0.995801411
193   0.995823213
194   0.995844790
195   0.995866145
196   0.995887282
197   0.995908203
198   0.995928913
199   0.995949414
200   0.995969710

[Cash]

В уравнении потерял один сомножитель. Правильно будет
$x^k = 1-x^k - \sum\limits_{i=2}^k C_k^i(1-\frac {1}{i}) x^{k-i}(1-x)^i$

[Shadow]

Как то сложно у Вас получается...У меня, изходя из этой рекурсивной функции
$f(n,x)=xf(n-1,x)+\frac{1-x^n}{n}$
получаются уравнения:
$x=1-x$
$x^2=\frac 1 2+x-\frac 3 2 x^2$
$x^3=\frac 1 3+\frac 1 2 x+x^2-\frac {11}{6}x^3$
и т.д. Последний коэффициент равен $1+\frac 1 2+\frac 1 3+...+\frac 1 n$
Получается обобщенное уравнение.
$\displaystyle x^n=\sum\limits_{i=0}^{n-1} \frac{x^i-x^n}{n-i}$

Мне трудно понять вашу формулу без допольнительных разъяснений

[Cash]

В формуле под знаком суммы стоит вероятность выпадения $i$ максимумов, из которых нам подходят лишь $1/i$