戎解证明题2：求解递推方程并证明结论 证明T(n)=T（[n/2]）+1的解是O(logn）(注：不能直接使用 主定理）。

### 回答1：
根据题意，我们可以得到递推式T(n)=T([n/2])+1，其中 [n/2] 表示向下取整，T(1)=1。

为了求解T(n)的时间复杂度，我们可以采用递归树的方法，将问题的规模缩小到1，然后计算递归树的深度。

首先，我们可以将T(n)表示为以下形式：

T(n) = T(n/2) + 1
= T(n/4) + 1 + 1
= T(n/8) + 1 + 1 + 1
...
= T(1) + k
= k + 1

其中，k表示递归树的深度。

因为我们知道，当n=1时，递归结束，所以k=log2n。

因此，T(n)的时间复杂度为O(logn)。

需要注意的是，这里我们并没有直接使用主定理来求解递归式的解，而是通过递归树的方式进行计算。主要是因为递归式不符合主定理的形式，无法直接套用公式。

### 回答2：
题目要求我们求解递推方程T(n)=T([n/2])+1，并证明结论T(n)=O(logn)。

首先，我们可以通过不断代入的方法求出一些初始值，看是否有规律可循。

当n=1时，T(1)=0；
当n=2时，T(2)=T(1)+1=1；
当n=3时，T(3)=T(1)+1=1；
当n=4时，T(4)=T(2)+1=2；
当n=5时，T(5)=T(2)+1=2；
当n=6时，T(6)=T(3)+1=2；
当n=7时，T(7)=T(3)+1=2；
当n=8时，T(8)=T(4)+1=3；
...

我们可以观察到，当n为奇数时，T(n)=T((n-1)/2)+1，当n为偶数时，T(n)=T(n/2)+1。

现在来证明结论T(n)=O(logn)。

我们假设n=2^k，其中k为一个正整数。

当n为2的幂时，我们有以下推导过程：
T(n) = T(n/2) + 1
= T(n/4) + 1 + 1
= T(n/8) + 1 + 1 + 1
= ...
= T(1) + 1 + 1 + ... + 1 (共k次)
= k
= logn

因此，当n为2的幂时，T(n)=k=logn，结论成立。

当n不为2的幂时，我们可以将n表示为2^k+c的形式，其中0<c<2^k。

我们可以发现，通过不断将奇数向下取整，最后一定可以得到2的幂（即k=0时的情况）。所以，当n不为2的幂时，T(n)的结果一定等于某个2的幂的T值再加上一些常数项。

综上所述，T(n)=O(logn)成立。

（证明完毕，300字）

### 回答3：
首先我们来求解递推方程T(n) = T([n/2])，其中[n/2]表示对n除以2进行向下取整。

对于递推方程T(n)，我们可以按照以下步骤进行求解：

1. 基本情况：当n=1时，递推方程T(n) = T([n/2])变为T(1) = T([1/2])，即T(1) = T(0)。显然T(1)的解为O(1)。

2. 递归情况：当n>1时，递推方程T(n) = T([n/2])可以分解为以下两步：
a) 计算T([n/2])，即将n除以2向下取整。
b) 递归求解T([n/2])。

由于每次都将n除以2向下取整，所以在递归的过程中，n的值会不断减小，最终会到达基本情况n=1。

假设递归调用的次数为k次，那么初始的n为n，第一次递归求解T(n/2)时，n变为n/2，第二次递归求解T(n/4)时，n变为n/4，以此类推，第k次递归求解T(n/2^k)时，n变为n/2^k=1，即k=log2(n)。

因此，递推方程T(n)的解的复杂度为O(logn)。

接下来，我们来证明T(n)=O(logn)。

假设T(n) = T(n/2) + c，其中c是一个常数。

根据递推方程的解T(n)=O(logn)，我们有T(n/2)=O(log(n/2))=O(logn-1)=O(logn)。

将T(n/2)代入原方程，我们有T(n) = T(n/2) + c = O(logn) + c。

因此，我们得到T(n)=O(logn) + c，其中c是一个常数。

综上所述，递推方程T(n)=T([n/2])的解为O(logn)。

注意：本解答不能直接使用主定理，而是通过逐步求解递推方程，并在递归的过程中计算每次递归的次数来得到解的复杂度。