| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1514 人关注过本帖
标题:如何求 500!
只看楼主 加入收藏
woodhead
Rank: 3Rank: 3
等 级:新手上路
威 望:9
帖 子:1124
专家分:0
注 册:2005-7-18
收藏
得分:0 

能不能把

int getBitNum(int n)
void calc(char*a,int n)

这两个讲一讲呢?


2006-01-04 17:10
303770957
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:6
帖 子:838
专家分:2125
注 册:2005-9-10
收藏
得分:0 

int getBitNum(int n)是一个求n!是几位数的函数。
比如:10的s次方=n!可得:s=[log1+log2+log3……+logn]注意:[]表示取整。
void calc(char*a,int n)这个函数是个重点,可惜要给你讲清楚很费事。
它是如何用数组去计算n!的函数,这中间有些语句是这个程序的核心部分!
呵呵!你自己体会吧。


♂ 死后定当长眠,生前何须久睡。♀
2006-01-04 17:41
woodhead
Rank: 3Rank: 3
等 级:新手上路
威 望:9
帖 子:1124
专家分:0
注 册:2005-7-18
收藏
得分:0 
谢谢了。

2006-01-04 17:56
303770957
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:6
帖 子:838
专家分:2125
注 册:2005-9-10
收藏
得分:0 

有好些朋友给我发贴或是发邮件说对我上面贴的程序感觉不明白,今天我把上述程序的算法描述如下:
求n!对整数范围的n,求n!

具体算法描述如下:

由于c程序设计语言中的基本数据类型所能表达的数据范围有限,对于一个比较大的n(比如

n=100),求n!时,表达其乘积的变量值必定要溢出,所以,单纯用一个求n!的算法是行不通

的。
可以把n!的结果放在数组中,数组中的每个元素都表示其n!值的一位。
对于输入的n想办法尽量精确的估计其n!所占的位数,就能确定数组元数的个数。
可以将n!表示成10的次幂,即:n!=10~m,则不小于m的最小整数就是n!的位数。对该试两

边取对数,有:m=log10(1)+log10(2)+log10(3)+……+log10(n)
循环求和,就能算出m的值,该值就是n!的精确位数。
树组空间用申请堆内存来解决。由于每个数组表示n!的一位数值,所以数组的类型用占一个

字节的char类型已经足够了。
当n很大时,堆空间可能失败。所以要考虑堆空间失败的执行操作。
数组初始化时,令数组的第一个元素(n!的第一位)为整数1,其余为0。
在计算n!时,是通过将数组中的值乘2,乘3,乘4……一直乘到n的方式求得的。把数组中的

内容为7!=5740(0是数组的第一个元素,5是数组中的第四个元素),紧界着乘以8。这时,8!

的位数(5)将首先被求得,然后,按照从高到低的顺序逐个乘以8。乘出的积与上次进位值相加

。由此可以确定当前的值(即相加值的个数),再将该数相加值整除10后作为下一次的进位值。
具体操作如下:
进位初试值为0,
8*0(个位数)=0, 加上进位值得0, 从而确定个位数为0,进位数值是0;
8*4(十位数)=32,加上进位值得32,从而确定十位数为2,进位数值是3;
8*7(百位数)=56,加上进位值得59,从而确定百位数为9,进位数值是5;
8*5(千位数)=40,加上进位值得45,从而确定千位数为5,进位数值是4;
8*0(万位数)=0, 加上进位值得4, 从而确定万位数为4,进位数值是0;
循环结束。
数组在做i从2到n 的乘法中,末尾0的个数不断的增多,而0乘以i总是为0。乘i时,可以跳过

这些0,因而算法可以作适当的优化。
设置起始位,初值为0。每次乘i前,都判断一下起始位值是否为0,若为0。则起始位增加1。

每次乘i,都从起始位开始。
最后,从数组的最后一个元素(n!的高位)起,直到第一个元素为止,逐个打印数组元素的

整数值,即为所求n!。
根据上述内容,得到下面的算法;
(1)给出n
(2)计算n!的位数
(3)申请数组空间并且初始化
(4)求n!
(5)输出n!
(6)返还数组空间
(7)结束
给出n的算法为:
(1)输入n
(2)若n小于0,则重新输入
(3)若n等于0,则结束
(4)若n大于0,则返回n
计算n!的位数的算法为:
(1)sum=1;
(2)for(i:1->n,步长为1)
(3)sun+=long10(i)
(4)返回整数部分
申请数组空间以及初始化的算法为:
(1)根据n!的位数申请堆空间
(2)若申请失败,则显示申请失败并退出程序的运行
(3)数组第一个元素<-1
(4)for(i:2->n!的位数,步长为1)
(5) 第i个元素<-0
(6)返回数组空间首地址
求n!的算法如下:
(1)1!位数<-1
(2)起始位<-0
(3)for(i:2->n,步长为1)
(4)相加值<-0
(5)i!位数<-(i-1)!位数+long10(i)
(6)若起始值等于0
(7)起始步<-起始步+1
(8)for(j:起始步->i!位数,步长为1)
(9)相加值<-相加值+i*第j个元素值
(10)第j个元素值<-相加值的个位数
(11)相加值<-相加值整除10
(12)结束
输出n!
(1)位序数<-0
(2)for(i:数组最后元素位->数组第一元素,步长为-1 )
(3)位序数整除68,则换行输出“第几个68位”
(4)输出第i元素的整型值
(5)位序数<-位序数+1
(6)换行
(7)结束


♂ 死后定当长眠,生前何须久睡。♀
2006-09-22 21:15
303770957
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:6
帖 子:838
专家分:2125
注 册:2005-9-10
收藏
得分:0 
希望大家能看懂我的描述将其中的精华学到,由于本人的水平有限,每讲明白的地方或是有讲错的地方给予纠正指出,谢谢!具体代码我已经在上面贴过!

♂ 死后定当长眠,生前何须久睡。♀
2006-09-22 21:18
帅加加
Rank: 1
等 级:新手上路
帖 子:21
专家分:0
注 册:2006-9-19
收藏
得分:0 
受教!

只要你打不死劳资,劳资就要站起来
2006-09-24 23:21
wyg_616
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2006-9-24
收藏
得分:0 
10的s次方=n!可得:s=[log1+log2+log3……+logn]注意:[]表示取整

这个表述好象是错误的吧!10的s次方1后有s个0,而n!所得好象很难是这么个数!

胸有成竹,而面如平湖这可拜上将军
2006-09-25 09:35
帅加加
Rank: 1
等 级:新手上路
帖 子:21
专家分:0
注 册:2006-9-19
收藏
得分:0 
楼上的,看帖要仔细啊!!!
n!=1*2*3*...*n;
s=[lg(n!)]=[lg(1*2*3*...n)]
=[lg(1)+lg(2)...+lg(n)]
lg(a*b)=lg(a)+lg(b)你应该知道吧

只要你打不死劳资,劳资就要站起来
2006-09-25 11:40
帅加加
Rank: 1
等 级:新手上路
帖 子:21
专家分:0
注 册:2006-9-19
收藏
得分:0 
这算法最关键的就是逐位乘n然后将模10的结果进位,对吧?
每乘一数就要循环一轮,运算量蛮大的

只要你打不死劳资,劳资就要站起来
2006-09-25 11:54
ligt0610
Rank: 1
等 级:新手上路
帖 子:204
专家分:5
注 册:2006-6-29
收藏
得分:0 
以下是引用303770957在2005-12-24 19:43:00的发言:
呵呵,其实100!也可以的,只是你要等一会运算结果才能出来的,要有耐心哦!

其实用大数写一下 很快就可以出来的闹


通过不断的学习与思考才是提高自己能力的最好途径。。。。。。。
2006-09-25 13:36
快速回复:如何求 500!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.042693 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved