algorithm - 如何对楼层编号的顺序求和？

Question

我如何总结以下序列：

⌊n∕2⌋ + ⌊n+1∕2⌋ + ⌊n+2∕2⌋ + ...... + (n-1)

我认为是丢弃地板并总结每层内的内容！这只是一个猜测。

给我任何提示或通用公式来帮助我总结它们

谢谢

Answer 1

由于您在编程问答网站上提问，我必须假设您想要一个计算答案。开始...

int sum = 0;
for (int j=0; j<n-1; ++j) {
    sum += (n+j)/2;
}

将int自动截断到地板。

不太聪明的答案是这样的。让n = 2k. 那么总和就变成了

k + k + k+1 + k+1 + ... + 2k-1 + 2k-1 = 2(k + k+1 + ... + 2k-1)

你可以使用公式

1 + 2 + ... + a = a(a+1)/2

用一点代数来完成它。

Answer 2

对于任意范围 1..20 你可以这样做：

sum = (1..20).inject{|sum, n| sum + (n/2.0).floor}

当然你可以使用任何范围。这个例子是用 Ruby 编写的，但是你可以在许多语言中做类似的事情——算法是一样的。

Answer 3

只要您不要求一个聪明的算法或优化，我能想到的最简单的方法就是古老的可信赖循环。在 C# 中，一种方法如下所示：

namespace Practice
{
    using System;

    public class SequenceAggregator
    {
        public double FirstElement
        {
            get;
            set;
        }

        public int Length
        {
            get;
            set;
        }

        public double Calculate()
        {
            double sum = 0;

            for (var i = FirstElement; i < FirstElement + Length; i++)
            {
                sum += Math.Floor(i / 2);
                Console.WriteLine("i={0}, floor(i/2)={1}, sum={1}", 
                                  i, Math.Floor(i/2), sum);
            }

            return sum;
        }
    }
}

您可以通过以下方式使用此类：

namespace Practice
{
    using System;

    class Program
    {
        static void Main(string[] args)
        {
            SequenceAggregator a = new SequenceAggregator();
            a.FirstElement = 1;
            a.Length = 3;
            Console.WriteLine("Sum:{0}", a.Calculate());
        }
    }
}

Answer 4

假设n是偶数，那么floor(n/2) == floor((n+1)/2)。和floor((n+2)/2) == floor(n/2) + 1。

拼图中的另一部分是等差数列之和的表达式，可以在这里找到。