C言語関係掲示板

過去ログ

No.902 同数間隔配置(バックトラック利用)

[戻る] [ホームページ]
No.620

同数間隔配置(バックトラック利用)
投稿者---Vine Linux User(2003/11/07 22:23:15)


どうしてもこの課題が分からないです。
例題から作成などしてみたんですが、仕組みは分かってはいるんですが、
プログラムでどうやって書いたらいいか分かりません。
どなたか教えてくださる方いましたらお願いします。
<課題>
1〜nの数が書かれたカードが2枚ずつある。
これらのカードを横1列に並べて、任意の数k(1≦k≦n)についてkと書かれた2枚のカードの間には
k枚のカードがあるようにする。
この条件を満たすすべての並べ方とその総数を求めなさい。
例えば、n = 7 であれば、

1 4 1 5 6 7 4 2 3 5 2 6 3 7
1 4 1 6 7 3 4 5 2 3 6 2 7 5
1 5 1 4 6 7 3 5 4 2 3 6 2 7
:
7 3 1 6 1 3 4 5 7 2 6 4 2 5
7 3 6 2 5 3 2 4 7 6 5 1 4 1
7 4 1 5 1 6 4 3 7 5 2 3 6 2
52 sequences found

と出力されるようなプログラムである。

レポートの実行例には、n = 7,8,9 の場合(出力が多ければ、上の例のように、
最初と最後の数行ずつ)を付ける。

<ヒント>
列のある方向から、1〜nの2つの数を順に置いていく方法を試みる。
既に使用した数を記録する配列、 列中で既に数が置かれた位置を記録する配列をうまく利用する。
#include <stdio.h>

#define MaxCNum  100    /*カード枚数最大値 (カードの数は 1..カード枚数)*/

int unused[MaxCNum+1];  /*使われたか否かの記録*/
int placed[MaxCNum+1];  /*[i]にはi番目(1..)に置かれた数 ([0]には番兵0)*/
int cardnum;            /*カード枚数*/
int seqnum;             /*並べ方の総数*/

void found()
/* 1つの解(placed[1..cardnum])が見つかった:出力する */
{ 
  int i;
 
  seqnum++;
  for(i=1; i<=cardnum*2; i++) 
    printf("%d ", placed[i]);
  printf("\n");
}

void lineup(int no)
/* 列のno番目の数以降を決める */
{ 
  int cd, strt,last;
  
  if(no > cardnum) 
    found();
  else { 
    /*ここからどのようなプログラムを書けばいいのでしょうか?*/
 for(cd=strt; cd<=last; cd++)
      if(unused[cd] ) {
        unused[cd] = 0; 
	placed[cd] = cd;
	placed[cd+2] = cd;
        lineup(no+1);
	unused[cd] = 1;
      }
}
}

int main()
{ 
  int i;
 
  printf("card num ? ");
  scanf("%d", &cardnum);
 
  while(cardnum >= 1 && cardnum <= MaxCNum) {
    for(i=1; i<=cardnum*2; i++) 
      unused[i] = 1;
   
    placed[0] = 0;
    seqnum = 0;
    
    lineup(1);
      
    printf("%d sequences found\n", seqnum);
   
    printf("card num ? "); 
    scanf("%d", &cardnum);
    
}
}


No.626

Re:同数間隔配置(バックトラック利用)
投稿者---すがりん(2003/11/08 18:53:41)


    /*ここからどのようなプログラムを書けばいいのでしょうか?*/
 for(cd=strt; cd<=last; cd++)
      if(unused[cd] ) {
        unused[cd] = 0; 
	placed[cd] = cd;
	placed[cd+2] = cd;
        lineup(no+1);
	unused[cd] = 1;
      }

これは

for(cd = 1; cd <= cardnum; cd++) {
  if(unused[cd] && !placed[no+cd+1] && no + cd + 1 <= cardnum * 2) {
    unused[cd] = 0;
    placed[no] = placed[no+cd+1] = cd;

    lineup(nextblank(no));

    placed[no] = placed[no+cd+1] = 0;
    unused[cd] = 1;
  }
}


