差一点就对了的100的阶乘问题

MyFreedom 2009-09-26 10:06:43
public class Factorial
{
static void Main()
{
int[] data = new int[200];
int digit = 1;//位数
data[1] = 1;

for (int i = 1; i <= 100; i++)
{
for (int j = 1; j < digit + 1; j++)
{
data[j] *= i; //先做每一位与i的乘积放在一个数组空间中
}

for (int j = 1; j <= 100; j++)
{
if (data[j] > 9)
{
for (int r = 1; r < digit+1; r++)
{
if (data[digit] > 9)
{
digit++;
}

data[j + 1] += data[j] / 10;
data[j] %= 10;
}
}
}

Console.Write("{0}!=", i);
for (int k = digit; k > 0; k--)
{
Console.Write(data[k]);
}

Console.Write("\n");
}

Console.ReadKey();

}

======================================================

这段代码在运行到71!的时候结果就开始不正确,第一位数为0,我想可能是位数的问题。但没找出来,高手们帮忙看看。
...全文
554 44 打赏 收藏 转发到动态 举报
写回复
用AI写文章
44 条回复
切换为时间正序
请发表友善的回复…
发表回复
MyFreedom 2009-09-30
  • 打赏
  • 举报
回复
谢谢各位的回帖,特别是cqsfd和sp1234两位。
写这段代码的初衷时想用最简单的方法来实现100的阶乘,并没有考虑通用性和执行效率问题。由于现在一些项目对于数据结构的应用也不是很多,所以一直对这方面比较淡视,惭愧。。。
535cheng110 2009-09-30
  • 打赏
  • 举报
回复
[Quote=引用 13 楼 sp1234 的回复:]
例如我们可以计算 5! * 50 ! * 100!,就可以这样测试:C# codeusing System;using System.Diagnostics;namespace ConsoleApplication2
{class Program
{staticvoid Main(string[] args)
{
Stopwatch sw=new Stopwatch();
sw.Start();
Console.WriteLine("5!*50!*100!={0}", BigInt.Factorial(5)* BigInt.Factorial(50)* BigInt.Factorial(100));
sw.Stop();
Console.WriteLine("共用时{0}毫秒", sw.Elapsed.Milliseconds);
Console.ReadKey();
}
}
}
[/Quote]

有个疑问,
掐的时间不对吧?仅仅看了毫秒?
应该是下面这样吧?
Console.WriteLine("共用时{0}毫秒", sw.Elapsed.TotalMilliseconds);
fpcc 2009-09-29
  • 打赏
  • 举报
回复
我自己测试过2000以内的。fpcfjf@126.com
fpcc 2009-09-29
  • 打赏
  • 举报
回复
如果想要找我,我有任意大小的数字求阶乘的,包括C和C#版。
ViewStates 2009-09-28
  • 打赏
  • 举报
回复
算法贴,速MARK。到时候来看
mohugomohu 2009-09-28
  • 打赏
  • 举报
回复
楼主你是想弄大数运算还是只是写个阶乘的算法啊?
阶乘的话用递归会好点
vesion 2009-09-28
  • 打赏
  • 举报
回复
唉。不太懂12楼的算法原理,能说能吗?
aimeast 2009-09-28
  • 打赏
  • 举报
回复
[Quote=引用 38 楼 cqsfd 的回复:]
引用 36 楼 aimeast 的回复:
给你看这个吧

http://download.codeplex.com/Project/Download/FileDownload.aspx?ProjectName=biginteger&DownloadId=42439&FileTime=128644106308600000&Build=15760

这位大哥,这段代码看得我头大,解释下代码原理如何?
大数运算,我也是才接触,找不到好资料参考,只是谈谈自己的一些想法。
[/Quote]

算了,你还是不要使用这个代码了。
这个代码里面存在严重bug,阅读完代码发现是一个思想错误。

大数思想就是模拟人在列竖式的时候的运算方式。不过要想运行速度快,还是有很多可以优化的地方的。
liaoyukun111 2009-09-28
  • 打赏
  • 举报
回复
这个还真的要关注
cqsfd 2009-09-28
  • 打赏
  • 举报
回复
[Quote=引用 36 楼 aimeast 的回复:]
给你看这个吧

http://download.codeplex.com/Project/Download/FileDownload.aspx?ProjectName=biginteger&DownloadId=42439&FileTime=128644106308600000&Build=15760
[/Quote]
这位大哥,这段代码看得我头大,解释下代码原理如何?
大数运算,我也是才接触,找不到好资料参考,只是谈谈自己的一些想法。
cqsfd 2009-09-28
  • 打赏
  • 举报
回复
于是我想到了用double型数组表示位数!
double型可以表示十进制数的308位!用每一个double,表示0-999......999(250个9),即一个double表示250位,可以大大提高算法执行效率,并进行更多位数的计算!一个double只占2个字节,1G空间可以有500000000个double的数组(空间是这么算的吧?C#能不能允许这么大的地址空间分配?),理论上就可以进行结果为50000000*250=125000000000位的大数的阶乘运算了!
aimeast 2009-09-28
  • 打赏
  • 举报
回复
给你看这个吧

http://download.codeplex.com/Project/Download/FileDownload.aspx?ProjectName=biginteger&DownloadId=42439&FileTime=128644106308600000&Build=15760
cqsfd 2009-09-28
  • 打赏
  • 举报
回复
29楼的方法提示了我。(29楼的代码我没有进行测试,有点懒,没测C/C++代码,但我认为效率是非常高的)
既然用int型数组,就应该物尽其用。int型能表示到20多亿,只用来表示0-9,太浪费了,可以用来表示0-99999,即数组中每一位int,表示大数的5位。在算法中,主要将
data[j + 1] += data[j] / 10;
data[j] %= 10;
改成 data[j + 1] += data[j] / 100000;
data[j] %= 100000;
算法执行的效率更高,表示的位数也越多!
既然int能表示20多亿,直接让每一位int表示0-99999999不行吗?不好意思,这是不行的。因为算法执行过程中,每一位都要进行乘法运算,若果某一位刚好表示到了99999999,再乘一个100000什么的,就溢出了!
所以用int型数组表示位数,也是不够大的!
cqsfd 2009-09-28
  • 打赏
  • 举报
回复
回过头来又看了一遍这个帖子,忽然明白了如何在普通PC上用C#来进行大数运算,得到的结果理论上可以达到上百万甚至上亿位,写出来和大家分享!
就拿这篇贴子算一个比较大的自然数的阶乘来说。
首先,从算法上来说,算一个大数阶乘,这篇帖子的算法基本上分为顺序计数和递归计算两种。
很多人想到递归,但递归真的不适合这里的大数运算。4,12,33楼的3种递归算法,我都进行了测试。33楼的算法有问题,只用double型可以表示308位的数,大了就不行的,思想上根本不可能进行大数运算的;12楼的方法,我算了1000!,耗时约1分半;4楼的方法,时间效率更高,我进行到3000!的测试,花费时间约2分半,但3000!结果也不过才9131位。再往下算,时间上根本就不允许了。
我用自己写的顺序执行的算法(其实完全是学习楼主的思想的,我只不过是帮他改正了一些小bug),扩大了数组范围,计算到了22000!,耗时约半分钟,计算到了85982位!
很明显,要进行大数计算,递归是不行的,楼主的基本思想才可以进行下去:用一个数组,数组中的每一位,表示大数中的一位。但正如12楼所说的,用int型数组的每一位,仅表示所求结果的大数的一位,是相当浪费的!这也限制也算法的效率!
hejunlong007 2009-09-28
  • 打赏
  • 举报
回复
public class Test2{
public static double all = 1d;

public static void main(String[] args){

Test2 a = new Test2();
System.out.println("this is test =="+a.getJiecheng(100));
}

public double getJiecheng(double a){

if(a == 1){
return 1;
}

all = a * getJiecheng(a-1);

return all;
}
}
pb_stu 2009-09-27
  • 打赏
  • 举报
回复
学习了
cqsfd 2009-09-27
  • 打赏
  • 举报
回复
Stopwatch sw = new Stopwatch();
sw.Start();
Factorial(400);
sw.Stop();
Console.WriteLine("共用时{0}毫秒", sw.Elapsed.Milliseconds);

Stopwatch sw1 = new Stopwatch();
sw1.Start();
Console.WriteLine("400!={0}", BigInt.Factorial(400));
sw1.Stop();
Console.WriteLine("共用时{0}毫秒", sw1.Elapsed.Milliseconds);
Console.ReadKey();
这是我的测试代码
  • 打赏
  • 举报
回复
不玩这个了,干正事喽!
cqsfd 2009-09-27
  • 打赏
  • 举报
回复
[Quote=引用 22 楼 sp1234 的回复:]
哦,还要改代码呀!

int[] data = new int[200];

改成

int[] data = new int[1000];


去测试一个算法的速度切实没有多大乐趣。多测试一些应用,例如测试 100!*29+50!*23!*37! 这样就先把应用说明白了。
[/Quote]
恩,是的,我刚接触工作不久,只是个小小的实习生...对实际应用都没什么概念。
  • 打赏
  • 举报
回复
[Quote=引用 21 楼 cqsfd 的回复:]
引用 20 楼 sp1234 的回复:
我们两个程序都打印同样的内容,仅仅去掉你的打印内容这不合适吧?!

另外,400!阶乘你在#9楼的代码能够运行?难道你在计算121!时不会出现异常“索引超出了数组界限。”吗?

我用你的代码  也是只打印最后结果啊
我把数组大小改了,改成1000位
[/Quote]

嗯,我的测试代码是:
            for (var i = 1; i <= 400; i++)
Console.WriteLine("{0}!={1}", i, BigInt.Factorial(i));

是打印每一个数的阶乘的。

或者是上面那种:
Console.WriteLine("5!*50!+100!={0}", BigInt.Factorial(5) * BigInt.Factorial(50) + BigInt.Factorial(100));

加载更多回复(24)

110,533

社区成员

发帖
与我相关
我的任务
社区描述
.NET技术 C#
社区管理员
  • C#
  • Web++
  • by_封爱
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告

让您成为最强悍的C#开发者

试试用AI创作助手写篇文章吧