数学难题一道！（挺有趣的哦 ）募概率和策略高手作答！

我们假设处于第k号歌曲时候，采用最优策略平基芦均需要E(k)次换曲才能够到底第200号歌。那么显然
E(200)=0,E(1)=E(199)=1
E(k)=min{E(k-1)+1,E(k+1)+1,AVE+1}
其中AVE=(E(1)+E(2)+...+E(200))/200
所以容易看出，团锋姿数列E在200时取最小值，然后在离开200时逐步变大（每次大1），然后知道某个地方，全部变成AVE+1
有对称性，两边开始变成AVE+1的号数离200要一样远，假设为h
那么我们有
E(200)=0
E(199)=E(1)=1
...
E(200-h)=E(h)=h
E(h+1)=E(h+2)=...=E(200-h-1)=AVE+1
200*AVE=E(1)+E(2)+...+E(200)
将h和AVE解出来就可以了

上面方程相当于
200*AVE=h(1+h)+(AVE+1)(199-2h)
即
(1+2h)AVE=h(h-1)+199
AVE=(h(h-1)+199)/(1+2h)
得到h=14时AVE可以有最小值381/29
所以应该是使用随机方案知道编号大于等于186或小于等于14时换成顺序的

也就是平塌绝均需要381/29次。
而对于开始编号不在186~14之间的（如开始为100），那么平均需要AVE+1=410/29=14.14次可以达到第200首个。
而编号在186~14之间的，都直接顺序就可以了，最小0次，最大14次

步骤一：随机换歌，直到 |与目标之间的误差宴差| ≤ |允许误差ep| ，即成功。
那铅祥握么，随机换歌次数n是多少呢？
如果ep=10，那么
1次成功的概率为(10*2+1)/200，约为0.1
2次成功的概率为1-(1-0.1)^2
……………………………………
n次成功的概率为1-(1-0.1)^n

我们不妨一直算到1-(1-0.1)^n>0.95（当槐庆然0.95也可以改成其他概率）

步骤二：按序换歌
最坏的情况：按序换歌的次数=ep
此时即可到达目标。

由上可知，总次数T=n+ep，而n又是ep的函数，所以T=f(ep)。
下面我来用C语言解决这个问题。
#include
#include
#include
#define CONFIRM 0.95
#define AMOUNT 200
main()
{
int ep,n;float P;
printf("ep\tT\n");
for(ep=0;ep<=AMOUNT/2;++ep)
{
P=(2*ep+1.0)/AMOUNT;
for(n=0;1-pow(1-P,n)<=CONFIRM;++n);
printf("%d\t%d\n",ep,n+ep);
}
system("pause");
}
运行结果：
ep T
0 598
1 200
2 121
3 88
4 70
5 58
6 51
7 46
8 42
9 40
10 38
11 36
12 35
13 34
14 34
15 33
16 33
17 33
18 33
19 33
20 34
21 34
22 34
23 35
24 35
25 36
26 36
27 37
28 37
29 38
30 39
31 39
32 40
33 41
34 42
35 42
36 43
37 44
38 45
39 45
40 46
41 47
42 48
43 49
44 50
45 50
46 51
47 52
48 53
49 54
50 55
51 56
52 57
53 57
54 58
55 59
56 60
57 61
58 62
59 63
60 64
61 65
62 66
63 66
64 67
65 68
66 69
67 70
68 71
69 72
70 73
71 74
72 75
73 76
74 77
75 78
76 79
77 80
78 80
79 81
80 82
81 83
82 84
83 85
84 86
85 87
86 88
87 89
88 90
89 91
90 92
91 93
92 94
93 95
94 96
95 96
96 97
97 98
98 99
99 100
100 101
请按任意键继续. . .

结论：取ep=15，16，17，18，19，可在33次以内找到目标（概率为95%）。

先换到190-10，再按顺序。在190-10之间有21个数，随机时换到的概率为冲扮21/200，把分数化为分子为1的数，可得1/9.523，即是换9.523次就可以得到1次，这答判闹时清罩在按顺序，最远的数10或190再换10次就可得到200这个数。最后用19.523次。其他的都比这个数大。如191-9的话需要19.526次，189-11的话需要11.69次。

ep T
0 598
1 200
2 121
3 88
4 70
5 58
6 51
7 46
8 42
9 40
10 38
11 36
12 35
13 34
14 34
15 33
16 33
17 33
18 33
19 33
20 34
21 34
22 34
23 35
24 35
25 36
26 36
27 37
28 37
29 38
30 39
31 39
32 40
33 41
34 42
35 42
36 43
37 44
38 45
39 45
40 46
41 47
42 48
43 49
44 50
45 50
46 51
47 52
48 53
49 54
50 55
51 56
52 57
53 57
54 58
55 59
56 60
57 61
58 62
59 63
60 64
61 65
62 66
63 66
64 67
65 68
66 69
67 70
68 71
69 72
70 73
71 74
72 75
73 76
74 77
75 78
76 79
77 80
78 80
79 81
80 82
81 83
82 84
83 85 84 86
85 87
86 88
87 89
88 90
89 91
90 92
91 93
92 94
93 95
94 96
95 96
96 97
97 98
98 99
99 100
100 101
~~~~~~~~~~~~~~~~~~~

运行盯答结果：稿则碧
ep T
0 598
1 200
2 121
3 88
4 70
5 58
6 51
7 46
8 42
9 40
10 38
11 36
12 35
13 34
14 34
15 33
16 33
17 33
18 33
19 33
20 34
21 34
22 34
23 35
24 35
25 36
26 36
27 37
28 37
29 38
30 39
31 39
32 40
33 41
34 42
35 42
36 43
37 44
38 45
39 45
40 46
41 47
42 48
43 49
44 50
45 50
46 51
47 52
48 53
49 54
50 55
51 56
52 57
53 57
54 58
55 59
56 60
57 61
58 62
59 63
60 64
61 65
62 66
63 66
64 67
65 68
66 69
67 70
68 71
69 72
70 73
71 74
72 75
73 76
74 77
75 78
76 79
77 80
78 80
79 81
80 82
81 83
82 84
83 85 84 86
85 87
86 88
87 89
88 90
89 91
90 92
91 93
92 94
93 95
94 96
95 96
96 97
97 98
98 99
99 100
100 101
请键举按任意键继续. . .

1