注册 登录
编程论坛 C++教室

[求助]计算N的阶乘N!

aipb2007 发布于 2007-08-12 13:18, 3304 次点击

考虑越界。

求一个相对高效的算法。
我做了一个,用数组,效率不好,看看大家的!

32 回复
#2
HJin2007-08-12 13:23
If you can overcome the problem of precision, Stirling's formula can be helpful:

n! = sqrt(2 Pi n) * (n/e)^n * e^alpha,

where 1/(12n +1)<alpha<1/(12n).
#3
aipb20072007-08-12 13:25
以下是引用HJin在2007-8-12 13:23:10的发言:
If you can overcome the problem of precision, Stirling's formula can be helpful:

n! = sqrt(2 Pi n) * (n/e)^n * e^alpha,

where 1/(12n +1)<alpha<1/(12n).

显然我看不懂!
太数学了!

#4
leeco2007-08-12 14:35
#5
圆圆的鸟蛋2007-08-12 16:45
以下是引用leeco在2007-8-12 14:35:54的发言:
http://dev.csdn.net/develop/article/29/29226.shtm

看晕了!

#6
野比2007-08-12 23:43
了解
#7
neverDie2007-08-14 12:14
以下是引用leeco在2007-8-12 14:35:54的发言:
http://dev.csdn.net/develop/article/29/29226.shtm

不懂!

顺便:用数组怎么做?

#8
wingyip2007-08-14 12:55
為什么不用遞歸呢?
#9
neverDie2007-08-14 13:32
以下是引用wingyip在2007-8-14 12:55:18的发言:
為什么不用遞歸呢?

遞歸?
递归?

怎么做?

#10
terisevend2007-08-14 13:37
递归很简单...但是只能应对小的数字的阶乘...

int _F( int a[], int n )
{
int s;

if( n <= 1 )
return 1;
else
s = n*_F( a, n-1 );
return s;
}
#11
野比2007-08-14 13:44
HJin, α和e的精度怎么弄? ... 取个20位?...

btw... 不要用递归.. 效率低了...可以考虑并行乘法...
先实现一个大数类比较好...
#12
狂人老大2007-08-14 13:47
递归我用过了 最多只能到计算到16!
#include<iostream>
int fac(int n);
using namespace std;
int main(){
int n;
int w;
cin>>n;
w=fac(n);
cout<<w<<endl;
}
int fac(int n){
int w;
if(n<0)
cout<<"error!"<<endl;
else if(n==0)
w=1;
else
w=n*fac(n-1);
return w;
}
#13
neverDie2007-08-14 14:14

看问题先,斑竹都说了考虑越界,肯定不是直接写个求 n!。直接的话,用循环不就好了。
一定要用大数类吗?

#14
缘吇弹2007-08-14 14:17
用数组存储计算
#15
neverDie2007-08-14 16:56
以下是引用缘吇弹在2007-8-14 14:17:33的发言:
用数组存储计算

怎么存?

#16
怪怪女巫2007-08-14 18:10

int fac(int k)
{
int t=1,i;
for(i=1;i<=k;i++)
t=t*i;
return(t);
}
void main()
{
int n,m;
cout<<"input n: ";
cin>>n;
m=fac(n);
cout<<n<<"!="<<m<<endl;
}
菜鸟级人物,我只学会用这种方法

#17
野比2007-08-15 00:48
以下是引用怪怪女巫在2007-8-14 18:10:30的发言:

菜鸟级人物,我只学会用这种方法

可以了, 只不过是容量小些罢了...

#18
缘吇弹2007-08-15 10:17
以下是引用neverDie在2007-8-14 16:56:30的发言:

怎么存?

每个位数作为数组的元素

#19
neverDie2007-08-15 12:00
以下是引用缘吇弹在2007-8-15 10:17:35的发言:

每个位数作为数组的元素

这位 BZ 你说了当没说。问题这是在运算,单把个数存数组当然简单,但是也会越界啊!

晕!

我还是找其他办法。
#20
缘吇弹2007-08-15 13:26
以下是引用neverDie在2007-8-15 12:00:22的发言:
这位 BZ 你说了当没说。问题这是在运算,单把个数存数组当然简单,但是也会越界啊!

晕!

我还是找其他办法。

希望下边对你有帮助。
using namespace std;
#include "StdAfx.h"
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <iomanip.h>

int GetNumber(); //输入 n
int GetBitLength(int n); //求n!的位数
char* Initialize(int); //初始化存储结果的值
void PrintValue(char *a,int size); //打印值到屏幕
void PrintValue(char *a,int size,char* fileName); //打印值到文件
char* GetValue(int val); //计算
char* SubGetValue(char* ,int);


int main()
{
int value=GetNumber();
char fileName[16];
int size=GetBitLength(value);
char *pa = Initialize(size);

//pa=GetValue();
pa=GetValue(value);

PrintValue(pa,size);

//sprintf(fileName,"%s","10000!.txt");
sprintf(fileName,"%d!.txt",value);

PrintValue(pa,size,fileName);
delete []pa; //note:
return 1;
}
//函数GetValue
// 求得计算结果
//返回结果
//History:
//1)char* GetValue()
//2)GetValue(int val)
// 参数:val 计算阶乘的值
char* GetValue(int val)
{
//定义一个数组存储阶乘的值
//首先得到10000!阶乘的位数
int VALUE=val;
int length=GetBitLength(VALUE);
char *arrValue = new char[length];
if(!arrValue) {
cout <<"申请内存失败!" << endl;
exit(1);
}
arrValue[0] = 1;
for(int i=1; i<length; i++)
arrValue[i] = 0;
arrValue=SubGetValue(arrValue,VALUE);
return arrValue;
}

