关于求100以内的任何数的阶乘的问题,求算法思路,不需要现成的代码。谢谢

时间:2021-08-09 00:22:21
要求100以内任何数的阶乘,要求最后结果以字符串的形式输出,请大家帮我想想思路,应该怎么入手解决,不需要现成的代码,想自己动手来写。。谢谢大家

18 个解决方案

#1


这个涉及到超长数字相乘,可以通过把乘数拆成独立的个数去乘被乘数,然后进行超长字数相加。
我以前是写的两个字符串相加相乘的函数。不知道能不能帮到你。这道题比看着要费功夫,不知道还有没有更简单的办法。

#2


用递归,比如计算n!,可以是n乘上(n-1)!,计算(n-1)!,可以是n-1乘上(n-2)!,依次类推,知道n=1时返回……

#3


阶乘可以用回归法,n!=n(n-1)

#4


一看1楼的解答,才知道我的答案不对,比较离谱,不好意思啦~~~

#5


我没思路,只有代码,还不是现成的:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int COMPARE(string number1, string number2) {
    int i,j;

    int length1 = number1.size();
    int length2 = number2.size();

    if(number1.size() == 0) number1 = "0";
    if(number2.size() == 0) number2 = "0";

    j = 0;
    for(i = 0; i < length1; ++i) {
        if(number1[i] == '0') ++j;
        else break;
    }
    number1 = number1.substr(j);

    j = 0;
    for(i = 0; i < length2; ++i) {
        if(number2[i] == '0') ++j;
        else break;
    }
    number2 = number2.substr(j);

    length1 = number1.size();
    length2 = number2.size();

    if(length1 > length2) {
        return 1;
    } else if(length1 == length2) {
        if(number1.compare(number2) > 0) {
            return 1;
        } else if(number1.compare(number2) == 0) {
            return 0;
        } else {
            return -1;
        }
    } else {
        return -1;
    }

    return 0;
}
string PLUS(string number1,string number2) {
    int i;
    int length1 = number1.size();
    int length2 = number2.size();

    string result="";

    reverse(number1.begin(), number1.end());
    reverse(number2.begin(), number2.end());

    for(i = 0; i < length1 && i < length2; i++) {
        char c = (char)(number1[i] + number2[i] - 48);
        result = result + c;
    }

    while(i < length1) {
        result = result + number1[i];
        ++i;
    }

    while(i < length2) {
        result = result + number2[i];
        ++i;
    }

    int carry = 0;
    for(i = 0; i < (int)result.size(); ++i) {
        int value = result[i] - 48 + carry;
        result[i] = (char)(value % 10 + 48);
        carry = value / 10;
    }

    if(carry !=0 ) {
        result = result + (char)(carry + 48);
    }

    for(i = result.size() - 1; i >= 0; i--) {
        if(result[i] != '0') break;
    }

    result = result.substr(0, i + 1);

    reverse(result.begin(), result.end());
    if(result.length() == 0) result = "0";
    return result;
}
string MINUS(string number1,string number2) {
    int i;
    string result = "";

    int length1 = number1.size();
    int length2 = number2.size();

    if(COMPARE(number2,number1) > 0) {
        return "-" + MINUS(number2, number1);
    }

    reverse(number1.begin(),number1.end());
    reverse(number2.begin(),number2.end());

    for(i = 0; i < length1 && i < length2; i++) {
        char c = number1[i] - number2[i] + 48;
        result = result + c;
    }

    if(i < length1) {
        for(; i < length1; i++) {
            result = result + number1[i];
        }
    }

    int carry = 0;
    for(i = 0; i < (int)result.length(); i++) {
        int value = result[i] - 48 + carry;
        if(value < 0) {
            value = value + 10;
            carry = -1;
        } else carry = 0;
        result[i]=(char)(value + 48);
    }

    for(i = result.size() - 1; i >= 0; i--) {
        if(result[i] != '0')break;
    }

    result = result.substr(0, i+1);

    reverse(result.begin(), result.end());
    if(result.length()==0) result = "0";
    return result;
}
string MULTIPLY(string number1, string number2) {
    int i, j;
    int *iresult;
    int length1 = number1.size();
    int length2 = number2.size();
    string result = "";

    reverse(number1.begin(), number1.end());
    reverse(number2.begin(), number2.end());

    iresult = (int*)malloc(sizeof(int) * (length1 + length2 + 1));
    memset(iresult, 0, sizeof(int) * (length1 + length2 + 1));

    for(i = 0; i < length1; i++) {
        for(j = 0; j < length2; j++) {
            iresult[i+j] += ((number1[i] - 48) * (number2[j] - 48));
        }
    }

    int carry = 0;
    for(i = 0; i < length1 + length2; i++) {
        int value = iresult[i] + carry;
        iresult[i] = value % 10;
        carry = value / 10;
    }

    for(i = length1 + length2 - 1; i >= 0; i--) {
        if(iresult[i] != 0)break;
    }

    for(; i >= 0; i--) {
        result = result + (char)(iresult[i]+48);
    }

    free(iresult);

    if(result == "") result = "0";
    return result;
}
string factorial(string n) {
    string temp = "1";
    string i;
    for(i = "1"; COMPARE(i, n) <= 0; i = PLUS(i, "1")) {
        temp = MULTIPLY(temp, i);
    }
    return temp;
}
int main(void) {
    cout << factorial("100") << endl;
    return 0;
}

