時計盤問題・考察（３）

　時計盤問題・考察（３）を示す。

　配置によって、T(n)の値は変化するが、最小値とその配置をすべて求めるプログラムを示す。

/* << tokei.c >> */
/* 時計盤問題。*/
#include <stdio.h>
#define N 99  /* nの最大値。*/
int count,    /* 解の個数。*/
    max[N+3], /* max[k]：p[1]からp[k]までの要素に対して、
                 隣接する3つの要素の和の中の最大値。*/
    min,      /* 配置の値の最小値。*/
    n,        /* 要素の個数。*/
    p[N+1];   /* 生成される順列。p[1]=1を固定。*/
void perm(int k);

int main() {
  int i;

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

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

    perm(2);
    printf("n=%d count=%d\n",n,count);
  }
}

/* 順列生成を基に、すべての配置を求める。*/
void perm(int k) {
  int i,w;

  if( k > n ) {
    /* p[2]<p[n] を満たさない場合、戻る。*/
    if( p[2] >= p[n] ) { return; }

    /* 3つの要素の和p[n-1]+p[n]+p[1]について、調べる。*/
    w = p[n-1]+p[n]+p[1];
    if( w > max[n] ) {
      max[n+1] = w;
    } else {
      max[n+1] = max[n];
    }

    /* 3つの要素の和p[n]+p[1]+p[2]について、調べる。*/
    w = p[n]+p[1]+p[2];
    if( w > max[n+1] ) {
      max[n+2] = w;
    } else {
      max[n+2] = max[n];
    }

    /* 最小値minの更新。*/
    if( max[n+2] < min ) { 
      min = max[n+2]; count = 0;
    }

    /* 現在までの最小値minを満たす配置を表示。*/
    if( max[n+2] <= min ) {
      count++; 
      printf("%5d %5d:",min,count);
      for( i=1; i<=n; i++ ) { printf("%d ",p[i]); }
      printf("\n");
    }
    return;
  }
 
  for( i=k; i<=n; i++ ) {                  
    w = p[k]; p[k] = p[i]; p[i] = w;       
    /* max[k]の更新。*/
    if( k < 3 ) {                          
      max[k] = 0;                          
      perm(k+1);                           
    } else {                               
      w = p[k-2]+p[k-1]+p[k];              
      if( w > max[k-1] ) {                 
        max[k] = w;                        
      } else {                             
        max[k] = max[k-1];                 
      }                                    
      /* max[k]がmin以下の場合、要素p[k+1]の確定に進み、
         minを超える場合、要素p[k]の更新に進む。*/
      if( max[k] <= min ) { perm(k+1); }   
    }                                      
    w = p[k]; p[k] = p[i]; p[i] = w;       
  }                                        
}

実行結果

（参考）