配列nを用意して、2*nの配列に1~Z、又は1~9までの数字を格納します。3の場合、123,132,213,231,312,321の順列で、ルールは1の時は1つ間を空けて1を、2の時は2つ間を空けて2を・・・
つまり、3の場合は 231213,312132 の二つがルールと合致しているので答えとなります。
1~Zまでで、上記のようにルールに当てはまる場合のみを出力するプログラムを書きたいのですがうまくいきません。下に考えてみたものを載せます。どなたか分かる方ご教授願います。
#include<stdio.h>
int p[99]={0},a[99]={0};
int n;
int count;
main(){
int i;
void perm(int k);
while(1){
scanf("%d",&n); if(n<=0){break;}
for(i=1;i<=n;i++){p[i]=i;}
count=0;
perm(1);
}
}
void perm(int k){
int i,w;
if(k>n){
count++;
for(i=1;i<=n;i++){a[i]=p[i];}
for(i=1;i<=n;i++){a[i+a[i]+1]=a[i];}
printf("[%d]:",count);
for(i=1;i<=2*n;i++){printf("%3d",a[i]);} printf("\n");
}
else{
for(i=k;i<=n;i++){
w=p[k];p[k]=p[i];p[i]=w;
perm(k+1);
w=p[k];p[k]=p[i];p[i]=w;
}
}
}
No.11ベストアンサー
- 回答日時:
★追記。
・調べる組み合わせの数式は『(n*2-2)P(n)』です。
4つでは、6P4=6×5×4×3=360通り
5つでは、8P5=8×7×6×5×4=6,720通り
6つでは、10P6=10×9×8×7×6×5=151,200通り
7つでは、12P7=12×11×10×9×8×7×6=3,991,680通り
8つでは、14P8=14×13×12×11×10×9×8×7=121,080,960通り
9つでは、16P9=16×15×14×13×12×11×10×9×8=4,151,347,200通り
※8つまでは計算終了するが、9つは時間がかかりすぎて確認できなかった。
#include <stdio.h>
#include <string.h>
// パズル型
typedef unsigned long puzzle_t;
// 定数
#define OK 1
#define ERR 0
#define SPC 0x20
// 文字列の反転
char *reverse( char buff[] )
{
char *head = buff;
char *tail = buff + strlen(buff) - 1;
char temp[ 1 ];
while ( head < tail ){
temp[ 0 ] = head[ 0 ];
head[ 0 ] = tail[ 0 ];
tail[ 0 ] = temp[ 0 ];
head++;
tail--;
}
return( buff );
}
// 表示文字列の作成
char *make( char buff[], puzzle_t x[], int max, puzzle_t msb )
{
int i;
memset( buff, SPC, BUFSIZ );
buff[ BUFSIZ - 1 ] = '\0';
for ( i = 0 ; i < max ; i++ ){
int no = 0;
do {
if ( x[i] & ((puzzle_t)1 << no) ){
buff[ no ] = (char)(i + '1');
}
} while ( !(msb & ((puzzle_t)1 << no++)) );
buff[ no ] = '\0';
}
return( reverse(buff) );
}
// チェック
int check( puzzle_t x[], int max, puzzle_t ans )
{
puzzle_t check = 0;
int i;
for ( i = 0 ; i < max ; i++ ){
check |= x[ i ];
}
return( (check == ans) ? OK : ERR );
}
// シフト
int shift( puzzle_t x[], int max, puzzle_t msb )
{
int i;
for ( i = 0 ; i < max ; i++ ){
if ( msb & x[i] ){
while ( !(x[i] & (puzzle_t)1) ){
x[i] >>= 1;
}
}
else{
x[i] <<= 1;
return( 1 );
}
}
return( 0 );
}
int main( void )
{
char buff[ BUFSIZ ];
puzzle_t x[ 50 ];
puzzle_t ans;
puzzle_t msb;
int max = 0;
int cnt = 0;
int i, n;
do {
printf( "3~15を入力して下さい:" );
scanf( "%d", &n );
printf( "\n" );
} while ( (n < 3) || (n > 15) );
ans = ~((~(puzzle_t)0) << (n * 2));
msb = ((puzzle_t)1 << (n * 2 - 1));
// ビットイメージの作成
for ( i = 0 ; i < n ; i++ ){
x[ i ] = (((puzzle_t)1 << (i + 2)) | (puzzle_t)1);
}
do {
if ( check(x,n,ans) == OK ){
printf( "%s⇒○\n", make(buff,x,n,msb) );
cnt++;
}
else{
// printf( "%s⇒×\n", make(buff,x,n,msb) );
}
max++;
} while ( shift(x,n,msb) );
if ( cnt == 0 ){
printf( "%d通り中、1個も解はなかった。\n", max );
}
else{
printf( "\n%d通り中、%d個の解が見つかった。\n", max, cnt );
}
return( 0 );
}
No.14
- 回答日時:
失礼、記述ミスをしてしまいました。
>1番目の要素の左の値
>1番目の要素の右の値
>2番目の要素の左の値
>2番目の要素の左の値
>……
ではなく
1番目の要素の左の値
1番目の要素の右の値
2番目の要素の左の値
2番目の要素の右の値
……
要は、順番に左、右、左、右、…ということです。
No.13
- 回答日時:
今までは左側の数字を一通り格納し終えてから右側の数字の構築を行っていましたが、
同時に行ってしまえば、総当たりでも N! 通りで済みますね。
まず、左側の数字 {1~N} の並び順を決定 (順列なので N! 通りの並べ方がある)し、
それを 2N の配列(0初期化しておく)の左から順に格納していきますが、
1番目の要素の左の値
1番目の要素の右の値
2番目の要素の左の値
2番目の要素の左の値
……
の順に繰り返すわけです。
ここで、左の値を格納しようとしたときにすでに別の値が入っていた場合には
次の0の位置を探してそこに格納します。
また、右の値を格納しようとしたときに、インデックスが範囲外であるか、
またはすでに別の値が入っていた場合には、その並びは合致しないものと判断し
次の並びの検証に移ります。
ところで、以前示されたリンク先のLangford's Problemのサイトによると、
Nの値は「4の倍数」または「4の倍数より1小さい数」の場合のみ合致する並びが
存在するようなので、N=9では存在しないようですね。
一応私のソースを載せておきます。N!通りの総当たり法なのでもう少し工夫の余地が
あるとは思いますが。
楽をするためSTL(C++のライブラリ)の next_permutation (順列の生成)や find を
使っているので注意。(でもSTLのコンテナは使っていなかったりと中途半端ですが。)
解の数から言っても、計算が終わるのを待っていられるのはせいぜいN=11が限度で
N=12になると延々と終わらず続くことになります。
(N=11でも解をファイルに書き出せばの話で、直接DOS画面に表示させるとそれだけで
相当遅くなるので注意。)
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// 配列の表示関数
void PrintSequence(int *seq, int seqCount)
{
for (int i=0; i<seqCount; i++) {
cout << seq[i] << ' ';
}
cout << endl;
}
int main()
{
int fig[] = {1,2,3,4,5,6,7,8};
const int count = sizeof(fig)/sizeof(fig[0]);
// next_permutation で使用するためあらかじめ昇順ソートしておく
sort(fig, fig+count);
// fig[] の順列並び替えをすべての場合について繰り返す
int totalCount = 0;
int matchedCount = 0;
do {
int seq[count * 2] = {0};
int seqIdxL = 0;
bool errorFound = false;
// seq[] の左から順に埋めていく(すでに値が入ってるときは次の 0 の位置)
for (int figIdx=0; figIdx < count; figIdx++) {
// 現在の値の左側の位置決め (現在位置以降にある 0 の位置を探す)
seqIdxL = distance( seq, find(seq+seqIdxL, seq+count*2, 0) );
seq[seqIdxL] = fig[figIdx];
// 右側位置決め(範囲外かすでに別の値が格納されている場合は飛ばす)
int seqIdxR = seqIdxL + fig[figIdx] + 1;
if (seqIdxR >= count * 2 || seq[seqIdxR] != 0) {
errorFound = true;
break;
}
// 右側位置に格納
seq[seqIdxR] = fig[figIdx];
}
// エラーなく終了(ルールに合致)した場合は表示
if (!errorFound) {
PrintSequence(seq, count*2);
matchedCount++;
}
totalCount++;
} while (next_permutation(fig, fig+count));
// 数を表示
cout << "Total Count : " << totalCount << endl;
cout << "Matched Count : " << matchedCount << endl;
return 0;
}
No.12
- 回答日時:
★改良版。
・改良版は次の2つの場所を修正します。
(1)make 関数の
編集前⇒buff[ no ] = (char)(i + '1');
編集後⇒buff[ no ] = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[ i ];
(2)shift 関数を下のものにします。また、check2 関数が追加です。
// チェック2
int check2( puzzle_t x[], int max, puzzle_t value )
{
int i;
for ( i = 0 ; i < max ; i++ ){
if ( x[i] & value ){
return( 1 );
}
}
return( 0 );
}
// シフト
int shift( puzzle_t x[], int max, puzzle_t msb )
{
int i;
for ( i = 0 ; i < max ; i++ ){
do {
if ( msb & x[i] ){
goto Jump;
}
x[i] <<= 1;
} while ( check2(&x[i + 1],(max - (i + 1)),x[i]) );
return( 1 );
Jump:
while ( !(x[i] & (puzzle_t)1) ){
x[i] >>= 1;
}
}
return( 0 );
}
最後に:
・改良版では少し高速になりましたので、11個まで確認できました。
下にその実行結果を載せます。
3つでは、5通り中、2個の解が見つかった。
4つでは、21通り中、2個の解が見つかった。
5つでは、103通り中、1個も解はなかった。
6つでは、643通り中、1個も解はなかった。
7つでは、4454通り中、52個の解が見つかった。
8つでは、34102通り中、300個の解が見つかった。
9つでは、288123通り中、1個も解はなかった。
10つでは、2641255通り中、1個も解はなかった。
11つでは、26234319通り中、35584個の解が見つかった。
・アルゴリズムを変えたため、表示される組み合わせ数も変化したようです。
アルゴリズムをもうちょっと工夫すれば、もっと高速になりそうだ!多分。
・以上。おわり。
回答ありがとうございます。
たくさん回答ならびにソースまで示して頂き正直驚きました。
ビット・イメージを利用しているところはなるほどと思いました。
総当りで解決するには相当な計算量がいるので、時間が計り知れませんが、この方法は計算量な格段に少なくてすみますね。
実は、私が質問してから、順列を配列に入れ、その配列を別の配列上で操作し、何とか組合せを出力できるものを作りました。
しかし、Oh-Orangeさんのお考えになったアルゴリズムは、数字を並べるという行為をより自然な形で表現されているとお見受けしました。
私のような初心者からするとOh-Orangeさんのプログラミングは高度なものに感じます。それゆえ勉強になるところが多々ありました。
やはり、発想の転換をして、別のアプローチに挑戦することが勉強なのだと感じました。
幾度ものご教授ありがとうございました。
No.10
- 回答日時:
★アルゴリズム
・4つの場合はビット・イメージを利用して、
400004⇒100001
30003⇒10001
2002⇒1001
101⇒101
と考える。
・上のビット値を OR して 11111111 になる値がルールと合致する『解』です。
組み合わせは、101、1001、10001、100001 を順番に1ビットずつシフトして求める。
総当りするよりは、少ない回数で求まります。
・101 は 101、1010、10100、101000、1010000、10100000 の6組
2002 は 1001、10010、100100、1001000、10010000の5組
30003 は 10001、100010、1000100、10001000 の4組
400004 は 100001、1000010、10000100 の3組となり
組み合わせは、6×5×4×3=360通り。
・5つの場合は、5000005 のビットイメージ 1000001 が1つ増える。
組み合わせは、8×7×6×5×4=6720通り。
・6つの場合は、60000006 のビットイメージ 10000001 が1つ増える。
組み合わせは、10×9×8×7×6×5=151200通り。
となります。
・unsigned long型で処理しているので 32Bit÷2=16、さらに1つ引くので 1~15 まで
処理できる。ただし、for 文のネストを1つずつ増やす必要がある。
ここを工夫すれば for 文をネストしないでも処理できそうです。
・以上。参考に。
No.9
- 回答日時:
#include <stdio.h>
#include <string.h>
// 定数
#define OK 1
#define ERR 0
#define SPC 0x20
// 文字列の反転
char *reverse( char buff[] )
{
char *head = buff;
char *tail = buff + strlen(buff) - 1;
char temp[ 1 ];
while ( head < tail ){
temp[ 0 ] = head[ 0 ];
head[ 0 ] = tail[ 0 ];
tail[ 0 ] = temp[ 0 ];
head++;
tail--;
}
return( buff );
}
// 表示
void print( unsigned long x[], int max, unsigned long msb )
{
char buff[ 33 ] = { 0 };
unsigned long bit;
int i, no;
memset( buff, SPC, sizeof(buff) );
buff[ sizeof(buff) - 1 ] = '\0';
for ( i = 0 ; i < max ; i++ ){
for ( no = 0, bit = 1 ; msb > bit ; bit <<= 1, no++ ){
if ( x[i] & bit ){
buff[ no ] = (char)(i + '1');
}
}
}
printf( "%s", reverse(buff) );
}
// チェック
int check( unsigned long x[], int max, unsigned long ans )
{
unsigned long check = 0;
int i;
for ( i = 0 ; i < max ; i++ ){
check |= x[ i ];
}
return( (check == ans) ? OK : ERR );
}
int main( void )
{
unsigned long msb = 0377 + 1;
unsigned long ans = 0377;
unsigned long x[ 4 ];
unsigned long a[ 4 ] = {
005,
011,
021,
041,
};
int max = 0;
int cnt = 0;
for ( x[3] = a[3] ; msb > x[3] ; x[3] <<=1 ){
for ( x[2] = a[2] ; msb > x[2] ; x[2] <<=1 ){
for ( x[1] = a[1] ; msb > x[1] ; x[1] <<=1 ){
for ( x[0] = a[0] ; msb > x[0] ; x[0] <<=1 ){
if ( check(x,4,ans) == OK ){
print( x, 4, msb );
printf( "⇒○\n" );
cnt++;
}
else{
/*
print( x, 4, msb );
printf( "⇒×\n" );
*/
}
max++;
}
}
}
}
printf( "%d通り中、%d個見つけた。\n", max, cnt );
return( 0 );
}
No.8
- 回答日時:
1103yさんが示したリンク先のLangford's Problemを見てみましたが、どうやら
数字の列を前半/後半に分けて考えるというものではないようですね。
「1~Nまでをそれぞれ2個ずつ含み、1と1の間に1個の数、2と2の間に2個の数、…
となるように配置された数字の列」のことのようです。
さらには、今回は2つずつのみですが、それぞれの数字が3つずつ(triplets)や
4つずつ(quadruple)なんてものも存在するようで。
となると、今までルールそのものを誤解していたようなので、別のアプローチが
必要です。
再び総当たりの方法を考えるとすると、
a[18] = {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9};
を並び替え、すべての場合について条件に適合しているか調べることになりますが、
この場合の並び替えのパターンは
(18の階乗)÷(2の9乗)=約12兆5000万通り
となるので、単純な並べ替えの総当たりはやめておいたほうがよさそう。
代わりに、それぞれの数字の位置インデックス持つ配列を考える方法なども考えられます。
配列posL[]に、各々の「左側にある方の数字」の位置インデックスを持たせるとします。
posL[0]=(左側にある数字1の位置インデックス)
posL[1]=(左側にある数字2の位置インデックス)
…
posL[N-1]=(左側にある数字Nの位置インデックス)
posL[0]~posL[N-1]の値が「0~(2N-1)までの数字からN個取り出す場合の順列の並び」と
なるように格納します。この場合、それぞれについて右側の数字のインデックスを
(右側インデックス)=(左側インデックス)+(要素の値)+1
で求めてposR[]に代入します。
posR[0]=posL[0]+1+1
posR[1]=posL[1]+2+1
…
posR[N-1]=posL[N-1]+N+1
この場合も、右側インデックスposR[]の構築中に、それまでに確定している要素との
衝突がないかどうかの判定をしていくことになります。
ただし、この方法でも、単純な総当たりで行っていく場合には、posL[]の並び替えで
(18の階乗)÷(9の階乗)=176億通り
のパターンがあるので、もっとパターンを絞り込む工夫が必要です。
この問題の解法については、リンク先からたどれるWebページや
関連する論文など参照してみたほうがよさそうです(英語ばかりのようですが)。
度重なるご回答ありがとうございます。
posL[] と posR[] をそれぞれ用意し、組み合わせるということでしょうか。
あと、C言語ではなく、perl言語ですが、このアルゴリズムを別の方法で実現させている方のサイトを見つけました。
http://www12.ocn.ne.jp/~kumo/kazunosa.html
しかし、これは別の方法で、且つperlはよく分かりませんので参考です。
No.7
- 回答日時:
もしかして、N=4以上の場合は「ルールを満たす並びは存在しない」だったりしませんかね。
N=4~10の場合について前半部分の順列の並び総当たりで調べてみても見つからないし、
N=4での24通りの並びについて、実際に全部書き出してみてもルールに該当しそうな
ものが見つからないんですが。
この回答への補足
回答ありがとうございます。
考えてみましたが、確かにそうかもしれません。
私の考えが間違っていたかもしれません。
と言うのは、tea_sheepさんのおっしゃるように、全ての順列を前半部分に列挙しても、3までしか順列には合致しないのかも知れません。
とすると、n=4の場合
23421314 と反転の 41312432
の2つを見つけ出すプログラムにしなければならないかもしれません。
http://www.wschnei.de/digit-related-numbers/lang …
http://mathworld.wolfram.com/LangfordsProblem.html
上のリンクはラングフォードの問題というものです。
但し、出題者には今まで考えてきた順列からチェックするというやり方を示されたような気がするのですが・・・
もしもソースをお考えでしたら参考までに拝見させて頂けるとありがたいです。
お手数お掛けしてすいません。
No.6
- 回答日時:
今回の問題の場合、前半部分の並びを決めると、後半部分については
ルールに合致する並びが「存在しない」か「1通りだけ存在する」かの
どちらかとなります。
そこで、それぞれの前半部分の並びについて、ルールに合致する後半部分が
存在するものと仮定して、前半部分の並びを元に、後半部分の並びを各要素
ごとに順に構築していきます。
その構築の途中で、何らかの矛盾(後半部分の配列インデックスが範囲外に
なったていたり、すでに別の要素がその位置に入っている)が生じた場合には
「存在しない」方だったと判断して、次の並びの検証に移ります。
手順としては1~3の場合、
(1)後半をゼロ埋めしておく
a[] = {3, 1, 2, 0, 0, 0};
(2)最初の要素(a[0]=3)の、後半部分におけるインデックスを決定
(後半インデックス)=(前半インデックス)+(要素の値)+1
なので、a[0]の後半でのインデックスは 0+3+1=4
(3)インデックスが後半部分の範囲内にあることを確認
この場合は 3~5 であること。4なので問題なし。
(4)後半インデックスの位置にすでに他の値が格納されていない(0である)ことを
確認して、値を格納する。
最初の要素なので問題なし
{3, 1, 2, 0, 3, 0} ← a[4]=3
(5)次の要素(a[1]=1)について (2)~(4) を実行
後半インデックス=1+1+1=3
{3, 1, 2, 1, 3, 0} ← a[3]=1
(6)最後の要素(a[2]=2) について (2)~(4) を実行
後半インデックス=2+2+1=5
{3, 1, 2, 1, 3, 2} ← a[5]=2
で完了。上記の(2)~(4)を前半部分の各要素について繰り返せばよいです。
上記例では(3),(4)のチェックで引っかかることなく後半部分を構築できたので
この並びがルールを満たしていることになります。
他の例として、{1,3,2,0,0,0}から開始すると、最初の要素 a[0]=1 に対する
後半部インデックスの範囲チェック(2)に引っかかるので、この並びは×。
別の例では、{3,2,1,0,0,0}だと、2つ目の要素 a[1]=2 の(4)のチェックにおいて
すでに別の値(a[0)が格納先(a[4])に入っているため、この並びも×。
再びのご回答ありがとうございます。
tea_sheepさんご指摘のように、(3)&(4)のチェックが重要になりますね。
特に、後半部は0に初期化されているので、(4)の時に、0がある場合にのみ値を代入するということですね。
No.5
- 回答日時:
よくよく考えたら、わざわざ後半部分の並びを作り出さなくても、
前半部分の各要素の値と位置からルールにマッチしているかどうかの
判定が可能でしたね。
それぞれの要素について、値と位置から後半部分における位置を計算し、
それが他の要素のものと重なっていなければOKという形で。
それなら、9!=約36万通りについて調べればいいので、まあ総当たりでも
何とかならないこともないですが。
回答ありがとうございます。
なるほど、あまり計算量を考えずやっていました。
前半部分からマッチしているかどうか判定するということですね
私も質問時から考えて来ましたが、前半部から一つずつルールに当てはめて、後半部分においていくというものを作りました。
やはり、ルールにあっているかどうかの判定が良く分かりません。
今考えているのは、例えばn=3の時
312132 を作ったとして、前半部 a[0] の値(3)が
後半部a[3] a[4]a[5]のどれかに入っていたとき、カウンタを設けて、カウンタに+1足す。
同様にa[1] a[2]についても後半部と比較します。
すると3つの数字が全部見つかった場合は、カウンタは3になります。
n=3なので、n==カウンタ となればルールと完全一致となり、出力するというものを作りましたが・・・3の場合は出来ますが4からがうまく行きませんでした。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) 十進BASICでの再帰についての質問です。 2 2022/11/18 09:17
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- C言語・C++・C# c言語配列の結合についてです。 なぜうまくいかないのでしょうか。 #include <stdio.h 4 2022/05/30 22:42
- C言語・C++・C# C言語 3 2022/11/09 13:27
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# 10人分の生徒の英語の点数{32,34,41,38,40,26,14,46,42,50} と数学の点 2 2022/05/26 21:31
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「指定されたキャストは有効で...
-
複数桁10進数の*桁目だけを抽出...
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語での引数の省略方法
-
【C++】関数ポインタの使い方
-
比較回数と交換回数表示について
-
C言語で三目並べをするプログラ...
-
if と配列の組み合わせ
-
商と剰余を同時に求める(C言語)
-
C言語での奇数の和
-
ラップ関数とはどんなものですか?
-
Arduinoのプログラムにエラーが...
-
C言語
-
並列プログラミングのπ計算につ...
-
C言語 エラーの原因がわからな...
-
インライン展開されているか確...
-
GlobalAllocの変数を関数に引き...
-
HANDLEて何ですか?
-
read関数をノンブロッキングで...
-
C++でvectorにテキストファイル...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
「指定されたキャストは有効で...
-
C言語 配列と関数の練習問題
-
複数桁10進数の*桁目だけを抽出...
-
(int *)の意味
-
if と配列の組み合わせ
-
ラップ関数とはどんなものですか?
-
卒業研究でよく分からないとこ...
-
【C++】関数ポインタの使い方
-
c言語
-
足して100になるような乱数のア...
-
C言語初心者です、、、お助けく...
-
数字列を3桁ごとにカンマで区切...
-
C言語 エラーの原因がわからな...
-
実数の整数部,小数部の取得
-
課題でつまってます・・・
-
商と剰余を同時に求める(C言語)
-
C言語の配列をC++のvectorに高...
-
std::set<int> で、ある値が何...
おすすめ情報