ACMの暗黙的な図の遍歴---コップの水を注ぐ問題
18138 ワード
水を注ぐ問題:例を引く:水をいっぱい入れた6リットルのコップがあって、空の3リットルのコップと1リットルのコップがあって、3つのコップはすべて目盛りがありません;道具を使わない場合、どうやって4リットルの水を量りますか?
賢いと信じているあなたはもう計算しました.(6,0,0)->(3,3,0)->(3,2,1)->(4,3,0);
今あなたの任務は1つの一般的な問題を解決することです:大きい中小の3つのコップを設置する容量はそれぞれa,bで、cは最初は大きいコップだけが水を満たして、その他の2つのコップは空です;
少なくともどのくらいのステップであるコップの中の誰がxリットルを持つことができますか?操作するたびに各コップの水量(0入力:3つのコップの容積a,b,c、そして秤量する水量d;(d<=c);
出力:操作の回数、操作後の3つのコップの水量(a,b,c)ごとに車に戻る.
この問題を分析すると、いくつかのステップに分けて完成することがわかりますが、最小限のステップ数を見つけることができるので、深さ優先遍歴法で列挙することはできません.
では、解答木の上で広さを優先して遍歴することができます.そうすれば、最小限のものを見つけることができます.
(1)1つのコップに水を注ぐが、他の道具がないため、2つの場合がある.水を注ぐか、注ぐコップがいっぱいになってから止まるか、具体的にどの案を選ぶかは、現在外に水を注ぐコップの水量と注ぐ残りの空間が誰が打つかによって決まる.Min()はこの仕事をしています
(2)visの役割は、すでにキューに存在する、またはすでにアクセスされている要素が再びアクセスされないことを保証することであり、操作を低減することができる.
ステップの最小化も保証できます.
(3)ノード構造体に含まれる情報は、親ノードの下付き、ステップ数、3つのカップの状態、親ノードから本ノードへの操作方法がlast_op推定が得られる;
(4)memset()は、最初は文字配列に値を付与ため、ヘッダファイルstringを含める必要がある.hですが、構造体、1次元配列、2次元配列などに値を付けることができます.グローバル変数が初期化されているため、ここでは値を割り当てる必要はありません.
(5)このコードは配列とfront rearを用いてキューをシミュレートする.すなわち,キューの先進的な先出し特性を用い,配列にランダムにアクセスする特性に役立つ(親ノードにアクセスする際に便利である)
(6)配列の大きさは十分である.解答木を分析すればわかる.
賢いと信じているあなたはもう計算しました.(6,0,0)->(3,3,0)->(3,2,1)->(4,3,0);
今あなたの任務は1つの一般的な問題を解決することです:大きい中小の3つのコップを設置する容量はそれぞれa,bで、cは最初は大きいコップだけが水を満たして、その他の2つのコップは空です;
少なくともどのくらいのステップであるコップの中の誰がxリットルを持つことができますか?操作するたびに各コップの水量(0
出力:操作の回数、操作後の3つのコップの水量(a,b,c)ごとに車に戻る.
この問題を分析すると、いくつかのステップに分けて完成することがわかりますが、最小限のステップ数を見つけることができるので、深さ優先遍歴法で列挙することはできません.
では、解答木の上で広さを優先して遍歴することができます.そうすれば、最小限のものを見つけることができます.
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 /* */
5 #define Min(a,b) ((a>b)?b:a)
6 // Min ;
7 const int MAX=1010;
8 //
9 typedef struct Node
10 {
11 int v[3];// ;
12 int fa;// ；
13 // ;
14 int last_op;//
15 //last_op ,
16 // , ;
17 int deepth;
18 // ; ；
19 }Node;
20 int cup_capacity[3];// ；
21 int water_to_get; // ;
22 Node q[MAX*MAX]; // ; ;
23 int vis[MAX][MAX];// ;
24 void print_path(int destination);// 0 destination ;
25 void bfs();//breath-first-search; ;
26 int main()
27 {
28 /* */
29 scanf("%d%d%d%d",&cup_capacity[0],&cup_capacity[1],&cup_capacity[2],&water_to_get);
30 /* */
31 memset(vis,0,sizeof vis);//sizeof ;
32 /*
33 memset() string.h，
34 ， ， ;
35 ， ;
36 */
37 bfs();
38 return 0;
39 }
40 void bfs()
41 {
42 q[0].v[0]=cup_capacity[0];
43 q[0].v[1]=q[0].v[2]=0;
44 q[0].fa=0;// ;
45 q[0].deepth=0;// 0; ;
46 q[0].last_op=0;// ;
47 vis[q[0].v[1]][q[0].v[2]]=1;//
48 // ;
49 // vis[0][0]=1;
50 int front=0,rear=1;// ; ;
51 while(front<rear)
52 {
53 Node N=q[front];// ;
54 if(N.v[0]==water_to_get||N.v[1]==water_to_get||N.v[2]==water_to_get)
55 {// , ;
56 // ;
57 printf("%d
",N.deepth);
58 // ;
59 print_path(front);
60 return;
61 }
62 for(int i=0;i<3;i++)// ;
63 {
64
65 for(int j=0;j<3;j++)// ;
66 {//i！=j; ;
67 Node &IN=q[rear];
68 if(i==j)continue;
69 int amount=Min(N.v[i],cup_capacity[j]-N.v[j]);//
70 // ； ;
71 for (int k=0;k<3;k++)
72 {
73 IN.v[k]=N.v[k];
74 }
75 IN.v[i]=N.v[i]-amount;// i amount ；
76 IN.v[j]=N.v[j]+amount;// j amou ;
77 // ； ;
78 if(!vis[IN.v[1]][IN.v[2]])
79 {
80 vis[IN.v[1]][IN.v[2]]=1;
81 IN.fa=front;// ；
82 IN.deepth=N.deepth+1;// ；
83 IN.last_op=10*i+j;// ;
84
85 rear++;
86 }//if
87 } //for(j)
88 } //for(i)
89 front++;// ;
90
91 }//while
92 }
93 void print_path(int destination)
94 {
95 if(q[destination].fa!=destination)
96 {
97 print_path(q[destination].fa);// ;
98 int from=q[destination].last_op/10,to=q[destination].last_op%10;
99 int num=q[q[destination].fa].v[from]-q[destination].v[from];
100 printf("cup %d (-%d)->cup %d
",from,num,to);
101 }
102 printf("(%d,%d,%d)
",q[destination].v[0],q[destination].v[1],q[destination].v[2]);
103
104 }(1)1つのコップに水を注ぐが、他の道具がないため、2つの場合がある.水を注ぐか、注ぐコップがいっぱいになってから止まるか、具体的にどの案を選ぶかは、現在外に水を注ぐコップの水量と注ぐ残りの空間が誰が打つかによって決まる.Min()はこの仕事をしています
(2)visの役割は、すでにキューに存在する、またはすでにアクセスされている要素が再びアクセスされないことを保証することであり、操作を低減することができる.
ステップの最小化も保証できます.
(3)ノード構造体に含まれる情報は、親ノードの下付き、ステップ数、3つのカップの状態、親ノードから本ノードへの操作方法がlast_op推定が得られる;
(4)memset()は、最初は文字配列に値を付与ため、ヘッダファイルstringを含める必要がある.hですが、構造体、1次元配列、2次元配列などに値を付けることができます.グローバル変数が初期化されているため、ここでは値を割り当てる必要はありません.
(5)このコードは配列とfront rearを用いてキューをシミュレートする.すなわち,キューの先進的な先出し特性を用い,配列にランダムにアクセスする特性に役立つ(親ノードにアクセスする際に便利である)
(6)配列の大きさは十分である.解答木を分析すればわかる.