algorithm - フロア番号のシーケンスを合計する方法は？

Question

次のシーケンスを合計するにはどうすればよいですか。

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

私が思うのは、床を捨てて、各床の中の何を合計するかです！これは単なる推測です。

それらを合計するのに役立つヒントや一般式を教えてください

ありがとう

Answer 1

あなたはプログラミングの Q&A サイトで質問しているので、計算上の回答が必要であると想定しなければなりません。ここに行きます...

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

nが偶数であると仮定すると、 floor(n/2) == floor((n+1)/2). そしてfloor((n+2)/2) == floor(n/2) + 1。

パズルのもう 1 つのピースは、算術数列の和の式です。ここで見つけることができます。

Answer 3

任意の範囲 1..20 の場合、次のことができます。

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

もちろん、任意の範囲を使用できます。この例は Ruby でのものですが、多くの言語で同様のことを行うことができます。アルゴリズムは同じです。

Answer 4

巧妙なアルゴリズムや最適化を求めていない限り、私が考えることができる最も単純なアプローチは、古き良き信頼できるループです。C# では、これを行う 1 つの方法は次のようになります。

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());
        }
    }
}