2012-09-04

Chapter 5 遞迴關係

請問這題到底在說什麼？我怎麼想也想不到2r-1次比較是怎麼算出來的..？一次比兩個...怎麼會是2r-1次
於

6 則留言:

  1. M2012年9月4日凌晨3:15

    他的意思是
    "如果我要決定砍哪兩個數字必須花2r-1次的比較"

    至於為什麼要花2r-1次，這不重要

    反正他的重點在於每一層的遞迴的cost是2r-1，所以遞迴關係式就是An = An-2 + 2r-1

    (如果下一題的演算法他說要花10r+65535次比較，那就是An = An-2 + 10r+65535)

    回覆刪除
  2. 月戀星辰2012年9月4日上午9:11

    作者已經移除這則留言。

    回覆刪除
  3. 月戀星辰2012年9月4日上午9:12

    無論Ar多少都是要2r-1？

    回覆刪除
  4. M2012年9月4日下午1:40

    作者已經移除這則留言。

    回覆刪除
  5. M2012年9月4日下午1:42

    fun( int r )　{

    　if ( r == 0 || r == 1 )
    　　return 0;

    　for ( int i = 0 ; i < 2r-1 ;i++ ) {
    　　if ( comparison ) // (*)
    　　　do something...
    　} // for...

    　return fun( r-2 );
    }

    然後問你請問(*)處跑了幾次
    r代9，A9 = 17 + A8
    r代8，A8 = 15 + A7
    ...

    反正2r-1這傢伙也會一直縮小，你就別太在意他演算法是怎麼寫了...

    回覆刪除
  6. 月戀星辰2012年9月4日晚上11:37

    好吧，感謝您的幫忙

    回覆刪除