#6


核心就是用int数组替代int或者long,自己实现基于int数组的数学运算。

#7


6楼正解。以前曾做过类似的东西。

#8


引用 1 楼 m13890 的回复:
这个涉及到超长数字相乘,可以通过把乘数拆成独立的个数去乘被乘数,然后进行超长字数相加。
我以前是写的两个字符串相加相乘的函数。不知道能不能帮到你。这道题比看着要费功夫,不知道还有没有更简单的办法。
不太明白您的意思。。能不能举个例子说明一下,比如20!要怎么实现

#9


引用 6 楼 ForestDB 的回复:
核心就是用int数组替代int或者long,自己实现基于int数组的数学运算。
能不能说得具体一点,比如我定义一个int a[10],我把结果要存在这个数组中,我怎么决定每个a[n]的值?谢谢

#10


我知道怎么做。我做过类似的,100的阶乘如果用int来存储应该会溢出,这时得想办法构建一个大数类,然后实现大数类的乘法运算,当然,这个大数类是以字符串来做为输入的,这样就不怕溢出了

#11


大数乘法,算法参考小学三、四年级乘法竖式。

#12


1234
×    4
--------
??

#13


将阶乘化成质因数幂的乘积(数论里的东西,记不清具体公式了),质因数幂使用快速幂算法求。然后就是考虑使用数组存储这个超长的结果了。使用这种方法,在1s内求10万以内任何一个数阶乘都不是问题。

#14


根据斯特林公式算一下大约157位,我上次写了个3的200次幂,里面那个类可以拿来用,可以参考下

#15


这里的重点是考大数计算。自己用数组来模拟大数字,比如10的100次方,就用int a[101]来表示,a[0]=a[1]=...=a[99]=0,a[100]=1

这样就解决了数字表达的问题,接下来就是解决新的数字表达的计算,主要是加法和乘法,回忆一下小学的竖式计算,一个个数字去计算,处理好进位就ok

#16


可以用数据拼接
int a[10];
a[0]表示个位到万位的数字
a[1]表示万位到亿位的数字
....

#17


用数组来模拟小学数学乘法的过程

#18


觉得15楼说的靠谱 关于求100以内的任何数的阶乘的问题,求算法思路,不需要现成的代码。谢谢

#1


这个涉及到超长数字相乘,可以通过把乘数拆成独立的个数去乘被乘数,然后进行超长字数相加。
我以前是写的两个字符串相加相乘的函数。不知道能不能帮到你。这道题比看着要费功夫,不知道还有没有更简单的办法。

#2


用递归,比如计算n!,可以是n乘上(n-1)!,计算(n-1)!,可以是n-1乘上(n-2)!,依次类推,知道n=1时返回……

#3


阶乘可以用回归法,n!=n(n-1)

#4


一看1楼的解答,才知道我的答案不对,比较离谱,不好意思啦~~~

#5


