| 财产已冻结 回复于：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。用字符窜表示。以后的是不用多说了吧。
|
| 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);
|
