マイクロソフトのコップ投げ問題-ダイナミックプランニング
3620 ワード
新浪微博でマイクロソフトの試験問題を見た.
タイトルの説明
1つのコップで、N階で割られると、Nより高い階でも割れる.M階で割らないと、Mより低い階でも割れることはない.このようなコップを2つあげて、100階より高い階でテストさせ、最小限のテスト回数でコップを割る階を見つけるように要求する.
ふとうしきかいほう
すべての議論は2つのコップの状況に基づいています.
下図のすべての図の赤い線は、2つのコップが残ったときの試転位置を示しており、コップが破砕した後、すなわち1つのコップしか残っていない場合は、既知の範囲の最下層から既知の範囲の最上層層に向かって試転するだけである.
1階しかない場合は、一度試打する必要があります.2階がある場合は、2回の試打が必要です.
3層が必要な場合,まず2回の試技で完成できるかどうかを議論し,図のような方法で可能であることが分かった.
4階が必要な場合は、まず2回の試技で完成できるかどうかを議論し、もうだめであることがわかり、少なくとも3回の試技が必要である.
5階が必要な場合は、まず3回以下の試技で完成できるかどうかを議論し、だめなら最大4回の試技で完成できるかどうかを議論します.次の図のように順番に類推します.
従って、100層がある場合、n+(n−1)+(n−2)+...+1>=100であり、その後n上を整列させるので、n=14となる.最悪の場合は14回の試技が必要です.
試打方法は、初めて14階で投げ、破れなければ27階(14+13)で投げ続け、破れずに39階(27+12)で投げ続け、順番に類推した.破れた場合、コップが1つ残って、既知の範囲の最下層から既知の範囲の最上層に層ごとに試打する.
ダイナミックプランニング解法
残りのi層をdp[i][j]で表すと仮定し,j個のカップの場合は最低何回試打する必要があるかを示す.
(1)dp[i][1]=i,つまりコップが1つしか残っていない場合は,第1層から層毎に試打するしかない.
(2)dp[0][j]=0であり,0層しか残っていない場合には,0回の試打を行うだけである.
(3)dp[1][j]=1であり,1層しか残っていない場合,j>0を前提として1回の試打を行う必要がある.
(4)dp[i][j] = min(1=
route[i][j]は、i階j個のコップが残っているときに、次の試打階を示す.j=1の場合、この範囲内の最下層から順に最上層へ試打する.
出力結果は、MIN STEP IS 14です.つまり、最大14回試投する方法がある.同時にroute配列がメソッドを印刷します.
たとえばroute配列の結果:
route[i][2]
1
0
2
1
3
2
4
3
5
3
6
3
7
4
8
4
9
4
10
4
11
5
12
5
13
5
14
5
15
5
16
6
17
6
18
6
19
6
20
6
21
6
22
7
23
7
24
7
25
7
26
7
27
7
28
7
29
8
30
8
31
8
32
8
33
8
34
8
35
8
36
8
37
9
38
9
39
9
40
9
41
9
42
9
43
9
44
9
45
9
46
10
47
10
48
10
49
10
50
10
51
10
52
10
53
10
54
10
55
10
56
11
57
11
58
11
59
11
60
11
61
11
62
11
63
11
64
11
65
11
66
11
67
12
68
12
69
12
70
12
71
12
72
12
73
12
74
12
75
12
76
12
77
12
78
12
79
13
80
13
81
13
82
13
83
13
84
13
85
13
86
13
87
13
88
13
89
13
90
13
91
13
92
14
93
14
94
14
95
14
96
14
97
14
98
14
99
14
100
14
したがって、route[100][2]=14であり、1回目の試転は14階であり、もし砕けていたら、1階から14階へ試転し、砕けていなければ、2回目の試転はroute[100-14][2]=route[86][2]=13、つまり14+13=27階で2回目の試転を行い、もし今回砕けていたら、14+1=15階から上へ試転し、今回砕けていていなければ、3回目の試転はroute[86-13][2]=route[73][2]=12で、つまり27+12=39階で試打を開始し,順次類推する.
タイトルの説明
1つのコップで、N階で割られると、Nより高い階でも割れる.M階で割らないと、Mより低い階でも割れることはない.このようなコップを2つあげて、100階より高い階でテストさせ、最小限のテスト回数でコップを割る階を見つけるように要求する.
ふとうしきかいほう
すべての議論は2つのコップの状況に基づいています.
下図のすべての図の赤い線は、2つのコップが残ったときの試転位置を示しており、コップが破砕した後、すなわち1つのコップしか残っていない場合は、既知の範囲の最下層から既知の範囲の最上層層に向かって試転するだけである.
1階しかない場合は、一度試打する必要があります.2階がある場合は、2回の試打が必要です.
3層が必要な場合,まず2回の試技で完成できるかどうかを議論し,図のような方法で可能であることが分かった.
4階が必要な場合は、まず2回の試技で完成できるかどうかを議論し、もうだめであることがわかり、少なくとも3回の試技が必要である.
5階が必要な場合は、まず3回以下の試技で完成できるかどうかを議論し、だめなら最大4回の試技で完成できるかどうかを議論します.次の図のように順番に類推します.
従って、100層がある場合、n+(n−1)+(n−2)+...+1>=100であり、その後n上を整列させるので、n=14となる.最悪の場合は14回の試技が必要です.
試打方法は、初めて14階で投げ、破れなければ27階(14+13)で投げ続け、破れずに39階(27+12)で投げ続け、順番に類推した.破れた場合、コップが1つ残って、既知の範囲の最下層から既知の範囲の最上層に層ごとに試打する.
ダイナミックプランニング解法
残りのi層をdp[i][j]で表すと仮定し,j個のカップの場合は最低何回試打する必要があるかを示す.
(1)dp[i][1]=i,つまりコップが1つしか残っていない場合は,第1層から層毎に試打するしかない.
(2)dp[0][j]=0であり,0層しか残っていない場合には,0回の試打を行うだけである.
(3)dp[1][j]=1であり,1層しか残っていない場合,j>0を前提として1回の試打を行う必要がある.
(4)dp[i][j] = min(1=
route[i][j]は、i階j個のコップが残っているときに、次の試打階を示す.j=1の場合、この範囲内の最下層から順に最上層へ試打する.
//dp.c
#include
#define LAYER 101
#define CUP 3
int main(){
int dp[LAYER][CUP], route[LAYER][CUP], i, j, k;
for(i=1; i dp[j-k][i]? dp[k-1][i-1]+1: dp[j-k][i]+1;
route[j][i] = min <= dp[j][i]? k: route[j][i];
dp[j][i] = min < dp[j][i]? min: dp[j][i];
}
}
printf("MIN STEP IS %d
", dp[LAYER-1][CUP-1]);
//for(i=1; i 出力結果は、MIN STEP IS 14です.つまり、最大14回試投する方法がある.同時にroute配列がメソッドを印刷します.
たとえばroute配列の結果:
route[i][2]
1
0
2
1
3
2
4
3
5
3
6
3
7
4
8
4
9
4
10
4
11
5
12
5
13
5
14
5
15
5
16
6
17
6
18
6
19
6
20
6
21
6
22
7
23
7
24
7
25
7
26
7
27
7
28
7
29
8
30
8
31
8
32
8
33
8
34
8
35
8
36
8
37
9
38
9
39
9
40
9
41
9
42
9
43
9
44
9
45
9
46
10
47
10
48
10
49
10
50
10
51
10
52
10
53
10
54
10
55
10
56
11
57
11
58
11
59
11
60
11
61
11
62
11
63
11
64
11
65
11
66
11
67
12
68
12
69
12
70
12
71
12
72
12
73
12
74
12
75
12
76
12
77
12
78
12
79
13
80
13
81
13
82
13
83
13
84
13
85
13
86
13
87
13
88
13
89
13
90
13
91
13
92
14
93
14
94
14
95
14
96
14
97
14
98
14
99
14
100
14
したがって、route[100][2]=14であり、1回目の試転は14階であり、もし砕けていたら、1階から14階へ試転し、砕けていなければ、2回目の試転はroute[100-14][2]=route[86][2]=13、つまり14+13=27階で2回目の試転を行い、もし今回砕けていたら、14+1=15階から上へ試転し、今回砕けていていなければ、3回目の試転はroute[86-13][2]=route[73][2]=12で、つまり27+12=39階で試打を開始し,順次類推する.