teratail header banner
teratail header banner
質問するログイン新規登録

質問編集履歴

18

aasdsad

2017/12/10 13:44

投稿

退会済みユーザー
title CHANGED
@@ -1,1 +1,1 @@
1
- C言語プログラミングの二分木と再帰法と動的計画法を使って解く問題に関する質問です。
1
+ aaC言語プログラミングの二分木と再帰法と動的計画法を使って解く問題に関する質問です。
body CHANGED
@@ -1,85 +1,1 @@
1
- C言語プログラミングの質問です。
2
-
3
- ーーーーーーーーーーーー問題文ーーーーーーーーーーーーーーー
4
-
5
- 京都では毎年八月十六日に五山の送り火が行
6
- われる. この日には, 五つの異なる形をした大き
7
- な焚き火が京都の山々でたかれる. この五つの
8
- 形には「大文字」, 「法・妙」, 「舟形」, 「左
9
- 大文字」, 「鳥居形」があり, 伝統的にこの順番
10
- で点火される.
11
- 京都はまた, 通りが長方形の格子状になるよ
12
- うに構築されている. それぞれの送り火の位置
13
- が, 以下に示すように二つの通りの交差上にあ
14
- るとする:
15
- 1. 大文字: 今出川通と白川通,
16
- 2. 法・妙: 北山通と下鴨本通(河原町通),
17
- 3. 舟形: 宝ヶ池通と千本通,
18
- 4. 左大文字: 北大路通と大宮通,
19
- 5. 鳥居形: 今出川通と西大路通,
20
- また, 自身が二つの通りのどちらかに居れば, 送
21
- り火を見ることができるとする.
22
-
23
- 一区画歩くのに五分かかるとし, 現在京都大
24
- 学吉田キャンパスにいるとする. 吉田キャンパ
25
- スは今出川通と東大路通の交差上にある. 今送
26
- り火が始まったとすると, 大文字の送り火は現
27
- 在の場所からちょうど見られる. しかし, 法・妙
28
- の送り火が始まると, 西の河原町通へ移動する
29
- ために十分かけて二区画歩くか, もしくは北の
30
- 北山通へ二十分かけて四区画歩く必要がある.
31
- ここで, 三つ目の舟形の送り火が宝ヶ池通と千
32
- 本通で始まるとどうなるだろうか. もし西へ向
33
- かうことを選んでおり, 今出川通と河原町通に
34
- いるのであれば, 西に三区画の千本通に向かう
35
- か, あるいは北に五区画の宝ヶ池通に向かうか
36
- を選ぶことができる. しかし, すでに東大路通
37
- と北山通にいるのであれば, 西に五区画の千本
38
- 通へ向かうか, あるいは北にたった一区画の宝ヶ
39
- 池通に向かうかを選ぶことができる.
40
- さて, 送り火を全て見るために歩くのに五分かかる
41
- 最短時間はいくらかであろうか.
42
-
43
- この問題を一般化すると以下のようになる。
44
-
45
- 今, ある自然数k に対して[-k, k] に座標を持つ
46
- ような, (2k + 1) × (2k + 1) の正方格子の原点
47
- (0,0) に居るとする. この格子の一区画を歩くの
48
- に1 単位時間かかる. ある順番でn 個の座標ペ
49
- ア(送り火の位置、iは順番)(x[i],y[i]), -k <= x[i],y[i] <= k(i = 1,2,...,n) が
50
- 与えられ, 全ての送り火を与えられた順番で見
51
- たい。また、送り火の位置が(x,y)とすると、(x,all)または(all,y)(allは-k <= all
1
+ aasmdmlasmdlma_sldmas_;mdlalsmd;lasdmsadlams;mdlsam;ldm;asm;dm;asmdm;lasdm;asdm;alsmdlasmd;mlasmdasdasd
52
- <= kを満たす任意の整数)に行けば送り火を見られるとする。
53
-
54
- この問題を動的計画法で解け。
55
-
56
-
57
- ーーーーーーーーーーーーーーーーーーーーー
58
-
59
- 入力形式はテキストファイルinput.txtに入っていて、入力形式は
60
- n
61
- k
62
- x[1] y[1]
63
- x[2] y[2]
64
- ・ ・
65
- ・ ・
66
- ・ ・
67
- x[n] y[n]
68
- です。
69
- ちなみに入力はうまくできました。
70
-
71
-
72
- この問題を二分木を使って解きたいんですが、アルゴリズムがわからないので教えて欲しいです。今思いついた解き方について少しして説明します。
73
- まず漸化式を以下のように決めました。
74
- (a[i],b[i])を (x[i],y[i]) が見える最短の位置とする。||は絶対値です。
75
-
76
- |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
77
-     (a[i],b[i]) = (x[i],b[i-1])
78
-
79
- |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
80
-     (a[i],b[i]) = (a[i-1],y[i])
81
-
82
- |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
83
-      最短路が二つできるから、ここで二分木を使うのかと思われるが実装方法がわからない。
84
-
85
- アルゴリズムを教えて欲しいです。

17

説明の変更。

2017/12/10 13:44

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -51,7 +51,7 @@
51
51
  たい。また、送り火の位置が(x,y)とすると、(x,all)または(all,y)(allは-k <= all
52
52
  <= kを満たす任意の整数)に行けば送り火を見られるとする。
53
53
 
54
- この問題を再帰法と動的計画法、二つのやり方で解け。
54
+ この問題を動的計画法で解け。
55
55
 
