英雄論壇

lcd242 寫:嗯 感謝 dulcet 兄為此題如此效力。
我剛有去看了網站，我想其中的重點是在 Solving Recurrences 中的部份
， 可惜他所解決的只到 T( n / (2 ^ i)) , i = 1~，至於這樣的問題，
算是簡單的(只要取log就行了)，而那題 鳥題，是 T( n / (2 ^ i) + c ), i = 1~
的form，在網站中不屬於 basic form，所以 Master Theorem 可能也不能解。
這幾天我有想到一個方法。
就是先將 Recurrences ，轉成 Algorithm，再將 Algorithm 轉成非遞回式的
Algorithm(理論上來說一定能轉)，再轉回數學式子，問題就在於 怎麼把 stack
轉成數學式。

布拉價 寫:喔買尬.....
整夜不睡覺只為ㄌ算這種鳥題目...
在下求知ㄉ精神
真是令人佩服....
欽敬!!欽敬!!

dulcet 寫:

lcd242 寫:

dulcet 寫: 這是程設的題目??還是數學的題目??
如果是數學的題目....解有無限個
解法是...先猜測..再代回驗正....只要滿足條件及可
but因為條件太少(只有兩個??).....所以有無限解
請再給些時間...我給你一個最最漂亮的解(50字or一個式子之內可以表達出來)
----------------------------------
如果是程設的題目..sorry..我是新手...

哦，這是數學的題目 ，一般來說解遞回不會要求你把"方程式的解" 解出，因為
n [- N 會有無限組解。
所以答案為一個 非遞回的 方程式，比如說
An = 3An-1 , n >= 1
{
A0 = 5
(n , n-1 跟 0 都是下標)
為一遞回式子
而其遞迴關係式的通解(general solution)為
An = 5(3^n) , n >= 0

或是有名的 Fibonacci 數列
Fn = Fn-1 + Fn-2 , n >=2 (n, n-1, n-2 為下標)
{
F0 = 0, F1 = 1 (F0中的0, F1中的1 為下標)
其通解為
Fn = (1/(5^(1/2))(((1+5^(1/2))/2)^n-((1-5^(1/2))/2)^n) , n >= 0

有個共同的特點是，解開的遞回式中已不包含原來的函數。
其解法目前書上看到的有：
1. 代入法
2. 特徵多項式法
3. 轉換法
4. 生成函數法
如果還有其他法，那我就不知道了，因為書上只有寫這幾種。
啊 這題 T(n) = 3T( n/2 + 1 ) + n , n>3, T(3) = 1
的迴關係式的通解，就是解不出來，有問過一些朋友，還沒有答案中。
至於書，我查過很多考試用書，連歷屆試題也一題一題的找，就是沒找到
類似的題目，自然就解不出。
這的確跟求時間複雜度很像，不過比較難，時間複雜度求的是一個近似值
(有時侯可以用猜的)，這個是要把精確的方程式求出。
我的參考書有
離散數學 (鼎荿), 試題詳解 86-88 (鼎荿), 習題詳解 (鼎荿)
DISCRETE AND COMBINATORIAL MATHEMATICS (離散聖經本)
INTRODUCTION TO ALGORITHMS (MIT舊版的)

我覺得你這一題應該是要問:1.請找到一個函數滿足題意
還是2.找到通解?
for example
f:n-->n,f(1)=2,f(f(n))=f(n)+n,f(n)<f(n+1)
這題
通解為:f(n)=[0.5((5)^0.5+1)n+0.5]..........[]為高斯函數
but卻有其他的解...如
若k+1屬於{f(1).....f(k)}.則可以定出
若k+1不屬於{f(1).....f(k)}.則定f(k+1)=f(k)+1
如此代回驗正...也會滿足原式(恕略)
so........
如果沒有遞增這條件..那這一題就是國小題...
現在切回原題
如果要求找到通解?..那麼的確是難題(連學長都不會)..值得討論..
如果要求解?那麼我來就可以了..不用麻煩學長....
我也可以告訴你f:n-->n,f(1)=2,f(f(n))=f(n)+n,f(n)<f(n+1)這題通解的解法
也是1.先猜測(和費氏數列有官)2.再猜測函數形式3.再猜測待定系數
4.再帶回驗正

lcd242 寫:

dulcet 寫:

lcd242 寫:
如果是條件不夠，那可能是今年出錯題目了，原題目為下
Solve the recurrence relation: T(n) = 3T( n/2 + 1 ) + n, for n>3 and T(3) = 1.

解的出來哦... T(n) = ....
請問是用 代入法 特徵多項式法 還是生成函數法 呢??
我連用什麼法都不知la...真遭

這是程設的題目??還是數學的題目??
如果是數學的題目....解有無限個
解法是...先猜測..再代回驗正....只要滿足條件及可
but因為條件太少(只有兩個??).....所以有無限解
請再給些時間...我給你一個最最漂亮的解(50字or一個式子之內可以表達出來)
----------------------------------
如果是程設的題目..sorry..我是新手...

哦，這是數學的題目 ，一般來說解遞回不會要求你把"方程式的解" 解出，因為
n [- N 會有無限組解。
所以答案為一個 非遞回的 方程式，比如說
An = 3An-1 , n >= 1
{
A0 = 5
(n , n-1 跟 0 都是下標)
為一遞回式子
而其遞迴關係式的通解(general solution)為
An = 5(3^n) , n >= 0

或是有名的 Fibonacci 數列
Fn = Fn-1 + Fn-2 , n >=2 (n, n-1, n-2 為下標)
{
F0 = 0, F1 = 1 (F0中的0, F1中的1 為下標)
其通解為
Fn = (1/(5^(1/2))(((1+5^(1/2))/2)^n-((1-5^(1/2))/2)^n) , n >= 0

有個共同的特點是，解開的遞回式中已不包含原來的函數。
其解法目前書上看到的有：
1. 代入法
2. 特徵多項式法
3. 轉換法
4. 生成函數法
如果還有其他法，那我就不知道了，因為書上只有寫這幾種。
啊 這題 T(n) = 3T( n/2 + 1 ) + n , n>3, T(3) = 1
的迴關係式的通解，就是解不出來，有問過一些朋友，還沒有答案中。
至於書，我查過很多考試用書，連歷屆試題也一題一題的找，就是沒找到
類似的題目，自然就解不出。
這的確跟求時間複雜度很像，不過比較難，時間複雜度求的是一個近似值
(有時侯可以用猜的)，這個是要把精確的方程式求出。
我的參考書有
離散數學 (鼎荿), 試題詳解 86-88 (鼎荿), 習題詳解 (鼎荿)
DISCRETE AND COMBINATORIAL MATHEMATICS (離散聖經本)
INTRODUCTION TO ALGORITHMS (MIT舊版的)

lcd242 寫:

dulcet 寫:

lcd242 寫:
如果是條件不夠，那可能是今年出錯題目了，原題目為下
Solve the recurrence relation: T(n) = 3T( n/2 + 1 ) + n, for n>3 and T(3) = 1.

解的出來哦... T(n) = ....
請問是用 代入法 特徵多項式法 還是生成函數法 呢??
我連用什麼法都不知la...真遭

這是程設的題目??還是數學的題目??
如果是數學的題目....解有無限個
解法是...先猜測..再代回驗正....只要滿足條件及可
but因為條件太少(只有兩個??).....所以有無限解
請再給些時間...我給你一個最最漂亮的解(50字or一個式子之內可以表達出來)
----------------------------------
如果是程設的題目..sorry..我是新手...

哦，這是數學的題目 ，一般來說解遞回不會要求你把"方程式的解" 解出，因為
n [- N 會有無限組解。
所以答案為一個 非遞回的 方程式，比如說
    An = 3An-1 , n >= 1
{
    A0 = 5
(n , n-1 跟 0 都是下標)
為一遞回式子
而其遞迴關係式的通解(general solution)為
An = 5(3^n) , n >= 0

或是有名的 Fibonacci 數列
    Fn = Fn-1 + Fn-2 , n >=2 (n, n-1, n-2 為下標)
{
    F0 = 0, F1 = 1 (F0中的0, F1中的1 為下標)
其通解為
Fn = (1/(5^(1/2))(((1+5^(1/2))/2)^n-((1-5^(1/2))/2)^n) , n >= 0

有個共同的特點是，解開的遞回式中已不包含原來的函數。
其解法目前書上看到的有：
1. 代入法
2. 特徵多項式法
3. 轉換法
4. 生成函數法
如果還有其他法，那我就不知道了，因為書上只有寫這幾種。
啊 這題 T(n) = 3T( n/2 + 1 ) + n , n>3, T(3) = 1
的迴關係式的通解，就是解不出來，有問過一些朋友，還沒有答案中。

dulcet 寫:

lcd242 寫:
如果是條件不夠，那可能是今年出錯題目了，原題目為下
Solve the recurrence relation: T(n) = 3T( n/2 + 1 ) + n, for n>3 and T(3) = 1.

解的出來哦... T(n) = ....
請問是用 代入法 特徵多項式法 還是生成函數法 呢??
我連用什麼法都不知la...真遭

這是程設的題目??還是數學的題目??
如果是數學的題目....解有無限個
解法是...先猜測..再代回驗正....只要滿足條件及可
but因為條件太少(只有兩個??).....所以有無限解
請再給些時間...我給你一個最最漂亮的解(50字or一個式子之內可以表達出來)
----------------------------------
如果是程設的題目..sorry..我是新手...

Kimano 寫:

lcd242 寫:我也來一題鳥題，研究所資工離散的題目
問了很多人都解不出，書上也沒有類似的題型

T(n) = 3T( n/2 + 1 ) + n
n > 3, T(3) = 1
請解遞回

看過很多題型，遞迴式裡的參數很少見到這種類型的( n/2 + 1)。
如果有參數是多項式，沒見過其系數非整數的(通常是1，這裡是 1/2)。
如果參數裡n的系數非整數的，通常參數為非多項式即 T(n/2)
(可以用轉換或代入法求解)。

這裡是 T( n/2 + 1 )
代入法不行，外面有 3 乘進去太難解。
轉換法， 如果是 T(n/2) trivial....這裡是 T(n/2 + 1) 不知道轉成什麼才收斂。
生成函數， 不知道要用那個生成函數(不屬於任何一種case)。
還有其他的結法嗎，這樣書上就沒寫了。

最後，如果很簡單就解出來的話，別笑我嘿，我是新手(NP Newbie)

這個題目...我記得是算時間複雜度的
我們演算法的期中考就有考這個
不過我......不會算

lcd242 寫:我也來一題鳥題，研究所資工離散的題目
問了很多人都解不出，書上也沒有類似的題型

T(n) = 3T( n/2 + 1 ) + n
n > 3, T(3) = 1
請解遞回

看過很多題型，遞迴式裡的參數很少見到這種類型的( n/2 + 1)。
如果有參數是多項式，沒見過其系數非整數的(通常是1，這裡是 1/2)。
如果參數裡n的系數非整數的，通常參數為非多項式即 T(n/2)
(可以用轉換或代入法求解)。

這裡是 T( n/2 + 1 )
代入法不行，外面有 3 乘進去太難解。
轉換法， 如果是 T(n/2) trivial....這裡是 T(n/2 + 1) 不知道轉成什麼才收斂。
生成函數， 不知道要用那個生成函數(不屬於任何一種case)。
還有其他的結法嗎，這樣書上就沒寫了。

最後，如果很簡單就解出來的話，別笑我嘿，我是新手(NP Newbie)