博雅旅游网 > 澳洲旅游网 > 斐济 > 斐济

斐波拉契数列的算法框图该如何表达?

著名的斐波拉契数列的非递归源程序

  计算斐波拉契数列F(n)

  F(n) = n n = 0,1,2

  F(n) = F(n-1) – F(n-3) n>=3

  要求不用递归算法计算

  /* 递归算法 */

  unsigned int fn(unsigned int n)

  {

  if(n < 3)

  {

  return n;

  }

  else

  {

  return (fn(n - 1) + fn(n - 2));

  }

  }

  /* 非递归算法 */

  #define STACKSZ 100

  static unsigned int stack[STACKSZ];

  static unsigned int idx;

  int push(unsigned int *e)

  {

  if(idx < STACKSZ)

  {

  stack[idx ++] = *e;

  return 1;

  }

  else

  {

  return 0;

  }

  }

  int pop(unsigned int *e)

  {

  if(idx > 0)

  {

  *e = stack[-- idx];

  return 1;

  }

  else

  {

  return 0;

  }

  }

  unsigned int fn2(unsigned int n)

  {

  unsigned int res;

  unsigned int cur;

  if(n < 3)

  {

  return n;

  }

  else

  {

  res = 0;

  cur = n;

  while(1)

  {

  if(cur < 3)

  {

  res += cur;

  if(pop(&cur) == 0)

  {

  break;

  }

  }

  else

  {

  cur --;

  push(&cur);

  cur --;

  }

  }

  return res;

  }

  }

  /* 测试程序 */

  void main(void)

  {

  #define NUM 40

  unsigned int i;

  printf("We will output the xxxxxxx number serial:\n");

  for(i = 0; i < NUM; i++)

  {

  printf("%d ", fn(i));

  }

  printf("\n");

  printf("We will output the xxxxxxx number serial using method 2:\n");

  for(i = 0; i < NUM; i++)

  {

  printf("%d ", fn2(i));

  }

  printf("\n");

  }

  两种解法区别:

  递归法:速度慢,但是可读性强,易维护,可以计算序列受堆栈大小限制

  非递归法:速度快,声空间(至少减少n个保存现场进栈的ss,pc寄存器值), 但是代码复杂,可读性差,不易维护,可以计算序列可以控制,但是也不易估算需要堆栈空间的大小

  

上一篇:黄金海岸(Gold Coast)绿林丛荫
下一篇:西澳美景:品味彩色的世外桃源(组图)
元芳正在关注以下资讯:

.