CodeIQ MAGAZINECodeIQ MAGAZINE

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

2016.10.28 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 12
  • このエントリーをはてなブックマークに追加
nabetani

出題者の鍋谷さんによる、「等比? 等差? フィボナッチ??」問題の解答と解説です。

初回挑戦でつまづいてしまった人が多かったという今回の問題。どういったところに気を付ければよかったのでしょうか?

こちらの記事で確認してみてくださいね!
by CodeIQ運営事務局

概要とか

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

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

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

【概要】

数列を与えます。
与えられた数列が以下のいずれの数列(の、途中の連続した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です。

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

■この問題にはテストケースが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]<nums[0] do
    fibs = fibs[1,4]+[fibs[-1]+fibs[-2]]
  end
  return fibs==nums
end

def solve(src)
  nums = src.split(/\s+/).map(&:to_i)
  return "G" if is_g(nums)
  return "A" if is_a(nums)
  return "F" if is_f(nums)
  return "x"
end

puts solve(gets)

Rational クラスのお陰で非常に楽に実装できます。

方針と実装(有理数クラスがない場合)

一方、C言語のような有理数がない処理系の場合、必要最小限の有理数を実装するのが良いでしょう。

挑戦いただいた方の中には

a, b, c が等比数列 ⇔ a×c=b×b

を利用した実装を行った方もいらっしゃいましたが、整数が 53bit や 64bit に制限されている場合は 桁落ちやオーバーフローが発生するのでよろしくありません。

入力の最大値が 100億、つまり34bit ほどありますので、乗算すると 64bit を超えます。

C# の decimal のような型が利用可能であれば、前述の条件を使うと簡単に書けて良いでしょう。しかし、C言語ではそうは行きません。

というわけで。

少々長くなりますが、必要最小限の有理数を使った、C言語の実装をお見せしましょう:

// clang -std=c99 -Wall
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

/// 等差数列なら true を返す
bool is_a( int64_t const * nums )
{
  int64_t diff0=nums[1]-nums[0];
  for( int i=1 ; i<4 ; ++i ){
    int64_t diff = nums[i+1]-nums[i];
    if ( diff != diff0 ){
      return false;
    }
  }
  return true;
}

/// 分子(n) と分母(d) のペア
struct pair{ int64_t n, d; };

/// n と d の最大公約数
int64_t gcd(int64_t n, int64_t d)
{
  while ( n != 0 ) {
     int64_t c=n;
     n = d % n;
     d = c;
  }
  return d;
}

/// n を d で割り、約分した結果のペアを返す
struct pair div( int64_t n, int64_t d )
{
  int64_t c = gcd(n,d);
  return (struct pair){n/c, d/c};
}

/// 2つの約分済み有理数が等しいかどうかを調べる
bool equals( struct pair a, struct pair b )
{
  return a.n==b.n && a.d==b.d;
}

/// 等比数列なら true
bool is_g( int64_t const * nums )
{
  struct pair r0=div(nums[1],nums[0]);
  for( int i=1 ; i<4 ; ++i ){
    struct pair r =div(nums[i+1], nums[i] );
    if ( ! equals( r0, r ) ){
      return false;
    }
  }
  return true;
}

/// フィボナッチ数なら true
bool is_f( int64_t const * nums )
{
  struct fibs{ int64_t m[5]; };
  struct fibs fibs = {{ 0,1,1,2,3}};
  while( fibs.m[0]<nums[0] ){
    fibs = (struct fibs){{
      fibs.m[1],fibs.m[2],fibs.m[3],fibs.m[4],
      fibs.m[3]+fibs.m[4],
    }};
  }
  for( int i=0 ; i<5 ; ++i ){
    if ( fibs.m[i] != nums[i] ){
      return false;
    }
  }
  return true;
}

/// 問題を解く。
char solve( int64_t const * nums )
{
  if ( is_a( nums ) ){
    return 'A';
  }
  if ( is_g( nums ) ){
    return 'G';
  }
  if ( is_f( nums ) ){
    return 'F';
  }
  return 'x';
}

int main(int argc, char const * argv[] )
{
  int64_t nums[5];
  fscanf( stdin, "%lld %lld %lld %lld %lld", nums, nums+1, nums+2, nums+3, nums+4 );
  putchar(solve( nums ) );
}

有理数の実装というと大掛かりに聞こえるかもしれませんが、約分と比較があるだけです。約分のために最小公倍数も必要になります。

C言語なので、フィボナッチ数のチェックに行数を要してしまっていますが、この部分は ruby の実装と同等です。

最後に

この問題は、非常に多くの方に挑戦いただいたんですが、初回正解率 1割以下、最終正解率も6割ちょっとという惨状でした。敗因の殆どは、浮動小数点数で戦おうとしてしまったことにありました。

等比数列かどうかの判断には、許容誤差ゼロで比が等しいことの確認が必要です。許容誤差ゼロということは、浮動小数点数は使えない(例外はありますが)ということです。

というわけで。

浮動小数点は便利ですが、場面を間違えるとひどい目に合います。気をつけましょう。

多くの方の挑戦、ありがとうございました。
また楽しんでいただける問題を出していきたいと思います。

CodeIQ運営事務局より

鍋谷さん、ありがとうございました!
現在、鍋谷さんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

最新の2問

そのほかの鍋谷さんの出題問題はこちらから!

  • 12
  • このエントリーをはてなブックマークに追加

■関連記事

第154回「今週のアルゴリズム:トーナメントでの想定対戦数は?」正解者発表... 「今週のアルゴリズム」とは 「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。 第154回は「今週のアルゴリズム:トーナメントでの想定対戦数は?」...
【夏のミステリー】殺人現場のコード 解答と解説... 【夏のミステリー】殺人現場のコード 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 殺人現場にプログラマが倒れていて、途中までプログラムが書かれている。 「続きを書いて欲しい」 これはダイイングメッセージなのか? どう...
数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説... 問題のおさらい n 個のキャンディをグループに分けます。 グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。 例えば、F(8, 3)=5 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...
第153回「今週のアルゴリズム:〇×ゲームの手順は何通り?」正解者発表... 「今週のアルゴリズム」とは 「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。 第153回は「今週のアルゴリズム:〇×ゲームの手順は何通り?」の問...
第152回「今週のアルゴリズム:ボーリングの最高点、最低点は?」正解者発表... 「今週のアルゴリズム」とは 「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。 第152回は「今週のアルゴリズム:ボーリングの最高点、最低点は?」...
第151回「今週のアルゴリズム:上下左右に箱を並べよう」正解者発表... 「今週のアルゴリズム」とは 「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。 第151回は「今週のアルゴリズム:上下左右に箱を並べよう」の問題で...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