2010年4月28日 星期三

UVa 548 Tree

解題策略

典型的Binary Tree的題目,牽涉到兩個跟Binary Tree相關的動作
  1. 我們知道只要有 inorder + postorder 就可得唯一的一棵 binary tree。那該怎麼把樹建起來呢 ? 我寫在 build_tree()裡。
  2. 樹建起來之後,該怎麼走這顆樹,才能找出最小路徑呢? 這我寫在 do_summing( ) 函數,遞迴往下累加總和,再回傳最小的樹葉回來。
Tree 天生就是遞迴結構,用遞迴來寫再自然不過了。

注意

Tree原本應該是NULL的地方,我都掛了外部點(External Node),這樣會讓程式碼清爽一些。

2010年4月24日 星期六

UVa 490 Rotating Sentences

解題策略

相當有趣的題目,要旋轉字串90度再印出。注意字串不足的部份要自行補白。
提供一個測資:
aaa    aaa
 bbb  bbb
  cccccc
   dddd
    ee
   f  f
  g    g
   h  h

2010年4月23日 星期五

UVa 455 Periodic Strings

解題策略

這題要找出字串中的最小週期,我的作法比較好玩一些。
首先用兩個指針i,j分別指向字串的頭兩個字母,像這樣:
abcdabcd
↑↑
我的基本想法很簡單,讓i,j之間保持一個固定間距,如果這個間距就是週期,那麼且同步往後移動指針,比對字母,i,j指的兩字母應該要一直都相同。
# 例子:不管何時,兩指針的字母皆同。
abcabcabc
↑  ↑
abcabcabc
 ↑  ↑
abcabcabc
  ↑  ↑

那麼我們的任務就是找出i, j 的間距啦。初始從週期值1開始比對兩字,不同表示尚未找到週期,拉開指針的間距一格 (++j) 。直到兩字相同 buf[i]==buf[j],這時候可能就是字串中的週期出現了,同步移動指針 (++i,++j) 持續往後比對。

這個作法有兩個Special case要考慮
  1. 字串只有一個字母的時候(長度為1),兩根指針還能指去哪,直接return 1。
  2. 有時候字串尾巴會出現一些破壞週期的字母,例如:abcabcabcd,或者hohaho。所以最後必須檢查找到的週期,跟字串長度是否恰好是倍數關係。若不能整除就表示有這種討人厭的破壞字母出現了,週期值直接等於字串長度。

2010年4月21日 星期三

UVa 10082 WERTYU

解題策略

慶祝新書入手,解了書中第一題噴題。盯著鍵盤建好Ascii對應表:如 map['W'] = 'Q',注意空格跟換行不需要換字。


2010年4月18日 星期日

Ruby 快速筆記: Block and Iterator

Block

Block是相當特別的東西,在某些語言裡block被稱做closure,
先看個例子,我需要連續打印"hello"五次,那麼這樣寫就行:
5.times { print "hello" }
# hellohellohellohellohello
Ruby是個純OO語言,所以數字5也有函數可以呼叫,times就是其中之一。
這個例子最常被拿來說嘴Ruby有多麼簡潔。

Block可以看作某種匿名的函數,或者是...一沱程式碼。
{ print "hello" }    # 這就是一個block
Block不能單獨存在,必須掛在function call後面,以供function使用,
例如它附掛在times這個函數後面,而5.times的功用就是連續執行這個block五次!
這程式可讀性實在高。(有什麼比5.times更接近五次?)

Iterator

那這個Block有什麼實際的用途呢?
Ruby裡的Iterator就是用Block來達成。
例如
a = ["apple", "banana", "orange"]  
這是一個字串Array,我們想要遍訪a的各個元素,該怎麼做呢?
a.each { |s| puts s+'is fruit' }

# 執行結果
# apple is fruit
# banana is fruit
# orange is fruit
a.each 這個方法會遍訪array的各個元素(此處就是水果的名稱),並且對每個元素就都調用一次Block。Block開頭處的 |變數| ,就代表當下的的陣列元素,例如上例的 |s|就是各個水果的名稱。這個例子我們將陣列內水果的名稱都打印出來。

以下還有很多例子
(1..100).each { |i| puts i }    # 依序印出數字1~100
('a'..'z').each { |c| puts c }  # 依序印出26個英文字母
[1,2,3,4,5].map { |e| e*e }     # [1,4,9,16,25] 陣列每個元素都取平方

open('aaa.txt').each do |line|  # 檔案逐行讀取
    puts line
end
Block算是相當便捷的用法。

最後一提,Block其實有兩種寫法:
1. do ... end
2. {...}
當然效果是一模一樣。
a.each { |e| puts e }

