Back

递归函数练习题 (recursive function exams)

发布时间: 2012-08-17 02:17:00

递归函数非常重要。在解决很多实际问题中，在大学课程中，以及很多面试过程中，都要被用到。可以说是计算机的基础。自己之前做WEB开发，没有太重视，所以做一些补习 ^_^ 

Recursive function is the basic and the most important of computer science, and it is widely used in solving real problems, college education (basic courses), and in the interviews for a programmer job.  so, let's have some exams for it.  

1. factorial .  (阶乘）

given n = 3. should get result = 3x2x1 = 6
given n = 5, should get result = 5x4x3x2x1 

参考答案： (answer)

def factorial n
  return 1 if n == 1
  return factorial(n-1) * n 
end

2. fabonacci numbers:   (fabonacci 数列）  0, 1, 1, 2, 3, 5, 8, 13 ......

参考答案：(answer)

# 0, 1, 1, 2, 3, 5, 8, 13
def fabonacci n
  return 0 if n == 0
  return 1 if n == 1
  return fabonacci(n-1) + fabonacci(n-2)
end
def get_array n
  result = []
  n.times.to_a.reverse.each { |i| result << fabonacci(i) }
  return result
end
puts "fabonacci 8: #{fabonacci(8).inspect}"    
puts "fabonacci 8(array): #{get_array(8).inspect}"

以上代码的输出：

fabonacci 8: 21
fabonacci 8(array): [13, 8, 5, 3, 2, 1, 1, 0]

( 一个非常有趣的现象是： 越到后来， 两个相邻fabonacci的比值越接近黄金分割。例如： fab(19)/fab(20) = 0.618033985017358   )

3. 最大公约数（greatest common divisor)    

例如： 54 = 54 x 1 = 27 x 2 = 18 x 3 = 9 x 6 ,   thus the divisors of 54 are:  [ 1,2,3,6,9,18,27,54]
同样： 24 's divisors : [1,2,3,4,6,8,12,24]
the common divisors :  [1,2,3,6] 
so , the greatest common divisor :  gcd(54,24) = 6

# need a > b
def get_greatest_common_divisors_simplest(a, b)
  return a if b == 0
  get_greatest_common_divisors_simplest(b, a%b)
end

require 'test/unit'
class DivisorsTest < Test::Unit::TestCase
  def test_get_greatest_common_divisors_simplest
    assert_equal 6, get_greatest_common_divisors_simplest(54, 24) 
  end 
end

4. Tower of Hanoi 

简单的说，就是计算把若干盘子从一个柱子保持原有顺序的转移到另一个柱子所需要的步骤。

given three pegs, one with a set of N disks of increasing size, determine the minimum (optimal) number of steps it takes to move all the disks from their initial position to another peg without placing a larger disk on top of a smaller one.

# see: http://en.wikipedia.org/wiki/Towers_of_Hanoi
def hanoi(n)
  return 1 if n == 1
  return 2 * hanoi( n -1) + 1 
end

require 'test/unit'
class HanoiTest < Test::Unit::TestCase
  def test_hanoi
    assert_equal 15, hanoi(4)
    assert_equal 8, hanoi(7)
  end 
end

5. （快速排序算法）Quick Sort

对一个数组进行排序，先选定一个 pivot （中间数），然后把低于这个中间数的数组元素放到less 数组中，高于它的，放在 greater数组中。 接下来，重复这个过程，对less和 greater进行迭代. (sort an array using pivot, and patition. It first divide a large list into 2 smaller lists: less and greater, then sort them recursively )

问题的核心在于： 1. 对数组进行分区 . 2. 递归重复排序的过程。3. 使用2个空的数组来保存排序结果。 ( the core of the problem is: 1. partition. 2 recursively sort. 3. declare blank arrays to store the sorted sub lits )

ef quick_sort(array)
  if array.size < 2
    #puts "array size == 1: #{array.inspect}"
    return array
  end
  # find the pivot
  pivot, array  = parition(array)
  # now let's sort...
  less, greater  = [], []
  # divide the array by pivot (partition)
  array.each { |e| e <= pivot ? less << e : greater << e }
  sorted_array = less + [pivot] + greater
  #puts "after sort,: #{sorted_array.inspect}, less: #{less.inspect}, greater: #{greater.inspect}"
  return quick_sort(less) + [pivot] + quick_sort(greater)
end
def parition(array)
  #puts "find pivot from array: #{array.inspect}"
  index = array.size / 2
  pivot = array.delete_at(index)
  #puts "index: #{index}, value: #{array[index]}, array: #{array.inspect}"

  return [pivot, array]
end

# call it: 
quick_sort(Range.new(1, 1e4).to_a.shuffle)  # Finished in 0.20154 seconds
quick_sort(Range.new(1, 1e5).to_a.shuffle)  # Finished in 2.58 seconds

Back