char* SubGetValue(char* arrValue,int n)
{
int index=0;
long carrier=0;
double bitCount = 1;
int begin = 0;

for(index=2; index<=n; ++index)
{
long multiValue = 0;
bitCount += log10((long double)index);
if(arrValue[begin] == 0)
begin++;

for(int j=begin; j<int(bitCount); ++j)
{
multiValue += (index*arrValue[j]);
arrValue[j] = char(multiValue % 10);
multiValue /= 10;
}
}
return arrValue;
}

//得到计算阶乘的值,此函数为新增
int GetNumber()
{
int n;
cout << "请输入要计算阶乘的n值: ";
cin >> n;
while(n < 0) {
cout << "输入错误,请重新输入: ";
cin >> n;
}
if(n == 0)
exit(1);
return n;
}

//函数GetBitLength
// 求得计算结果的位数,本函数为新增加
//参数
// n 需要计算的阶乘的数
//返回结果的位数
int GetBitLength(int n)
{
double sum = 1.0;
for(int i=1; i<=n; i++)
sum += log10((long double)i);
return int(sum);
}

//-----------
//函数:Initialize
// 初始化存储结果的数组
//参数:
// size 数组的长度
//返回值
// 初始化后的数组
//-------------
char * Initialize(int size)
{
char *arrValue = new char[size];
if(!arrValue) {
cout << size<<"太大,申请内存失败!" << endl;
exit(1);
}
arrValue[0] = 1;
for(int i=1; i<size; i++)
arrValue[i] = 0;
return arrValue;
}

//-----------
//函数:PrintValue
// 将结果输入到屏幕上
//参数:
// buff 存储结果的数组
// buffLen 数组的长度
// fileName 文件名
//-------------
void PrintValue(char *buff, int buffLen)
{
int bit = 0;
int nCol=0;
for(int i=buffLen-1; i>=0; i--) {
if(bit % 10 == 0)
{
cout << " " ;
nCol++;
if(nCol==10)cout<<endl;
}
cout << int (buff[i]);
bit++;
}
cout << endl;

}
//-----------
//函数:PrintValue
// 将结果输入到一个文件中
//参数:
// buff 存储结果的数组
// buffLen 数组的长度
// fileName 文件名
//-------------

void PrintValue(char *buff,int buffLen,char *fileName)
{
int bit = 0;
int nCol=0;

FILE *fp=NULL;
//-----------------------------

if (fileName==NULL) return ;
fp=fopen(fileName,"wt");
if (fp==NULL)
{
printf("不能创建文件%s",fileName);
return ;
}

for(int i=buffLen-1; i>=0; i--)
{
fprintf(fp,"%d",int(buff[i]));

if(bit % 9 == 0)
{
fprintf(fp,"%s"," ");
nCol++;
if(nCol==8)
{
fprintf(fp,"%s","\n");
nCol=0;
}
}
bit++;

}
fprintf(fp,"\n");
fclose(fp);
}

#21
野比2007-08-15 13:42

上面的方法可以完成计算n!, 但是不够... 32767!就是上限了...
这个完全算不上"大数"...
n也要用数组来存放...

#22
缘吇弹2007-08-15 14:40
以下是引用野比在2007-8-15 13:42:59的发言:

上面的方法可以完成计算n!, 但是不够... 32767!就是上限了...
这个完全算不上"大数"...
n也要用数组来存放...

那么LS上想。。。

#23
雨中飞燕2007-08-15 18:19
算大数阶乘四行代码就够了,不算大括号和main,return 0;和头文件这几行的话

[此贴子已经被作者于2007-8-15 18:27:29编辑过]


#24
狂人老大2007-08-16 00:13
回复:(缘吇弹)以下是引用neverDie在2007-8-15 12:0...
为什么运行你的程序会有2个错误啊
去掉using namespace std;后少了一个
还有一个是不是要建新工程啊
我照着书上的过程建了 还是错的
#25
wingyip2007-08-16 09:21
樓主是指已經超過int范圍那種嗎?
#26
jh87921232007-08-16 10:26

下面是我自己写的 仅供参考:

#include<stdio.h>
void main()
{
int a,b,c;
float jc,jc2,jc3;
float fact(int a);

scanf("%d,%d,%d",&a,&b,&c);
jc=fact(a);
jc2=fact(b);
jc3=fact(c);
printf("阶乘是%f,%f,%f\n",jc,jc2,jc3);
}


float fact(int a)
{
int i;
float f;
f=1;
i=1;
while (i<=a)
{
f=f*i;
i++;
}
return(f);
}

#27
aipb20072007-08-16 10:33
缘吇弹的代码不错,还没仔细看,肯定比我那个好多了。

野比意思是要输入都能满足越界吧,我觉得够了,计算到那么大。实用性来讲的话。
呵呵,谢谢你们
#28
狂人老大2007-08-16 16:48
雨中飞燕的四行代码我看了  很好的算法
#29
yuyunliuhen2007-08-16 17:10
好热闹啊,偶路过看看!
#30
卧龙孔明2007-08-17 18:06
以下是引用leeco在2007-8-12 14:35:54的发言:
http://dev.csdn.net/develop/article/29/29226.shtm

太强了

#31
野比2007-08-20 00:19

MATLAB或Mathematica中的阶乘都可以轻易做到N多位... 就是输入输出都考虑了越界的...

不过还是要看你的具体需求了...

太少的用迭代就ok了

#32
qkjenjoy2007-08-24 17:22

用递归

[此贴子已经被作者于2007-8-24 17:24:34编辑过]

#33
kakawei2007-11-06 11:27
递归占用内存比较大,还是用循环比较好.
int N=1;int n;
cin>>n;
for(int i=1;i<=n;i++)
{
N*=i;
}
cout<<N<<endl;
1