大家有兴趣的可以贴出更加简洁明了以及高效的算法核心函数,可以满足阶乘以及两个大数相乘
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;
}
囧,不允许我输入太多,完整例子看下一楼
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;
}
囧,不允许我输入太多,完整例子看下一楼
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;namespace Factorial
{
class Program
{
static void Main(string[] args)
{
//乘法计算
MultiplicationCalculation(); DateTime BeginTime = DateTime.Now;
DateTime EndTime = DateTime.Now; //阶乘计算
FactorialCalculation(); EndTime = DateTime.Now;
Console.WriteLine(EndTime.Subtract(BeginTime).TotalSeconds + " seconds!");
Console.ReadKey();
} /// <summary>
/// 乘法计算,适合两个超大数相乘.
/// </summary>
static void MultiplicationCalculation()
{
string StrFactorX = string.Empty; //因数X - String
string StrFactorY = string.Empty; //因数Y - String
char[] cFactorX = null; //因数X - String
char[] cFactorY = null; //因数Y - String
Dictionary<int, int> ProductZ = new Dictionary<int, int>(); //乘积Z - Dictionary
Dictionary<int, int> FactorX = new Dictionary<int, int>(); //因数X - Dictionary
Dictionary<int, int> FactorY = new Dictionary<int, int>(); //因数Y - Dictionary int DecimalDigits = 0; //小数位数 //接收输入
Console.Write("please input a numeric:");
StrFactorX = Console.ReadLine();
Console.Write("please input the other one:");
StrFactorY = Console.ReadLine(); //计算小数位,小数位 = 因数X小数位 + 因数Y小数位
DecimalDigits = StrFactorX.Trim().Length - StrFactorX.IndexOf(".") - 1
+ StrFactorY.Trim().Length - StrFactorY.IndexOf(".") - 1; //将输入的string转换为Char[]反转并放入Dictionary中
StrFactorX = StrFactorX.Replace(".", string.Empty).Trim();
StrFactorY = StrFactorY.Replace(".", string.Empty).Trim();
cFactorX = StrFactorX.ToCharArray().Reverse().ToArray();
cFactorY = StrFactorY.ToCharArray().Reverse().ToArray();
for (int i = 0; i < cFactorX.Length; i++)
{
FactorX.Add(i, int.Parse(cFactorX[i].ToString()));
}
for (int i = 0; i < cFactorY.Length; i++)
{
FactorY.Add(i, int.Parse(cFactorY[i].ToString()));
} //计算乘积
ProductZ = GetProduct(FactorX, FactorY);
//显示结果
ShowResult(ProductZ, DecimalDigits);
}
/// <summary>
/// 阶乘计算
/// 目前测试,1000的阶乘大约4秒,10000的阶乘大约 220s.
/// </summary>
static void FactorialCalculation()
{
Dictionary<int, int> ProductZ = new Dictionary<int, int>(); //乘积Z - Dictionary
Dictionary<int, int> FactorX = new Dictionary<int, int>(); //因数X - Dictionary
int Number = 0; //阶乘数
char[] cFactorX = null; //因数 - Char[] //初始化乘积,避免出错
ProductZ.Add(0, 1); //接收输入
Console.WriteLine(@"Please input a numeric:");
Number = int.Parse(Console.ReadLine().Trim()); //阶乘数历遍,从1开始
for (int i = 1; i <= Number; i++)
{
//清空因数
FactorX.Clear(); //每100个数输出一次
if (i % 100 == 0) Console.WriteLine(i.ToString()); //将输入的string转换为Char[]反转并放入Dictionary中
//如1234,放入则为0-4,1-3,2-2,3-1, (位数 - 值)
cFactorX = i.ToString().ToCharArray().Reverse().ToArray(); //因数X元素历遍,从0开始<--这里的j就表示了每个元素所在的位数
for (int j = 0; j < cFactorX.Length; j++)
{
FactorX.Add(j, int.Parse(cFactorX[j].ToString()));
} //计算乘积,将上一次的结果作为因数Y传入
ProductZ = GetProduct(FactorX, ProductZ);
} //显示结果
ShowResult(ProductZ);
} /// <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;
} /// <summary>
/// 显示结果
/// </summary>
/// <param name="Product">乘积 - Dictionary</param>
/// <param name="DecimalDigits">小数位数 - int</param>
static void ShowResult(Dictionary<int, int> Product, int DecimalDigits)
{
StringBuilder sb = new StringBuilder();
foreach (KeyValuePair<int, int> kvp in Product.Reverse())
{
sb.Append(kvp.Value);
//当循环到小数位时,将"."插入
if (kvp.Key == DecimalDigits) sb.Append(".");
}
Console.WriteLine("Result:" + sb.ToString());
} /// <summary>
/// 显示结果
/// </summary>
/// <param name="Product">乘积 - Dictionary</param>
static void ShowResult(Dictionary<int, int> Product)
{
ShowResult(Product, 0);
}
}
}
def f(n)
i = 1
while n > 0
i *= n
n -= 1
end
return i
end
puts f(1000)这个算1000的阶乘，貌似连2秒都不到啊
嗯，好，支持你。但是实际测量的结果看来，你不能再用Dict处理这种事情了，因为可能有同步的问题。
毕竟Dict是线程安全的，整个过程也许多次EnterCriticalSection呢。
(算法未修改,只是把放置容器从Dictionary修改为List)
这次:
1000的阶乘 0.5s
10000的阶乘 90s
(还是没办法达到 甘草 在6楼说的 10000的阶乘 6秒的速度)核心代码如下: public static List<int> GetProduct(List<int> FactorX, List<int> FactorY)
{
List<int> ret = new List<int>();
int Carry = 0; //进位数
int Product = 0; //乘积
int Position = 0; //位数
int Number = 0; //乘积 % 10 取余的余数
int TempNumber = 0; //旧值 //循环历遍因数X中的元素
for (int i = 0; i < FactorX.Count; i++)
{
//清除进位数
Carry = 0;
//循环历遍因数Y中的元素
for (int j = 0; j < FactorY.Count; j++)
{
//取得乘积,例如 9 * 9 = 81
Product = FactorX[i] * FactorY[j]; //取得位数,例如 因数X的第1位 * 因数Y的第1位,那么其乘积所在开始的位数则为2,
//比如 20 * 30 中两个十位数相乘其结果
//开始的位数为(2所在位数为1 + 3所在位数为1) = 6所在位数为2,即是600
Position = i + j;
//取得乘积 % 10 取余的余数
Number = Product % 10;
//判断乘积结果中该位是否有值,有值则相加,否则插入
if (ret.Count > 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((Number + Carry) % 10);
//取得当前进位值,當前進位值 = (乘积 + 进位)/10 取整
Carry = (int)Math.Floor((Product + Carry) / 10.0);
}
}
//当最后进位数不为0时,需要新增最高位,其值为进位数
if (Carry != 0) ret.Add(Carry);
}
return ret;
}
完整代码见下一楼
有时间继续改进.using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;namespace Factorial
{
class Program
{
static void Main(string[] args)
{ //乘法计算
FactorialWithList.MultiplicationCalculation(); int Number = 0; //接收输入
Console.WriteLine(@"Please input a numeric:");
Number = int.Parse(Console.ReadLine().Trim()); DateTime BeginTime = DateTime.Now;
DateTime EndTime = DateTime.Now; //阶乘计算
FactorialWithList.FactorialCalculation(Number); EndTime = DateTime.Now;
Console.WriteLine(EndTime.Subtract(BeginTime).TotalSeconds + " seconds!");
Console.ReadKey();
}
}
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace Factorial
{
class FactorialWithList
{
public static List<int> GetProduct(List<int> FactorX, List<int> FactorY)
{
List<int> ret = new List<int>();
int Carry = 0; //进位数
int Product = 0; //乘积
int Position = 0; //位数
int Number = 0; //乘积 % 10 取余的余数
int TempNumber = 0; //旧值 //循环历遍因数X中的元素
for (int i = 0; i < FactorX.Count; i++)
{
//清除进位数
Carry = 0;
//循环历遍因数Y中的元素
for (int j = 0; j < FactorY.Count; j++)
{
//取得乘积,例如 9 * 9 = 81
Product = FactorX[i] * FactorY[j]; //取得位数,例如 因数X的第1位 * 因数Y的第1位,那么其乘积所在开始的位数则为2,
//比如 20 * 30 中两个十位数相乘其结果
//开始的位数为(2所在位数为1 + 3所在位数为1) = 6所在位数为2,即是600
Position = i + j;
//取得乘积 % 10 取余的余数
Number = Product % 10;
//判断乘积结果中该位是否有值,有值则相加,否则插入
if (ret.Count > 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((Number + Carry) % 10);
//取得当前进位值,當前進位值 = (乘积 + 进位)/10 取整
Carry = (int)Math.Floor((Product + Carry) / 10.0);
}
}
//当最后进位数不为0时,需要新增最高位,其值为进位数
if (Carry != 0) ret.Add(Carry);
}
return ret;
}
/// <summary>
/// 乘法计算,适合两个超大数相乘.
/// </summary>
public static void MultiplicationCalculation()
{
string StrFactorX = string.Empty; //因数X - String
string StrFactorY = string.Empty; //因数Y - String
char[] cFactorX = null; //因数X - String
char[] cFactorY = null; //因数Y - String
List<int> ProductZ = new List<int>(); //乘积Z - Dictionary
List<int> FactorX = new List<int>(); //因数X - Dictionary
List<int> FactorY = new List<int>(); //因数Y - Dictionary int DecimalDigits = 0; //小数位数 //接收输入
Console.Write("please input a numeric:");
StrFactorX = Console.ReadLine();
Console.Write("please input the other one:");
StrFactorY = Console.ReadLine(); //计算小数位,小数位 = 因数X小数位 + 因数Y小数位
DecimalDigits = StrFactorX.Trim().Length - StrFactorX.IndexOf(".") - 1
+ StrFactorY.Trim().Length - StrFactorY.IndexOf(".") - 1; //将输入的string转换为Char[]反转并放入Dictionary中
StrFactorX = StrFactorX.Replace(".", string.Empty).Trim();
StrFactorY = StrFactorY.Replace(".", string.Empty).Trim();
cFactorX = StrFactorX.ToCharArray().Reverse().ToArray();
cFactorY = StrFactorY.ToCharArray().Reverse().ToArray();
for (int i = 0; i < cFactorX.Length; i++)
{
FactorX.Add(int.Parse(cFactorX[i].ToString()));
}
for (int i = 0; i < cFactorY.Length; i++)
{
FactorY.Add(int.Parse(cFactorY[i].ToString()));
} //计算乘积
ProductZ = GetProduct(FactorX, FactorY);
//显示结果
ShowResult(ProductZ, DecimalDigits);
}
/// <summary>
/// 阶乘计算
/// 目前测试,1000的阶乘大约4秒,10000的阶乘大约 220s.
/// </summary>
public static void FactorialCalculation(int Number)
{
List<int> ProductZ = new List<int>(); //乘积Z - Dictionary
List<int> FactorX = new List<int>(); //因数X - Dictionary char[] cFactorX = null; //因数 - Char[] //初始化乘积,避免出错
ProductZ.Add(1); //阶乘数历遍,从1开始
for (int i = 1; i <= Number; i++)
{
//清空因数
FactorX.Clear(); //每100个数输出一次
if (i % 100 == 0) Console.WriteLine(i.ToString()); //将输入的string转换为Char[]反转并放入Dictionary中
//如1234,放入则为0-4,1-3,2-2,3-1, (位数 - 值)
cFactorX = i.ToString().ToCharArray().Reverse().ToArray(); //因数X元素历遍,从0开始<--这里的j就表示了每个元素所在的位数
for (int j = 0; j < cFactorX.Length; j++)
{
FactorX.Add(int.Parse(cFactorX[j].ToString()));
} //计算乘积,将上一次的结果作为因数Y传入
ProductZ = GetProduct(FactorX, ProductZ);
} //显示结果
ShowResult(ProductZ);
} /// <summary>
/// 显示结果
/// </summary>
/// <param name="Product">乘积 - Dictionary</param>
/// <param name="DecimalDigits">小数位数 - int</param>
public static void ShowResult(List<int> Product, int DecimalDigits)
{
StringBuilder sb = new StringBuilder();
for (int i = Product.Count - 1; i >= 0; i--)
{
sb.Append(Product[i]);
//当循环到小数位时,将"."插入
if (i == DecimalDigits) sb.Append(".");
}
Console.WriteLine("Result:" + sb.ToString());
} /// <summary>
/// 显示结果
/// </summary>
/// <param name="Product">乘积 - Dictionary</param>
public static void ShowResult(List<int> Product)
{
ShowResult(Product, 0);
}
}
}
http://topic.csdn.net/t/20030916/20/2267097.html
"
n=100000!
计算过程耗时33.537718s,clock=120049771.000000
输出过程耗时0.154203
"
==================
有时间再继续优化.
pack away after.help you raised up!
#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");
}
本次基本算法没有多大改动,但是修改进制,由10进制--> 1,000,000,000 进制
1000!阶乘0.048s 48ms (包含输出,以及每1000输出一次)
10000!阶乘5.553125s 5531.25ms (包含输出,以及每1000输出一次)代码如下:using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;namespace Factorial
{
class Program
{
static void Main(string[] args)
{
int Number = 0; //接收输入
Console.WriteLine(@"Please input a numeric:");
Number = int.Parse(Console.ReadLine().Trim()); DateTime BeginTime = DateTime.Now;
DateTime EndTime = DateTime.Now; //阶乘计算
FactorialWithBaseNumberAndList.FactorialCalculation(Number); EndTime = DateTime.Now;
Console.WriteLine(EndTime.Subtract(BeginTime).TotalMilliseconds + " ms!");
Console.ReadKey();
}
}
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace Factorial
{
class FactorialWithBaseNumberAndList
{
public const ulong baseNumber = 1000000000;
public static List<ulong> GetProduct(List<ulong> FactorX, List<ulong> FactorY)
{
List<ulong> ret = new List<ulong>();
ulong Carry = 0; //进位数
ulong Product = 0; //乘积
int Position = 0; //位数
ulong Number = 0; //乘积 % baseNumber 取余的余数
ulong TempNumber = 0; //旧值 //循环历遍因数X中的元素
for (int i = 0; i < FactorX.Count; i++)
{
//清除进位数
Carry = 0;
//循环历遍因数Y中的元素
for (int j = 0; j < FactorY.Count; j++)
{
//取得乘积,例如 9 * 9 = 81
Product = FactorX[i] * FactorY[j]; //取得位数,例如 因数X的第1位 * 因数Y的第1位,那么其乘积所在开始的位数则为2,
//比如 20 * 30 中两个十位数相乘其结果
//开始的位数为(2所在位数为1 + 3所在位数为1) = 6所在位数为2,即是600
Position = i + j;
//取得乘积 % baseNumber 取余的余数
Number = Product % baseNumber;
//判断乘积结果中该位是否有值,有值则相加,否则插入
if (ret.Count > Position)
{
//临时存放旧值
TempNumber = ret[Position];
//更新当前位的值,当前位值 = (旧值 + 取得乘积 % baseNumber 取余的余数 + 上一次进位数) % baseNumber 取余
ret[Position] = (TempNumber + Number + Carry) % baseNumber;
//取得当前进位值,當前進位值 = (旧值 + 乘积 + 进位)/baseNumber 取整
Carry = (ulong)Math.Floor((TempNumber + Product + Carry) / baseNumber * 1.0);
}
else
{
//插入位数,值
ret.Add((Number + Carry) % baseNumber);
//取得当前进位值,當前進位值 = (乘积 + 进位)/10 取整
Carry = (ulong)Math.Floor((Product + Carry) / baseNumber * 1.0);
}
}
//当最后进位数不为0时,需要新增最高位,其值为进位数
if (Carry != 0) ret.Add(Carry);
}
return ret;
} /// <summary>
/// 阶乘计算
/// </summary>
public static void FactorialCalculation(int Number)
{
List<ulong> ProductZ = new List<ulong>(); //乘积Z - Dictionary
List<ulong> FactorX = new List<ulong>(); //因数X - Dictionary //初始化乘积,避免出错
ProductZ.Add(1); //阶乘数历遍,从1开始
for (int i = 1; i <= Number; i++)
{
//清空因数
FactorX.Clear(); //每1000个数输出一次
if (i % 1000 == 0) Console.WriteLine(i.ToString()); FactorX.Add(Convert.ToUInt64(i)); //计算乘积,将上一次的结果作为因数Y传入
ProductZ = GetProduct(FactorX, ProductZ);
} //显示结果
ShowResult(ProductZ);
} /// <summary>
/// 显示结果
/// </summary>
/// <param name="Product">乘积 - List </param>
/// <param name="DecimalDigits">小数位数 - int</param>
public static void ShowResult(List<ulong> Product)
{
StringBuilder sb = new StringBuilder();
for (int i = Product.Count - 1; i >= 0; i--)
{
sb.Append(Product[i]);
}
Console.WriteLine("Result:" + sb.ToString());
}
}
}
http://topic.csdn.net/t/20030916/20/2267097.html
中提及的33s,还有一个数量级... ...
==========
看来硬乘这种初级算法,应该没办法再跳一个数量级了.
要改算法了
用的是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] + " ");
}
}
}
}10000 的阶乘:
有 35660 位
时间: 379 毫秒
2846 2596 8091 7054 5189 0641 3212 1198 6889 0148 0514 0170 2799 2307 9417 9994 2744 1134 0003 7644 4377 2990 7867 5778 4775 8158 8406 2142 3175 2883 0042 3399 4015 3518 7390 5242 1161 3827 1617 4819 8241 9982 7592 4182 8925 9787 8981 2425 3120 5946 5996 2598 6706 5601 6157 2036 0323 9792 6328 7367 1705 5741 9759 6209 9479 7203 4615 3698 1198 9709 2611 2775 0048 4198 8454 1047 5544 6424 4213 6573 3030 7670 3628 8258 0354 8967 4611 1709 7369 5786 0367 0191 0715 1273 0587 2810 4115 8640 5612 8116 5385 3259 6842 5825 9955 8468 8146 4304 2558 9836 6493 1705 9251 7172 0427 6597 4074 4613 3400 0541 9405 2462 3034 3686 9154 0594 ........太长了.........
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;
}
这与你用的cpu有关系的，你的cpu好，就要快，你的cpu烂，就慢
/*******************
*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;
}
#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
另外，在我的博客有《大数阶乘之计算从入门到精通系列》 文章。
在这个系列，我准备讨论阶乘计算的各种算法，但是限于各种原因，没有最终完成。初学者可参考其中3篇仅仅属于入门级算法的文章，这三种算法的特点是程序简单，速度较慢，但是仍然快于许多人写的代码。其中阶乘之计算从入门到精通－入门篇之一，计算1万阶乘需2.7秒阶乘之计算从入门到精通－入门篇之二，计算1万阶乘需0.86秒阶乘之计算从入门到精通－入门篇之三，计算1万阶乘需0.25秒