急勾配の判定 in JavaScript DouKaku?

有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の和は0とします）．

任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」であるかどうかを判定する述語関数を定義してください．

必須ではありませんが，効率についてコメントがあれば面白いかもしれませんね．

効率は悪くないと思うけど、工夫はしてません。

仕様面ではっきりしないのは、
１．空リストは急勾配？ not 急勾配？
２．問題文の「空列の和は0とします」をどう読むか。
　　[0] は 0 + 空列なので、not 急勾配になる？
　　（sum の初期値を 0 とするか -∞ にするかというだけの話だけど）

Array.prototype.isHeavySlope = function() {
  var sum = 0;
  for (var i = this.length-1; i >= 0; i--) {
    if (this[i] <= sum) return false;
    sum += this[i];
  }
  return true;
}

>>> [].isHeavySlope()
true
>>> [0].isHeavySlope()
false
>>> [1,0].isHeavySlope()
false
>>> [0,1].isHeavySlope()
false
>>> [4,2,1].isHeavySlope()
true
>>> [3,2,1].isHeavySlope()
false

リストを前から見ていくこともできます。
後ろから見るほうがシンプルだけど、リストの長さが未確定の場合はこちらが有利。
ちなみに [1,0].isHeavySlope() は true になりますが何か？

Array.prototype.isHeavySlope = function() {
    if (this.length == 0) return true;
    var pre, sub;
    for each (var n in this) {
        if (pre == undefined) {
            sub = pre = n;
        } else {
            sub -= n;
            if (pre <= n || sub <= 0) return false;
            pre = n;
        }
    }
    return true;
}

DouKaku?

急勾配の判定

Posted feedbacks - JavaScript

Index

Feed

Other

Link

Pathtraq