递归是一种数学上分而自治的思想。
A、将原问题分解为规模较小的问题进行处理
分解后的问题与原问题类型完全相同,当规模较小。
通过小规模问题的解,能够轻易求得原生问题的解
B、问题的分解时有限的
当边界条件不能满足时,分解问题(继续递归)
当边界条件满足时,直接求解(递归结束)
递归模型的一般表示法:
递归在程序设计中的应用
递归函数:
函数体中存在自我调用的函数
递归函数必须有递归出口(边界条件)
函数的无限递归将导致程序崩溃
使用递归函数时不要陷入递归函数的执行细节,应首先建立递归模型和确立边界条件。
int sum(unsigned int n)
{
int ret;
if(n > 1)
{
ret = n + sum(n - 1);
}
else if(n == 1)
{
ret = 1;
}
return ret;
}
unsigned int Fibonacci(unsigned int n)
{
unsigned int ret ;
if(2 < n)
{
ret = Fibonacci(n -1) + Fibonacci(n -2);
}
else if((n == 1) || (n == 2))
{
ret = 1;
}
return ret;
}
int _strlen_(const char* s)
{
int ret = 0;
if(*s != '\0')
{
ret = 1 + _strlen_(s+1);
}
else
{
ret = 0;
}
return ret;
}
代码简化:
unsigned int _strlen_(const char* s)
{
return s?((*s)?(1 + _strlen_(s + 1)):0):0;
}
typedef struct
{
int data;
Node* next;
}Node;
Node* reverse(Node* list)
{
Node* ret = NULL;
if(list == NULL || list->next == NULL)
{
ret = list;
}
else
{
Node* guard = list->next;
ret = reverse(list->next);
guard->next = list;
list->next = NULL;
}
return ret;
}
typedef struct
{
int data;
Node* next;
}Node;
Node* merge(Node* list1, Node* list2)
{
Node* ret = NULL;
if(NULL == list1)
{
ret = list2;
}
else if(NULL == list2)
{
ret = list1;
}
else if(list1->data < list2->data)
{
list1->next = merge(list1->next,list2);
ret = list1;
}
else
{
list2->next = merge(list2->next, list1);
ret = list2;
}
return ret;
}
汉诺塔问题:
A、将木块借助B柱由A柱移动到C柱
B、每次只能移动一块木块
C、小木块只能出现在大木块之上
汉诺塔问题的解决方案:
A、将n-1个木块借助C柱由A柱移动到B柱
B、将最底层的木块直接移动到C柱
C、将n-1个木块借助A柱由B柱移动到C柱
/*********************************
* n:木块的数量
* A:A柱
* B:B柱
* C:C柱
* 汉诺塔问题:将n个木块从A柱借助B柱移动到C柱
* ******************************/
void HanoiTower(int n, char A, char B, char C)
{
if(n == 1)
{
cout << A << "-->" << C << endl;
}
else
{
//将A柱上的n-1个木块借助C柱移动到B柱
HanoiTower(n-1, A, C, B);
//将A柱上的木块,直接移动到C柱
HanoiTower(1, A, B, C);
//将B柱上的n-1个木块借助A柱移动到C柱
HanoiTower(n-1, B, A, C);
}
}
void permutation(char* s, char* ret)
{
if('\0' == *s)
{
cout << ret << endl;
}
else
{
int len = strlen(s);
for(int i = 0; i < len; i++)
{
if(0 == i || (s[0] != s[i]))
{
swap(s[0], s[i]);
permutation(s+1, ret);
swap(s[0], s[i]);
}
}
}
}
程序运行后有一个特殊的内存区域(栈)供函数调用使用:
A、用于保存函数中的实参、局部变量、临时变量等
B、从起始地址开始往一个方向增长
C、有一个专用指针标识当前已用内存的顶部
程序中的栈区:
逆序打印单链表中的偶数结点:
typedef struct
{
int data;
Node* next;
}Node;
void r_print_even(Node* list)
{
if(NULL !=list)
{
r_print_even(list->next);
if(list->data %2 == 0)
{
cout << list->data << endl;
}
}
}
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。八皇后问题就是回溯算法的典型,第一步按照顺序放一个皇后,然后第二步符合要求放第2个皇后,如果没有位置符合要求,那么就要改变第一个皇后的位置,重新放第2个皇后的位置,直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见,就是这条路走不通,然后返回前一个路口,继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数,剪去一些不可能到达最终状态(即答案状态)的节点,从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。`
在8X8的国际象棋棋盘上,有8个皇后,每个皇后占一个格子,要求皇后之间不会出现相互***的现象(任意两个皇后不能处在同一行、同一列或者同一对角线上)。
棋盘的定义:
二维数组(10X10),0表示位置为空,1表示皇后,2表示边界。
位置的定义:
struct Pos
{
int x;
int y;
};
方向定义:
水平左方向(-1, 0)
水平右方向(1, 0)
垂直上方向(0, 1)
垂直下方向 (0, -1)
左上对角线方向 (-1, 1)
左下对角线方向 (-1, -1)
右下对角线方向 (1, -1)
右上对角线方向 (1, 1)
template <int SIZE>
class QueueSolution : public Object
{
protected:
enum{N = SIZE + 2};//棋盘大小
struct Pos : public Object
{
Pos(int px = 0, int py = 0):x(px),y(py){}
int x;
int y;
bool operator==(const Pos& other)
{
return (this->x = other.x && this->y == other.y);
}
};
int m_chessBoard[N][N];//棋盘数据
Pos m_direction[3];//方向数据
LinkedList<Pos> m_solution;//皇后的位置
int m_count;//解决方案的数量
void init()
{
m_count = 0;
//初始化棋盘边界
for(int x = 0; x < N; x += (N-1))
{
for(int y = 0; y < N; y++)
{
m_chessBoard[x][y] = 2;//垂直边界
m_chessBoard[y][x] = 2;//水平边界
}
}
//初始化棋盘
for(int x = 1; x <= SIZE; x++)
{
for(int y = 1; y <= SIZE; y++)
{
m_chessBoard[x][y] = 0;
}
}
//左下角对角线方向
m_direction[0] = Pos(-1, -1);
//垂直向下方向
m_direction[1] = Pos(0, -1);
//右下角对角线方向
m_direction[2] = Pos(1, -1);
}
//打印棋盘
void printBoard()
{
for(m_solution.move(0); !m_solution.end(); m_solution.next())
{
cout << "(" << m_solution.current().x << "," << m_solution.current().y<< ") ";
}
cout << endl;
for(int x = 0; x < N; x++)
{
for(int y = 0; y < N; y++)
{
switch (m_chessBoard[x][y])
{
case 0:
cout << " ";
break;
case 1:
cout << "Q";
break;
case 2:
cout << "#";
break;
}
}
cout << endl;
}
}
bool check(int x, int y, int direction)
{
bool flag = true;
do
{
x += m_direction[direction].x;
y += m_direction[direction].y;
flag = flag && (m_chessBoard[x][y] == 0);
}while(flag);
return (m_chessBoard[x][y] == 2);
}
void run(int y)
{
if(y < SIZE)
{
for(int x = 1; x < SIZE; x++)
{
if(check(x,y,0) && check(x,y,1)&&check(x,y,2))
{
m_chessBoard[x][y] = 1;
m_solution.insert(Pos(x, y));
run(y+1);
m_chessBoard[x][y] = 0;
m_solution.remove(m_solution.length() - 1);
}
}
}
else
{
m_count++;
printBoard();
}
}
public:
QueueSolution()
{
init();
}
void run()
{
run(1);
cout << "Total:" << m_count << endl;
}
};
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。