gc_8_7_longint.c

gc:高级程序员考试用书的c程序源文件

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

int Factor(int N)         //我添加的,以验证自己的程序是否正确
{
	if (N <= 1) return 1;            /*递归结束条件*/
	else return N*Factor(N-1);       /*递归执行部分*/
}


/*函数,输入长整数函数,将长整数存于数组a,并返回该长整数的位数*/
#define MAXN 400
int readMaxInt(int *a)
{
	int len,i;
	char s[MAXN];
	printf("Inter long integer:\n");
	scanf("%s",s);
	len = strlen(s);
	for (i = len; i>= 1; i--)
		a[i] = s[len-i] - '0';
	return a[0] = len;
}


/*函数,输出长整数函数*/
void writeMaxInt(int *a)
{
	int i;
	for (i = *a; i>=1;i--)
		printf("%d",a[i]);
	//printf("\n");
}



/*函数,长整数规整函数*/
int formal(int *a)
{
	int p;
	for(p = 1;p < a[0] || a[p] >= 10; p++) {
		if(p >= a[0]) a[p+1] = 0;
		a[p+1] += a[p]/10;
		a[p] = a[p]%10;
	}
	if (p>a[0]) a[0] = p;
	return a[0];
}



/*函数,长整数除以普通整数函数*/
/*将存于a中的长整数除以普通整数j,并将商存于a中,函数返回整除后的余数*/
int divInt(int *a,int j)
{
	int p,k;
	k = p = a[0]; a[0] = 0;
	while (p > 0) {
		a[p-1] += a[p]%j*10;
		a[p] = a[p]/j;
		if (a[k] == 0) k--;
		p--;
	}
	p = a[0]/10;
	a[0] = k;     //这才是正确的位数
	formal(a);
	return p;     //返回余数
}



/*函数,将长整数转换成二进制长整数函数*/
/*该函数将存于a中的长整数转换为二进制,并存于整数数组b中,采用除2取余法,转换,即用2不断去除*/
/*待转换的十进制数,直至商为0为止,以最后余数为最高位,将所得各次余数依次排列存储*/
void dec2bin(int *a,int *b)
{
	int p;
	b[0] = 0;
	while (a[0] > 0) {          /*用2不断去除待转换的十进制数直至商为0为止*/
		b[0]++;
		b[b[0]] = a[1]%2;         /*一个余数 了,然后求商*/
		p = a[0];
		while (p>0) {     /*对a执行除2运算*/
			if(a[p]%2 && p>1) a[p-1] += 10;
			a[p] /= 2;
			if (a[a[0]] == 0) a[0]--;
			p--;
		}
	}
}


/*函数,计算普通整数的组合函数*/
/*两个普通整数的组合数,可能是一个大整数,为此两整数的组合用长整数存储.........
本例子的两个整数的组合是c(a,b) = a! / ((a-b)!)                                */

int gcd(int M,int N)   /*求最大公因子函数*/
{
	if (N == 0) return M;
	else return gcd(N,M%N);
}



void combine(int a,int b,int *c)
{
	int i,j,x,k;
	int d[MAXN],u[MAXN];
	for (k = 0,i = a;i >= a-b+1;i--) u[++k] = i;
	u[0] = k;
	for(i = 1;i <= b; i++) d[i] = i;
	for(i = 1;i <= u[0];i++)
		if(u[i] != 1)
			for(j = 1;j <= b;j++)
				if(d[j] != 1 && u[i] != 1) {
					x = gcd(u[i],d[j]);
					u[i] /= x;d[j] /=x;
				}

	for(c[0] = c[1] = i = 1;i <= u[0];i++)
		if(u[i] != 1) {
			for(j = 1;j <= c[0]; j++)
				c[j] = c[j] * u[i];
			formal(c);
		}
}

/*函数,求两长整数和的函数*/
void add(int *a,int *b)
{
	int i;

	while(a[0] < b[0])        /*如果b的位数多,在a的首部添0*/
		a[++a[0]] = 0;
	for(i=1;i<=b[0];i++)
		a[i] += b[i];
	formal(a);
}