ぐらいでしょうね。
  • カードを使ったかどうかの判定のほかに2枚目のカードが置けるかという判定も必要です。
    ※1枚目は置けるものとしています。というか置ける位置を引数で渡してる。
  • というわけでnextblankはnoの直後の、空いている位置(の添字)を返す関数です。空きがなければ全部詰まっていることになりますからそこで再帰終了、と。
    というような関数nextblank(別にほかの名前でもいいです)を自作してください。
  • placed[]の初期化も必要ですね。--> placed[MaxCNum+1] = {0};


#placedの添字を1から始めて<=cardnum*2で判定するのも不自然な気がしますが。。。(普通は 0 〜 < cardnum*2)

No.627

Re:同数間隔配置(バックトラック利用)
投稿者---Vine Linux User(2003/11/08 22:05:17)


お返事ありがとうございます。
すがりんさんのを参考にして作ってみます。
分からなくなるようでしたらまた書き込みたいと思いますが、
その機会には、またよろしくお願いします。

No.629

Re:同数間隔配置(バックトラック利用)
投稿者---Vine Linux User(2003/11/08 23:54:18)


関数nextblankなのですが…
int nextblank(int cnt)
{
  int j; 
  for(j=1; j <= cardnum*2; j++ ){
    if(unused[j] == 0)
      return j;
  }
  return 0;
}  


noの直後の、空いている位置(の添字)を返す関数です。
空きがなければ全部詰まっていることになりますからそこで再帰終了、と。
というすがりんさんの考えを基に作ったつもりなんですが…。
だめみたいです。
unused[] == 1がスペースを使用済で、
unused[] == 0がスペースの空きを表してると思っていると思って
いるんですが、間違いでしょうか!?
あと、再帰終了なんですが、関数nextblankの中に書くのでしょうか?
再帰を終らせるということがよく分からないです。
何か意見をいただけると幸いです。
初心者ですみません。

No.633

Re:同数間隔配置(バックトラック利用)
投稿者---Vine Linux User(2003/11/09 02:05:29)


すがりんさんとかずまさんの考え方を合わせれば、目的のプログラム
を作ることができました。
本当にありがとうございました。

No.632

Re:同数間隔配置(バックトラック利用)
投稿者---かずま(2003/11/09 00:43:10)


面白そうなのでやってみました。
出力の形式が課題の指示に従っていないので、解答とはなりません。
また、速くはありませんから、n = 12 ぐらいまでが限度でしょう。
#include <stdio.h>

#define N  20

int prev[N+1], next[N+1], card[2*N+1], n, count;

void print(void)
{
    int i;
    ++count;
    printf("[%d]", count);
    for (i = 1; i <= 2*n; i++) printf(" %2d", card[i]);
    printf(count <= 4 ? "\n" : "\r");
}

void line(int pos)
{
    if (pos > 2*n)
        print();
    else if (card[pos])
        line(pos+1);
    else {
        int i;
        for (i = next[0]; i != 0 && pos + i + 1 <= n*2; i = next[i])
            if (card[pos + i + 1] == 0) {
                next[prev[i]] = next[i];
                prev[next[i]] = prev[i];
                card[pos + i + 1] = card[pos] = i;
                line(pos+1);
                card[pos + i + 1] = card[pos] = 0;
                next[prev[i]] = i;
                prev[next[i]] = i;
            }
    }
}

int main(void)
{
    while (printf("n: "), scanf("%d", &n) == 1 && n <= N) {
        int i;
        for (i = 0; i < n; i++)
            prev[i+1] = i,  next[i] = i+1;
        prev[0] = n,  next[n] = 0;
        count = 0;
        line(1);
        printf("\n count = %d\n", count);
    }
    return 0;
}