我没思路,只有代码,还不是现成的:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int COMPARE(string number1, string number2) {
    int i,j;

    int length1 = number1.size();
    int length2 = number2.size();

    if(number1.size() == 0) number1 = "0";
    if(number2.size() == 0) number2 = "0";

    j = 0;
    for(i = 0; i < length1; ++i) {
        if(number1[i] == '0') ++j;
        else break;
    }
    number1 = number1.substr(j);

    j = 0;
    for(i = 0; i < length2; ++i) {
        if(number2[i] == '0') ++j;
        else break;
    }
    number2 = number2.substr(j);

    length1 = number1.size();
    length2 = number2.size();

    if(length1 > length2) {
        return 1;
    } else if(length1 == length2) {
        if(number1.compare(number2) > 0) {
            return 1;
        } else if(number1.compare(number2) == 0) {
            return 0;
        } else {
            return -1;
        }
    } else {
        return -1;
    }

    return 0;
}
string PLUS(string number1,string number2) {
    int i;
    int length1 = number1.size();
    int length2 = number2.size();

    string result="";

    reverse(number1.begin(), number1.end());
    reverse(number2.begin(), number2.end());

    for(i = 0; i < length1 && i < length2; i++) {
        char c = (char)(number1[i] + number2[i] - 48);
        result = result + c;
    }

    while(i < length1) {
        result = result + number1[i];
        ++i;
    }

    while(i < length2) {
        result = result + number2[i];
        ++i;
    }

    int carry = 0;
    for(i = 0; i < (int)result.size(); ++i) {
        int value = result[i] - 48 + carry;
        result[i] = (char)(value % 10 + 48);
        carry = value / 10;
    }

    if(carry !=0 ) {
        result = result + (char)(carry + 48);
    }

    for(i = result.size() - 1; i >= 0; i--) {
        if(result[i] != '0') break;
    }

    result = result.substr(0, i + 1);

    reverse(result.begin(), result.end());
    if(result.length() == 0) result = "0";
    return result;
}
string MINUS(string number1,string number2) {
    int i;
    string result = "";

    int length1 = number1.size();
    int length2 = number2.size();

    if(COMPARE(number2,number1) > 0) {
        return "-" + MINUS(number2, number1);
    }

    reverse(number1.begin(),number1.end());
    reverse(number2.begin(),number2.end());

    for(i = 0; i < length1 && i < length2; i++) {
        char c = number1[i] - number2[i] + 48;
        result = result + c;
    }

    if(i < length1) {
        for(; i < length1; i++) {
            result = result + number1[i];
        }
    }

    int carry = 0;
    for(i = 0; i < (int)result.length(); i++) {
        int value = result[i] - 48 + carry;
        if(value < 0) {
            value = value + 10;
            carry = -1;
        } else carry = 0;
        result[i]=(char)(value + 48);
    }

    for(i = result.size() - 1; i >= 0; i--) {
        if(result[i] != '0')break;
    }

    result = result.substr(0, i+1);

    reverse(result.begin(), result.end());
    if(result.length()==0) result = "0";
    return result;
}
string MULTIPLY(string number1, string number2) {
    int i, j;
    int *iresult;
    int length1 = number1.size();
    int length2 = number2.size();
    string result = "";

    reverse(number1.begin(), number1.end());
    reverse(number2.begin(), number2.end());

    iresult = (int*)malloc(sizeof(int) * (length1 + length2 + 1));
    memset(iresult, 0, sizeof(int) * (length1 + length2 + 1));

    for(i = 0; i < length1; i++) {
        for(j = 0; j < length2; j++) {
            iresult[i+j] += ((number1[i] - 48) * (number2[j] - 48));
        }
    }

    int carry = 0;
    for(i = 0; i < length1 + length2; i++) {
        int value = iresult[i] + carry;
        iresult[i] = value % 10;
        carry = value / 10;
    }

    for(i = length1 + length2 - 1; i >= 0; i--) {
        if(iresult[i] != 0)break;
    }

    for(; i >= 0; i--) {
        result = result + (char)(iresult[i]+48);
    }

    free(iresult);

    if(result == "") result = "0";
    return result;
}
string factorial(string n) {
    string temp = "1";
    string i;
    for(i = "1"; COMPARE(i, n) <= 0; i = PLUS(i, "1")) {
        temp = MULTIPLY(temp, i);
    }
    return temp;
}
int main(void) {
    cout << factorial("100") << endl;
    return 0;
}

#6


核心就是用int数组替代int或者long,自己实现基于int数组的数学运算。

#7


6楼正解。以前曾做过类似的东西。

#8


引用 1 楼 m13890 的回复:
这个涉及到超长数字相乘,可以通过把乘数拆成独立的个数去乘被乘数,然后进行超长字数相加。
我以前是写的两个字符串相加相乘的函数。不知道能不能帮到你。这道题比看着要费功夫,不知道还有没有更简单的办法。
不太明白您的意思。。能不能举个例子说明一下,比如20!要怎么实现

#9


引用 6 楼 ForestDB 的回复:
核心就是用int数组替代int或者long,自己实现基于int数组的数学运算。
能不能说得具体一点,比如我定义一个int a[10],我把结果要存在这个数组中,我怎么决定每个a[n]的值?谢谢

#10


我知道怎么做。我做过类似的,100的阶乘如果用int来存储应该会溢出,这时得想办法构建一个大数类,然后实现大数类的乘法运算,当然,这个大数类是以字符串来做为输入的,这样就不怕溢出了

#11


大数乘法,算法参考小学三、四年级乘法竖式。

#12


1234
×    4
--------
??

#13


将阶乘化成质因数幂的乘积(数论里的东西,记不清具体公式了),质因数幂使用快速幂算法求。然后就是考虑使用数组存储这个超长的结果了。使用这种方法,在1s内求10万以内任何一个数阶乘都不是问题。

#14


根据斯特林公式算一下大约157位,我上次写了个3的200次幂,里面那个类可以拿来用,可以参考下

#15


这里的重点是考大数计算。自己用数组来模拟大数字,比如10的100次方,就用int a[101]来表示,a[0]=a[1]=...=a[99]=0,a[100]=1

这样就解决了数字表达的问题,接下来就是解决新的数字表达的计算,主要是加法和乘法,回忆一下小学的竖式计算,一个个数字去计算,处理好进位就ok

#16


可以用数据拼接
int a[10];
a[0]表示个位到万位的数字
a[1]表示万位到亿位的数字
....

#17


用数组来模拟小学数学乘法的过程

#18


觉得15楼说的靠谱 关于求100以内的任何数的阶乘的问题,求算法思路,不需要现成的代码。谢谢