ハッシュ

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

class Hash
    M = 1046527

    def initialize
        @ary = []
    end

    def get_char(ch)
        if ch == 'A'
            return 1
        elsif ch == 'C'
            return 2
        elsif ch == 'G'
            return 3
        elsif ch == 'T'
            return 4
        end
        0
    end

    def get_key(str)
        sum = 0
        p = 1
        (0..(str.size - 1)).each do |i|
            sum += p * get_char(str[i])
            p *= 5
        end
        sum
    end

    def h1(key)
        key % M
    end

    def h2(key)
        1 + (key % (M - 1))
    end

    def h0(key, i)
        h1(key) + i * h2(key)
    end

    def exist?(str)
        key = get_key(str)
        i = 0
        while true do
            h = h0(key, i)
            if @ary[h] == str
                return true
            elsif @ary[h].nil?
                return false
            end
            i += 1
        end
    end

    def insert(str)
        key = get_key(str)
        i = 0
        while true do
            h = h0(key, i)
            if @ary[h] == str
                return false
            elsif @ary[h].nil?
                @ary[h] = str
                return true
            end
            i += 1
        end
    end
end
hash = Hash.new
n = gets.to_i
n.times do
    command, str = gets.split(" ")
    if command == 'insert'
        hash.insert(str)
    elsif command == 'find'
        if hash.exist?(str)
            puts "yes"
        else
            puts "no"
        end
    end
end

二分探索

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

def binary_search(ary, key)
    left = 0
    right = ary.size
    while left < right do
        mid = (left + right) / 2
        return true if key == ary[mid]
        if key > ary[mid]
            left = mid + 1
        elsif key < ary[mid]
            right = mid
        end
    end
    return false
end

sum = 0
n = gets.to_i
ary = gets.split(" ").map(&:to_i)
q = gets.to_i
gets.split(" ").map(&:to_i).each do |x|
    sum += 1 if binary_search(ary, x)
end

puts sum

線形探索

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

# 線形探索
def search(ary, key)
    n = ary.size
    ary << key
    i = 0
    while (ary[i] != key) do
        i += 1
    end
    i != n
end

def main
    n = gets.to_i
    s = gets.split(" ").map(&:to_i)
    q = gets.to_i
    t = gets.split(" ").map(&:to_i)
    count = 0
    t.each do |x|
        count += 1 if search(s, x)
    end
    puts count
end

main

連結リスト

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

class Node
    attr_accessor :key, :nexts, :prev
end

class LinerList
    def initialize
        @null = Node.new
        @null.nexts = @null
        @null.prev = @null
    end

    def search(key)
        cur = @null.nexts
        while cur != @null and cur.key != key do
            cur = cur.nexts
        end
        cur
    end

    def delete(t)
        return if t == @null
        t.prev.nexts = t.nexts
        t.nexts.prev = t.prev
    end

    def delete_first
        delete @null.nexts
    end

    def delete_last
        delete @null.prev
    end

    def delete_key(key)
        delete(search(key))
    end

    def insert(key)
        x = Node.new
        x.key = key
        x.nexts = @null.nexts
        @null.nexts.prev = x
        @null.nexts = x
        x.prev = @null
    end

    def dump
        cur = @null.nexts
        keys = []
        while cur != @null do
            keys << cur.key
            cur = cur.nexts
        end
        puts keys.join(" ")
    end
end

n = gets.to_i
list = LinerList.new
n.times do
    com, key = gets.split(" ")
    if com == "insert"
        list.insert(key.to_i)
    elsif com == "delete"
        list.delete_key(key.to_i)
    elsif com == "deleteFirst"
        list.delete_first
    elsif com == "deleteLast"
        list.delete_last
    end
    # list.dump
end
list.dump

キュー

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

class Proccezz
    attr_accessor :name, :t
    def initialize(name, t)
        @name = name
        @t = t
    end
end

class Queue
    LEN = 100005
    def initialize
        @head = 0
        @tail = 0
        @q = []
    end

    def enqueue(x)
        @q[@tail] = x
        @tail = (@tail + 1) % LEN
    end

    def dequeue
        x = @q[@head]
        @head = (@head + 1) % LEN
        x
    end

    def empty?
        @tail == @head
    end
end

def min(a, b)
    a < b ? a : b
end

elaps = 0
queue = Queue.new
n, q = gets.split(" ").map(&:to_i)
n.times do
    name, t = gets.split(" ")
    queue.enqueue Proccezz.new(name, t.to_i)
end

while ! queue.empty? do
    proc = queue.dequeue
    c = min(q, proc.t)
    proc.t -= c
    elaps += c
    if proc.t > 0
        queue.enqueue(proc)
    else
        puts "#{proc.name} #{elaps}"
    end
end

スタック

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

class Stack
    def initialize
        @top = 0
        @ary = []
    end

    def push(x)
        @top += 1
        @ary[@top] = x
    end

    def pop
        @top -= 1
        @ary[@top + 1]
    end

    def dump
        puts @ary.join(" ")
    end
end

def main
    stack = Stack.new
    while s = gets do
        s = s.chomp
        if s == "+"
            a = stack.pop
            b = stack.pop
            stack.push a + b
        elsif s == "-"
            b = stack.pop
            a = stack.pop
            stack.push a - b
        elsif s == "*"
            a = stack.pop
            b = stack.pop
            stack.push a * b
        else
            stack.push s.to_i
        end
    end
    stack.pop
end

puts main

シェルソート

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

def trace(ary)
    puts ary.join(", ")
end

# 配列を受取、挿入ソートする
def insertionSort(ary, g)
    n = ary.size - 1
    (g..n).each do |i|
        v = ary[i]
        j = i - g
        while (j >= 0 and ary[j] > v) do
            ary[j + g] = ary[j]
            j -= g
        end
        ary[j + g] = v
        trace ary
    end
    ary
end

def shellSort(ary)
    n = ary.size
    gen = []
    h = 1
    while h <= n do
        gen << h
        h = 3 * h + 1
    end
    gen_n = gen.size
    (gen_n - 1).downto(0).each do |i|
        insertionSort(ary, gen[i])
    end
end

ary = gets.split(" ").map(&:to_i) # 標準入力からスペース区切りで配列を受け取る
trace ary # 初期値表示
shellSort ary