1405.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 

      #include <stdio.h>
      #include <string.h>

      #define base 10000 /* the base must be 10000 */
      #define MAX 10000

      typedef struct hp
      {
      	int list[MAX];
      	int len;
      }hp;

      /*
       *c = a + b
       */
      hp *hp_add(hp *a,hp *b,hp *c)
      {
      	int i;
      	memset(c->list,0,MAX);
      	for(i = 0;i < a->len || i < b->len;i++)
      		c->list[i] = a->list[i] + b->list[i];
      	for(i = 0;i < a->len || i < b->len;i++){
      		c->list[i + 1] += c->list[i] / base;
      		c->list[i] %= base;
      	}
      	c->len = a->len > b->len ? a->len : b->len;
      	if(c->list[c->len] > 0) c->len++;
      	return c;
      }

      /*c = a * b*/
      hp *hp_mul(hp *a,hp *b,hp *c)
      {
      	int i,j;
      	memset(c,0,sizeof(hp));
      	for(i = 0;i < a->len;i++)
      		for(j = 0;j < b->len;j++){
      			c->list[i + j] += a->list[i] * b->list[j];
      			c->list[i + j + 1] += c->list[i + j] / base;
      			c->list[i + j] %= base;
      	}
      	for(i = 0;i < a->len + b->len;i++){
      		c->list[i + 1] += c->list[i] / base;
      		c->list[i] %= base;
      	}
      	c->len = a->len + b->len;
      	while(c->len > 1 && c->list[c->len - 1] == 0)c->len--;
      	return c;
      }

      			

      hp * hp_write(hp * x)
      {
      	int i,t;
      	printf("%d",x->list[x->len - 1]);
      	for(i = x->len - 2;i >= 0;i--)
      	{
      		t = x->list[i];
      		if(base != 10000) printf("error");
      		if(t < 1000)printf("0");
      		if(t < 100)printf("0");
      		if(t < 10)printf("0");
      		printf("%d",t);
      	}
      	return x;
      }


hp a[18], one;
hp mem[2],*p1=mem,*p2=mem+1, *temp;

int main()
{
	int i, n, j;

	a[0].len = 1; a[0].list[0] = 2;
	a[1].len = 1; a[1].list[0] = 3;
	one.len = 1; one.list[0] = 1;

	scanf( "%d", &n );

	for( i=2; i<n; i++ )
	{
		p1->len = 1; p1->list[0] = 1;
		for( j=0; j<i; j++ )
		{
			hp_mul( a+j, p1, p2 );
			temp = p1;
			p1 = p2;
			p2 = temp;
		}
		hp_add( p1, &one, p2 );
		a[i] = *p2;
	}

	for( i=0; i<n; i++ )
	{
		hp_write( a+i );
		printf( "\n" );
	}

	return 0;
}