模板
教程
環境
性能
功能
管理
求算大數（比如100）階乘的思路
如題~~ DX們指點指點啊~~:m01: 財產已凍結 回復于：2004-04-26 00:54:59 頂上去~~順便撈一分~~：） uiibono 回復于：2004-04-26 08:47:49 [quote:5e8a88d9b4="財產已凍結"]如題~~ DX們指點指點啊~~:m01:[/quote:5e8a88d9b4] 按定義算就行了，用迭代法。 para
如題~~
DX們指點指點啊~~ :m01:
| 財產已凍結 回復于：2004-04-26 00:54:59 |
| 頂上去~~順便撈一分~~：） |
| uiibono 回復于：2004-04-26 08:47:49 |
| [quote:5e8a88d9b4="財產已凍結"]如題~~
DX們指點指點啊~~ :m01:[/quote:5e8a88d9b4] 按定義算就行了，用迭代法。 |
| parady 回復于：2004-04-26 10:22:02 |
| [quote:026b7ba8d5="uiibono"]
按定義算就行了，用迭代法。[/quote:026b7ba8d5] 這樣好像不行吧，太大了，會溢出的！ |
| henngy 回復于：2004-04-26 10:23:47 |
| 很容易的遞歸函數，，自己寫試試 |
| luopengxo 回復于：2004-04-26 10:51:14 |
| 遞歸 |
| 財產已凍結 回復于：2004-04-26 12:50:57 |
| [quote:b77a0de9a6="henngy"]很容易的遞歸函數，，自己寫試試[/quote:b77a0de9a6]
好像沒那么容易吧~~ 誰能給個完整的思路？ :em16: |
| 風中的楓葉 回復于：2004-04-26 13:19:41 |
| 仍然按定義算就行了，用迭代法，你用long double定義變量！ |
| sprinklexu 回復于：2004-04-26 18:33:06 |
| 定義一個一維數組，每一個數組元素代表一個10000的數
然后按照10000進一 如果覺得靜態數組麻煩還可以定義鏈表來解決。 |
| 財產已凍結 回復于：2004-04-26 19:24:51 |
| [quote:097709b9b9="風中的楓葉"]仍然按定義算就行了，用迭代法，你用long double定義變量！[/quote:097709b9b9]
long double太小了，仍會溢出的。 |
| 財產已凍結 回復于：2004-04-26 19:27:38 |
| [quote:cb761f37ea="sprinklexu"]定義一個一維數組，每一個數組元素代表一個10000的數
然后按照10000進一 如果覺得靜態數組麻煩還可以定義鏈表來解決。[/quote:cb761f37ea] 我也曾想過把結果存入一個數組中，數組中的每一個元素代表數字的每一位，可是實現起來比較困難，不知道從哪里下手。 :em16: |
| sprinklexu 回復于：2004-04-27 09:18:14 |
| 為什么要只顯示一位??？
一個元素顯示一個小于10000的數 這樣還可以減少數組的大小[/code] |
| lllll 回復于：2004-04-27 10:09:13 |
| 一個大數，例如，3284789421570324478324。用字符竄表示。以后的是不用多說了吧。 |
| clearcase/" target="_blank" >cc8829 回復于：2004-04-27 10:53:23 |
| 將大數字符串表示，按一定長度分段，比如說8位，每段分別參與運算，考慮段間進位和退位的問題，所有運算都做完之后，將所有運算結果再合成一個字符串，即是結果。 |
| chg.s 回復于：2004-04-27 11:36:22 |
| 下面的longint不是通用的長整數類，而是為了求階乘特別設計的，所以構造函數功能非常有限，也沒有重載operator*。不過對這個具體問題，夠用了。:p
[code:1:c8b4277ee4] #include <iostream> #include <iomanip> #include <vector> using namespace std; class longint { private: vector<int> iv; public: longint(void) { iv.push_back(1); } longint& multiply(const int &); friend ostream& operator<<(ostream &, const longint &); }; ostream& operator<<(ostream &os, const longint &v) { vector<int>::const_reverse_iterator iv_iter = v.iv.rbegin(); os << *iv_iter++; for ( ; iv_iter < v.iv.rend(); ++iv_iter) { os << setfill('0') << setw(4) << *iv_iter; } return os; } longint& longint::multiply(const int &rv) { vector<int>::iterator iv_iter = iv.begin(); int overflow = 0, product = 0; for ( ; iv_iter < iv.end(); ++iv_iter) { product = (*iv_iter) * rv; product += overflow; overflow = 0; if (product > 10000) { overflow = product / 10000; product -= overflow * 10000; } *iv_iter = product; } if (0 != overflow) { iv.push_back(overflow); } return *this; } int main(int argc, char **argv) { longint result; int l = 0; sscanf(argv[1], "%d", &l); for (int i = 2; i < l; ++i) { result.multiply(i); } cout << result << endl; return 0; }[/code:1:c8b4277ee4] 運行a.out 100得到99的階乘。 大致的想法就是用一個vector<int>來保存一個長整數。vector中的每一個元素保存長整數中的四位。 例如 3368230 保存為 iv[0]=8230, iv[1]=336。 這個數乘10的過程是： product=iv[0]*10=82300; overflow=product/10000=8; product-=overflow*10, product = 2300; ----Next loop product=iv[1]*10=3360; product += overflow, product = 3368; //overflow是低四位的乘積中萬位以上的數字 ----end 得到的結果是iv[0]=2300, iv[1]=3368 --> 33682300. |
| odin_free 回復于：2004-04-27 11:43:58 |
| 網上很多大數算法 找簡單的看看
多數是字符串的解決方法 |
| whyglinux 回復于：2004-04-27 11:46:12 |
| 很好。怎樣用C++解決實際問題，這就是一個生動的實例，特別值得C++學習者仔細研究。 |
| mirnshi 回復于：2004-04-27 12:33:36 |
| 找個數學庫，一切ok |
| flc1976 回復于：2004-04-27 16:04:54 |
| 給你一個
class DGDY{ int res=1; int factorial(int ii){ if ( ii!=1) res= ii* factorial(ii-1); return res; } } 用java編譯運行一下你就明白了。 |
| redspider 回復于：2004-04-27 18:02:32 |
| 計算這么大的數，做什么用的 |
| IaMaBoY 回復于：2004-04-28 08:46:50 |
| 網上的大數庫都是以科學計數表示的 怎么讓它全部顯示阿 |
| lijunyu 回復于：2004-05-01 11:24:15 |
| 降一個數表示為科學計數法的形式
NEe 如1024表示為1.024E3的形式 將前面的數值部分和后面的指數部分設為類的2個數據成員 重載+-*/=這些運算符 就可以解決了 |
| THEBEST 回復于：2004-05-01 12:29:27 |
| 錢能書上一練習：
[code:1:fdbd41766a]/* 可以把n!的結果放在數組中，數組中每個元素都表示n!值的一位. 對整數范圍內的n,求n!. 對于輸入的n想辦法晝精確地估計出n!所占的位數.就能確定數組元素的個數 可以將n!表示成10的次冪,即n!=10^M(10的M次方)則不小于M的最小整數就是 n!的位數，對該式兩邊取對數，有?=log10^n!即： M = log10^1+log10^2+log10^3...+log10^n 循環求和,就能算得M值，該M是n!的精確位數。 數組初始化時,令數組第一個元素(n!的第一位)為整數1,其余為0. 在數組中計算n!時是通過將數組中的值乘2,3,4,。。一直到乘n的方式得的 把數組的第一個元素看做是n!的最低位，最后一個元素看做是最高位。 */ #include <iostream> using namespace std; #include <cmath> #include <cstdlib> #include <iomanip> int getN(); //輸入n int getBitNum(int n); //求n!的位數 char *init(int size); void calc(char *a,int n); //求n! void display(char *a,int size); int main() { int n = getN(); int size = getBitNum(n); char *pa = init(size); calc(pa,n); display(pa,size); delete []pa; //note: } int getN() { int n; cout << "Please input n of n! : "; cin >> n; while(n < 0) { cout << "input error,again: "; cin >> n; } if(n == 0) exit(1); return n; } int getBitNum(int n) { double sum = 1.0; for(int i=1; i<=n; i++) sum += log10((long double)i); //參數為double &和long double& //不轉換重載函數不能解析 return int(sum); //不轉換會有warning } char * init(int size) { char *pa = new char[size]; if(!pa) { //n太大時考慮申請內存不成功情況的執行動作 cout << "too large factor of " << size << endl; exit(1); } pa[0] = 1; for(int i=1; i<size; i++) pa[i] = 0; return pa; } void calc(char *a, int n) { double bitcount = 1; int begin = 0; for(int i=2; i<=n; ++i) { long add = 0; //源為long and=0;由于and是C++關鍵字，所以出錯。 //故所有為add的源文為and.不小心的出錯點。 bitcount += log10((long double)i); if(a[begin] == 0) begin++; for(int j=begin; j<int(bitcount); ++j) { add += (i*a[j]); a[j] = char(add % 10); add /= 10; } } } void display(char *a, int size) { int bit = 0; for(int i=size-1; i>=0; i--) { if(bit % 50 == 0) cout << endl << "The" << setw(5) << (bit/50+1) << " \'s 50 bit: "; cout << int (a[i]); //思考：為什么需要進行顯式的整形轉換呢? bit++; } cout << endl; } [/code:1:fdbd41766a] |
| mzpvsww 回復于：2004-05-01 12:34:58 |
| 亂說，這個是要用鏈表分段算的，要不，100！你的機器早就game over了 |
| THEBEST 回復于：2004-05-01 14:22:32 |
| [quote:698961e0b5="mzpvsww"]亂說，這個是要用鏈表分段算的，要不，100！你的機器早就game over了[/quote:698961e0b5]什么意思? |
| mzpvsww 回復于：2004-05-01 14:59:30 |
| 你的機器可以容忍100！的大??？？？不會益出？？？ |
| THEBEST 回復于：2004-05-01 15:29:30 |
| 你有沒有看上面的程序???
并不是直接存儲啊,沒看到是用數組嗎? |
| hefish 回復于：2004-05-02 00:19:38 |
| 就是《數據結構》里面曾經說到的 分段乘法。
只要內存足夠，可以計算出n! |
| yardley 回復于：2004-05-14 17:29:22 |
| 我寫的程序。
name : factorial.c function: 計算階乘 memo : 使用數組來保存特大的運算結果 計算100000!耗費時間1400秒 使用特殊技巧以加快計算 |
| improgrammer 回復于：2004-05-21 13:00:29 |
| 給個用16進制顯示的程序：
N的大小不是問題， 我只分配了256字節來表示結果，N最大可取到(300)base10。 再大，多分配些字節就是了。 時間效率不是問題，很快的。 void print_base16(unsigned char *v,int size) { int i; printf("\n0X"); for(i=size-1;i>=0;--i) { if(v[i]) { break; } } for(;i>=0;--i) { printf("%02X",v[i]); } } int multiply(unsigned char *v,int size,int n) { int i,t=0; for(i=0;i<size;++i) { t += v[i] * n; v[i] = t & 0xFF; t >>= 8; } return t; } void factor(int n) { unsigned char v[256]; int i; for(i=0;i<256;++i)v[i]=0; v[0]=1; for(;n>0;--n) { if(multiply(v,256,n)) { printf("%i over flow!\n",n); break; } } print_base16(v,256); |
- 評論列表（網友評論僅供網友表達個人看法，并不表明本站同意其觀點或證實其描述）
-
