编程小技巧

    返回首页    发表留言
本文作者:李德强
          技巧二十四:1000的阶乘
 
 

        今天跟大家分享的小技巧是关于大数求阶乘的。在前面文章中我们提到过使用递归来计算n的阶乘的累加和,有很多朋友对求阶乘这个问题很是困惑,认为当n很大时,用于计算并存储结果的变量就已经溢出了,所以求阶乘也就成了一个值得讨论的问题。现在我们就来针对求阶乘问题跟大家分享一下这个小技巧,如何来计算一个很大数的阶乘,如何来存储一个具有很多位的整数。

        我们知道在无论是在C语言中,还是C++,还是Java中整型变量的存储空间都是有限的,通常是4个字节,或是8个字节,如果是超长型整数可能有16个字节,虽然这些整型变量的字节数很多,但能够存放的整数位也是有限的。如果我们想要计算1000的阶乘,结果已经超过了2000位整数,16个字节的变量是无法存储这样庞大的数的,所以我们需要想一个办法,能让我们的变量存放这样多位数的整数。

        普通变量的存储空间不足以存放这么多位的整数,但我们可以采用另种变通的方式来存储它们,比如采用字符串的方式来存储整数,向系统申请一个4000个字节的内存空间,每一个字节用于存放一个0~9的数字,这样就可以表示4000位的整数了,而为了与人们日常读数的习惯,数字通常都是从左向右为高位到低位,所以我们定义这样的数据结构:

 

typedef struct s_num
{
	//数值
	char* n;
	//右向左起始位置
	char* p;
	//数值长度
	int len;
	//存储空间大小
	int size;
} s_num;

 

        有了这样的数据结构,我们就可以方便的使用它计算阶乘了,但问题是我们定义了这样的数据结构用于存储很多位的整数,但对这样的整数做四则运算也就成了问题的关键,我们不能再使用+、-、*、/这样的运算符对这个数据结构进行计算,我们只能自己编写四则运算的程序。下面我们来编写对这样数据结构的加法和乘法的运算法则,因为求阶乘的运算只涉及到加法和乘法:

 

//加法
int s_add(s_num* tar, s_num* src0, s_num *src1)
{
	char* p0 = src0->p;
	char* p1 = src1->p;
	char* pt = tar->n;
	char en = 0;
	int length = src0->len > src1->len ? src0->len : src1->len;
	//循环计算加法
	for (int i = 0; i < length; i++)
	{
		char n0 = *p0;
		char n1 = *p1;
		if (i >= src0->len)
		{
			n0 = '0';
		}
		if (i >= src1->len)
		{
			n1 = '0';
		}
		//计算和
		char res = CHAR2NUM(n0) + CHAR2NUM(n1) + en;
		//计算进位的值
		en = res / 10;
		//当前位结果
		*pt = NUM2CHAR(res % 10);
		p0--;
		p1--;
		pt++;
	}
	int len = length;
	//处理最高位进位值
	if (en != 0)
	{
		*pt = NUM2CHAR(en);
		pt++;
		len++;
	}
	*pt = 0;
	//高低位反转位置
	for (int i = 0; i < len / 2; i++)
	{
		char t = tar->n[i];
		tar->n[i] = tar->n[len - 1 - i];
		tar->n[len - 1 - i] = t;
	}
	tar->len = len;
	tar->p = tar->n + tar->len - 1;
	return 0;
}