a.each do |e|
    puts e
end
慣例是block內有多行程式碼用do end,若單行則用{}較緊湊。

2010年4月17日 星期六

Ruby 快速筆記: 流程控制

流程控制都差不多,一般語言該有的都有

if-else 敘述

if weight > 80
    puts "You are too fat!"
elsif weight > 60
    puts "You are ok"
else
    puts "You are too thin!"
end

While範例

Echo程式,會重複你輸入的字句
while line = gets
    puts line
end

For Loop

印出1~10的平方,形式相當簡潔
for i in 1..10
    print i*i
end

# 1 4 9 16 25 ...

倒裝句

比較特別的一點,就是從Perl借來的倒裝句法(後置條件)
可以創造出近似英文敘述的語句,相當漂亮。
puts "Good Job" if price<100
puts "Level Up!" if exp>10000
例如我們想把陣列內元素全部依序pop出來
array = [1,3,5]
while not array.empty?
    puts array.pop
end

#上面那幾行意義完全等同這一句
puts array.pop while not array.empty?
事實上還有個 until loop,剛好判斷條件跟while相反
所以這樣寫效果也一樣
puts array.pop until array.empty?

Ruby 快速筆記: 一個簡單的函數

一個簡單的函數叫 say_hi ,很容易理解。
def say_hi ( name )
    s = "Hello, "+ name
    return s
end
也可以像php一樣把變數嵌到字串裡,用法是 #{變數} 。
但只有""雙引號夾住的字串才會解析,''單引號不會,這點也像php。
def say_hi ( name )
    s = "Hello, #{name}"
    return s
end
Ruby會自動回傳最後出現的變數值,所以return也可以省略。
def say_hi ( name )
    "Hello, #{name}"   #這樣寫效果一樣
end
呼叫的效果
puts say_hi("David")    # "Hello, David"
puts say_hi "Mary"      # "Hello, Mary" 括號也可以省略
省略括號的用法自己看狀況斟酌
如果參數很多,易搞混順序,還是加一下比較好。

Ruby 快速筆記: Hello Ruby

Hello Ruby

不可免俗得來一下 Hello Ruby
puts "Hello Ruby!"  # 螢幕印出 Hello Ruby!
puts跟C/C++的用法一樣,輸出字串到螢幕上並附上一個換行\n。

Ruby有一個蠻有趣的特性,就是呼叫函數時若不會造成歧義,可省略括號。
puts("Hello Ruby")  
puts "Hello Ruby"  # 這兩行意思一樣

這有什麼好處呢?除了少敲幾下鍵盤外,可以讓code看起來更簡單清爽
例如Ruby 的 setter
s = Song.new
s.title="星晴"     # 這行原本是 s.title=("星晴") 
s.singer="周滷蛋"  # 看似直接存取成員變數,其實是透過setter函數
                  # 兼顧了物件的封裝性跟程式碼的可讀性

Ruby Way

Ruby允許函數使用少數幾個特殊符號作為的結尾。
而這些符號都有特殊的意義,例如上面提到的等號(=)通常就拿來作為setter
還有問號(?) 以問號結尾的函數會回傳True/False
2.zero?    # falsev  (是零嗎?)
[].empty?  # true    (陣列是空的嗎?)

驚嘆號(!)代表危險,或者會改動原本的變數值
s = "DAVID"
s.downcase    # 回傳"david" ,但s依然是"DAVID"。
s.downcase!   # s變成"david"

這種規則就叫做 Ruby way

Ruby 快速筆記: Everything is Object

Ruby裡所有的東西都是物件。
包括數字、陣列、字串都是物件。
所以會生出一些看似神奇的用法

# 數字是物件
-55.abs          # 55       (取絕對值)
2.zero?          # false    (是零否?)
10.to_f          # 10.0     (轉成浮點數)
20.to_s          # "20"     (轉成字串)
1.2.round        # 1        (四捨五入)

# 字串也是物件
"KERKER".length  #  6       (取字串長度)
"hello".upcase   # "HELLO"  (轉成大寫)

# Array也是物件
[1,5,2].sort     # [1,2,5]  (陣列排序)
[1,2,3].reverse  # [3,2,1]  (陣列反轉)
a.push("f")      # 作為stack使用

這些用法都很簡單,也很直覺。

2010年4月1日 星期四

UVa 10405 Longest Common Subsequence

Dynamic Programming的基本題 LCS

DJWS的LCS筆記
洪朝貴老師的動態規劃講義

這題我寫了兩種解法
LCS() 是一般的作法,最清楚直接。
LCS_save_memory() 是針對記憶體優化過的算法。

這題唯一要小心的點就是UVa的字串中包含空格。