56
56
 
57
57
  ーーーーーーーーーーーーーーーーーーーーー
@@ -69,8 +69,8 @@
69
69
  ちなみに入力はうまくできました。
70
70
 
71
71
 
72
- この問題を再帰法と二分木を使ってC言語で解きたくて、書てみたんですが、実装方法がわからないところがあります。解き方について少しして説明します。
72
+ この問題を二分木を使って解きたいんですが、アルゴリズムがわからないので教えて欲しいです。今思いついた解き方について少しして説明します。
73
- まず再帰の漸化式を以下のように決めました。
73
+ まず漸化式を以下のように決めました。
74
74
  (a[i],b[i])を (x[i],y[i]) が見える最短の位置とする。||は絶対値です。
75
75
 
76
76
  |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
@@ -82,186 +82,4 @@
82
82
  |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
83
83
       最短路が二つできるから、ここで二分木を使うのかと思われるが実装方法がわからない。
84
84
 
85
- ちなみに未完成のソースコードはこちらです。(未完成であり、間違った結果を出力してしまっているので、実装方法がわかる聡明な方は、お読みにならないことをお勧めします。)funcという二分木と再帰を用いて(a[i],b[i])までの最短路を求める関数の実装方法がわかりません。再帰呼び出しの位置がが違うのだと思いますが、どこで呼び出せばいいのかもわかりません。
86
-
87
- ```C言語
88
- #include<stdio.h>
89
- #include<stdlib.h>
90
-
91
- struct node {
92
- int value;// このノードが保持している値
93
- int length;// 最短路の長さ
94
- struct node *left_ptr; // 左枝
95
- struct node *right_ptr; // 右枝
96
- };
97
- // ツリーの頂点 root
98
- static struct node *root = NULL;
99
-
100
- int x[100]; //送り火の位置のx座標
101
- int y[100]; //送り火の位置のy座標
102
- int count = 1; //データ入力のための変数
103
-
104
- void print_tree(struct node *);
105
- void find_shortest_path(int,int*,int*,int*); //最短路を求める再帰関数
106
- void make_tree(struct node **node,int value,int length); //二分木を作る関数
107
- int main(){
108
-
109
- //
110
- //データの入力
111
- //
112
- int input[100];
113
- int ret;
114
- int a,b;
115
-
116
- FILE *file;
117
- file = fopen("input.txt","r");
118
- if(file == NULL) {
119
- printf("the file can`t be opened\n");
120
- return -1;
121
- }
122
- int m = 0;
123
- while(( ret = fscanf( file , "%d %d" , &a , &b )) != EOF ) {
124
- input[m] = a;
125
- m++;
126
- input[m] = b;
127
- m++;
128
- }
129
- fclose(file);
130
- // end input
131
-
132
- int n = input[0];// 送り火の数(n)
133
- int k = input[1];// (2k+1)x(2k+1)の格子のサイズ
134
- int now_x,now_y = 0; //現在の位置
135
-
136
- //送り火の位置の入力
137
- for(int v = 2; v < m; v++){
138
- if(v % 2 == 0){
139
- x[v / 2] = input[v];
140
- }else{
141
- y[ (v-1)/2 ] = input[v];
142
- }
143
- }
144
- //
145
- //データの入力終了
146
- //
147
-
148
-
149
- //データを出力
150
- printf("n = %d,k = %d\n",n,k);
151
- for(int v = 1; v < n+1; v++){
152
- printf("(x[%d],y[%d]) = (%d,%d)\n",v,v,x[v],y[v]);
153
- }
154
-
155
-
156
- int address1 = 1; //アドレスを確保するための適当な値
157
- int address2 = 2;
158
- int address3 = 3;
159
- find_shortest_path(n,&address1,&address2,&address3);
160
-
161
- print_tree(root);
162
-
163
- return 0;
164
- }
165
-
166
-
167
- //*l は(x[n],y[n])が見える最短路の長さ
168
- //(*a,*b)は(x[n],y[n])が見える最短の位置
169
- //
170
- void find_shortest_path(int n ,int *a,int *b,int *l){
171
- if(n != 0){
172
- find_shortest_path(n-1,a,b,l);
173
- int pre_a = *a;
174
- int pre_b = *b;
175
- int pre_l = *l;
176
-
177
-
178
- //if(abs(x[n] - pre_a) < abs(y[n]- pre_b)){
179
- *a = x[n];
180
- *b = pre_b;
181
- *l = *l + abs(x[n] - pre_a);
182
- printf("r\n");
183
- make_tree(&root->right_ptr,count,*l);
184
- count++;
185
-
186
- *l = pre_l;
187
- //}else if (abs(x[n] - pre_a) > abs(y[n]- pre_b)){
188
- *a = pre_a;
189
- *b = y[n];
190
- *l = *l + abs(y[n] - pre_b);
191
- printf("l\n");
192
- make_tree(&root->left_ptr,count,*l);
193
- count++;
194
- //}
195
-
196
- }else{
197
- *a = 0;
198
- *b = 0;
199
- *l = 0;
200
- printf("0\n");
201
- make_tree(&root,count,*l);
202
- count++;
203
- }
204
- }
205
-
206
- //length は(x[n],y[n])が見える最短路の長さ
207
- void make_tree(struct node **node, int value,int length)
208
- {
209
- int result; // 数値の大小比較結果
210
-
211
- // ノードが存在しない場合
212
- if ((*node) == NULL) {
213
-
214
- // 新しい領域を割り当てノードを作成する
215
- (*node) = malloc(sizeof(struct node));
216
- if ((*node) == NULL){
217
- fprintf(stderr, "NULL");
218
- exit (8);
219
- }
220
-
221
- // メンバを初期化
222
- (*node)->left_ptr = NULL;
223
- (*node)->right_ptr = NULL;
224
- (*node)->value = value;
225
- (*node)->length = length;
226
-
227
- // make_tree関数を終了
228
- return;
229
- }
230
-
231
- // 現在のノードより大きかったら正。小さかったら負。等しかったら0
232
- if ((*node)->value < value) {
233
- result = 1;
234
- } else if ((*node)->value > value) {
235
- result = -1;
236
- } else if ((*node)->value == value) {
237
- result = 0;
238
- }
239
-
240
- // 現在の数値が既にあれば、新たなノードは作成せずmake_tree関数を終了
241
- if (result == 0)
242
- return;
243
-
244
- // 大きかったら右枝に移動
245
- if (0 < result) {
246
- make_tree(&(*node)->right_ptr, value,length);
247
- }
248
- // 小さかったら左枝に移動
249
- else {
250
- make_tree(&(*node)->left_ptr, value,length);
251
- }
252
- }
253
-
254
- void print_tree(struct node *now)
255
- {
256
- if (now == NULL)
257
- return;
258
-
259
- print_tree(now->left_ptr);
260
- printf("%d %d\n",now->value,now->length);
261
- print_tree(now->right_ptr);
262
- }
263
-
264
-
265
- ```
266
-
267
- できれば動的計画法で解くアルゴリズム教えてくれるとありがたいです。
85
+ アルゴリズム教えて欲しいです。

16

説明の追加

2017/12/09 15:30

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -39,15 +39,17 @@
39
39
  池通に向かうかを選ぶことができる.
40
40
  さて, 送り火を全て見るために歩くのに五分かかる
41
41
  最短時間はいくらかであろうか.
42
+
42
43
  この問題を一般化すると以下のようになる。
43
44
 
44
- 今, ある自然数k に対して[ k, k] に座標を持つ
45
+ 今, ある自然数k に対して[-k, k] に座標を持つ
45
46
  ような, (2k + 1) × (2k + 1) の正方格子の原点
46
47
  (0,0) に居るとする. この格子の一区画を歩くの
47
48
  に1 単位時間かかる. ある順番でn 個の座標ペ
48
- ア(x[i],y[i]), -k <= x[i],y[i] <= k(i = 1,2,...,n) が
49
+ (送り火の位置、iは順番)(x[i],y[i]), -k <= x[i],y[i] <= k(i = 1,2,...,n) が
49
50
  与えられ, 全ての送り火を与えられた順番で見
51
+ たい。また、送り火の位置が(x,y)とすると、(x,all)または(all,y)(allは-k <= all
50
-
52
+ <= kを満す任意の整数)に行けば送り火を見られるとする
51
53
 
52
54
  この問題を再帰法と動的計画法、二つのやり方で解け。
53
55
 

15

コード修正

2017/12/09 05:05

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -100,7 +100,7 @@
100
100
  int count = 1; //データ入力のための変数
101
101
 
102
102
  void print_tree(struct node *);
103
- void func(int,int*,int*,int*); //最短路を求める再帰関数
103
+ void find_shortest_path(int,int*,int*,int*); //最短路を求める再帰関数
104
104
  void make_tree(struct node **node,int value,int length); //二分木を作る関数
105
105
  int main(){
106
106
 
@@ -154,7 +154,7 @@
154
154
  int address1 = 1; //アドレスを確保するための適当な値
155
155
  int address2 = 2;
156
156
  int address3 = 3;
157
- func(n,&address1,&address2,&address3);
157
+ find_shortest_path(n,&address1,&address2,&address3);
158
158
 
159
159
  print_tree(root);
160
160
 
@@ -165,9 +165,9 @@
165
165
  //*l は(x[n],y[n])が見える最短路の長さ
166
166
  //(*a,*b)は(x[n],y[n])が見える最短の位置
167
167
  //
168
- void func_find_shortest_path(int n ,int *a,int *b,int *l){
168
+ void find_shortest_path(int n ,int *a,int *b,int *l){
169
169
  if(n != 0){
170
- func_find_shortest_path(n-1,a,b,l);
170
+ find_shortest_path(n-1,a,b,l);
171
171
  int pre_a = *a;
172
172
  int pre_b = *b;
173
173
  int pre_l = *l;

14

追加の説明

2017/12/08 04:26

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -165,9 +165,9 @@
165
165
  //*l は(x[n],y[n])が見える最短路の長さ
166
166
  //(*a,*b)は(x[n],y[n])が見える最短の位置
167
167
  //
168
- void func(int n ,int *a,int *b,int *l){
168
+ void func_find_shortest_path(int n ,int *a,int *b,int *l){
169
169
  if(n != 0){
170
- func(n-1,a,b,l);
170
+ func_find_shortest_path(n-1,a,b,l);
171
171
  int pre_a = *a;
172
172
  int pre_b = *b;
173
173
  int pre_l = *l;

13

追加の説明

2017/12/08 04:21

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -80,7 +80,7 @@
80
80
  |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
81
81
       最短路が二つできるから、ここで二分木を使うのかと思われるが実装方法がわからない。
82
82
 
83
- ちなみに未完成のソースコードはこちらです。funcという二分木と再帰を用いて(a[i],b[i])までの最短路を求める関数の実装方法がわかりません。再帰呼び出しの位置がが違うのだと思いますが、どこで呼び出せばいいのかもわかりません。
83
+ ちなみに未完成のソースコードはこちらです。(未完成であり、間違った結果を出力してしまっているので、実装方法がわかる聡明な方は、お読みにならないことをお勧めします。)funcという二分木と再帰を用いて(a[i],b[i])までの最短路を求める関数の実装方法がわかりません。再帰呼び出しの位置がが違うのだと思いますが、どこで呼び出せばいいのかもわかりません。
84
84
 
85
85
  ```C言語
