問24・25:辞書式順列と1000桁のフィボナッチ数列

スポンサーリンク

問24:辞書式順列の問題

Lexicographic permutations

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると

012 021 102 120 201 210
になる.

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?

回答

answer = (0..9).to_a.permutation.map(&:join)[999_999]
puts answer
#=> 2783915460

Array#permutationの通り順列を返すメソッドがArrayクラスに定義されているので用いました。

permutationメソッドの返り値はリファレンスの通り、
0123456789という数字列→[0,1,2,3,4,5,6,7,8,9]と返る
ので、Array#mapとArray#joinで各数字を連結しています。

配列のインデックスは 0 から始まるので
100万個目のインデックスは99万9999個目の要素を取り出せば得られます。

※問24ブランチのプルリクエスト

問25:1000桁のフィボナッチ数列

1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

フィボナッチ数列は以下の漸化式で定義される:

Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1.
最初の12項は以下である.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
12番目の項, F12が3桁になる最初の項である.

1000桁になる最初の項の番号を答えよ.

回答

フィボナッチ数列の生成メソッドは問2で作ったことがあるので流用しました。
問2の回答

# frozen_string_literal: true

require 'minitest/autorun'
require './problem'

require 'minitest/reporters'
Minitest::Reporters.use!

class ProblemTest < Minitest::Test
  def test_nth_digit_fibonacci_number
    assert_equal 12, nth_digit_fibonacci_number(3)
  end
end
# frozen_string_literal: true

def nth_digit_fibonacci_number(nth_digit)
  fibonacci_sequence = [1, 1]

  loop do
    n = fibonacci_sequence[-2, 2].inject(:+)
    break if n.to_s.length == nth_digit

    fibonacci_sequence << n
  end

  fibonacci_sequence.size + 1
end

puts nth_digit_fibonacci_number(1_000)
#=> 4782

nth_digit_fibonacci_numberメソッドに桁数を数字で引数で持つようにして、
計算されるフィボナッチ数列の桁数がその値と等しくなったときに
ループから抜けるようにしました。

最終的な解は1000桁を超える最初の項の番号なので、
ループを抜けるまでに作ったフィボナッチ数列の数に 1 を足して求まります。

※問25ブランチのプルリクエスト

この記事の内容が役に立ったと思いました、SNSで記事を共有していただけますと幸いです。