T(0) = 1, T(1) = 0, T(n ) = 2* T(n-2) 的递归关系
Recurrence relation for T(0) = 1, T(1) = 0, T(n ) = 2* T(n-2)
我正在尝试查找上述表达式的递归关系。
我推断：
T(n) = C*T(n-2)
T(n-2) = 2C*T(n-4)
T(n-4) = 3C * T(n-6)
...
T(n) = k/2C * T(n-k)
我被困在这里了。这是正确的方法吗？什么是简化方程中没有T的简化递推关系？
写了一个python程序，发现关系：
def rec(num):
if num == 0:
return 1
elif num == 1:
return 0
else:
return 2 * rec(num - 2)
经过多次测试，我发现了这个规律：
index 2, 3, 4, 5, 6, 7, 8....
result 2, 0, 4, 0, 8, 0, 16....
所以结果可能是 2^(n/2) 当 n = 2k && 0 当 n = 2k + 1（k 属于 Z）
让我们观察将此函数扩展 m 次时的行为：
T(n) = 2^2 * T(n - 2*2)
= 2^3 * T(n - 2*3)
= 2^4 * T(n - 2*4)
= ...
= 2^m * T(n - 2m)
当n为：
- 偶数：
n - 2m最终为零，也就是说最大值为m = n / 2，即T(n) = 2^(n/2)
- 奇数："最终等于1，也就是说
T(n) = 2^(...) * T(1) = 0
如果我们想用一个表达式来写：
T(n) = (1 - n + floor[n/2]) * 2^(n/2)
我正在尝试查找上述表达式的递归关系。
我推断：
T(n) = C*T(n-2)
T(n-2) = 2C*T(n-4)
T(n-4) = 3C * T(n-6)
...
T(n) = k/2C * T(n-k)
我被困在这里了。这是正确的方法吗？什么是简化方程中没有T的简化递推关系？
写了一个python程序，发现关系：
def rec(num):
if num == 0:
return 1
elif num == 1:
return 0
else:
return 2 * rec(num - 2)
经过多次测试，我发现了这个规律：
index 2, 3, 4, 5, 6, 7, 8....
result 2, 0, 4, 0, 8, 0, 16....
所以结果可能是 2^(n/2) 当 n = 2k && 0 当 n = 2k + 1（k 属于 Z）
让我们观察将此函数扩展 m 次时的行为：
T(n) = 2^2 * T(n - 2*2)
= 2^3 * T(n - 2*3)
= 2^4 * T(n - 2*4)
= ...
= 2^m * T(n - 2m)
当n为：
- 偶数：
n - 2m最终为零，也就是说最大值为m = n / 2，即T(n) = 2^(n/2) - 奇数："最终等于1，也就是说
T(n) = 2^(...) * T(1) = 0
如果我们想用一个表达式来写：
T(n) = (1 - n + floor[n/2]) * 2^(n/2)