86
86
  #include<stdio.h>

12

追加の説明。

2017/12/08 04:19

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -80,7 +80,7 @@
80
80
  |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
81
81
       最短路が二つできるから、ここで二分木を使うのかと思われるが実装方法がわからない。
82
82
 
83
- ちなみに未完成のソースコードはこちらです。funcという二分木と絡めた再帰を用いて最短路を求める実装方法がよくわかりません。
83
+ ちなみに未完成のソースコードはこちらです。funcという二分木と再帰を用いて(a[i],b[i])までの最短路を求める関数の実装方法がわかりません。再帰呼び出しの位置がが違うのだと思いますが、どこで呼び出せばいいのかもわかりません。
84
84
 
85
85
  ```C言語
86
86
  #include<stdio.h>

11

追加の説明

2017/12/08 04:17

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -80,7 +80,7 @@
80
80
  |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
81
81
       最短路が二つできるから、ここで二分木を使うのかと思われるが実装方法がわからない。
82
82
 
83
- ちなみに未完成のソースコードはこちらです。funcという二分木と絡めた再帰関数の実装方法がよくわかりません。
83
+ ちなみに未完成のソースコードはこちらです。funcという二分木と絡めた再帰を用いて最短路を求める実装方法がよくわかりません。
84
84
 
85
85
  ```C言語
