【アルゴリズムの勉強】Rubyで8王妃（エイトクイーン）問題を解いてみる
8王妃（エイトクイーン）問題とは
チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。
クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。
Rubyで実装
QUEEN = 8 @is_set = Array.new(QUEEN){false} @is_set_diagonal_right = Array.new(QUEEN * 2 - 1){false} @is_set_diagonal_left = Array.new(QUEEN * 2 - 1){false} @queen_position = [] @count = 0 def calc_pattern(column) QUEEN.times{|row| unless @is_set[row] || @is_set_diagonal_right[column + row] || @is_set_diagonal_left[column - row + (QUEEN - 1)] @queen_position[column] = row if column == (QUEEN - 1) @count += 1 else @is_set[row] = @is_set_diagonal_right[column + row] = @is_set_diagonal_left[column - row + (QUEEN - 1)] = true calc_pattern(column + 1) @is_set[row] = @is_set_diagonal_right[column + row] = @is_set_diagonal_left[column - row + (QUEEN - 1)] = false end end } end calc_pattern(0) p @count # => 92
【アルゴリズムの勉強】Rubyでユークリッドの互除法を書いてみる
ユークリッドの互除法によって2つの自然数の最大公約数を求める処理をRubyで再帰を用いて実装する。
ユークリッドの互除法とは
ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである[注釈 1]。
Rubyで実装
def euclid_gcd(x, y) return x if y == 0 euclid_gcd(y, x % y) end p euclid_gcd(8, 20) # => 4 p euclid_gcd(100, 200) # => 100 p euclid_gcd(1, 12) # => 1
【アルゴリズムの勉強】Rubyでデータ構造のキューを書いてみる
アルゴリズムの勉強としてリングバッファによるキューをRubyで実装する。
キューとは
キュー（英: queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー[2]、取り出すことをデキュー[3]という。
Rubyで実装
class Queue def initialize(capacity) @number = @front = @rear = 0 @max = capacity @que = Array.new(capacity) p @que end def enque(value) if @number >= @max puts "キューは満杯です" else @que[@rear] = value @number += 1 if (@rear + 1) == @max @rear = 0 else @rear += 1 end p @que end end def deque if @number <= 0 puts "キューは空です" else result = @que[@front] @number += -1 if (@front + 1) == @max @front = 0 else @front += 1 end puts "#{result}を取り出しました" end end def next_value if @number <= 0 puts "キューは空です" else result = @que[@front] puts "次に取り出される値は#{result}です" end end def search(value) for i in 0..(@number - 1) index = (i + @front) % @max if @que[index] == value puts "#{value}はキュー内に存在します" return end end puts "#{value}はキュー内に存在しません" end def clear @number = @front = @rear = 0 puts "キューを空にしました。" end def capacity puts "キューの容量は#{@max}です" end def number_of_data puts "キューには#{@number}つのデータが格納されています" end def empty? if @number <= 0 puts "キューは空です" else puts "キューは空ではありません" end end def full? if @number >= @max puts "キューは満杯です" else puts "キューはまだ空き領域が存在します" end end def dump if @number <= 0 puts "スタックは空です" else for index in 0..(@number - 1) puts @que[index] end end end end queue = Queue.new(5) # => [nil, nil, nil, nil, nil] queue.enque(5) # => [5, nil, nil, nil, nil] queue.enque(12) # => [5, 12, nil, nil, nil] queue.deque # => 5を取り出しました queue.enque(2) # => [5, 12, 2, nil, nil] queue.enque(52) # => [5, 12, 2, 52, nil] queue.deque # => 12を取り出しました queue.next_value # => 次に取り出される値は2です queue.search(2) # => 2はキュー内に存在します queue.capacity # => キューの容量は5です queue.number_of_data # => キューには2つのデータが格納されています queue.empty? # => スタックはまだ空き領域が存在します queue.enque(87) # => [5, 12, 2, 52, 87] queue.enque(32) # => [32, 12, 2, 52, 87] queue.enque(412) # => [32, 412, 2, 52, 87] queue.enque(999) # => キューは満杯です queue.clear # => キューを空にしました。 queue.empty? # => キューは空です
【アルゴリズムの勉強】Rubyでデータ構造のスタックを書いてみる
スタックとは
スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。
特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。
Rubyで実装
class Stack def initialize(capacity) @pointer = 0 @max = capacity @stack = Array.new(capacity) p @stack end def push(value) if @pointer >= @max puts "スタックは満杯です" else @stack[@pointer] = value @pointer += 1 p @stack end end def pop if @pointer <= 0 puts "スタックは空です" else @pointer += -1 puts "#{@stack[@pointer]}を取り出しました" end end def next_value if @pointer <= 0 puts "スタックは空です" else result = @stack[@pointer - 1] puts "次に取り出される値は#{result}です" end end def search(value) for index in 0..(@pointer - 1) if @stack[index] == value puts "#{value}はスタック内に存在します" return end end puts "#{value}はスタック内に存在しません" end def clear @pointer = 0 puts "スタックを空にしました。ポインタの位置は#{@pointer}です" end def capacity puts "容量のサイズは#{@max}です" end def number_of_data puts "スタックには#{@pointer}つのデータが格納されています" end def empty? if @pointer <= 0 puts "スタックは空です" else puts "スタックはまだ空き領域が存在します" end end def full? if @pointer >= @max puts "スタックは満杯です" else puts "スタックはまだ空き領域が存在します" end end def dump if @pointer <= 0 puts "スタックは空です" else for index in 0..(@pointer - 1) puts @stack[index] end end end end stack = Stack.new(5) # => [nil, nil, nil, nil, nil] stack.push(5) # => [5, nil, nil, nil, nil] stack.push(12) # => [5, 12, nil, nil, nil] stack.pop # => 12を取り出しました stack.push(2) # => [5, 2, nil, nil, nil] stack.push(52) # => [5, 2, 52, nil, nil] stack.next_value # => 次に取り出される値は52です stack.search(2) # => 2はスタック内に存在します stack.capacity # => 容量のサイズは5です stack.number_of_data # => スタックには3つのデータが格納されています stack.empty? # => スタックはまだ空き領域が存在します stack.push(87) # => [5, 2, 52, 87, nil] stack.push(12) # => [5, 2, 52, 87, 12] stack.full? # => スタックは満杯です
【アルゴリズムの勉強】Rubyでハッシュ法（オープンアドレス法）を使用してデータの追加・検索・削除を行う
概要
ハッシュ法（オープンアドレス法）を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。
オープンアドレス法とは
衝突が発生した際、テーブル中の空いている別の番地を探す方式を開番地法と呼ぶ。その方法としてハッシュ関数とは別の関数を用いて次の候補となる番地を求める。別の番地を探す関数は繰り返し適用することによってテーブル内の全ての番地を走査できるように選ぶ。
Rubyで実装
OCCUPIED = 0 EMPTY = 1 DELETED = 2 KEY = 0 STATUS = 1 ALONE = true def create_hash_table(table_size) return Array.new(table_size, [nil, EMPTY]) end def get_hash_value(key, table_size) return key % table_size end def get_rehash_value(hash_value, table_size) return (hash_value + 1) % table_size end def add_data(key, hash_table, table_size) result = search(key, hash_table, table_size) if result != nil puts "この値は既に追加済みです" return end hash_value = get_hash_value(key, table_size) target = hash_table[hash_value] table_size.times {|index| if target[STATUS] == EMPTY || target[STATUS] == DELETED hash_table[hash_value] = [key, OCCUPIED] p hash_table return end hash_value = get_rehash_value(hash_value, table_size) target = hash_table[hash_value] } puts "値を追加するスペースが存在しません" end def delete_data(key, hash_table, table_size) result = search(key, hash_table, table_size) return if result.nil? result[STATUS] = DELETED p hash_table end def search(key, hash_table, table_size, is_alone = false) hash_value = get_hash_value(key, table_size) target = hash_table[hash_value] table_size.times {|index| if target[STATUS] == EMPTY || target[STATUS] == DELETED puts "#{key}は見つかりませんでした" if is_alone return nil end if target[STATUS] == OCCUPIED && target[KEY] == key puts "#{key}はハッシュテーブルに存在します" if is_alone return target end hash_value = get_rehash_value(hash_value, table_size) target = hash_table[hash_value] } return nil end table_size = 5 hash_table = create_hash_table(table_size) p hash_table # => [[nil, 1], [nil, 1], [nil, 1], [nil, 1], [nil, 1]] add_data(13, hash_table, table_size) # => [[nil, 1], [nil, 1], [nil, 1], [13, 0], [nil, 1]] add_data(3, hash_table, table_size) # => [[nil, 1], [nil, 1], [nil, 1], [13, 0], [3, 0]] add_data(4, hash_table, table_size) # => [[4, 0], [nil, 1], [nil, 1], [13, 0], [3, 0]] add_data(9, hash_table, table_size) # => [[4, 0], [9, 0], [nil, 1], [13, 0], [3, 0]] add_data(12, hash_table, table_size) # => [[4, 0], [9, 0], [12, 0], [13, 0], [3, 0]] add_data(12, hash_table, table_size) # => この値は既に追加済みです add_data(11, hash_table, table_size) # => 値を追加するスペースが存在しません search(4, hash_table, table_size, ALONE) # => 4はハッシュテーブルに存在します delete_data(12, hash_table, table_size) # => [4, 0], [9, 0], [12, 2], [13, 0], [3, 0]] search(12, hash_table, table_size, ALONE) # => 12は見つかりませんでした
【アルゴリズムの勉強】Rubyでハッシュ法（チェイン法）を使用してデータの追加・検索・削除を行う
概要
ハッシュ法（チェイン法）を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。
チェイン法とは
衝突を起こしたキー同士をポインタでつなぐ方式を連鎖法と呼ぶ。テーブルの各番地にはキーそのものではなく、同族キーを保持するリンクリストを格納する。
Rubyで実装
original_data = [3, 6, 10, 12, 13, 15, 31, 40] KEY = 0 NEXT = 1 def create_hash_table(table_size) return Array.new(table_size) end def get_hash_value(key, table_size) return key % table_size end def add_data(key, hash_table, table_size) hash_value = get_hash_value(key, table_size) target = hash_table[hash_value] while !target.nil? if target[KEY] == key puts "この値は既に追加済みです" return end target = target[NEXT] end data = [key, hash_table[hash_value]] hash_table[hash_value] = data end def delete_data(key, hash_table, table_size) hash_value = get_hash_value(key, table_size) target = hash_table[hash_value] past_target = nil while !target.nil? if target[KEY] == key if past_target == nil hash_table[hash_value] = target[NEXT] else past_target[NEXT] = target[NEXT] end return end past_target = target target = target[NEXT] end puts "#{key}は見つかりませんでした" end def search(key, hash_table, table_size) hash_value = get_hash_value(key, table_size) target = hash_table[hash_value] while !target.nil? if target[KEY] == key puts "#{key}はハッシュテーブルに存在します" return end target = target[NEXT] end puts "#{key}は見つかりませんでした" end table_size = 5 hash_table = create_hash_table(table_size) p hash_table # => [nil, nil, nil, nil, nil] # 元のデータをハッシュテーブルに追加 original_data.each{|data| add_data(data, hash_table, table_size) } p hash_table # => [[40, [15, [10, nil]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil] # 新しくデータを追加 add_data(35, hash_table, table_size) p hash_table # => [[35, [40, [15, [10, nil]]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil] # 検索 search(15, hash_table, table_size) # => 15はハッシュテーブルに存在します # 削除 delete_data(15, hash_table, table_size) p hash_table # => [[35, [40, [10, nil]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil]
【アルゴリズムの勉強】Rubyでハッシュ法を使用せずデータの追加を行う
概要
ハッシュ法を使用せず昇順にソートされた状態のデータに新しい値の追加を行う。
バイナリサーチのアルゴリズムを用いて挿入すべき位置を見つけ値を追加し、それ以降の全要素を一つずつ後方へ移動するため、ハッシュ法を用いたデータの追加と比べ効率は悪い。
Rubyで実装
original_data = [1, 3, 5, 6, 8, 10, 12, 13, 15, 17, 20, 24, 30] def add_data(value, asc_sorted_data) number_of_elements = asc_sorted_data.count insert_location = get_insert_location(value, asc_sorted_data, number_of_elements) if insert_location == -1 puts "#{value}は既に追加済みです" return asc_sorted_data end while insert_location <= number_of_elements original_value = asc_sorted_data[insert_location] asc_sorted_data[insert_location] = value value = original_value insert_location += 1 end return asc_sorted_data end def get_insert_location(target, asc_sorted_data, number_of_elements) left = 0 right = number_of_elements - 1 # バイナリサーチのアルゴリズムを使用 while left <= right center = (left + right) / 2 return -1 if asc_sorted_data[center] == target if asc_sorted_data[center - 1] < target && asc_sorted_data[center] > target break end if asc_sorted_data[center] < target left = center + 1 else right = center - 1 end end if center == (number_of_elements - 1) && asc_sorted_data[center] < target insert_location = center + 1 else insert_location = center end return insert_location end p original_data # => [1, 3, 5, 6, 8, 10, 12, 13, 15, 17, 20, 24, 30] data = add_data(11, original_data) p data # => [1, 3, 5, 6, 8, 10, 11, 12, 13, 15, 17, 20, 24, 30]
