急勾配の判定
Posted feedbacks - Other
とりあえず急勾配な場合でもO(n)。かっこわるいです。 一般的にはもっと良いはず。ランダムな数列において後ろから見たときに急勾配の条件に合わない値が出てくる確率ってどのくらいなんでしょう。（考えるのめんどくさい）
1 2 3 4 5 6 7 8 9 10 | List.metaClass.is急勾配 {->
def sum
for (val in delegate.reverse()) {
if (sum != null && val <= sum) {
return false
}
sum = (sum?:0) + val
}
return true
}
|
組み込み関数reversedのオーダは分かりませんが、少なくともそれ以外の部分は要素数について、線形時間です。
1 2 3 4 5 6 7 8 9 10 11 12 13 | #!/usr/bin/python
def checkSteep(target):
li = reversed(target)
sum = 0
for x in li:
if x <= sum: return False
sum += x
return True
if __name__ == '__main__':
print 'Steep' if checkSteep([32, 16, 8, 4, 2, 1]) else 'not Steep' # => Steep
print 'Steep' if checkSteep([32, 15, 8, 4, 2, 1]) else 'not Steep' # => not Steep
|
nobsun
#8891()
Rating1/1=1.00
有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の和は0とします）．
任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」であるかどうかを判定する述語関数を定義してください．
必須ではありませんが，効率についてコメントがあれば面白いかもしれませんね．
[ reply ]