86
86
  #include<stdio.h>

10

説明の追加

2017/12/08 04:14

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -80,7 +80,7 @@
80
80
  |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
81
81
       最短路が二つできるから、ここで二分木を使うのかと思われるが実装方法がわからない。
82
82
 
83
- ちなみに未完成のソースコードはこちらです。fという二分木と絡めた再帰関数の実装方法がよくわかりません。
83
+ ちなみに未完成のソースコードはこちらです。funcという二分木と絡めた再帰関数の実装方法がよくわかりません。
84
84
 
85
85
  ```C言語
86
86
  #include<stdio.h>

9

コードの編集

2017/12/08 04:12

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -99,7 +99,8 @@
99
99
  int y[100]; //送り火の位置のy座標
100
100
  int count = 1; //データ入力のための変数
101
101
 
102
+ void print_tree(struct node *);
102
- void f(int,int*,int*,int*); //最短路を求める再帰関数
103
+ void func(int,int*,int*,int*); //最短路を求める再帰関数
103
104
  void make_tree(struct node **node,int value,int length); //二分木を作る関数
104
105
  int main(){
105
106
 
@@ -150,54 +151,53 @@
150
151
  }
151
152
 
152
153
 
153
- int p = 1; //アドレスを確保するための適当な値
154
+ int address1 = 1; //アドレスを確保するための適当な値
154
- int q = 2;
155
- int r = 20;
155
+ int address2 = 2;
156
+ int address3 = 3;
156
- f(n,&p,&q,&r);
157
+ func(n,&address1,&address2,&address3);
157
158
 
158
- //答えを出力
159
+ print_tree(root);
159
- printf("(x,y) = (%d %d), answer = %d\n",p,q,r);
160
160
 
161
161
  return 0;
162
162
  }
163
163
 
164
164
 
165
- // *l は(x[n],y[n])が見える位置(a[n],b[n])に到るまでの路の長で最短路の長さ
165
+ //*l は(x[n],y[n])が見える最短路の長さ
166
- // (*a,*b) は(a[n],b[n])に対応す
166
+ //*a,*bは(x[n],y[n])が見え最短の位置
167
+ //
167
- void f(int n ,int *a,int *b,int *l){
168
+ void func(int n ,int *a,int *b,int *l){
168
169
  if(n != 0){
169
- f(n-1,a,b,l);
170
+ func(n-1,a,b,l);
170
- int pre_a = *a; //(a[n-1] , b[n-1]) = (pre_a,pre_b)
171
+ int pre_a = *a;
171
172
  int pre_b = *b;
172
173
  int pre_l = *l;
173
- if(abs(x[n] - pre_a) < abs(y[n]- pre_b)){
174
- *a = x[n]; //(a[n],b[n]) = (x[n],b[n-1])
175
- *b = pre_b;
176
- *l = *l + abs(x[n] - pre_a);
177
- }else if (abs(x[n] - pre_a) > abs(y[n]- pre_b)){
178
- *a = pre_a; //(a[n],b[n]) = (a[n-1],y[n])
179
- *b = y[n];
180
- *l = *l + abs(y[n] - pre_b);
181
- }else{
182
-
183
- //(a[n-1],b[n-1])から(x[n],y[n])が見える位置、(a[n],b[n)同じだった時、分岐するのだが、ここの実装方法がわかリマセン。
184
- *a = x[n];
185
- *b = pre_b;
186
- *l = *l + abs(x[n] - pre_a);
187
- make_tree(root->right_ptr,count,*l);
188
- count++;
189
-
190
- *a = pre_a;
191
- *b = y[n];
192
- *l = *l + abs(y[n] - pre_b);
193
- make_tree(root->left_ptr,count,*l);
194
- count++;
195
- }
196
174
 
175
+
176
+ //if(abs(x[n] - pre_a) < abs(y[n]- pre_b)){
177
+ *a = x[n];
178
+ *b = pre_b;
179
+ *l = *l + abs(x[n] - pre_a);
180
+ printf("r\n");
181
+ make_tree(&root->right_ptr,count,*l);
182
+ count++;
183
+
184
+ *l = pre_l;
185
+ //}else if (abs(x[n] - pre_a) > abs(y[n]- pre_b)){
186
+ *a = pre_a;
187
+ *b = y[n];
188
+ *l = *l + abs(y[n] - pre_b);
189
+ printf("l\n");
190
+ make_tree(&root->left_ptr,count,*l);
191
+ count++;
192
+ //}
193
+
197
194
  }else{
198
195
  *a = 0;
199
196
  *b = 0;
200
197
  *l = 0;
198
+ printf("0\n");
199
+ make_tree(&root,count,*l);
200
+ count++;
201
201
  }
202
202
  }
203
203
 
@@ -249,7 +249,17 @@
249
249
  }
250
250
  }
251
251
 
252
+ void print_tree(struct node *now)
253
+ {
254
+ if (now == NULL)
255
+ return;
256
+
257
+ print_tree(now->left_ptr);
258
+ printf("%d %d\n",now->value,now->length);
259
+ print_tree(now->right_ptr);
260
+ }
252
261
 
262
+
253
263
  ```
