回答編集履歴
2
コードの効率化修正で追記
answer
CHANGED
|
@@ -140,4 +140,86 @@
|
|
|
140
140
|
とペアの組は三種類あり、N=6のときであれば15種類あります。
|
|
141
141
|
このペアというのは、辺のない正N角形で各頂点から1本ずつ線を引いている図形と対応できるので
|
|
142
142
|
(N-1)!! = (N-1)*(N-3)*(N-5)...*1 個あります。([二重階乗](https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%87%8D%E9%9A%8E%E4%B9%97))
|
|
143
|
-
このように階乗で増えていくのでN=14くらいから再帰が深くなりすぎて最後までは辿りつかないようです。
|
|
143
|
+
このように階乗で増えていくのでN=14くらいから再帰が深くなりすぎて最後までは辿りつかないようです。
|
|
144
|
+
|
|
145
|
+
|
|
146
|
+
**ここより先追記。**
|
|
147
|
+
二重階乗であることを使えば再帰しなくても済んだので効率的に求めることができました。
|
|
148
|
+
N=200で1億回目でも簡単に求まります。
|
|
149
|
+
自分が試したところN=10000000程度でも問題はなかったです。
|
|
150
|
+
```C
|
|
151
|
+
#include <stdio.h>
|
|
152
|
+
#define N 200
|
|
153
|
+
|
|
154
|
+
void show(int *,int ,int );
|
|
155
|
+
|
|
156
|
+
int main(void){
|
|
157
|
+
int i,k,n,index,count=0;
|
|
158
|
+
// S = {0,0,0,...,0,-1}
|
|
159
|
+
int S[N/2] = {0};
|
|
160
|
+
S[N/2-1] = -1;
|
|
161
|
+
|
|
162
|
+
//入力
|
|
163
|
+
printf("繰返し回数->");
|
|
164
|
+
scanf("%d",&k);
|
|
165
|
+
printf("要素の番号->");
|
|
166
|
+
scanf("%d",&n);
|
|
167
|
+
//昇順列の二つずつ各ペアに置換の求める
|
|
168
|
+
while(count<k-1){
|
|
169
|
+
index = 0;
|
|
170
|
+
count++;
|
|
171
|
+
//毎回表示するならこれを実行
|
|
172
|
+
//show(S,count,n);
|
|
173
|
+
|
|
174
|
+
S[index]++ ;
|
|
175
|
+
// 繰り上がり
|
|
176
|
+
while(S[index] >= N-1-2*index){
|
|
177
|
+
S[index] = 0;
|
|
178
|
+
S[index+1]++;
|
|
179
|
+
index++;
|
|
180
|
+
}
|
|
181
|
+
//全部調べたら終了
|
|
182
|
+
//配列最後の-1は表示時の終了条件で使うので代入
|
|
183
|
+
if(S[N/2-1] != -1){
|
|
184
|
+
S[N/2-1] = -1;
|
|
185
|
+
break;
|
|
186
|
+
}
|
|
187
|
+
}
|
|
188
|
+
|
|
189
|
+
//表示
|
|
190
|
+
show(S,k,n);
|
|
191
|
+
return 0;
|
|
192
|
+
}
|
|
193
|
+
|
|
194
|
+
void show(int *S,int k,int n){
|
|
195
|
+
int i,temp,index=0;
|
|
196
|
+
// A[] = {1,2,3,4,...,N}
|
|
197
|
+
int A[N];
|
|
198
|
+
for(i=0;i<N;i++){A[i] = i+1;}
|
|
199
|
+
while(*S != -1){
|
|
200
|
+
/* Sの置換表現通りに入れ替え */
|
|
201
|
+
temp = A[2*index+1];
|
|
202
|
+
A[2*index+1] = A[ 2*index+1+(*S)];
|
|
203
|
+
A[2*index+1+(*S)] = temp;
|
|
204
|
+
//次の置換へ
|
|
205
|
+
index++;
|
|
206
|
+
S++;
|
|
207
|
+
}
|
|
208
|
+
|
|
209
|
+
printf("\n%d回目: ",k);
|
|
210
|
+
for(i=0;i<N;i+=2){printf("(%d,%d) ",A[i],A[i+1]);}
|
|
211
|
+
for(i=0;i<N;i+=2){
|
|
212
|
+
if( A[i]==n ){printf("\n%dのペアは%dです。\n",n,A[i+1]);break;}
|
|
213
|
+
if(A[i+1]==n){printf("\n%dのペアは%dです。\n",n, A[i] );break;}
|
|
214
|
+
if(i==N-2){printf("%dのペアはありません\n",n);}
|
|
215
|
+
}
|
|
216
|
+
|
|
217
|
+
}
|
|
218
|
+
```
|
|
219
|
+
|
|
220
|
+
少し数学チックに解いた部分はあるのですが、アルゴリズム的にはN=6の場合
|
|
221
|
+
(12)(34)(56)の一つ目の(12)の部分をみて左の数値を固定して、右の数値を自分より後の数値と入れ替えることを考えます。（”後”とは入れ替えないような自分自身と入れ替える場合も含みます）
|
|
222
|
+
(1[2])(34)(56)だから2の移動先は2,3,4,5,6の5通りで入れ替えた後はそれより右の組だけを考えます。たとえばこの例で2が5と入れ替わったとしましょう。すると
|
|
223
|
+
(15)(34)(26)となり、ここで(15)は固定して残りの(34)(26)で同じことを繰り返すことによって同じパターンが出ずに全てを網羅できます。
|
|
224
|
+
ここで入れ替えた所をそれぞれ自分自身からの距離(2と5を入れ替えるのであれば3)を配列にして格納することで再帰することなく、求めることができます。
|
|
225
|
+
ちなみN=6の場合だと2の移動先が5通り、その次の右側の数字の移動先が3通り、その次の右側の数字が1通りなので全部で15通りと、ちゃんとN!!通りになっていることが確かめられます。
|
1
誤字脱字
answer
CHANGED
|
@@ -134,10 +134,10 @@
|
|
|
134
134
|
|
|
135
135
|
ところでN=4のときであれば
|
|
136
136
|
1. (1,2)(3,4)
|
|
137
|
-
2. (1,3)(
|
|
137
|
+
2. (1,3)(2,4)
|
|
138
138
|
3. (1,4)(2,3)
|
|
139
139
|
|
|
140
140
|
とペアの組は三種類あり、N=6のときであれば15種類あります。
|
|
141
|
-
このペアというのは、辺のない正N角形で各頂点から1本ずつ線を引いている図形と対応でき
|
|
141
|
+
このペアというのは、辺のない正N角形で各頂点から1本ずつ線を引いている図形と対応できるので
|
|
142
|
-
|
|
142
|
+
(N-1)!! = (N-1)*(N-3)*(N-5)...*1 個あります。([二重階乗](https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%87%8D%E9%9A%8E%E4%B9%97))
|
|
143
143
|
このように階乗で増えていくのでN=14くらいから再帰が深くなりすぎて最後までは辿りつかないようです。
|