c# – 获得n下面每个数字的总和

发布时间：2020-12-15 18:34:40 所属栏目：百科来源：网络整理

导读：这是我的代码,但它要慢,任何方式更快地做到这一点.. 我打的数字范围是123456789,但我不能低于15秒,我需要它低于5秒.. long num = 0;for (long i = 0; i = n; i++){ num = num + GetSumOfDigits(i);}static long GetSumOfDigits(long n){ long num2 = 0; long

这是我的代码,但它要慢,任何方式更快地做到这一点..
我打的数字范围是123456789,但我不能低于15秒,我需要它低于5秒..

long num = 0;

for (long i = 0; i <= n; i++)
{
    num = num + GetSumOfDigits(i);
}

static long GetSumOfDigits(long n)
{
    long num2 = 0;
    long num3 = n;
    long r = 0;
    while (num3 != 0)
    {
        r = num3 % 10;
        num3 = num3 / 10;
        num2 = num2 + r;
    }

    return num2;
}

sum =(n(n 1))/ 2不给我我需要的结果,不能正确计算..

对于N = 12,总和是1 2 3 4 5 6 7 8 9(1 0)(11)(1 2)= 51.
我需要用公式而不是循环来做这个.

我在大约6秒内完成了大约15次测试.

并行我从15秒到4-8秒进行了一次测试..

只是为了向你展示我正在做的测试是很难的…

[Test]
public void When123456789_Then4366712385()
{
   Assert.AreEqual(4366712385,TwistedSum.Solution(123456789));
}

在我的电脑上,我可以在5秒内完成所有测试.
看这个照片..

使用DineMartine答案我得到了以下结果：

解决方法

您的算法复杂度为N log(N).我找到了一个更好的复杂度log(N)算法.我们的想法是迭代数字位数：

log10(n) = ln(n)/ln(10) = O(log(n)).

该算法的演示涉及许多组合演算.所以我选择不在这里写.

这是代码：

public static long Resolve(long input)
{
    var n = (long)Math.Log10(input);
    var tenPow = (long)Math.Pow(10,n);
    var rest = input;
    var result = 0L;
    for (; n > 0; n--)
    {
        var dn = rest / tenPow;
        rest = rest - dn * tenPow;
        tenPow = tenPow / 10;
        result += dn * (rest + 1) + dn * 45 * n * tenPow + dn * (dn-1) * tenPow * 5 ;
    }

    result += rest * (rest + 1) / 2;

    return result;
}

现在你可以在几分之一秒内解决问题.

想法是将输入写为数字列表：

假设解决方案由函数f给出,我们正在寻找g在n上的递归表达式：

实际上g可以写成如下：

如果你找到h,问题就会得到解决.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!