[scheme] CSIE.NTNU (2012.3-001)

系上程式設計能力鑑定的其中一題, 順便拿來練習 scheme
(當然當時是用 C++ 寫 XD)




概要：
某戰鬥貓比賽 貓有其等級與血量
等級一和等級二的貓咪砲 攻擊力都為 1
等級三的貓咪砲攻擊力為 1(lv1) + 1(lv2) = 2
等級四的貓咪砲攻擊力為 1(lv2) + 2(lv3) = 3

攻擊力 n 則每次攻擊令敵人減少 n HP
等級 L 的貓咪 擁有 lv.1, lv.2, ... lv.L 的貓咪砲各一顆

在決鬥時 為避免敵人慘死 不能敵人的HP打至負值
（如果敵人HP=2 不可以用攻擊力3以上的砲彈打他）
當敵方HP為 0 時就勝利

請問 等級 N 的貓咪, 最少要幾顆砲彈才能打贏 HP 為 H 的對手？

INPUT
你的貓的等級　敵人的血量

OUTPUT
需要的砲彈

---

仔細推敲之後發現並不困難
因為費氏數列的特性 讓這題可以直接用貪婪法求解 ～

---

Scheme (R5RS) :

(define cat-table (make-vector 100 0))
(vector-set! cat-table 1 1)
(vector-set! cat-table 2 1)

(define (fill-cat n)
  (define (iter i)
    (if (< i n)
        (begin (vector-set! cat-table i
                     (+ (vector-ref cat-table (- i 1))
                        (vector-ref cat-table (- i 2))))
               (iter (+ i 1)))))
  (iter 3))
(fill-cat 100)

(define (cat n) (vector-ref cat-table n))

(define (foo)
  (define (attack hp level i)
    (cond ((zero? hp) i)
          ((> (cat level) hp) (attack hp (- level 1) i))
          (#t (attack (- hp (cat level)) (- level 1) (+ i 1)))))
  (let ((level (read)) (hp (read)))
    (if (not (eof-object? hp))
        (begin
          (display (attack hp level 0))
          (newline)
          (foo)))))

(foo) ;; start proc..