//乘法
int s_mul(s_num* tar, s_num* src0, s_num *src1)
{
	s_clear();
	if (src1->len < src0->len)
	{
		s_num* t = src0;
		src0 = src1;
		src1 = t;
	}
	char* p0 = src0->p;
	char* p1 = src1->p;
	for (int i = 0; i < src0->len; i++)
	{
		char en = 0;
		char n0 = *p0;
		char* pt = temp0.n;
		char* p1 = src1->p;

		//乘法
		for (int j = 0; j < src1->len; j++)
		{
			char n1 = *p1;
			//计算乘法结果
			char res = CHAR2NUM(n0) * CHAR2NUM(n1) + en;
			//计算进位
			en = res / 10;
			*pt = NUM2CHAR(res % 10);
			p1--;
			pt++;
		}
		int len = src1->len;
		if (en != 0)
		{
			*pt = NUM2CHAR(en);
			pt++;
			len++;
		}
		*pt = 0;
		for (int e = 0; e < len / 2; e++)
		{
			char t = temp0.n[e];
			temp0.n[e] = temp0.n[len - 1 - e];
			temp0.n[len - 1 - e] = t;
		}
		temp0.len = len;
		temp0.p = temp0.n + temp0.len - 1;
		for (int s = 0; s < i; s++)
		{
			//temp1 *= 10
			temp0.p++;
			*(temp0.p) = '0';
			*(temp0.p + 1) = 0;
			temp0.len++;
		}
		//累加和
		s_add(&temp2, &temp0, &temp1);
		s_cpy(&temp1, &temp2);
		p0--;
	}
	s_cpy(tar, &temp1);
	return 0;
}

 

        其实,上面两个函数是我们在小学里学过的加法和乘法的运算法则:

加法:按位相加,大于10则进位;

乘法:按位相乘,结果累加。

        最后编写一个main函数用于计算1000的阶乘:

 

int main(int argc, char *argv)
{
	s_num n;
	s_num mut;
	s_num res;
	s_num inc;
	s_num sum;
	s_init(&n, "1");
	s_init(&mut, "1");
	s_init(&res, "0");
	s_init(&inc, "1");
	s_init(&sum, "0");
	// 1000!
	for (int i = 0; i < 1000; i++)
	{
		//计算n的阶乘
		s_mul(&res, &mut, &n);
		s_cpy(&mut, &res);
		//将n加1
		s_add(&sum, &inc, &n);
		s_cpy(&n, &sum);
	}
	printf("%s\n", res.n);
}

 

        运行结果为:

 

40238726007709377354370243392300398571937486421071
46325437999104299385123986290205920442084869694048
00479988610197196058631666872994808558901323829669
94459099742450408707375991882362772718873251977950
59509952761208749754624970436014182780946464962910
56393887437886487337119181045825783647849977012476
63288983595573543251318532395846307555740911426241
74743493475534286465766116677973966688202912073791
43853719588249808126867838374559731746136085379534
52422158659320192809087829730843139284440328123155
86110369768013573042161687476096758713483120254785
89320767169132448426236131412508780208000261683151
02734182797770478463586817016436502415369139828126
48102130927612448963599287051149649754199093422215
66832572080821333186116811553615836546984046708975
60290095053761647584772842188967964624494516076535
34081989013854424879849599533191017233555566021394
50399736280750137837615307127761926849034352625200
01588853514733161170210396817592151090778801939317
81141945452572238655414610628921879602238389714760
88506276862967146674697562911234082439208160153780
88989396451826324367161676217916890977991190375403
12746222899880051954444142820121873617459926429565
81746628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422614
39742869330616908979684825901254583271682264580665
26769958652682272807075781391858178889652208164348
34482599326604336766017699961283186078838615027946
59551311565520360939881806121385586003014356945272
24206344631797460594682573103790084024432438465657
24501440282188525247093519062092902313649327349756
55139587205596542287497740114133469627154228458623
77387538230483865688976461927383814900140767310446
64025989949022222176590433990188601856652648506179
97023561938970178600408118897299183110211712298459
01641921068884387121855646124960798722908519296819
37238864261483965738229112312502418664935314397013
74285319266498753372189406942814341185201580141233
44828015051399694290153483077644569099073152433278
28826986460278986432113908350621709500259738986355
42771967428222487575867657523442202075736305694988
25087968928162753848863396909959826280956121450994
87170124451646126037902930912088908694202851064018
21543994571568059418727489980942547421735824010636
77404595741785160829230135358081840096996372524230
56085590370062427124341690900415369010593398383577
79394109700277534720000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000000000000000

 

        程序运算的结果是正确的,但这里采用的是循环计算1000的阶乘,而并没有采用递归的方式。请读者自己思考如何采用递归的方式来计算1000的阶乘,自己动手实现程序,并验证结果是否正确。

 

本例代码下载(请将下载后的文件修改为example.tar.gz解压即可)

 

        今天的小技巧你学会了吗?

 

 

    返回首页    返回顶部
  看不清?点击刷新

 

  Copyright © 2015-2018 问渠网 辽ICP备15013245号