阶乘(1000的阶乘,10000的阶乘...)以及大数相乘(几十万位乘几十万位)
大家有兴趣的可以贴出更加简洁明了以及高效的算法
核心函数,可以满足阶乘以及两个大数相乘
1,000的阶乘4秒
10,000的阶乘220秒
100,000的阶乘.... ...(汗,没算完,算了1个半小时算到45,000左右)
大数相乘可以支持到N大(没测试过到底多大,Dictionary把内存撑爆为止吧,呵呵^_^)
核心函数如下:
/// <summary> /// 将传入的因数X,因数Y的Dictionary中的元素循环进行相乘. /// </summary> /// <param name="FactorX">因数X</param> /// <param name="FactorY">因数Y</param> /// <returns>乘积结果的Dictionary</returns> static Dictionary<int, int> GetProduct(Dictionary<int, int> FactorX , Dictionary<int, int> FactorY) { Dictionary<int, int> ret = new Dictionary<int, int>(); //乘积,返回结果 int Carry = 0; //进位数 int Product = 0; //乘积 int Position = 0; //位数 int Number = 0; //乘积 % 10 取余的余数 int TempNumber = 0; //旧值 //循环历遍因数X中的元素 foreach (KeyValuePair<int, int> kvpFactorX in FactorX) { //清除进位数 Carry = 0; //循环历遍因数Y中的元素 foreach (KeyValuePair<int, int> kvpFactorY in FactorY) { //取得乘积,例如 9 * 9 = 81 Product = kvpFactorY.Value * kvpFactorX.Value; //取得位数,例如 因数X的第1位 * 因数Y的第1位,那么其乘积所在开始的位数则为2, //比如 20 * 30 中两个十位数相乘其结果 //开始的位数为(2所在位数为1 + 3所在位数为1) = 6所在位数为2,即是600 Position = kvpFactorX.Key + kvpFactorY.Key; //取得乘积 % 10 取余的余数 Number = Product % 10; //判断乘积结果中该位是否有值,有值则相加,否则插入 if (ret.Keys.Contains(Position)) { //临时存放旧值 TempNumber = ret[Position]; //更新当前位的值,当前位值 = (旧值 + 取得乘积 % 10 取余的余数 + 上一次进位数) % 10 取余 ret[Position] = (TempNumber + Number + Carry) % 10; //取得当前进位值,當前進位值 = (旧值 + 乘积 + 进位)/10 取整 Carry = (int)Math.Floor((TempNumber + Product + Carry) / 10.0); } else { //插入位数,值 ret.Add(Position, (Number + Carry) % 10); //取得当前进位值,當前進位值 = (乘积 + 进位)/10 取整 Carry = (int)Math.Floor((Product + Carry) / 10.0); } } //当最后进位数不为0时,需要新增最高位,其值为进位数 if (Carry != 0) ret.Add(ret.Keys.Max() + 1, Carry); } return ret; }def f(n) i = 1 while n > 0 i *= n n -= 1 end return iendputs f(1000)
[解决办法]
10000的阶乘，我没有精确计时，我只是心里默念1秒，2秒，居然在第六秒的时候就IO出来了。。。
[解决办法]
#include <stdio.h>#include <stdlib.h>#define MAX_NUM 100#define MOD_OF_ARY 10000int main(){ static int ary[MAX_NUM] = { 1 }; int i, j; int width; /*---表示结果的"宽度"---*/ int current_num; /*--- 当前数字 ---*/ /*--- 从大到小进行阶乘计算 ---*/ for( width = 0 , current_num = MAX_NUM ; current_num > 1; current_num-- ){ /*--- 对每一个‘分段’进行运算 ---*/ for( i = j = 0; i <= width; i++ ){ /*--- 当前运算的‘有效数值’ ---*/ ary[i] = ( (j += ary[i] * current_num) ) % MOD_OF_ARY; /*--- 当前运算的‘进位数值’ ---*/ j /= MOD_OF_ARY; } if ( ary[i] = j ){ /*如果有进位，则索引向前推进*/ width++; } } printf ( "%d", ary[width] ); /*--- 将求的数值输出 ---*/ for( j = width - 1; j >= 0; j-- ){ printf( "%04d", ary[j] );/*--- 这里的6跟MOD_OF_ARY的位数有关 ---*/ } printf ("\n"); system ("pause"); }
[解决办法]
以前自己用土方法写的，乘法没做优化，10000!还能凑合吧，100000就太慢了。
用的是10^32进制
using System;using System.Collections.Generic;using System.Text;namespace ConsoleApplication4{ class Program { public static void Main(string[] args) { HugeInt A = HugeInt.Factorial(10000); Console.WriteLine(HugeInt.DecimalScale(A)); } //只能算正整数,如果大家有兴趣可以自己为类加一个正负号 class HugeInt { public List<ulong> IntList; public ulong DivMod; public HugeInt() { IntList = new List<ulong>(); } public HugeInt(ulong number) { IntList = new List<ulong>(); IntList.Add(number); Carry(this); } public HugeInt(HugeInt number) { IntList = new List<ulong>(number.IntList); } public static HugeInt operator +(HugeInt A, HugeInt B) { HugeInt result; if (B.IntList.Count > A.IntList.Count) { result = A; A = B; B = result; } result = new HugeInt(A); for (int i = 0; i < B.IntList.Count; i++) result.IntList[i] += B.IntList[i]; Carry(result); return result; } //A必须大于B,否则会出现Bug public static HugeInt operator -(HugeInt A, HugeInt B) { HugeInt result = new HugeInt(A); for (int i = 0; i < B.IntList.Count; i++) { if (result.IntList[i] < B.IntList[i]) { result.IntList[i] += 0x100000000; int position = i + 1; while (result.IntList[position] == 0) position++; result.IntList[position]--; while (position > i + 1) { result.IntList[position] = 0xFFFFFFFF; position--; } } result.IntList[i] -= B.IntList[i]; } Decarry(result); return result; } //虽然B用的是ulong,但如果B大于2^32的话,会出现溢出bug,B大于2^32的话先将B转为HugeInt,用下面的乘法来算 public static HugeInt operator *(HugeInt A, ulong B) { HugeInt result = new HugeInt(A); for (int i = 0; i < result.IntList.Count; i++) result.IntList[i] *= B; Carry(result); return result; } public static HugeInt operator *(HugeInt A, HugeInt B) { HugeInt Result = new HugeInt(); for (int i = 0; i < B.IntList.Count; i++) { if (B.IntList[i] == 0) continue; HugeInt Temp = A * B.IntList[i]; InsertZero(Temp, (uint)i); Result += Temp; Carry(Result); } return Result; } //除法,余数保存在divmod里面,相当于包含了%运算,B < 2^32 public static HugeInt operator /(HugeInt A, ulong B) { HugeInt result = new HugeInt(A); int length = A.IntList.Count; ulong current; ulong mod = 0; for (int i = length - 1; i >= 0; i--) { current = result.IntList[i] / B; mod = result.IntList[i] - current * B; result.IntList[i] = current; if (i > 0) result.IntList[i - 1] += mod << 32; } Decarry(result); result.DivMod = mod; return result; } //乘法运算时的错位 private static void InsertZero(HugeInt A, uint B) { ulong[] Temp = new ulong[B]; A.IntList.InsertRange(0, Temp); } //进位运算 private static void Carry(HugeInt A) { ulong carry = 0; int length = A.IntList.Count; for (int i = 0; i < length; i++) { carry = A.IntList[i] >> 32; A.IntList[i] = A.IntList[i] & 0x00000000FFFFFFFF; if (i == length - 1 && carry > 0) A.IntList.Add(carry); else if (i < length - 1) A.IntList[i + 1] += carry; } } //退位运算 private static void Decarry(HugeInt A) { while (A.IntList.Count > 0 && A.IntList[A.IntList.Count - 1] == 0) A.IntList.RemoveAt(A.IntList.Count - 1); } //以10进制输出 public static string DecimalScale(HugeInt A) { StringBuilder builder = new StringBuilder(); HugeInt Temp = new HugeInt(A); while (Temp.IntList.Count > 0) { Temp /= 100000000; if (Temp.IntList.Count > 0) builder.Append(Reverse(Temp.DivMod.ToString("#00000000"))); else builder.Append(Reverse(Temp.DivMod.ToString())); } return Reverse(builder.ToString()); } public static HugeInt Factorial(int n) { HugeInt Temp = new HugeInt(1); ulong currentValue = 1; for (ulong i = 1; i <= (ulong)n; i++) { currentValue *= i; if (currentValue * (ulong)(i + 1) > uint.MaxValue) { Temp *= currentValue; currentValue = 1; } } if (currentValue > 1) Temp *= currentValue; return Temp; } private static string Reverse(string original) { char[] arr = original.ToCharArray(); Array.Reverse(arr); return new string(arr); } } }}
[解决办法]
这个郭先强精通:
看他的结果:
http://www.emath.ac.cn/hugecalc/index.htm#Factorial
40000000!的计算只花了67秒半
[解决办法]
public class BigFactorial { /** * 从左到右找到第一个非零的数的下标 */ public static int firstNoZeroPos(int[] array) { int pos = 0; while (pos < array.length) { if (array[pos] != 0) { break; } ++pos; } return pos; } /** * 计算 n 的阶乘 */ public static void calculateFactorial(int n, int[] result) { // 保存结果的数组清0 for (int i = 0; i < result.length; ++i) { result[i] = 0; } result[result.length - 1] = 1; int carry = 0; int temp = 0; int pos = 0; for (int i = 1; i <= n; ++i) { pos = firstNoZeroPos(result); for (int k = result.length - 1; k >= pos - 1; --k) { temp = result[k] * i + carry; result[k] = temp % 10000; carry = temp / 10000; } } } public static void main(String[] args) { int[] result = new int[30000]; // 存储结果的数组, 每个元素存储0-9999的一个数 long startTime; long endTime; int n = 10000; startTime = System.currentTimeMillis(); calculateFactorial(n, result); endTime = System.currentTimeMillis(); // 输出结果 int pos = firstNoZeroPos(result); System.out.println(n + " 的阶乘:"); System.out.println("有 " + (result.length - pos) * 4 + " 位"); System.out.println("时间: " + (endTime - startTime) + " 毫秒"); for (int i = pos; i < result.length; ++i) { if (result[i] < 10) { System.out.print("000" + result[i] + " "); } else if (result[i] < 100) { System.out.print("00" + result[i] + " "); } else if (result[i] < 1000) { System.out.print("0" + result[i] + " "); } else { System.out.print(result[i] + " "); } } }}
[解决办法]
这个是利用数组计算 1000! 46ms
vs2008 编译执行
// Console.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "atltime.h"#define size 100000 static void exe(double N) { int Data[size] ; int i, j, r, k; int digit; long tm1=GetTickCount(); for (i = 0; i < size; i++) Data[i] = 0; Data[0] = 1; Data[1] = 1; digit = 1; for (i = 1; i <= N; i++) { for (j = 1; j <= digit; j++) Data[j] *= i; // 做处理,主要是进位问题 for (j = 1; j <= digit; j++) { if (Data[j] > 9) { // 只要有一个存在着要进位,所有都会做进位处理 //向高位进位的,所以j++,进位后,再循环看高位有没有需要处理进位的 for (r = 1; r <= digit; r++) { if (Data[digit] > 9) digit++; Data[r + 1] += Data[r] / 10; Data[r] = Data[r] % 10; } } } } long tm2=GetTickCount(); printf("%f的阶乘的螟 %d \r\n",N,digit); j = 0; for (k = digit; k > 0; k--) { j += 1; printf("%d",Data[k]); } long tm3=GetTickCount(); printf("\r\ncalc time:%d ms\r\n",tm2-tm1); printf("printf time:%d ms\r\n",tm3-tm2); }int _tmain(int argc, _TCHAR* argv[]){ exe(10000); return 0;}
[解决办法]
前两天刚写了一个，其实是一道ACM题，经过大牛的帮助，AC了
/********************Author: Run* www.nlogn.cn*******************/#include<stdio.h>#include<string.h>#define M 100000 #define MOD 10int mut(int r[],int n)/*做乘法*/{ int p=0,j,i,sum,pos=0; for(i=2;i<=n;i++) { for(j=0;j<=pos;j++) { sum=r[j]*i+p; r[j]=sum%MOD; p=sum/MOD; /* printf("sum=%d,r[%d]=%d,p=%d\n",sum,j,r[j],p);*/ } while(p) { r[j]=p%MOD; pos=j; p=p/MOD; j++; } } return pos;}void print(int r[],int pos)/*打印结果*/{ int i; for(i=pos;i>=0;i--) { printf("%d",r[i]); }}int main(void){ int res[M],n,pos; while(scanf("%d",&n)!=EOF) { memset(res,0,M*sizeof(int)); res[0]=1; if(n==0) printf("1\n"); else if(n==1) printf("1\n"); else { pos=mut(res,n); print(res,pos); printf("\n"); } }return 0;}
[解决办法]
算法差不多的话，计算时间跟计算机硬件，所用语言有些关系吧。
[解决办法]
如果要有一个最小的程序，这个可能是最小的，不过速度不快。
//版本7：采用10进制，在主流编译器可以实现1-200000的阶乘，扣除#include 和 #define语句，共153个字节，但是速度较慢。 #include <stdio.h>#define N 10 //计算N的阶乘，修改N的定义可计算200000以内任意数的阶乘int a[N*5]={1},n=N,i,c,m;void main(){for(;n;n--){for(c=i=0;i<=m;i++)a[i]=(c+=a[i]*n)%10,c/=10;while(c)a[++m]=c%10,c/=10;}for(;m>=0;)printf("%d",a[m--]);}转自我的博客：http://blog.csdn.net/liangbch/archive/2008/11/05/3230428.aspx