センチュリーパズル問題（２）考察１

　センチュリーパズル問題（１）考察１を示します。

（２）考察１

　1から9までの数を１回ずつ使って帯分数を作り、100を表す方法をすべて求めるプログラムを示す。

●プログラム(century.c)

/* << century.c >> */
/* センチュリーパズル（100以下）*/
#include <stdio.h>
#define N 9   /* 集合{1,2,…,n}の最大個数。*/            
#define M 100 /* 帯分数の最大値。*/
int count,    /* 解の個数。*/
    m,        /* 指定する帯分数の値。*/
    n,        /* 要素数。*/
    p[N+1];   /* 生成される順列。*/
void perm(int k);

int main() {
  int i;

  while( 1 ) {

    /* nの読み込み。*/                         
    scanf("%d",&n);                            
    if( (n <=0 )||(n > N) ) { break; }         

    /* 指定する帯分数の値mの読み込み。*/
    scanf("%d",&m);
    if( (m <= 0)||(m > M) ) { break; }

    /* 初期設定。*/
    for( i=1; i<=n; i++ ) { p[i] = i; }
    count = 0;

    /* 求める帯分数の生成。*/
    perm(1);
    printf("n = %3d m=%3d  count=%5d\n",n,m,count);
  }
}

/* 順列生成の方法を基に、求める帯分数を生成する。*/
void perm(int k) {
  int i,j,
      t,  /* 帯分数の値。*/
      t1, /* 帯分数の整数部分。*/
      t2, /* 帯分数の分子。*/
      t3, /* 帯分数の分母。*/
      w;

  if( k > n ) {

    /* 整数部分t1が1桁の場合、整数部分t1を計算する。*/
    t1 = p[1];

    /* 分子の桁数≧分母の桁数より、jは5から8まで。*/
    for( j=5; j<=8; j++ ) {
      /* 分子t2がj-1桁の場合、分子t2を計算する。*/
      t2 = 0; 
      for( i=2; i<=j; i++ ) { t2 = t2*10 + p[i]; }

      /* 分母t3が9-j桁の場合、分母t3を計算する。*/
      t3 = 0; 
      for( i=j+1; i<=9; i++ ) { t3 = t3*10 + p[i]; }

      /* 帯分数の値tを求める。*/
      t = t1+t2/t3;
      /* 帯分数の値がmを超えた場合、分子/分母の値は、
         増大していくのでループを出る。*/
      if( t > m ) { break; }

      /* 「分子が分母で割りきれる」かつ指定された値mと
　　　　　一致する。*/
      if( (t2%t3 == 0)&&(t1+t2/t3 == m) ) {
        count++;
        printf("[%5d] ",count);
        printf("%d + %d/%d\n",t1,t2,t3);
      }
    }

    /* 整数部分t1が2桁の場合、整数部分t1を計算する。*/
    t1 = p[1]*10+p[2];

    /* 分子の桁数≧分母の桁数より、jは6から8まで。*/
    for( j=6; j<=8; j++ ) {
      /* 分子t2がj-2桁の場合、分子t2を計算する。*/         
      t2 = 0; 
      for( i=3; i<=j; i++ ) { t2 = t2*10 + p[i]; }

      /* 分母t3が9-j桁の場合、分子t3を計算する。*/          
      t3 = 0; 
      for( i=j+1; i<=9; i++ ) { t3 = t3*10 + p[i]; }

      /* 帯分数の値tを求める。*/
      t = t1+t2/t3;
      /* 帯分数の値がmを超えた場合、分子/分母の値は、
         増大していくのでループを出る。*/
      if( t > m ) { break; }

      /* 「分子が分母で割りきれる」かつ指定された値mと 
　　　　　一致する。*/                                   
      if( (t2%t3 == 0)&&(t1+t2/t3 == m) ) {
        count++;
        printf("[%5d] ",count);
        printf("%d + %d/%d\n",t1,t2,t3);
      }

      /* 整数部分t1が3桁以上の場合は、扱わない。*/
    }
    return;
  }

  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;
  }
}