Question

算法设计与分析题目

递归方程 f(n)=4f(n/2)+n f(1)=1 其中,n是2的幂 用递推法解此方程 求详细过程

Answer 1

设n=2^k,把原式变形为f(2^k)/4^k=f(2^(k-1))/4^(k-1)+0.5^k,令a(k)=f(2^k)/4^k,得a(k)=a(k-1)+0.5^k (a(0)=1),a(k)=2-0.5^k,f(n)=2n^2-n

Answer 2

int func (int num){

//判断输入是否为2的幂 
  if (num<0||(num&(num-1))!=0){

   return -1;

  }

  int i=1,result=1;

  while (i<num){

   i=2*i;

   result = 4*result+i;

  }

  return result;

 }

追问

要列算式。。。这个没用