ガジェット通信

見たことのないものを見に行こう

「等比? 等差? フィボナッチ?? 」問題の解題・解説

DATE:
  • ガジェット通信を≫

概要とか

「等比? 等差? フィボナッチ??」という問題が先日締め切られました。挑戦者数が多い割に正答率が低く、初回投稿の正解率10%以下という状況でした。

間違ってしまった方のために、何がまずかったのか、どうすればよかったのかをコードを交えて解説させていただきたいと思います。

まずは問題のおさらいです。今回の問題は以下のような内容でした。

div.nabesg{width:450px;float:right;}table.nabe{margin-left:30px;}img.nabe{float:right;width:400px}table.nabe td, table.nabe th{padding:3px;}table.nabe th{background-color: #ccc;}table.nabe td{background-color: #ddd;}code.nabe{border:solid 1px #ccc;font-family:”Courier”;}td code.nabe{border:none;}ol.nabe li{margin-left:2em;}ul.nabe li{margin-left: :1em;}.center{text-align:center;}.right{text-align:right;}blockquote.nabe{border:solid 1px;padding:1mm 1mm 1mm 1mm ;}【概要】

数列を与えます。
与えられた数列が以下のいずれの数列(の、途中の連続した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, … という数列はフィボナッチではありません。
【解答方法】

■挑戦言語は下記のプログラム言語選択で選択可能なものであれば何でもOKです。
自分の書いたプログラム言語を選択
解答欄にソースコードを記入
送信前に「提出前に確認」ボタンをクリック(構文エラーがないかどうかチェックできます)
「解答コードは正常に実行されました」というメッセージを確認の上、「解答を送信」ボタンで解答してください。

■この問題にはテストケースが12件用意されています。すべてに通れば正解です!
【採点について】
採点は「ideone」を使ってプログラムを実行し、標準入力および標準出力のテストケースと照合して正誤を判定します
各言語の標準入力と標準出力はこちらを参考にしてください

※なおCodeIQで使用しているideoneは企業版のため、webで公開されているコンシューマー版ideoneとは対応言語・バージョン・挙動が異なるかもしれません。実行くんとも異なるかもしれません。
企業版ideoneの対応バージョンは、「提出前チェック」の結果とともに表示されます。

問題の方は、5要素の数列が

等比数列
等差数列
フィボナッチ数列の一部
上記以外

のどれに該当するのかを答えるだけというシンプルなものでした。入力となる数は、1〜100億の整数で、昇順に整列済みです。

実際のテストケースは以下の通りでした:

#
テストケース
正解
1

160816114 194672138 235655746 285267482 345323794

G
2

9845600625 9876856500 9908211600 9939666240 9971220736

G
3

9715064832 9751864320 9788803200 9825882000 9863101250

G
4

1234 6912 12590 18268 23946

A
5

9999999990 9999999991 9999999992 9999999993 9999999994

A
6

1 2000000000 3999999999 5999999998 7999999997

A
7

13 21 34 55 89

F
8

121393 196418 317811 514229 832040

F
9

1134903170 1836311903 2971215073 4807526976 7778742049

F
10

9983848527 9987006973 9990166419 9993326864 9996488308

x
11

969323029 1568397607 2537720636 4106118243 6643838879

x
12

1032569015 1670731762 2703300777 4374032539 7077333316

x

罠・方針・実装(有理数クラスの利用)

テストケースの 11番 と 12番 は、等比数列ではないものの、隣接項の比を倍精度(double)で計算すると、全て「0.6180339887498949」になります。もう少し桁数を多くすると、「0.61803398874989485, 0.6180339887498948475, 0.6180339887498948485, 0.6180339887498948481」などとなり、等比数列ではないことが分かるんですが、double では表現できない桁で違いが発生しています。

5番や9番も double で計算すると、等比数列と判断されるでしょう。つまり、double 程度の桁数では等比数列かそうでないのかは判断できないということです。

そもそも、浮動小数点数は、許容誤差がある世界で使うべき型です。許容誤差が全くないこの問題のようなケースでは浮動小数点数を使うべきではありません。

ではどうするか。

ruby のような、多倍長整数を使った有理数が利用可能な処理系であれば、有理数を使うのが良いでしょう。

フィボナッチ数については、
cia_rana 様の記事
のような計算をするとより美しいと思いますが、もっと平易で非効率的な実装でも何の問題もありません。

というわけで、まずは ruby による実装をお見せしましょう:

def is_g(nums)
nums.each_cons(2).map{ |x,y| x.to_r/y }.uniq.size==1
end

def is_a(nums)
nums.each_cons(2).map{ |x,y| y-x }.uniq.size==1
end

def is_f(nums)
fibs = [ 0, 1, 1, 2, 3 ]
while fibs[0]

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。