2015年01月18日

C#で数列が急勾配かどうかを判定する

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その63

■問題 (出題者:nobsun さん)
有限の長さの数列で,各要素の値が,その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします(空列の和は0とします). 任意の長さ(ただし有限の長さの)数列を与えられたとき,それが「急勾配の列」であるかどうかを判定する述語関数を定義してください. 必須ではありませんが,効率についてコメントがあれば面白いかもしれませんね.

まずは、素直に解いたもの。 再帰とLINQ使ってます。
急勾配の判定の定義を、ほぼそのままコードにしています。

private static bool IsSteepSlope(IEnumerable<int> nums) {
    if (!nums.Any())
        return true;
    var x = nums.First();
    var xs = nums.Skip(1);
    return (x > xs.Sum()) && IsSteepSlope(xs);
}
このIsSteepSlopeを使ったコードはこんな感じ。
static void Main(string[] args) {
    int[] nums = { 32, 16, 8, 4, 2, 1 };
    bool r = IsSteepSlope(nums);
    Console.WriteLine(r.ToString());
    Console.ReadLine();
}

でも、何回も何回も、数列を走査する必要があるので、効率的とは言えません。 もう少し効率の良い方法も考えてみました。
有限個の数列なので、先頭から走査するのではなく、最後尾から走査すれば効率よく、急勾配かどうかを判定できそうです。
つまり、急な下り斜面かどうかを調べるのではなく、急な上り斜面かどうかを調べるコードにするということですね。

private static bool IsSteepSlope(IEnumerable<int> nums) {
    int sum = 0;
    foreach (var n in nums.Reverse()) {
        if (n <= sum)
            return false;
        sum += n;
    }
    return true;
}


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52403785