虫食い算・最大値問題（１０）考察

虫食い算・最大値問題（１０）考察を示します。

（１０）考察

　試行錯誤で解を求める方法では、見逃した解があるかもしれないという不安がぬぐえない。安心するには、解の候補をすべて列挙して、チェックするしかないが、手作業では限界がある。プログラムで解く方法を示す。そのためには、集合{1,2,…,9}上の順列をすべて生成することが必要になる。集合{1,2,…,9}上のすべての順列を生成するプログラム（C言語）を紹介する。

/* << perm.c >> */
/* 集合{1,2,…,9}上の順列をすべて生成する。*/
#include <stdio.h>
int a[10], /* 順列を保存する配列。*/   
    count; /* 順列の個数。*/  
void perm(int k);

int main() {                         
  int i;   

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

  /* 順列の生成。*/
  perm(1);
}

/* 順列を生成する再帰関数。*/
void perm(int k) { 
  int i,w;                                             

  if( k > 9 ) {                                        
    /* 順列の表示。*/
    count++; printf("%8d: ",count);                    
    for( i=1; i<=9; i++ ) { printf("%2d",a[i]); }
    printf("\n");
    return;
  } 
    
  for( i=k; i<=9; i++ ) {                            
    /* 交換。*/
    w = a[k]; a[k] = a[i]; a[i] = w;                 
    perm(k+1); 
    /* 交換を戻す。*/                                
    w = a[k]; a[k] = a[i]; a[i] = w;            
  }                                                    
}

実行結果

　問題（４）を解くプログラムを示す。

/* << mondai4.c >> */
/* 問題（４）を解くプログラム。*/
#include <stdio.h>
int a[10], /* 順列を保存する配列。*/   
    maxv;  /* 求める最大値。*/
void perm(int k);

int main() {                         
  int i;   

  /* 初期設定。*/
  for( i=1; i<=9; i++ ) { a[i] = i; }
  maxv = 0;

  /* 順列の生成。*/
  perm(1);
}

/* 順列を生成する再帰関数。*/
void perm(int k) { 
  int i,v,v1,v2,w;

  if( k > 9 ) {                                        
    v1=1000*a[1]+100*a[2]+10*a[3]+a[4];
    v2=10000*a[5]+1000*a[6]+100*a[7]+10*a[8]+a[9];
    v=v1*v2;
    if( v > maxv ) {
      maxv = v;
      /* 更新された最大値の表示。*/
      printf("%4d×%5d = %9d\n",v1,v2,v);
    }
    return;
  } 
    
  for( i=k; i<=9; i++ ) {                            
    /* 交換。*/
    w = a[k]; a[k] = a[i]; a[i] = w;                 
    perm(k+1); 
    /* 交換を戻す。*/                                
    w = a[k]; a[k] = a[i]; a[i] = w;            
  }                                                    
}