大数n的阶乘

1 /***************************************************************************************************/
2 /*  Copyright (C) 2008  Chipset
3 /*
4 /*  This program is free software: you can redistribute it and/or modify
5 /*  it under the terms of the GNU Affero General Public License as
6 /*  published by the Free Software Foundation, either version 3 of the
7 /*  License, or (at your option) any later version.
8 /*
9 /*  but WITHOUT ANY WARRANTY; without even the implied warranty of
10 /*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 /*  GNU Affero General Public License for more details.
12 /*
13 /*  You should have received a copy of the GNU Affero General Public License
14 /*  along with this program. If not, see <http://www.gnu.org/licenses/>.
15 /****************************************************************************************************/
16
17 #include <iostream>
18 #include <vector>
19 void cal_factorial(std::vector<int>& a, int n)
20 {
21   int carry = 0;
22   a.push_back(1);
23   int tmp;
24
25   for(int i = 2; i <= n; ++i)
26   {
27     for(int j = 0; j < a.size(); ++j)
28     {
29       tmp = a[j] * i + carry;
30       a[j] = tmp % 10;
31       carry = tmp / 10;
32     }
33     while(carry)
34     {
35       a.push_back(carry % 10);
36       carry /= 10;
37     }
38   }
39 }
40
41 void show_factorial(const std::vector<int>& v, int n)
42 {
43   for(int i = v.size() - 1; i > -1; --i)
44   std::cout << v[i];
45 }
46
47 //测试
48 #include <windows.h>
49 int main()
50 {
51   int n;
52   do{
53     std::cout << "Input a number(greater than 0) for factorial:\n";
54     std::cin >> n;
55     if(n < 0)
56     std::cout << "Must be greater than 0\n";
57   }while(n < 0);
58   Sleep(1000);
59   std::vector<int> v;
60   DWORD time = GetTickCount();
61   cal_factorial(v, n);
62   time = GetTickCount() - time;
63   std::cout << n << "! is as long as " << v.size() << " bit(s). " << n << "! ==\n" ;
64   show_factorial(v, n);
65   std::cout << "\ncalculating " << n << "! used " << time << " ms, memory used: "
66                 << v.size()* sizeof(int) << " bytes.\n";
67   system("pause");
68   return 0;
69 }
以上算法速度比较慢，仅仅供初学者参考，更快的版本在这里http://www.cppblog.com/Files/Chipset/Factorial.zip

posted on 2009-01-01 18:50 Chipset 阅读(342) 评论(4) 编辑收藏引用所属分类: 算法和数据结构

Feedback

# re: 大数n的阶乘 2009-01-22 16:04 nk_ysg

基数不应该选10，应该选大一点比如10000，加快运算回复更多评论

# re: 大数n的阶乘 2009-02-06 12:45 Chipset

@nk_ysg
谢谢，有空我再看看。回复更多评论

# re: 大数n的阶乘 2009-04-07 21:00 祝你好运

@nk_ysg
确实是应该选取10000(可以考虑100000)，这样在计算比较大的n！时很快。但是用__int64和10000000000这样的数的效率却反而变慢了。
我试过。回复更多评论

# re: 大数n的阶乘 2009-04-09 20:17 Chipset

谢谢楼上的朋友，其实关于n的阶乘问题我感觉没有必要再去研究，因为这是一个算法的数学问题，不是程序问题，仅仅靠增大基数可能是不够的。别人已经写过一个很快的大数n的阶乘了，如果再想超越很难很难。在这里可以下再测试：http://www.cppblog.com/Files/Chipset/Factorial.zip 回复更多评论

刷新评论列表