254
264
 
255
265
  できれば動的計画法で解くアルゴリズムも教えてくれるとありがたいです。

8

説明の追加

2017/12/08 04:07

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -70,10 +70,13 @@
70
70
  この問題を再帰法と二分木を使ってC言語で解きたくて、書いてみたんですが、実装方法がわからないところがあります。解き方について少しして説明します。
71
71
  まず再帰の漸化式を以下のように決めました。
72
72
  (a[i],b[i])を (x[i],y[i]) が見える最短の位置とする。||は絶対値です。
73
+
73
74
  |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
74
75
      (a[i],b[i]) = (x[i],b[i-1])
76
+
75
77
  |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
76
78
      (a[i],b[i]) = (a[i-1],y[i])
79
+
77
80
  |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
78
81
       最短路が二つできるから、ここで二分木を使うのかと思われるが実装方法がわからない。
79
82
 
@@ -159,8 +162,7 @@
159
162
  }
160
163
 
161
164
 
162
- // *l は(x[n],y[n])が見える最短路の長さ
165
+ // *l は(x[n],y[n])が見える位置(a[n],b[n])に到るまでの路の長で最短路の長さ
163
- // (a[n],b[n])は(x[n],y[n])が見える最短の位置とすると、
164
166
  // (*a,*b) は(a[n],b[n])に対応する。
