1.为一个分治算法编写伪代码，该算法用来计算指数函数a^n的值，其中a>0,n是一个正整数 2.假设n=2^k,为该算法的键值比较次数建立递推关系式并求解 3.请见该算法与解同样问题的蛮力算法做一个比较

1. 以下是指数函数a^n的分治算法的伪代码：

function pow(a, n):
    if n == 0:
        return 1
    else if n % 2 == 0:
        half = pow(a, n/2)
        return half * half
    else:
        half = pow(a, (n-1)/2)
        return half * half * a

在这个算法中，如果指数n为0，则返回1。否则，如果n为偶数，则将指数分成两半，递归地计算a的一半指数的平方，然后将这两个平方相乘。如果n为奇数，则先计算(n-1)/2的一半指数的平方，然后将其乘以自身和a的乘积。这个算法的时间复杂度为O(log n)。

2. 假设n=2^k，则该算法的键值比较次数可以建立如下的递推关系式：

T(k) = T(k/2) + 1 (n>1)
T(0) = 0

其中，T(k)表示在计算a^n时的键值比较次数。第k步时，需要比较a^(2^(k-1))和a^(2^(k-1))的乘积，因此需要进行1次键值比较。然后，将n缩小一半，递归地进行下一步计算。

根据递推关系式，我们可以得到：

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

因此，该算法的键值比较次数为O(log n)。

3. 与蛮力算法相比，分治算法的优势在于它可以将指数n缩小一半，从而减少指数运算的次数。蛮力算法需要进行n-1次乘法运算，而分治算法只需要进行log n次乘法运算。因此，当指数n很大时，分治算法的效率要远高于蛮力算法。