本稿はCodeIQで2014年11月10日～同年12月1日に出題された「一番割り算の多い組み合わせは？」という問題の解法に関する記事です。

一番割り算の多い組み合わせは？【解説】

1～nまでの整数から2つを選ぶすべての組み合わせについて素直にユークリッドの互除法を適用し、除算回数の最大値を探すプログラムを書いてみます。以下はRubyのコードです。

# a > b > 0 前提ということで。
def count(a, b)
  c = 1 # 除算回数カウンタ
  while b > 0 && a%b != 0
    a, b = b, a%b
    c+=1
  end
  c
end

n = ARGV[0].to_i # 入力値は引数で取ることにする
mc = 0 # 除算回数の最大値
ma = mb = 0 # 除算が最大になるときのaとb

# a = bの場合は除算回数が1なのは明らかなので、a > bとする
(1..n-1).map{|b|
  (b+1..n).map{|a|
    c = count(a, b)
    if mc < c
      ma, mb, mc = a, b, c
    end
  }
}

puts "n=#{n}"
puts [mc, ma, mb].join' ' if n > 1

小さ目の入力に対してはこれで十分です。実際に動かしてみて、正しく解が得られるかを確認してみてください。次に、このコードに少し追記します。ifブロック内を次のように書き替え、最大除算回数が更新されるタイミングで、互除法の計算を行う2整数を出力するようにします。

    if mc < c
      ma, mb, mc = a, b, c
      puts [mc, ma, mb].join' '
    end

これを、試しにn=1000として実行してみると、次のように出力されます。

この結果を見ればすぐに気が付くと思いますが、最大値が更新される場合の2整数がフィボナッチ数列の項になっています。

本問は「aまでの数で、互除法の最大除算回数が最大になるものを見つける」という問題ですが、aの値が大きくなればそれだけ互除法の計算をする回数が増えてしまいます。そこで見方を少し変えて、「互除法による除算回数がn回であるとするときの、“最小の”整数組」がいくつになるのかを考えます。

まず、除算が1回で終わる場合を考えてみましょう。2つの整数が同じ値であった場合は除算1回で済むことが明白ですから、2つの整数は異なるものにしておきます。

2つの整数をr1, r2(r1 > r2)とすると、r1の値に関わらずr2が1であれば良いですが、“最小値”を求めるなら、r1 = 2, r2 = 1の場合になります。

次は、除算が2回で終わる場合を次のように考えてみましょう。

r1 = k1 * r2 + r3
r2 = k2 * r3 + r4

2回で割り切れるとき、r4は0になります。k1, k2は除算時の商に相当し、いずれも1以上の整数になります。つまり、

r1 ≧ r2 + r3
r2 ≧ r3

とすることができ、r1～r3はすべて整数ですので最小値にしたければ、

r2 ≧ 2, r3 ≧ 1 より、
r1 ≧ 2 + 1 = 3

となり、r1 = 3, r2 = 2の場合に最小になります。この要領で除算回数を増やしていくと、除算回数が3回の場合は

r1 ≧ r2 + r3
r2 ≧ r3 + r4
r3 ≧ 2
r4 ≧ 1

から、

r2 ≧ 2 + 1 = 3
r1 ≧ 3 + 2 = 5

で、最小値はr1 = 5, r2 = 3になります。除算回数を4回とすると、

r1 ≧ r2 + r3
r2 ≧ r3 + r4
r3 ≧ r4 + r5
r4 ≧ 2
r5 ≧ 1

から、

r3 ≧ 2 + 1 = 3
r2 ≧ 3 + 2 = 5
r1 ≧ 5 + 3 = 8

これくらい書くと見えてきましたね。

[除算回数, 最小の整数セット]の形で書きならべると、

[1, 2, 1]
[2, 3, 2]
[3, 5, 3]
[4, 8, 5]
[5, 13, 8]
.
.
.

のように、2つの整数はフィボナッチ数列の一般項であることがわかります。このように除算回数を調べていくことで、簡単に解を得ることができます。

def solve(n)
  a, b = 2, 1 # フィボナッチ数列の2項
  c = 1 # a, bの互除法で計算した場合の除算回数に相当する

  while n > a + b
    a, b = a+b, a
    c += 1
  end

  [c, a, b]
end

# 本問で指定した3つの入力
[1234, 123456, 1234567890].map{|n|
  puts "n=#{n}"
  puts solve(n).join' '
}

# 実行結果
# n=1234
# 14 987 610
# n=123456
# 24 121393 75025
# n=1234567890
# 43 1134903170 701408733

カメヲラボ

主にプログラミングとお勉強全般について書いてます

一番割り算の多い組み合わせは？【解説】

一番割り算の多い組み合わせは？【解説】