8-2-19.c

2005软件工程师考试下午编程题源代码

/*中国系统分析员顾问团，http://www.csai.cn*/
/*程序员下午考试指南书籍源码*/

#include <stdio.h>
#define N 200
#define M 200
#define  Limit 2000

struct { 
int id; int k;
} way[Limit];    /*存储每次移动的位置和薄片张数 */

int mc = 0;    /*移动次数 */
int c[N], a[N], n;

int init( int *np, int *c, int *a ) {   /* 输入初始数据，估算ai */
int i, n, d, min, v; long sum = 0L;
printf ("输入n:"); scanf ("%d",&n); printf ("输入各堆的薄片数(<%d)\n", M);
for (i = 0; i < n; i++){
scanf ( "%d",&d); 
c[i] = ( d >= 0 && d < M) ? d : 0;
}
for (i = 0; i < n; i++) sum += c[i];
if (sum % n) return 0;
v = (int)(sum / n); a[0] = 0; a[1] = v - c[0];
for (i = 1; i <n-1; i++) a[i+1] = v + 2*a[i]-a[i-1] -c[i];
for (min = 0, i = 1; i < n; i++) if (a[i] < min) min = a[i];
for (i = 0; i < n; i++) a[i] -= min;
*np = n; return 1;
}

void move (int i, int k, int n, int *c, int *a){
if (i > 0) { 
c[i-1] += k;
c[i] -= k;
}
if (i < n-1) {
c[i+1] += k;
c[i] -= k;
}
a[i] -= k; way[mc].id = i; way[mc++].k = k;
}

void search(int *c, int *a, int n) {
int i, k, m, pov, moved;
do {
pov = moved = 0;
for (i = 0; i < n; i++)    /*搜索满足策略(1)的堆*/
if (a[i] > 0 ) { 
pov = 1;
if (( i==0 || i==n-1 )?(c[i]>=a[i]) : (c[i] >= 2*a[i])) {
move( i, a[i], n, c, a );   /*完成一次移动*/
moved = 1; break;
}
}
if ( pov && !moved) {  /*找薄片数最多的堆，且被相邻堆全部取走*/
for (m = 0, i = 0; i < n; i++)
if (a[i] > 0 && c[i] > m ) {
k = i; m = c[i]; 
}
if (k > 0 && k < n-1) m /= 2 ;  move (k, m, n, c, a);
}
} while (mc < Limit && pov);
}

void main(){
int i;
if (init(&n, c, a) == 0 ) { 
printf("薄片总数不能被平分\n"); return;
}
search(c, a, n); printf(" 序号 移动位置号 各相邻位置得到薄片数\n");
for (i = 0; i < mc; i++)
printf("%4d%10d%18d\n", i+1, way[i].id, way[i].k);
printf("\n");
}