Question

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

数学难题一道！（挺有趣的哦 ）募概率和策略高手作答！
题目是这样子的：
有个MP3 里面有200首歌 给这两百首歌编号，分别为1，2，3...200
好了题目开始了
此MP3有两种换歌的方法：

第一种 按序换歌 即1号歌换一次换到2号歌 2号歌换一次换到3号歌 或者5号歌换一次换到4号歌 4号歌换一次换到3号歌...
歌的顺序是首尾相连的，即1号可以换到200号，200号也可以换到1号

第二种 随机换歌 即从一首歌随机跳到包括它在内的另一首歌上去
所有歌被换到的概率是相同的 并且某歌换一次后仍有换到自身的可能（例如1号歌随机换一次 可能得到50号歌 也可能得到150号歌 也可能得到1号歌）

好了 当我在听100号歌的时候 突然想听200号歌了 于是我想用一种最优的策略从第100首跳到第200首上 这种策略显然是先随机换歌 换到某一靠近200号歌的歌上时，再按序换歌。
问题是 应当随机换到几号歌时，再切换成按序换歌，使得策略最优？？？

题目是比较难的 望高手给个提示或者做出解答 有结果的话+50
2L的朋友 我觉得应该不是这么简单的分析的吧
不知道你有没考虑权重的问题，即191和199在你看来是等价的（而事实上不是）
我觉得正确的思路应该是 设某次随机后换到第N首歌 然后再考察第n+1（ORn-1）首歌和第N首的关系 解不等式
但是。。我列的式子越后面越迷糊 到最后都要用积分来做...囧
(*&^%$%^&*()_(*&^%$#....

Answer 1

我们假设处于第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次

Answer 2

步骤一：随机换歌，直到 |与目标之间的误差| ≤ |允许误差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 <stdio.h>
#include <math.h>
#include <stdlib.h>
#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%）。

Answer 3

先换到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次。

Answer 4

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
~~~~~~~~~~~~~~~~~~~

Answer 5

运行结果：
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
请按任意键继续. . .

Answer 6

1