3

我需要在不使用乘法运算符的情况下计算数字的阶乘。因为这个限制，我直接尝试使用重复加法。它有点工作。但是，我的程序正在努力获得更大数字的阶乘。有没有更好的方法来解决问题？

这是我的代码：

void main(){
     unsigned long num = 0, ans = 1, temp = 1;

    printf("Enter a number: ");
    scanf("%lu", &num);

    while (temp <= num){
        int temp2 = 0, ctr = 0;
        while (ctr != temp){
            temp2 += ans;
            ctr ++;
        }
        ans = temp2;
        temp ++;
    }

    printf("%lu! is %lu\n", num, ans);
}
4

2 回答 2

4

您可以使用位移和加法来实现更快（比重复加法）的乘法函数，以在二进制中执行“长乘法”。

unsigned long long mul_ull(unsigned long long a, unsigned long long b)
{
    unsigned long long product = 0;
    unsigned int shift = 0;

    while (b)
    {
        if (b & 1)
        {
            product += a << shift;
        }
        shift++;
        b >>= 1;
    }
    return product;
}

编辑：使用单个位移和加法的上述替代实现：

unsigned long long mul_ull(unsigned long long a, unsigned long long b)
{
    unsigned long long product = 0;

    while (b)
    {
        if (b & 1)
        {
            product += a;
        }
        a <<= 1;
        b >>= 1;
    }
    return product;
}

实际上，这是否比重复添加更快取决于编译器所做的任何优化。优化编译器可以分析重复的加法并将其替换为乘法。优化编译器还可以分析上述mul_ull函数的代码并将其替换为乘法，但这对于优化器来说可能更难发现。所以在实践中，重复加法算法最终比优化后的位移加法算法更快是完全合理的！

此外，如果第二个参数是当其中一个数字远大于另一个时被相乘的数字中的较小者（这对于阶乘计算来说是典型的），则函数的上述实现mul_ull往往会执行得更好。b执行时间大致与 的对数b（何时b为非零）成正比，但也取决于 的二进制值中 1 位的数量b。因此对于阶乘计算，将旧运行产品放在第一个参数中a，将新因子放在第二个参数b中。

使用上述乘法函数的阶乘函数：

unsigned long long factorial(unsigned int n)
{
    unsigned long long fac = 1;
    unsigned int i;

    for (i = 2; i <= n; i++)
    {
        fac = mul_ull(fac, i);
    }
    return fac;
}

由于算术溢出，上述factorial函数可能会在大于 20 时产生不正确的结果。n需要 66 位来表示 21！但unsigned long long只需要 64 位宽（这通常是大多数实现的实际宽度）。

于 2021-01-11T11:40:58.917 回答
0

对于较大的 值n，需要大格式。
由于您不能使用乘法，因此您必须自己实现它似乎是合乎逻辑的。
实际上，由于只需要添加，因此如果我们不寻求高效率，则实施起来并不困难。

无论如何都有一点困难：您必须将输入整数转换为数字数组。由于我猜不允许模数，我在snprintf函数的帮助下实现了它。

结果：

100! is 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

注意：此结果是即时提供的。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NDIGITS     1000        // maximum number of digits

struct MyBig {
    int digits[NDIGITS + 2];        // "+2" to ease overflow control
    int degree;
};

void reset (struct MyBig *big) {
    big->degree = 0;
    for (int i = 0; i <= NDIGITS; ++i) big->digits[i] = 0;
}

void create_with_div (struct MyBig *big, int n) {  // not used here
    reset (big);
    while (n != 0) {
        big->digits[big->degree++] = n%10;
        n /= 10;
    }
    if (big->degree != 0) big->degree--;
}

void create (struct MyBig *big, int n) {
    const int ND = 21;
    char dig[ND];
    snprintf (dig, ND, "%d", n);
    int length = strlen (dig);
    
    reset (big);
    big->degree = length - 1;
    for (int i = 0; i < length; i++) {
        big->digits[i] = dig[length - 1 - i] - '0';
    }
}

void print (struct MyBig *big) {
    for (int i = big->degree; i >= 0; --i) {
        printf ("%d", big->digits[i]);
    }
}

void accumul (struct MyBig *a, struct MyBig *b) {
    int carry_out = 0;
    for (int i = 0; i <= b->degree; ++i) {
        int sum = carry_out + a->digits[i] + b->digits[i];
        if (sum >= 10) {
            carry_out = 1;
            a->digits[i] = sum - 10;
        } else {
            carry_out = 0;
            a->digits[i] = sum;
        }
    }
    int degree = b->degree;
    while (carry_out != 0) {
        degree++;
        int sum = carry_out + a->digits[degree];
        carry_out = sum/10;
        a->digits[degree] = sum % 10;
    }
    if (a->degree < degree) a->degree = degree;
    if (degree > NDIGITS) {
        printf ("OVERFLOW!!\n");
        exit (1);
    }
}

void copy (struct MyBig *a, struct MyBig *b) {
    reset (a);
    a->degree = b->degree;
    for (int i = 0; i <= a->degree; ++i) {
        a->digits[i] = b->digits[i];
    }
}

void fact_big (struct MyBig *ans, unsigned int num) {
    create (ans, 1);
    int temp = 1;
    while (temp <= num){
        int ctr = 0;
        struct MyBig temp2;
        reset (&temp2);
        while (ctr != temp){
            accumul (&temp2, ans);
            ctr ++;
        }
        copy (ans, &temp2);
        temp ++;
    }
    return;
}

unsigned long long int fact (unsigned int num) {
    unsigned long long int ans = 1;
    int temp = 1;
    while (temp <= num){
        int ctr = 0;
        unsigned long long int temp2 = 0;
        while (ctr != temp){
            temp2 += ans;
            ctr ++;
        }
        ans = temp2;
        temp ++;
    }
    return ans;
}

void main(){
    unsigned long long int ans;
    unsigned int num;
    
    printf("Enter a number: ");
    scanf("%u", &num);
    
    ans = fact (num);
    printf("%u! is %llu\n", num, ans);
    
    struct MyBig fact;
    fact_big (&fact, num);
    printf("%u! is ", num);
    print (&fact);
    printf ("\n");
}
于 2021-01-11T16:00:56.150 回答