计算三角数

Question

三角数是以下三个因素的乘积：

\text{Triangular number} = x(x + 1)(x + 2)

有办法让代码更快吗？实际上，代码计算小于或等于用户给定的整数的每个三角形数。

#include 

int main(void) {       

    int firstFactor = 0;
    int secondFactor = 1;
    int thirdFactor = 2;

    int userInput;
    int product = 0;

    printf("Enter a integer: ");
    scanf("%d", &userInput);

    if(userInput == 0) {
        printf("User input is a triangular number\n");
        return 0;
    }

    do {
        firstFactor++;
        secondFactor++;
        thirdFactor++;
        product = firstFactor * secondFactor * thirdFactor;
    } while(product < userInput);

    if(product == userInput) {
        printf("User input is a triangular number\n");
    } else {
        printf("User input is not a triangular number\n");
    }
    return 0;
}

Answer 1

我看到了几种加快速度的方法。

请注意，至少有一个因子是偶数，而恰恰有一个因子是3的倍数，因此这些数字都可以被6整除。假设随机输入，在开始时对此进行测试将在6个案例中的5个实例中找到一个廉价操作的答案：

if (userInput % 6) {
    printf("User input is not a triangular number\n");
    return 0;
}

至于其余部分，如果设n=x+ 1，则得到

T(n-1)=(n-1)(n)(n+1)=n^3-n

因此，我们可以在O(1)时间内求解，尽管多维数据集根是一个比较昂贵的操作：

#include     /* Link with -lm in gcc */

int n;

n = (int) (ceil(cbrt(userInput)) + 0.1);
if (n * (n-1) * (n+1) == userInput)
    printf("User input is a triangular number\n");
else
    printf("User input is not a triangular number\n");

我们在ceil之后添加D4，因为double值可能类似于6.9999999999759，当转换为int时，它会舍入错误的数字。(int)强制转换禁止编译器警告从double到int的转换。

Answer 2

这似乎是一次相当有能力的尝试。很清楚它是如何工作的。我有一些观察或改进：

• 使用scanf() (或其他方式)读取输入时，必须检查错误。在这种情况下，我们只需要确保返回值(进行转换的次数)为1(即scanf()已分配给userInput)：if (scanf("%d“&userInput) != 1) { fprintf(stderr，”用户输入不是数字！\n“)；返回1；}
• 我们是否应该接受负面的输入？我认为最好使用unsigned int，只要求用户获得正值。
• 对于这些因素，我们并不需要三个变量。由于secondFactor总是等于firstFactor+1，而thirdFactor总是等于firstFactor+2，所以我们可以用以下表达式替换它们: do { firstFactor++；积= firstFactor * (firstFactor + 1) * (firstFactor + 2)；}while(积< userInput)；我可以重写为for循环，因为存在增量步骤(firstFactor++;)。
• 小心算术溢出--如果输入接近INT_MAX (或移动到无符号类型后的UINT_MAX )，那么product可能会超过整数类型的限制--对于有符号类型来说尤其糟糕，因为溢出是未定义的行为。我们可能希望确保没有达到这个限制，或者使用比int更广泛的D22类型(如果存在-- long long int可以是相同的大小)，或者使用限制的立方根测试产品(可能使用中的cbrt() )。
• 我们不需要对userInput == 0进行特殊的测试。如果我们在增量product之前计算firstFactor，那么循环的第一次迭代将生成0。
• 我们可以通过格式化测试数字作为输出的一部分来改进打印。

修改代码

#include 

int main(void)
{
    printf("Enter an integer: ");

    unsigned int userInput;
    if (scanf("%u", &userInput) != 1) {
        fprintf(stderr, "User input is not a number!\n");
        return 1;
    }

    /* avoid overflow by dividing input by one of the factors */
    for (unsigned int firstFactor = 0;  firstFactor * (firstFactor + 1) <= userInput / (firstFactor + 2);  ++firstFactor) {
        if (userInput == firstFactor * (firstFactor + 1) * (firstFactor + 2)) {
            printf("%u is a triangular number\n", userInput);
            return 0;
        }
    }

    printf("%u is not a triangular number\n", userInput);
    return 0;
}