技术

Ruby实战

先从一段Ruby程序开始，即欧几里德最大公约数的算法实现：
测试用例当然要先，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
require 'test/unit'
require './one/Apple'

class TestApple < Test::Unit::TestCase

  def test_cal
    ys = Apple.new
    assert_equal(5,ys.gcd(35,25))
    assert_equal(50,ys.gcd(100,50))
    assert_equal(9,ys.gcd(27,18))
    assert_equal(5,ys.gcd(5,10))
    assert_equal(5,ys.gcd(5,0))
    assert_equal(-5,ys.gcd(-5,0))
    assert_raise(ArgumentError){ys.gcd(0,0)}
    assert_equal(23,ys.gcd(0,23))
  end
end

然后就是算法的实现代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Apple

  def gcd(arg1=0, arg2=0)
    if((arg1==0)&&(arg2==0))
      raise ArgumentError, "arg1 and arg2 are 0.", caller
    else
      gcdImpl(arg1,arg2)
    end    
  end
  
  def gcdImpl(arg1=0, arg2=0)
    if(arg2 == 0)
      return arg1
    elsif
      temp=arg1%arg2
      if(temp == 0)
        return arg2
      else
        gcdImpl(arg2,temp)
      end
    end
  end

end

从一个算法的描述来实现一个算法，仅仅是编写一段程序而已。而对于算法这种问题的程序化解决方案而言，需要如何一回事情呢？比方说，最大公约数到底是怎么一回事，5和0的最大公约数怎么可能是5呢？所以要学习算法到底是怎么一回事，需要探讨更多的问题？
对于问题的理解、性能、选择、数据结构、如何设计、算法的描述、正确性证明、分析、代码实现等等一系列单元。当程序实现仅仅是第一反应的时候，问题理解、分析、设计、验证就变得异常重要了。
算法所拥有的通用问题类型：排序、查找、字符串处理、图问题、组合问题、几何问题、数值问题；都是一些已经相当成熟的问题类型。很多使我们常常听说或者涉及的，也是算法设计和分析频繁的地方，算是很多的“肩膀”吧，算法都是都是在这里站立起来的。