165
167
  void f(int n ,int *a,int *b,int *l){
166
168
  if(n != 0){
@@ -169,11 +171,11 @@
169
171
  int pre_b = *b;
170
172
  int pre_l = *l;
171
173
  if(abs(x[n] - pre_a) < abs(y[n]- pre_b)){
172
- *a = x[n];
174
+ *a = x[n]; //(a[n],b[n]) = (x[n],b[n-1])
173
175
  *b = pre_b;
174
176
  *l = *l + abs(x[n] - pre_a);
175
177
  }else if (abs(x[n] - pre_a) > abs(y[n]- pre_b)){
176
- *a = pre_a;
178
+ *a = pre_a; //(a[n],b[n]) = (a[n-1],y[n])
177
179
  *b = y[n];
178
180
  *l = *l + abs(y[n] - pre_b);
179
181
  }else{

7

説明の追加

2017/12/07 13:38

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -75,7 +75,7 @@
75
75
  |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
76
76
      (a[i],b[i]) = (a[i-1],y[i])
77
77
  |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
78
-      最短路が二つできるここの扱いがわからない。
78
+      最短路が二つできるから、ここで二分木を使うかと思われる実装方法がわからない。
79
79
 
80
80
  ちなみに未完成のソースコードはこちらです。fという二分木と絡めた再帰関数の実装方法がよくわかりません。
81
81
 

6

説明追加

2017/12/07 13:33

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -1,5 +1,7 @@
1
1
  C言語プログラミングの質問です。
2
2
 
3
+ ーーーーーーーーーーーー問題文ーーーーーーーーーーーーーーー
4
+
3
5
  京都では毎年八月十六日に五山の送り火が行
4
6
  われる. この日には, 五つの異なる形をした大き
5
7
  な焚き火が京都の山々でたかれる. この五つの
@@ -45,8 +47,13 @@
45
47
  に1 単位時間かかる. ある順番でn 個の座標ペ
46
48
  ア(x[i],y[i]), -k <= x[i],y[i] <= k(i = 1,2,...,n) が
47
49
  与えられ, 全ての送り火を与えられた順番で見
48
- たい.
50
+ たい
49
51
 
52
+ この問題を再帰法と動的計画法、二つのやり方で解け。
53
+
54
+
55
+ ーーーーーーーーーーーーーーーーーーーーー
56
+
50
57
  入力形式はテキストファイルinput.txtに入っていて、入力形式は
51
58
  n
52
59
  k

5

説明追加

2017/12/07 13:23

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -64,11 +64,11 @@
64
64
  まず再帰の漸化式を以下のように決めました。
65
65
  (a[i],b[i])を (x[i],y[i]) が見える最短の位置とする。||は絶対値です。
66
66
  |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
67
- (a[i],b[i]) = (x[i],b[i-1])
67
+     (a[i],b[i]) = (x[i],b[i-1])
68
68
  |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
69
- (a[i],b[i]) = (a[i-1],y[i)
69
+     (a[i],b[i]) = (a[i-1],y[i]
70
70
  |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
71
- 最短路が二つできる。ここの扱いがわからない。
71
+      最短路が二つできる。ここの扱いがわからない。
72
72
 
73
73
  ちなみに未完成のソースコードはこちらです。fという二分木と絡めた再帰関数の実装方法がよくわかりません。
74
74
 

4

説明追加

2017/12/07 13:21

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -62,7 +62,7 @@
62
62
 
63
63
  この問題を再帰法と二分木を使ってC言語で解きたくて、書いてみたんですが、実装方法がわからないところがあります。解き方について少しして説明します。
64
64
  まず再帰の漸化式を以下のように決めました。
65
- (a[i],b[i])を (x[i],y[i]) が見える最短の位置とする。
65
+ (a[i],b[i])を (x[i],y[i]) が見える最短の位置とする。||は絶対値です。
66
66
  |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
67
67
  (a[i],b[i]) = (x[i],b[i-1])
68
68
  |x[i] - a[i-1]| < |y[i] - b[i-1]|の時

3

説明追加

2017/12/07 13:10

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -43,26 +43,35 @@
43
43
  ような, (2k + 1) × (2k + 1) の正方格子の原点
44
44
  (0,0) に居るとする. この格子の一区画を歩くの
45
45
  に1 単位時間かかる. ある順番でn 個の座標ペ
46
- ア(xi,yi), -k <= xi,yi <= k(i = 1,2,...,n) が
46
+ ア(x[i],y[i]), -k <= x[i],y[i] <= k(i = 1,2,...,n) が
47
47
  与えられ, 全ての送り火を与えられた順番で見
48
48
  たい.
49
49
 
50
50
  入力形式はテキストファイルinput.txtに入っていて、入力形式は
51
51
  n
52
52
  k
53
- x1 y1
53
+ x[1] y[1]
54
- x2 y2
54
+ x[2] y[2]
55
55
  ・ ・
56
56
  ・ ・
57
57
  ・ ・
58
- xn yn
58
+ x[n] y[n]
59
+ です。
60
+ ちなみに入力はうまくできました。
59
61
 
60
62
 
63
+ この問題を再帰法と二分木を使ってC言語で解きたくて、書いてみたんですが、実装方法がわからないところがあります。解き方について少しして説明します。
64
+ まず再帰の漸化式を以下のように決めました。
65
+ (a[i],b[i])を (x[i],y[i]) が見える最短の位置とする。
66
+ |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
67
+ (a[i],b[i]) = (x[i],b[i-1])
68
+ |x[i] - a[i-1]| < |y[i] - b[i-1]|の時
69
+ (a[i],b[i]) = (a[i-1],y[i)
70
+ |x[i] - a[i-1]| = |y[i] - b[i-1]|の時
71
+ 最短路が二つできる。ここの扱いがわからない。
61
72
 
62
- 問題を再帰法と二分木を使ってC言語でいんですが、実装方法がわかりません。
73
+ ちなみに未完成ソースコードはこちらです。fいう二分木と絡め再帰関数の実装方法がよくわかりません。
63
- できれば動的計画法で解く方法も教えてくれるとありがたいです。
64
74
 
65
- ちなみに未完成のソースコードはこちらです。fという二分木と絡めた再帰関数の実装方法がよくわかりません。
66
75
  ```C言語
67
76
  #include<stdio.h>
68
77
  #include<stdlib.h>
@@ -232,4 +241,6 @@
232
241
  }
233
242
 
234
243
 
235
- ```
244
+ ```
245
+
246
+ できれば動的計画法で解くアルゴリズムも教えてくれるとありがたいです。

2

コードの編集

2017/12/07 13:08

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -69,7 +69,7 @@
69
69
 
70
70
  struct node {
71
71
  int value;// このノードが保持している値
72
- int length;
72
+ int length;// 最短路の長さ
73
73
  struct node *left_ptr; // 左枝
74
74
  struct node *right_ptr; // 右枝
75
75
  };
@@ -78,14 +78,15 @@
78
78
 
79
79
  int x[100]; //送り火の位置のx座標
80
80
  int y[100]; //送り火の位置のy座標
81
- int count = 1;
81
+ int count = 1; //データ入力のための変数
82
82
 
83
- void f(int,int*,int*,int*);
83
+ void f(int,int*,int*,int*); //最短路を求める再帰関数
84
- void print_value(struct node *now);
85
- void make_tree(struct node **node,int value,int length);
84
+ void make_tree(struct node **node,int value,int length); //二分木を作る関数
86
85
  int main(){
87
86
 
87
+ //
88
- //input
88
+ //データの入力
89
+ //
89
90
  int input[100];
90
91
  int ret;
91
92
  int a,b;
@@ -118,27 +119,37 @@
118
119
  y[ (v-1)/2 ] = input[v];
119
120
  }
120
121
  }
122
+ //
123
+ //データの入力終了
124
+ //
121
125
 
126
+
127
+ //データを出力
122
128
  printf("n = %d,k = %d\n",n,k);
123
129
  for(int v = 1; v < n+1; v++){
124
130
  printf("(x[%d],y[%d]) = (%d,%d)\n",v,v,x[v],y[v]);
125
131
  }
126
132
 
133
+
127
- int p = 1;
134
+ int p = 1; //アドレスを確保するための適当な値
128
135
  int q = 2;
129
136
  int r = 20;
130
137
  f(n,&p,&q,&r);
131
138
 
139
+ //答えを出力
132
140
  printf("(x,y) = (%d %d), answer = %d\n",p,q,r);
133
- print_value(root);
134
141
 
135
142
  return 0;
136
143
  }
137
144
 
145
+
146
+ // *l は(x[n],y[n])が見える最短路の長さ
147
+ // (a[n],b[n])は(x[n],y[n])が見える最短の位置とすると、
148
+ // (*a,*b) は(a[n],b[n])に対応する。
138
149
  void f(int n ,int *a,int *b,int *l){
139
150
  if(n != 0){
140
151
  f(n-1,a,b,l);
141
- int pre_a = *a;
152
+ int pre_a = *a; //(a[n-1] , b[n-1]) = (pre_a,pre_b)
142
153
  int pre_b = *b;
143
154
  int pre_l = *l;
144
155
  if(abs(x[n] - pre_a) < abs(y[n]- pre_b)){
@@ -151,7 +162,7 @@
151
162
  *l = *l + abs(y[n] - pre_b);
152
163
  }else{
153
164
 
154
- //最短路が同じだった時、分岐
165
+ //(a[n-1],b[n-1])から(x[n],y[n])見える位置、(a[n],b[n)同じだった時、分岐するのだが、ここの実装方法がわかリマセン。
155
166
  *a = x[n];
156
167
  *b = pre_b;
157
168
  *l = *l + abs(x[n] - pre_a);
@@ -172,6 +183,7 @@
172
183
  }
173
184
  }
174
185
 
186
+ //length は(x[n],y[n])が見える最短路の長さ
175
187
  void make_tree(struct node **node, int value,int length)
176
188
  {
177
189
  int result; // 数値の大小比較結果
@@ -196,7 +208,6 @@
196
208
  return;
197
209
  }
198
210
 
199
- // テキストから取り出した数値をノードの数値と比較
200
211
  // 現在のノードより大きかったら正。小さかったら負。等しかったら0
201
212
  if ((*node)->value < value) {
202
213
  result = 1;
@@ -220,14 +231,5 @@
220
231
  }
221
232
  }
222
233
 
223
- void print_value(struct node *now)
224
- {
225
- if (now == NULL)
226
- return;
227
-
228
- print_value(now->left_ptr);
229
- printf("%d %d\n", now->value,now->length);
230
- print_value(now->right_ptr);
231
- }
232
234
 
233
235
  ```

1

コードの追加

2017/12/07 12:57

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -35,17 +35,199 @@
35
35
  と北山通にいるのであれば, 西に五区画の千本
36
36
  通へ向かうか, あるいは北にたった一区画の宝ヶ
37
37
  池通に向かうかを選ぶことができる.
38
- さて, 送り火を全て見るために歩くのにかかる
38
+ さて, 送り火を全て見るために歩くのに五分かかる
39
39
  最短時間はいくらかであろうか.
40
40
  この問題を一般化すると以下のようになる。
41
41
 
42
- 今, ある自然数k に対して[ k; k] に座標を持つ
42
+ 今, ある自然数k に対して[ k, k] に座標を持つ
43
- ような, (2k + 1) (2k + 1) の正方格子の原点
43
+ ような, (2k + 1) × (2k + 1) の正方格子の原点
44
- (0; 0) に居るとする. この格子の一区画を歩くの
44
+ (0,0) に居るとする. この格子の一区画を歩くの
45
45
  に1 単位時間かかる. ある順番でn 個の座標ペ
46
- ア(xi; yi), k xi; yi k, i = 1; 2; : : : ; n が
46
+ ア(xi,yi), -k <= xi,yi <= k(i = 1,2,...,n)
47
47
  与えられ, 全ての送り火を与えられた順番で見
48
48
  たい.
49
49
 
50
+ 入力形式はテキストファイルinput.txtに入っていて、入力形式は
51
+ n
52
+ k
53
+ x1 y1
54
+ x2 y2
55
+ ・ ・
56
+ ・ ・
57
+ ・ ・
58
+ xn yn
59
+
60
+
61
+
50
62
  この問題を再帰法と二分木を使ってC言語でときたいんですが、実装方法がわかりません。
51
- できれば動的計画法で解く方法も教えてくれるとありがたいです。
63
+ できれば動的計画法で解く方法も教えてくれるとありがたいです。
64
+
65
+ ちなみに未完成のソースコードはこちらです。fという二分木と絡めた再帰関数の実装方法がよくわかりません。
66
+ ```C言語
67
+ #include<stdio.h>
68
+ #include<stdlib.h>
69
+
70
+ struct node {
71
+ int value;// このノードが保持している値
72
+ int length;
73
+ struct node *left_ptr; // 左枝
74
+ struct node *right_ptr; // 右枝
75
+ };
76
+ // ツリーの頂点 root
77
+ static struct node *root = NULL;
78
+
79
+ int x[100]; //送り火の位置のx座標
80
+ int y[100]; //送り火の位置のy座標
81
+ int count = 1;
82
+
83
+ void f(int,int*,int*,int*);
84
+ void print_value(struct node *now);
85
+ void make_tree(struct node **node,int value,int length);
86
+ int main(){
87
+
88
+ //input
89
+ int input[100];
90
+ int ret;
91
+ int a,b;
92
+
93
+ FILE *file;
94
+ file = fopen("input.txt","r");
95
+ if(file == NULL) {
96
+ printf("the file can`t be opened\n");
97
+ return -1;
98
+ }
99
+ int m = 0;
100
+ while(( ret = fscanf( file , "%d %d" , &a , &b )) != EOF ) {
101
+ input[m] = a;
102
+ m++;
103
+ input[m] = b;
104
+ m++;
105
+ }
106
+ fclose(file);
107
+ // end input
108
+
109
+ int n = input[0];// 送り火の数(n)
110
+ int k = input[1];// (2k+1)x(2k+1)の格子のサイズ
111
+ int now_x,now_y = 0; //現在の位置
112
+
113
+ //送り火の位置の入力
114
+ for(int v = 2; v < m; v++){
115
+ if(v % 2 == 0){
116
+ x[v / 2] = input[v];
117
+ }else{
118
+ y[ (v-1)/2 ] = input[v];
119
+ }
120
+ }
121
+
122
+ printf("n = %d,k = %d\n",n,k);
123
+ for(int v = 1; v < n+1; v++){
124
+ printf("(x[%d],y[%d]) = (%d,%d)\n",v,v,x[v],y[v]);
125
+ }
126
+
127
+ int p = 1;
128
+ int q = 2;
129
+ int r = 20;
130
+ f(n,&p,&q,&r);
131
+
132
+ printf("(x,y) = (%d %d), answer = %d\n",p,q,r);
133
+ print_value(root);
134
+
135
+ return 0;
136
+ }
137
+
138
+ void f(int n ,int *a,int *b,int *l){
139
+ if(n != 0){
140
+ f(n-1,a,b,l);
141
+ int pre_a = *a;
142
+ int pre_b = *b;
143
+ int pre_l = *l;
144
+ if(abs(x[n] - pre_a) < abs(y[n]- pre_b)){
145
+ *a = x[n];
146
+ *b = pre_b;
147
+ *l = *l + abs(x[n] - pre_a);
148
+ }else if (abs(x[n] - pre_a) > abs(y[n]- pre_b)){
149
+ *a = pre_a;
150
+ *b = y[n];
151
+ *l = *l + abs(y[n] - pre_b);
152
+ }else{
153
+
154
+ //最短路が同じだった時、分岐
155
+ *a = x[n];
156
+ *b = pre_b;
157
+ *l = *l + abs(x[n] - pre_a);
158
+ make_tree(root->right_ptr,count,*l);
159
+ count++;
160
+
161
+ *a = pre_a;
162
+ *b = y[n];
163
+ *l = *l + abs(y[n] - pre_b);
164
+ make_tree(root->left_ptr,count,*l);
165
+ count++;
166
+ }
167
+
168
+ }else{
169
+ *a = 0;
170
+ *b = 0;
171
+ *l = 0;
172
+ }
173
+ }
174
+
175
+ void make_tree(struct node **node, int value,int length)
176
+ {
177
+ int result; // 数値の大小比較結果
178
+
179
+ // ノードが存在しない場合
180
+ if ((*node) == NULL) {
181
+
182
+ // 新しい領域を割り当てノードを作成する
183
+ (*node) = malloc(sizeof(struct node));
184
+ if ((*node) == NULL){
185
+ fprintf(stderr, "NULL");
186
+ exit (8);
187
+ }
188
+
189
+ // メンバを初期化
190
+ (*node)->left_ptr = NULL;
191
+ (*node)->right_ptr = NULL;
192
+ (*node)->value = value;
193
+ (*node)->length = length;
194
+
195
+ // make_tree関数を終了
196
+ return;
197
+ }
198
+
199
+ // テキストから取り出した数値をノードの数値と比較
200
+ // 現在のノードより大きかったら正。小さかったら負。等しかったら0
201
+ if ((*node)->value < value) {
202
+ result = 1;
203
+ } else if ((*node)->value > value) {
204
+ result = -1;
205
+ } else if ((*node)->value == value) {
206
+ result = 0;
207
+ }
208
+
209
+ // 現在の数値が既にあれば、新たなノードは作成せずmake_tree関数を終了
210
+ if (result == 0)
211
+ return;
212
+
213
+ // 大きかったら右枝に移動
214
+ if (0 < result) {
215
+ make_tree(&(*node)->right_ptr, value,length);
216
+ }
217
+ // 小さかったら左枝に移動
218
+ else {
219
+ make_tree(&(*node)->left_ptr, value,length);
220
+ }
221
+ }
222
+
223
+ void print_value(struct node *now)
224
+ {
225
+ if (now == NULL)
226
+ return;
227
+
228
+ print_value(now->left_ptr);
229
+ printf("%d %d\n", now->value,now->length);
230
+ print_value(now->right_ptr);
231
+ }
232
+
233
+ ```