[数据结构与算法]递归，迭代算法

几种算法

一，.递归方程(用迭代法)
*斐波那契数列

斐波那契数列：第1，2两个数为1，1。从第三个数开始，该数是其前面两个数之和。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main()
{
 int n = 0;
 int a = 1;
 int b = 1;
 int c = 0;
 int i = 0;
 scanf("%d", &n);
 printf("%5d %5d ", a, b);
 for (i = 0; i < n - 2;i++)
 {
   c = a + b;
   a = b;
   b = c;
   printf("%5d ", c);
 }
 printf("\n");
 system("pause");
 return 0;
}

*汉诺塔递归

#include<stdio.h>
void move(int n,char a,char b,char c)
{
if(n==1)
printf("\t%c->%c\n",a,c); //当n只有1个的时候直接从a移动到c 
else
{ 
move(n-1,a,c,b); //把a的n-1个盘子通过c移动到b 
printf("\t%c->%c\n",a,c); //把a的最后1个盘(最大的盘)移动到c 
move(n-1,b,a,c); //吧b上面的n-1个盘通过a移动到c 
} 
}
int main()
{
int n;
printf("请输入要移动的块数："); 
scanf("%d",&n);
move(n,'a','b','c');
}

*插入排序递归

 void insert(vector<int>& a, int x=1)    
{                                                   //第一个参数为向量，第二个参数为将要向前插入的数
 if(x >= (int)a.size())       //判断是否已经到了向量的最大值
  return;        //是即返回，程序结束
 int temp = a[x],j;       //定义变量，temp存储当前数值
 for(j = x; j > 0 && a[j-1] > temp; j--)     //和插入排序普通算法一样，从当前数开始，从后往前插入
  a[j] = a[j-1];         //通过赋值，节省时间
 a[j] = temp;               //找到正确位置后，赋值，
 insert(a, x+1);        //递归，开始插入下一个数
}

2.迭代法
*每次用递归方程的右项代替左项
*每次代替，随着n的降低，多一项
*直到出现初值停止迭代
*带入初值，求出递归方程
*用数学归纳法验证正确性

3.贪心算法:不从整体考虑，从局部或是某种意义上的最优解
*贪心选择性质:一个问题的整体最优解可以用子结构最优解达到，并且后一子问题在前一问题基础
*最优子结构性质:一个问题最优解包含子问题最优解