/*主函数*/
void main()
{
	int k;    //除数
	int y;   //余数
	int a[MAXN];
	int b[MAXN];
	int c[MAXN];      /*求组合函数时定义的存储结果的数组*/
	int a1; int b1;    /*求组合函数时的两个整数*/
	int aj,bj,cj;      /*a!,b!,(a-b)!的值存储在这三个变量里,验证一下结果而已*/
	int x;  /*选项值,如果输入字符选项值,好像回车也算,不好处理,总是当输入了两个字符,所以这里用
			用整型选项,我想,如果选项用字符值,那么字符的循环是用while(1),里面输入打断的条件吗?*/

	int d[MAXN],e[MAXN]; /*求两长整数和所用到的两个数组,要求输入两个长整数*/

	printf("1,输入长整数函数\n");
	printf("2,输出长整数函数\n");
	printf("3,长整数规整函数\n");
	printf("4,长整数除以普通整数函数\n");
	printf("5,将长整数转换成二进制长整数函数\n");
	printf("6,计算普通整数的组合函数\n");
	printf("7,求两长整数和函数\n");
	printf("0,退出程序");
	printf("\n");
	printf("\n请输入一个选项,输入0退出\n");
	scanf("%d",&x);

	while (x!=0) {
		switch (x)
		{

			case 1: readMaxInt(a);printf("%d个\n",a[0]); break;
			case 2:writeMaxInt(a); printf("\n"); break;
			case 3:formal(a);printf("规整了一次\n"); break;
			case 4:
				printf("输入除数\n");
				scanf("%d",&k);
				printf("被除数\n");
				writeMaxInt(a);
			    y=divInt(a,k);
				printf("除数:%d \n",k);
				printf("商\n");
				writeMaxInt(a);
				printf("余数:%d\n",y);
				break;
			case 5:dec2bin(a,b); printf("转换后的数值如下:\n"); writeMaxInt(b); break;
			case 6:
				//int a;
			    //int b;
				//int c[MAXN];
				printf("请输入第一个整数a\n");
				scanf("%d",&a1);
				printf("请输入第二个整数b\n");
				scanf("%d",&b1);
				combine(a1,b1,c);
				printf("她们的组合(c(a,b)=a!/((a-b)!b!)如下: \n");
				writeMaxInt(c);
				printf("验证一下看看,较好的方法是用长整数存储这几个阶乘,不然数值大了,计算错误,以后改\n");
				aj=Factor(a1);
				printf("a!=%d\n",aj);
				bj=Factor(b1);
				printf("b!=%d\n",bj);
				cj=Factor(a1-b1);
				printf("a1-b1=%d\t",a1-b1);
				printf("%d!=%d\n",a1-b1,cj);
				printf("所以a!/((a-b)!b!)=%d!/((%d!)%d!)=",aj,cj,bj);
				printf("\n%d(整型运算的结果)\n",aj/(cj*bj));//前面一个用长整型存贮的,后面一个是我们用到的长整数数组(正确)
				writeMaxInt(c);printf("(长整数数组运算的结果)\n");
				break;
			case 7:
				{printf("要求输入两个长整数,这两个长整数相加,结果存在第一个长整数数组\n");
				readMaxInt(d);
			    readMaxInt(e);
				printf("你所输入的第一个长整数:\n");
				writeMaxInt(d);
				printf("你所输入的第二个长整数:\n");
				writeMaxInt(e);
				add(d,e);
				printf("\n结果如下,\n");

				writeMaxInt(d);
			   break;}
			   default:break;
		}

		printf("\n\n1,输入长整数函数\n");
		printf("2,输出长整数函数\n");
		printf("3,长整数规整函数\n");
		printf("4,长整数除以普通整数函数\n");
		printf("5,将长整数转换成二进制长整数函数\n");
		printf("6,计算普通整数的组合函数\n");
		printf("7,求两长整数和函数\n");
		printf("0,退出程序");
		//printf("\n");
		printf("\n输入一个选项,输入0退出\n\n");

		scanf("%d",&x);
	}
}