-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
15692118659
小标
2019-05-08
来源 ：
阅读 1894
评论 0
摘要：本文主要向大家介绍了C/C++知识点之数据结构(10)_递归，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之数据结构(10)_递归，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。 "
递归时一种数学上分而自治的思想，将原有问题分解为规模较小的问题进行处理。
1.分解后的问题与原问题的类型完全相同，但规模较小；
2.通过小规模问题的解，能够轻易的求得原问题的解。
问题的分解是有限的（递归不能无限进行）
1.问题的边界条件不满足时，分解问题(递归继续进行)
2.但边界条件满足时，直接求解(递归结束)
- 递归函数
1.函数体中存在自我调用的函数
2.递归函数必须有递归出口（边界条件）
3.函数的无限递归将导致程序崩溃
递归思想的应用：
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;
}将木块借助B由A柱移动到C柱，每次只能移动一个木块，只能出现小木块在大木块之上。
问题分解：
--将n-1个木块借助C柱由A柱移动到B柱；
--将底层的唯一木块直接移动到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);
}
}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;
}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]);
}
}
}
}总结：
1.递归是一种将问题分而自治的思想，用递归解决问题首先要建立递归的模型；
2.递归解法必须边界条件，否则无解；
3.不要陷入递归函数的执行细节，学会通过代码描述递归问题。
Tip：递归的思想还可以用于回溯穷举的场合。
程序运行后有一个特殊的内存区域供函数调用使用。
1.用于保存函数中的实参，局部变量、临时变量等。
2.起始地址开始往一个方向增长(如：高地址->低地址)
3.有一个专用”指针”，标识当前已经使用内存的“顶部”
程序中的栈区：一段特殊的专用内存区。
实例分析：
逆序打印单链表中的偶数节点：
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个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。`
在一个8 8的国际象棋棋盘上，有8个皇后，每个皇后占一格，要求皇后之间不会出现相互“×××”的现象(不能有两个皇后处在同一行，同一列或者同一对角线)。
关键数据结构定义：
棋盘： 二维数组( 10 10), 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)
算法思路：
1.初始化： j = 1,
2.初始化： i = 1;
3.从第j行开始，恢复i的有效值（通过函数调用栈进行回溯），判断第i个位置
A: 位置i可放入皇后，标记位置(i, j), j++, 转步骤2
B: 位置i不可放入皇后：i++, 转步骤A
C: 当i>8时，j--，转步骤3
结束：第8行有位置可放入皇后。
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;
}
};总结：
程序运行后的栈存储区专门供函数调用使用，用于保存实参，局部变量，临时变量等；
利用栈存储区能够方便的实现回溯算法，八皇后问题是回溯的经典应用。
本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！
喜欢 | 0
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式AI+学习就业服务平台 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
资料领取
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
