【300分】如何算99999的阶乘？
刚刚测试了一下System.Numerics.BigInteger类，最简单的阶乘...结果吓了我一跳...
先来月经的递归算法...
static System.Numerics.BigInteger Factorial(System.Numerics.BigInteger i){ if (i.IsZero || i.Sign == -1) return System.Numerics.BigInteger.Zero; if (i.IsOne) return System.Numerics.BigInteger.One; else return i * Factorial(i - 1);} static void Main(string[] args){ if (args.Length < 1) return; int i; if (int.TryParse(args[0], out i)) { System.Numerics.BigInteger bi = i; System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); bi = Factorial(bi); sw.Stop(); //计算结果太长，只输出结果长度 Console.Write("结果长度：{0} 用时：{1}", bi.ToString().Length, sw.Elapsed); }}static System.Numerics.BigInteger Factorial(System.Numerics.BigInteger i){ System.Numerics.BigInteger result = 1; while (true) { if (i < 2) return result; result *= i; i--; }}using System;using System.Collections.Generic;using System.Linq;using Oyster.Math;namespace csdnTest{ class Program { static void Main(string[] args) { DateTime beginTime = DateTime.Now; IntX result = Factorial(1000000); DateTime endTime = DateTime.Now; Console.WriteLine(endTime - beginTime); Console.WriteLine(result); Console.ReadKey(); } static IntX Factorial(int n) { int[] counter = GetPowCounter(n); SortedDictionary<IntX, bool> sDict = new SortedDictionary<IntX, bool>(); //计算幂乘并将结果压入优先队列(使用优化过的大数乘法,在计算相等规模的大数乘法时，效率最高) for (int i = 2; i <= n; i++) { if (counter[i] > 0) sDict.Add(IntX.Pow(i, (uint)counter[i]), false); } IntX valueA = 1, valueB; //用SortedDictionary模拟优先队列进行最后的计算 while (sDict.Count > 1) { valueA = sDict.ElementAt(0).Key; valueB = sDict.ElementAt(1).Key; sDict.Remove(valueA); sDict.Remove(valueB); sDict.Add(valueA * valueB, false); } return sDict.ElementAt(0).Key; } //做质因数分解,以便使用幂乘进行计算 static int[] GetPowCounter(int n) { int[] pList = GetPrime(n); int[] pCounter = new int[n + 1]; for (int i = 0; i < pList.Length; i++) { int k = n; while ((k /= pList[i]) > 0) pCounter[pList[i]] += k; } return pCounter; } //生成质数列表 static int[] GetPrime(int n) { List<int> prime = new List<int>(); bool[] flags = new bool[n + 1]; for (int i = 2; i <= n; i++) { if (!flags[i]) prime.Add(i); for (int j = 0; j < prime.Count; j++) { if (prime[j] * i > n) break; flags[prime[j] * i] = true; if (i % prime[j] == 0) break; } } return prime.ToArray(); } }}
[解决办法]
很霸道嘛...沙发板凳都自个占了..
[解决办法]
学习学习
[解决办法]
应该可以看到System.Numerics是怎么实现的吗？
是不是傅里叶变换就看的出来撒
我没测试过...
[解决办法]
mark
[解决办法]
楼主 开个专题 讲一下大数运算啊
mark
[解决办法]
Friendly UP~
[解决办法]
Friendly UP~
[解决办法]
看到标题就知道你要说BinInteger了~~
[解决办法]
C#效率是不是太差了?我用Java写了一个.
x86 jdk 1.6
9999: RS length:35656 成功生成（总时间：1 秒）
15000: RS length:56130成功生成（总时间：2 秒）
20000: RS length:77338成功生成（总时间：3 秒）
99999: RS length:456569成功生成（总时间：1 分钟 41 秒）
public static void compBigInteger(int jc){ BigInteger bigi = BigInteger.ONE; BigInteger temp = null; for(int i=2;i<=jc;i++){ temp = new BigInteger(i+""); bigi = bigi.multiply(temp); } String rs = bigi.toString(); //System.out.println(rs); System.out.println(jc + ": RS length:"+rs.length()); } public static void main(String[] ars) { compBigInteger(99999); }
[解决办法]
膜拜一下撒
[解决办法]
up............
[解决办法]
C# Java 这些非原生的东西还最求什么效率，效率不是这些语言的优势，稳定安全才是它们的优势，有这样的结果应该很正常.什么东西都不可能是最好的。
[解决办法]
学习一下。
[解决办法]
学习了.
[解决办法]