アルゴ式をRubyで解く。【データ構造】

ハガユウキ

データ構造とは、効率的に管理されたデータの集合体。

アルゴリズムを実装するとき、入力として読み込んだ値や計算中に求めた値を、データ構造という形で保持します。そして必要に応じて、データ構造から所望の値を取り出します。

データ構造に値を挿入して管理したり、データ構造に格納されたデータを変更したり、データ構造から所望の値を取得したりするような要求をクエリ (query) と呼びます。

多くの場合、どのようなクエリが要求されるかによって、データ構造を適切に設計する必要があります。日々大規模化するデータを扱うためには、各クエリに高速に応える必要があるからです。

ハガユウキ

データ構造におけるクエリとは、データ構造に対するCRUD操作要求のこと

ハガユウキ

attr系のメソッドを定義すると、nameとかname=とかのゲッタセッターメソッドがクラスの中に定義されると思っといた方が良い

バイナリサーチ用のメソッドがある

キーワード引数のデフォルト値は省略することができる。デフォルト値を持たないキーワード引数は、呼び出し時に省略することができる

ハガユウキ

スタック

スタック（stack）
最後に入れたデータが最初に取り出される（最初に入れたデータが最後に取り出される）ようなデータ構造。 FILO（First In, Last Out、先入れ後出し）とかLIFO（Last In, First Out、後入れ先出し）とも呼ばれる。キュー（FIFO）と対比されることが多い。Apr 22, 2002

ハガユウキ

自己代入は、左辺がnil or falseの場合に、右辺が変数に代入される
左辺がnil or falseではないなら、そのままその変数が利用される

ハガユウキ

Array#countは引数に指定した値と同じ要素が配列に何個存在するか、数えることができる

Array#insertは、指定したインデックスの直前に要素を挿入することができる
(つまり、そのインデックスに指定した要素が入っていることになる)

ハガユウキ

Range#entriesはselfを配列に変換する

ハガユウキ

操作に規則性を見つける

ハガユウキ

ただし、2 は N まで一巡したらまた候補になるので N の後ろに来るとみなせます

この視点なかったな。
そう考えると、偶数の操作は前から1要素を取り出す
奇数の操作は前から取り出した1要素を後ろに追加する
これを配列の長さが1になるまで繰り返す。

すごい規則性あるな

ハガユウキ

untilはwhileのfalse版
unlessはifのfalse版
ややこしい

ハガユウキ

配列の要素を出力して、その出力した要素を配列から削除するという操作は、だいたい破壊的メソッドを使えば１回で同時にできる

ハガユウキ

reverse は自身の要素を逆順に並べた新しい配列を生成して返します。 reverse! は自身を破壊的に並べ替えます。 reverse! は self を返します。

reverseは非破壊的、revrseは破壊的だったのか。

ハガユウキ

木

木はグラフの特殊な場合を表すものである。木に慣れおくと、木の形をしたデータ構造を適切に扱えるようになる。

無向グラフ G が木であるとは
G が連結であって、サイクルをもたない

ハガユウキ

グラフ

グラフは対象物の関係性を表すものである。
対象物は「頂点」とよび、対象物の関係を表す線を「辺」と呼ぶ

グラフの各辺には向きがついている時とついていない時があり、ついているときのグラフを有向グラフ、ついていないときのグラフを無向グラフと呼ぶ

グラフを用いると、友人関係、鉄道路線、タスクの依存関係など、さまざまな関係性を表現できる
世の中におけるさまざまな問題は、グラフに関する問題としてとらえ直すことができます。

考えられる選択肢をすべて調べ上げる方法として「問題をグラフを用いて定式化する」という手法がしばしば有効です。

また、有向グラフ辺 e=(u,v) に対して、頂点 u を辺 e の始点とよび、頂点 v を辺 e の終点と呼びます。

各辺 e に実数値または整数値をとる重みが付随したグラフを考えることもあります。その場合のグラフを特に重み付きグラフとよびます。各辺に重みのついていないグラフを、特にそのことを強調したいときは重みなしグラフとよびます。

また、辺 e=(u,v) に対して、

頂点 u,v は、辺 e の端点である

頂点 u,v は、互いに隣接している

辺 e は、頂点 u,v に接続している
といいます。

また、無向グラフ G の各頂点 v に対して、v に接続している辺の本数を頂点 v の次数といいます。さらに有向グラフ G の各頂点 v に対して、v を始点とする辺の本数を頂点 v の出次数といい、 v を終点とする辺の本数を頂点 v の入次数といいます。

さらに、

無向グラフにおいて次数が 0 であるような頂点を葉
有向グラフにおいて出次数が 0 であるような頂点をシンク
有向グラフにおいて入次数が 0 であるような頂点をソース
といいます。

ハガユウキ

サイクル、パス

元のグラフの一部であるようなグラフを部分グラフとよびます。

部分グラフのうち、特に重要なものに次のものがあります (下図参照)。

パス：隣接する頂点をたどっていくことで、始点から終点へと到達できる部分グラフ
サイクル：隣接する頂点をたどっていくことで、元の頂点に戻ってこれる部分グラフ
ただし多くの場合、パスは「同じ頂点を二度以上通ってはいけない」ものとします。

ハガユウキ

根付き木

木に対して、特定の 1 つの頂点を特別扱いして根とよぶことがあります。根をもつ木のことを根付き木とよびます。根をもたない木に対して、そのことを強調するときは根なし木とよびます。根付き木を描画するときは、下図のように、根を最も上に描くことが通例となっています (根なのに上！！)。

ハガユウキ

根を除く頂点のうち、その頂点に接続している辺が 1 本しかないものを葉とよびます。根以外の頂点 v について、v に隣接している頂点のうち、根側にある頂点 p を v の親とよびます。このとき v は p の子であるといいます。

また、すべての頂点に対して子の個数が 2 以下であるような根付き木を二分木とよびます。二分木を使いこなせるようになると、ヒープ、二分探索木、セグメント木などのさまざまなデータ構造が考えられるようにもなります。

ハガユウキ

根付き木の各頂点 v について、v から見て子頂点の方向のみに着目すると「v を根とする根付き木」とみなせます。これを v を根とする部分木とよびます。

部分木を上手に扱うことは、木の探索において本質的です。

ハガユウキ

頂点 v を根とする部分木に含まれる頂点のうち、v 以外の頂点を v の子孫とよびます

ハガユウキ

とりあえず、木のデータ構造から値を探索したいなら、再起処理を使えば良い。
木構造をクラスにしたからTLEになるのはわかるが、実際の業務だとこの書き方をするから、納得できんなあ

ハガユウキ

根付き木の各頂点の深さの最大値を、木の高さとよびます

ハガユウキ

フィボナッチ数列を構成する数はフィボナッチ数として知られ、一般にFnと表記される

ハガユウキ

フィボナッチ数のアルゴリズムできた

# @param [Integer] number
# return [Integer]
def get_fibonacci_number(number:)
  return 0 if number.zero?
  return 1 if number == 1

  get_fibonacci_number(number: number - 1) + get_fibonacci_number(number: number - 2)
end

begin
  number = gets.chomp.to_i
  fibonacci_number = get_fibonacci_number(number: number)
  puts fibonacci_number
rescue StandardError => e
  p "raise error", e.message
end