私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「等比？ 等差？ フィボナッチ？？」（CodeIQ）を参照してください。
数列を与えます。
与えられた数列が以下のいずれの数列（の、途中の連続した5項）なのかを判別するプログラムを書いてください。
記号 名称 G 等比数列 A 等差数列 F フィボナッチ数 x G,A,Fのいずれにも該当しない
【入出力】
入力は
1 2 4 8 16こんな感じです。
スペース区切りで 5個の10 進数が並んでいます。
出力は、
Gのように、G, A, F, x のいずれかを出力してください。
末尾の改行はあってもなくても構いません。
【例】
入力 出力 1 2 4 8 16 G 1 2 3 4 5 A 3 5 8 13 21 F 1 2 123 1234 9999 x
【補足】
入力に含まれる値は、1以上、100億以下の整数です。
入力は、全て狭義単調増加列になっています。
不正な入力に対処する必要はありません。
G, A, F は大文字ですが、 x は小文字です。
1, 4, 5, 9, 14, 23, ... という数列はフィボナッチではありません。
Rubyで解答しています。
#!/usr/bin/ruby
def makeFibTable()
ret = [0,1]
i = 2
while ret.last < 10000000000
ret << ret[i-2] + ret[i-1]
i += 1
end
return ret
end
def isGeometricSeq(args)
a = Rational(args[1], args[0])
for i in 2...args.size
if a != Rational(args[i], args[i-1]) then return false end
end
return true
end
def isArithmeticSeq(args)
a = args[1] - args[0]
for i in 2...args.size
if a != args[i] - args[i-1] then return false end
end
return true
end
def isFibonacciSeq(args)
st = -1
FibTable.each_with_index{|v, i|
if v == args[0] then
st = i
break
end
}
if st < 0 then return false end
for i in 1...args.size
if args[i] != FibTable[st+i] then return false end
end
return true
end
def solve(args)
if isGeometricSeq(args) then return "G"
elsif isArithmeticSeq(args) then return "A"
elsif isFibonacciSeq(args) then return "F"
else return "x"
end
end
# main
FibTable = makeFibTable()
while line = gets
line.strip!
if line.empty? then next end
args = line.split.map{|a| a.to_i}
puts solve(args)
end
出題者がTwitterに書いている通り簡単な問題です。
等差数列、等比数列は何も悩むところはないでしょう。問題はフィボナッチ数だけです。入力値の最大値は1,000,000,000ですが試しにフィボナッチ数列を作ってみたら100項にも満たずに1,000,000,000を超えたので表引きにしてしまいました。
等比数列かどうかを判定します。初項と第二項の比をとって以降の各項の比が同じかどうかをチェックするだけです。
少数になる場合があったら困ると思ってRationalを使ったのですが、問題文の補足に単調増加と書いてあるので何も考えずに整数の割り算でOKだったはずです。
等差数列かどうかを判定します。初項と第二項の差をとって以降の各項の差が同じかどうかをチェックするだけです。
1,000,000,000以下の範囲でフィボナッチ数列を生成し、定数FibTableに保持します。
フィボナッチ数列かどうかを判定します。
FibTableを探索して最初に一致する項が見つかったら、入力値の次の項とFibTableの次の項も同じかをチェックして行きます。
isGeometricSeq()、makeFibTable()、isFibonacciSeq()を順次チェックし、trueが返ってきた時は相当する記号を返します。全部falseなら"x"を返します。
フィボナッチ数列に含まれる値かどうかを判定する方法を少し調べたのですがわからなかったので表引きにしました。探索を二分探索などにすればもっと速くなりますが項数が少ないので線形探索で十分でしょう。
親切にも「1, 4, 5, 9, 14, 23, ... という数列はフィボナッチではありません。」と注釈されていたので助かりました。この注釈を見ていなかったら大きい方から差をとってそれがそのひとつ前の値と一致するか、というロジックを実装してリジェクトされていたと思います。