能不能把
int getBitNum(int n)
void calc(char*a,int n)
这两个讲一讲呢?
有好些朋友给我发贴或是发邮件说对我上面贴的程序感觉不明白,今天我把上述程序的算法描述如下:
求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)结束