kkzhuoji
2015-03-18 12:43
采纳率: 100%
浏览 5.0k
已采纳

求解下列递推关系式,给出确切解:

(1)T(n)=T(n-1)+n/2; T(1)=1

(2)T(n)=8T(n-1)-15T(n-2); T(1)=1,T(2)=4

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • zengnm 2015-03-18 15:27
    已采纳

    这是数学问题吧?
    (1)T(n)=T(n-1)+n/2 = T(n-2) + (n-1)/2 + n/2 = ...... = T(n - (n-1)) + 2/2 + ... (n-1)/2 + n/2 = (n+2)(n-1)/4 +1;
    ( 2) T(n) - 3T(n-1) = 5(T(n-1) - 3T(n-2)) , 令S(n)= T(n+1) - 3T(n) ,n>=1;
    有S(n) = 5S(n-1),S(1) = 4-3*1=1;
    ∴ S(n) = 5^(n-1);
    ∴T(n+1) - 3T(n) = 5^(n-1);即T(n+1) = 3T(n) + 5^(n-1) = 3(3T(n-1) + 5^(n-2))+5^(n-1) =... = 3^n * T(1) + 5^n(1-(3/5)^n)/2
    ∴ T(n) = 3^(n-1) + 5^(n-1)/2 (1- (3/5)^(n-1)),n>= 1;

    已采纳该答案
    评论
    解决 1 无用
    打赏 举报
  • threenewbee 2015-03-18 15:06

    很简单,就是递归算法,比如第一题:
    T(1) = 1
    T(2) = 1 + 1 = 2
    T(3) = 2 + 1.5 = 3.5
    T(4) = 3.5 + 2 = 5.5
    T(5) = 5.5 + 2.5 = 8
    以此类推,继续算下去就行了。
    你也可以写一个程序:
    double foo(int n)
    {
    if (n == 1) return 1;
    return foo(n - 1) + n / 2.0;
    }
    然后让计算机帮你算。

    评论
    解决 无用
    打赏 举报
  • threenewbee 2015-03-18 15:07

    另一个类似,就直接给你程序,自己用计算机去算:
    int foo(int n)
    {
    if (n == 1) return 1;
    if (n == 2) return 4;
    return 8 * foo(n - 1) - 15 * foo(n - 2);
    }

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题