时间戳

首页 > 解决方案 > 我的程序太慢了

c++ - 我的程序太慢了

问题描述

我是编程初学者，我正在学习一门 C++ 语言。

我必须创建一个程序，首先加载一定数量的数字，然后再加载数字。如果它们不是 2 的幂，我需要得到一个一个一个相加的结果，否则我需要减去这个数字。

例如：对于 3，结果是 = -1 - 2 + 3 = 0（1 和 2 是 2 的幂）对于 4，结果是 = -1 - 2 + 3 - 4 = -4

听起来这不是问题，但是程序必须转换为结果的最大值是 1 000 000 000。它必须在 3 秒内给出结果。

我在下面粘贴我的代码。请帮助我在短时间内转换大量数字的能力。

#include <iostream>

using namespace std;

int main()
{
    long long amount, number, i = 0, a, b, result = 0;

    cin >> amount;

    while (i < amount) {
        cin >> number;

        if (number < 100000000) {
            a = 1;
            result = 0;
        } else if (100000000 <= number) {
            a = 100000001;
            result = 4999999791564546;
        }

        while (a <= number) {
            b = a;

            while (b % 2 == 0 && b > 1) {
                b = b / 2;
            }

            if (b == 1) {
                result = result - a;
            } else {
                result = result + a;
            }

            a++;
        }

        cout << result << endl;
        i++;
    }
}

标签： c++while-loop

解决方案

所有学分都归昆汀所有。我提出了同样的想法，但昆汀首先提到了，所以所有的功劳都归他所有。

在所有这些竞争激烈的编程挑战中，您会看到大量数字和时间限制，“蛮力”或“循环遍历所有内容”肯定不会产生预期的结果。

一个好的算法总是更好的解决方案。

所以查看任务，我们需要添加除一些之外的所有值。这意味着，解决方案的第一步是添加所有值，然后减去“一些不需要的”值（2 的幂）。中间结果是所有“想要的”值的总和。

还需要添加所有不需要的值（2 的幂）。

最终结果是中间结果减去 2 的幂的总和。或者，正如任务描述中用混淆的词所述：“所有值的总和”-“2 的幂和”-“2 的幂和” .

因此，作为第 1 步，我们需要计算所有值的总和。这是一个众所周知的算法。你到处都可以找到。值 6 的简短说明：

123456
654321
------
777777

因此，我们在一行中写入值的序列，在下一行中写入相反的序列。最后一行总结了单个数字。而且，我们将很容易看到这种模式：n * (n+1) / 2

2 的幂和类似简单。在二进制数系统中，2 的幂是一个只有一个设置位的值：

 1 = 0001
 2 = 0010
 4 = 0100
 8 = 1000
---------
Sum: 1111

总和是所有位都设置的值。通过一些简单的摆弄，我们可以很容易地找到解决方案。

请在下面查看完整的工作解决方案。请注意：它会非常快，输入值对计算时间几乎没有影响。

#include <iostream>
#include <algorithm>

constexpr unsigned long MaxSource = 1000000000UL;

int main()
{
    // Get the Base value from the user
    std::cout << "Enter a number (1..1000000000):\n";

    unsigned long sourceNumber {0};
    std::cin >> sourceNumber;

    // Limit input value
    sourceNumber = std::clamp (sourceNumber, 1UL, MaxSource);

    // calculate the sum of all values in the range 1..sourceNumber
    const long long t1 {static_cast<long long>(sourceNumber)};
    const long long t2 {t1+1};
    const long long sum1 { (t1 * t2) >> 1 };

    // Now calculate the sum of all powers of 2
    long long sum2 {0x00000000'FFFFFFFF};
    long long bitTestMask {0x00000000'80000000};

    // find the highest set bit
    while (0 == (t1 & bitTestMask)) {
        bitTestMask = bitTestMask >> 1;
        sum2 = sum2  >> 1;
    }

    std::cout << "Result:  " << sum1 - sum2 - sum2 << "\n";

    return 0;
}

我省略了典型的竞争性程序多个测试用例的东西。

可惜没有人会读到这个。. .

推荐阅读