急勾配の判定 in Ruby DouKaku?

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

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

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

　素直に書いてみました。

class SteepAngle
    def self.steep?(l)
        (l.size < 2) || (0...l.size - 1).all? { |i| l[i] > l[i + 1...l.size].inject(0) { |r,e| r + e } }
    end
end

puts SteepAngle.steep?(ARGV.map { |p| p.to_i }) ? "steep" : "not steep"

#8894を参考にさせて頂きました。数列を反転後、合計値を先頭に書き込みながら大小比較をしています。

def super_decreasing?(a)
  r = a.reverse
  while r[1] && (w = r[0] < r[1])
    r[1] += r[0]
    r.shift
  end
  w ? "yes. super_decreasing." : "not super_decreasing."
 end

p super_decreasing?([8, 4, 2, 1]) # => yes..
p super_decreasing?([8, 3, 2, 1]) # => not..
p super_decreasing?([1]) # => not..
p super_decreasing?([]) # => not..
p super_decreasing?([1, -4, -5]) # => yes..

#! /usr/bin/ruby

class Array
    def steep?
        reverse.inject(0) do |sum, previous|
            return false unless previous > sum
            sum += previous
        end
        true
    end
end

p [5, 3, 2].steep?

畳み込みを使ったほうが綺麗ですが、Rubyの畳み込み(inject)は左から(foldl相当)なので、reverseする分重くなりそうですね。

というわけで、普通に実装してみました。

class Array
  def steep?
    sum = 0
    (self.size - 2).downto(0) do |index|
      if self[index] <= (sum += self[index + 1])
        return false
      end
    end
    true
  end
end

p [100, 50, 25, 12, 6, 3, 1].steep?

DouKaku?

急勾配の判定

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq