三合一效果:
代码-C语言:
#include <stdio.h>
# include <stdlib.h>
#define SIZE 77200 //70000!需要77198个int空间
# define size 9290 //第40万个斐波那契需要9290个int的存储空间
# define WEI 10000 //阶乘与乘方每满10000 进位一次
# define MAX 1000000000//斐波那契每一个int存9位
int JCorCF(int n,int m,int data[]);//计算m的阶乘 或者 n的m次幂 n<1时计算m的阶乘
int FBNQ(int a[][size],int b); //求第b个斐波那契数
int print(int data[],int index,int choose);//输出位数和结果并初始化
int gainint(int *p,int a,int b);//输入int *p直至满足(a,b)输入结束,并返回*p的值
int main()
{
int FB[3][size]={0},JC[SIZE]={0},SS[2],index,i,choose;
char JM[][35]={"请输入N [1,70000]:\n","显示第几个斐波那契?[1,400000]:\n","输入N [2,70000]"};
int domain[][2]={{1,70000},{1,400000},{2,70000}};
do{
printf("0:大数阶乘\n1:大数斐波那契\n2:大数N的M次方\n3:退出\n输入选择[0,3]:");
gainint(&choose,0,3);//用户选择
if(choose==3) return 0;
printf("%s",JM[choose]);//输出提示
gainint(&SS[0],domain[choose][0],domain[choose][1]);//输入
if(choose==2)//如果是N的M次幂
{
printf("输入M [2,60000]:");
gainint(&SS[1],2,60000);
print(JC,JCorCF(SS[0],SS[1],JC),choose);//输出N^M次幂
}
else if(choose==1) //输出斐波那契
{
index=FBNQ(FB,SS[0]);
print(FB[(SS[0]-1)%3],index,choose);
for(i=0;i<=index;i++)//初始化
FB[(SS[0]-1)%3][i]=FB[SS[0]%3][i]=0;
}
else if(!choose)//否则阶乘
print(JC,JCorCF(0,SS[0],JC),choose);
system("cls");
}while(1);
return 0;
}
int gainint(int *p,int a,int b)//输入int *p直至满足(a,b)输入结束,并返回*p的位数
{
do{
*p=a-1;
scanf("%d",p);
while(getchar()!='\n');
if(*p>b||*p<a)
printf("输入有误,请重新输入(%d--%d):\n",a,b);
}while(*p>b||*p<a);
return *p;
}
int JCorCF(int n,int m,int data[])
{
int i,j,k;
int index =1; //位数暂定为1
data[1]=1; /* 初始化,令2^0=1 */
for (i=1;i<=m;i++) /* 计算n的m次幂或m的阶乘*/
{
if(n<1)for(j=1;j<=index;j++)
data[j]=data[j]*i;/*每一位数字都乘以n,模仿乘法计算*/
else for (j=1;j<=index;j++)
data[j]=data[j]*n;/*每一位数字都乘以i,模仿乘法计算*/
for(k=1;k<index;k++)
if(data[k]>=WEI)
{
data[k+1]+=data[k]/WEI; /* 当前位向前进位 */
data[k]%=WEI; /*当前位进位之后的值 */
}
/* 单独处理最高位,若计算之后的最高位>=WEI,则位数index加1 */
while(data[index]>=WEI&&index<=SIZE-1)
{
data[index+1]=data[index]/WEI; /* 向最高位进位 */
data[index++]%=WEI; /* 进位之后的值 位数index加1 */
}
}
return index<=SIZE-1?index:0;/* 检验数组是否溢出,若未溢出,则返回位数 */
}
int FBNQ(int a[][size],int b)
{
int i,j,m,k,c[]={0,1,2},index=1;
a[0][1]=a[1][1]=1;/*初值为1 1*/
for (i=1;i<=b;i++)
{
for (j=1;j<=index; j++)
a[c[2]][j]=a[c[0]][j]+a[c[1]][j];
for (k=1;k<index; k++)
if (a[c[2]][k]>=MAX)
{
a[c[2]][k+1]+=a[c[2]][k]/MAX; /* 当前位向前进位 */
a[c[2]][k]%=MAX; /*当前位进位之后的值 */
}
while (a[c[2]][index]>=MAX&&index <=size-1)
{
a[c[2]][index+1] = a[c[2]][index]/MAX; /* 向最高位进位 */
a[c[2]][index++]%=MAX; /* 进位之后的值,位数+1*/
}
for(m=0;m<3;m++)
c[m]=(c[m]+1)%3;//对c[0--2]循环做加法
}
return (index<=size-1)?index:0;
}
int print(int data[],int index,int choose)
{
int sum=(index-1)*(choose==1?9:4);
char A[]={"%09d"};
if (index) //检验数组是否溢出,若未溢出,则打印值 */
{
sum+=printf("%d",data[index]);
data[index--]=0;
}
if(choose!=1) A[2]='4';
while(index>0)
{
printf(A,data[index]);
data[index--]=0;
}
printf("\n共%d位\n",sum);
system("pause");
return sum;
}
分开1斐波那契:
# include <stdlib.h>
# include <stdio.h>
# define M 1000000000/*每一个int存9位*/
# define size 9290/*第40万个斐波那契需要9290个int的存储空间*/
# define MAX 400000
int add(int a[][size],int d);
int main()
{
int shu[3][size]={0,0,0},num,wei=0,k,t;/*初始化shu[][];*/
while(wei<1||wei>MAX){
printf("显示第几个斐波纳挈数?(1--%d):\n",MAX);
scanf("%d",&wei);
while(getchar()!='\n');
}
t=k=num=add(shu,wei);
wei=(wei-1)%3;
k=printf("%d",shu[wei][num--]);
while(num>0)
printf("%09d",shu[wei][num--]);
printf("\n共%d位\n",(t-1)*9+k);
getchar();
return 0;
}
int add(int a[][size],int b)
{
int i,j,m,k,c[]={0,1,2},index=1;
a[0][1]=a[1][1]=1;/*初值为1 1*/
for (i=1;i<=b;i++)
{
for (j=1;j<=index; j++)
a[c[2]][j]=a[c[0]][j]+a[c[1]][j];
for (k=1;k<index; k++)
if (a[c[2]][k]>=M)
{
a[c[2]][k+1]+=a[c[2]][k]/M; /* 当前位向前进位 */
a[c[2]][k]%=M; /*当前位进位之后的值 */
}
while (a[c[2]][index] >= M&& index <= size-1)
{
a[c[2]][index+1] = a[c[2]][index]/M; /* 向最高位进位 */
a[c[2]][index++]%=M; /* 进位之后的值,位数+1*/
}
for(m=0;m<3;m++)
c[m]=(c[m]+1)%3;//对c[0--2]循环做加法
}
return index;
}
大数阶乘:
大数字阶乘 int 与unsigned __int64类型存储方式与计算速度的比较
大数字阶乘已经是老掉牙的东西了,有 斯特林快速求解阶乘的近似公式 还有利用double求精准位数的高手……,不过今天要说的是求精确值的算法,在开始学阶乘的运算时大概都是递归开始 递归慢不如迭代法 之后又用char存储,每个存一位。但是当数字达到20000时发现慢的要死;之后又改为int 存储,一个int存一位,速度快了一点,但是内存浪费严重 如果求30000的阶乘要开辟121288个int的空间相当于 121288*4个字节 如果再高点 如果40000 那么 内存太大 虽然编译没问题 但是程序一运行就挂了 之后又改为一个int存4位 速度更快了 内存也降下来了 求30000的阶乘需要30322个int空间 ,但是我还想更快 更节省内存 不由的想到了把 int改为 __int64 或者unsigned __int64 在测试中我放弃了__int64因为它虽然比int快但不如unsigned __int64快。之后测试 确定了 一个 unsigned __int64 存14位那么 结果如何呢?速度更快了。这个快不仅体现在运算上,还体现在输出时间上。
下面是int和unsigned __int64的代码:
//int 一个int存4位
#include <stdio.h>
#define SIZE 77200 //30000!有121288位,但是每四位进一位,所以即使是40000!也只用到41279位,50000! 53310*4位左右
# define N 10000 /*10000不要改效率更快*/ //60000! 65195*4位左右 7000! 77920左右
int BigFact(int m, int data[]);//计算m的阶乘
void main()
{
int data[SIZE] = {0}; /*存储SIZE位数,元素全部初始化为0,data[0]空着 */
int index,j,n=0; /* 数组元素个数,表示阶乘值的位数 */
while(n<1||n>70000)
{
printf("输入n int 求n!4 (1-70000)注:\n10000!用时约2秒\n20000!用时约5秒\n30000!用时约11秒\n40000!用时约21秒\n50000!用时约37秒\n60000!用时约52秒\n70000!用时约73秒\n");
scanf("%d", &n);
while(getchar()!='\n');
}
printf("%d!=\n", n);
n=index = BigFact(n,data);/* 计算阶乘n!,返回阶乘值的位数 */
if (index) /* 检验数组是否溢出,若未溢出,则打印阶乘值 */
printf("%d",data[index--]);
while(index>0)
printf("%04d",data[index--]);
printf("\n位数大约为%d±4位\n ",n*4);
getchar();
}
/*函数功能:计算m!,存于数组data中,若数组未溢出,则返回阶乘值的位数,否则返回0*/
int BigFact(int m, int data[])
{
int i, j, k;
int index = 1; /* 数组元素个数,表示阶乘值的位数 */
data[1] = 1; /* 初始化,令1!=1 */
for (i=1; i<=m; i++) /* 计算阶乘m!*/
{
for (j=1; j<=index; j++)
data[j]=data[j] * i;/*每一位数字都乘以i,模仿乘法计算*/
for (k=1; k<index; k++)
if (data[k]>=N) /*阶乘值的每位数字应在0~9之内若>=10,则进位*/
{
data[k+1]+=data[k]/N; /* 当前位向前进位 */
data[k]%=N;
/*当前位进位之后的值 */
}
/* 单独处理最高位,若计算之后的最高位>=10,则位数index加1 */
while (data[index] >=N && index <= SIZE-1)
{
data[index+1] = data[index]/N; /* 向最高位进位 */
data[index]%=N; /* 进位之后的值 */
index++; /* 位数index加1 */
}
}
return index <= SIZE-1?index:0;/* 检验数组是否溢出,若未溢出,则返回阶乘值的位数 */
}
接下来为unsigned __int64
#include <stdio.h>
#define SIZE 22056
typedef unsigned __int64 elem;
const unsigned __int64 N=100000000000000;//一个elem存14位
int BigFact(elem m,elem data[]);//计算m的阶乘
void main()
{
elem data[SIZE] = {0}; /*存储SIZE位数,元素全部初始化为0,data[0]空着 */
int index,n=0; /* 数组元素个数,表示阶乘值的位数 */
while(n<1||n>70000)
{
printf("输入n求n!14位 unsigned __int64(1-70000)注:\n10000!用时约1秒\n20000!用时约5秒\n30000!用时约11秒\n40000!用时约21秒\n50000!用时约34秒\n60000!用时约50秒\n70000!用时约70秒\n");
scanf("%I64u", &n);
while(getchar()!='\n');
}
printf("%I64u!=\n", n);
n=index = BigFact(n,data);/* 计算阶乘n!,返回阶乘值的位数 */
if (index) /* 检验数组是否溢出,若未溢出,则打印阶乘值 */
printf("%I64u",data[index--]);
while(index>0)
printf("%014I64u",data[index--]);
printf("\n位数大约为%d±14位 占用空间%d个unsigned__int64\n ",n*14,n);
getchar();
}
/*函数功能:计算m!,存于数组data中,若数组未溢出,则返回阶乘值的位数,否则返回0*/
int BigFact(elem m,elem data[])
{
int i, j, k;
int index = 1; /* 数组元素个数,表示阶乘值的位数 */
data[1] = 1; /* 初始化,令1!=1 */
for (i=1; i<=m; i++) /* 计算阶乘m!*/
{
for (j=1; j<=index; j++)
data[j]=data[j] * i;/*每一位数字都乘以i,模仿乘法计算*/
for (k=1; k<index; k++)
if (data[k]>=N) /*阶乘值的每位数字应在0~9之内若>=10,则进位*/
{
data[k+1]+=data[k]/N; /* 当前位向前进位 */
data[k]%=N;
/*当前位进位之后的值 */
}
/* 单独处理最高位,若计算之后的最高位>=10,则位数index加1 */
while (data[index] >=N && index <= SIZE-1)
{
data[index+1] = data[index]/N; /* 向最高位进位 */
data[index++]%=N; /* 进位之后的值 位数index加1 */
}
}
return index <= SIZE-1?index:0;/* 检验数组是否溢出,若未溢出,则返回阶乘值的位数 */
}
比较一下 :
阶乘! 时间(秒): int unsigned __int64
10000 2 1
20000 5 4.5
30000 11 10.5
40000 21 20
50000 37 34
60000 52 49
70000 73 70
输出速度因为unsigned __int64是以%014I64d输出一次14位 而 int 是%04d 输出一次4位 明显int输出慢