算法

dik斯特拉________________________
@graph = {}
@graph["start"] = {}
@graph["start"]["a"] = 6
@graph["start"]["b"] = 2
@graph["a"] = {}
@graph["a"]["fin"] = 1
@graph["b"] = {}
@graph["b"]["a"] = 3
@graph["b"]["fin"] = 5
@graph["fin"] = {}

costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = 999999

parents = {}
parents["b"] = "start"
parents["fin"] = nil

@processed = []


def find_a(costs)
  low_cost = Float::INFINITY
  low_node = nil
  costs.each do |node, cost|
    if low_cost>cost and !@processed.include? node
      low_cost = cost
      low_node = node
    end
  end
  return low_node
end

def dike(costs, parents)
  while find_a(costs)
    node = find_a(costs)
    neighbors = @graph[node]
    neighbors.each do |to_node,to_cost|
      new_cost = to_cost + costs[node]
      if new_cost < costs[to_node]
        costs[to_node] = new_cost
        parents[to_node] = node
      end
    end
    @processed.push(node)
  end
end

dike(costs, parents)
puts "final cost is #{costs}"
puts "______________________"
puts "final parents is #{parents}"

动态规划

递归，假规划————
@knownResults = {}

def recMC(coinValueList,amount)
  minCount = amount
  if coinValueList.include? amount
    return 1
  elsif @knownResults.include? amount
    return @knownResults[amount]
  else
    filterList = coinValueList.select {|coinValue| coinValue < amount}
    filterList.each do |coinValue|
      count = 1 + recMC(coinValueList,amount - coinValue)
      if minCount > count
        minCount = count
      end
    end
    @knownResults[amount] = minCount
    return minCount
  end
end

puts recMC([1,5,10,21,50],63)

minCoin = {}
minCoin[0] = 0

迭代_____________________________________

def makeAmountList(coinValueList, totalAmount, minCoins)
  (1..totalAmount).each do |amount|
    count = amount
    selectList = coinValueList.select {|value| value <= amount }
    selectList.each do |coinValue|
      if minCoins[amount - coinValue] + 1 < count
        count = minCoins[amount - coinValue] + 1
      end
    end
    minCoins[amount] = count
  end
end

makeAmountList([1,5,10,20,50,100], 120, minCoin)

puts minCoin

金额查找____________________________
minCoin = {}
coinsUsed = {}

def makeAmountList(coinValueList, totalAmount, minCoins,coinsUsed)
  (0..totalAmount).each do |amount|
    count = amount
    coin = 1
    selectList = coinValueList.select {|value| value <= amount }
    selectList.each do |coinValue|
      if minCoins[amount - coinValue] + 1 < count
        count = minCoins[amount - coinValue] + 1
        coin = coinValue
      end
    end
    minCoins[amount] = count
    coinsUsed[amount] = coin
  end
end

makeAmountList([1,5,10,20,50,100], 20, minCoin, coinsUsed)

def printCoins(coinsUsed, amount)
  left = amount
  while amount > 0
    puts coinsUsed[amount]
    amount = amount - coinsUsed[amount]
  end
end

printCoins(coinsUsed, 17)

假hash__________________
class HashTable
  def initialize()
    @size = 11
    @slots = Array.new(@size)
    @data = Array.new(@size)
  end

  def get(key)
    startslot = self.hashfunction(key)

    data = nil
    stop = false
    found = false
    position = startslot
    while @slots[position] != nil and !found and !stop
      if @slots[position] == key
        found = true
        data = @data[position]
      else
        position = self.rehash(position)
        if position == startslot
          stop = true
        end
      end
    end
    puts data
  end

  def put(key,data)
    hashvalue = self.hashfunction(key)

    if @slots[hashvalue] == nil
      @slots[hashvalue] = key
      @data[hashvalue] = data
    else
      if @slots[hashvalue] == key
        @data[hashvalue] = data
      else
        nextslot = self.rehash(hashvalue)
        while @slots[nextslot] != nil and @slots[nextslot] != hashvalue
          nextslot = self.rehash(hashvalue)
        end
        @slots[nextslot] = key
        @data[nextslot] = data
      end
    end
  end

  def hashfunction(key)
    num = 0
    key.each_byte {|c| num = num + c}
    return num % @size
  end

  def rehash(oldhash)
    return oldhash + 1
  end
end

a = HashTable.new()
a.put('fuck','shit')
a.put('ffff','cccc')
a.get('fuck')

_______冒泡
def bubbleSort(alist)
  index = alist.length - 2
  (1..alist.length - 1).each do
    (0..index).each do |i|
      if alist[i] > alist[i+1]
        alist[i], alist[i+1] = alist[i+1], alist[i]
      end
    end
    index = index - 1
  end
end

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
puts alist

_____________快排
def quickSortHelper(array, left, right)
  if(left < right)
    pivot = partition(array, left, right)
    quickSortHelper(array,left,pivot-1)
    quickSortHelper(array,pivot+1,right)
  end
end

def partition(array,left,right)
  pivotValue = array[left]
  leftIndex = left + 1
  rightIndex = right
  done = false
  while !done
    while leftIndex <= rightIndex && array[leftIndex] <= pivotValue
      leftIndex = leftIndex + 1
    end

    while rightIndex >= leftIndex && array[rightIndex] >= pivotValue
      rightIndex = rightIndex - 1
    end

    if rightIndex < leftIndex
      done = true
    else
      array[leftIndex],array[rightIndex] = array[rightIndex],array[leftIndex]
    end
  end
  array[left],array[rightIndex] = array[rightIndex],array[left]
  return rightIndex
end

def quickSort(array)
  quickSortHelper(array,0, array.length-1)
end

ar = [1,10,2,9,3,8]
res = quickSort(ar)
puts "#{res}"