代理网站建设,免费的seo,网站策划的步骤,小吃加盟招商方案目录 递归和分治思想一些实例逆序输出字符串查找数组元祖是否存在汉诺塔问题八皇后问题更多#xff1a;递归和分治思想 如果可以使用迭代#xff0c;尽量别使用递归。由编译原理可以知道#xff0c;每次自调用的时候#xff0c;计算机都需要保存在调用#xff0c;浪费时间… 目录 递归和分治思想一些实例逆序输出字符串查找数组元祖是否存在汉诺塔问题八皇后问题更多 递归和分治思想 如果可以使用迭代尽量别使用递归。由编译原理可以知道每次自调用的时候计算机都需要保存在调用浪费时间空间。当然迭代是当我们知道循环次数的时候。而当我们不知道循环次数比如说对于文件夹和文件进行遍历不知道深度的情况下我们就需要递归来实现。 显然递归是先解决小的问题这种思想是分治思想。根据具体需求来决定是否使用递归。 递归要注意 结构是选择结构而迭代是循环结构必须有基线条件和递归条件防止出现死循环如果知道循环次数的话尽量使用递归对于某些编程式函数有对于尾递归的迭代优化递归逻辑更容易理解一些实例 逆序输出字符串 #includeiostream
using namespace std;void print(){char a;cina;if(a!#) print(); // 不是停止符先自调用 if(a!#) couta; //在回来的时候打印自己的字符
}
int main(){print();return 0;
} 查找数组元祖是否存在 很多时候我们需要查找一个数组中是否有一个元素。如果使用迭代肯定十分简单时间复杂度为O(n)。 此时如果使用分而治之的思想我们可以使用二分法来进行查找。不论多大的数据时间复杂度显著降低为O(log_2 n)。也就是说一个大小为123456789的数组使用迭代我们需要123456789个时间单位。但是二分法只需要27次。 实现思路 首先转化的思想对数组进行排序。如果不排序那么low和high就没有意义了。再用迭代进行二分#includeiostream
#includealgorithm
using namespace std;
const int SIZE 5;
const int NONE -1;
//二分查找并且返回element的位置没查找到则返回NONE
templateclass T
int BinFind(T *arr,int low,int high,T elem){ int mid;if(lowhigh)return NONE;else{mid (lowhigh)/2;if(arr[mid] elem)return mid;else if(elemarr[mid])return BinFind(arr,mid1,high,elem);elsereturn BinFind(arr,low,mid-1,elem);}
}
int main(){int *arr new int [SIZE];cout请输入SIZE个数据; for(int i0;iSIZE;i)cinarr[i];sort(arr,arrSIZE);int elem;cout输入您要查找的数据endl;cinelem; int index BinFind(arr,0,SIZE-1,elem);if (index1)cout含有这个数据\n;elsecout不含有这个数据;return 0;
} 汉诺塔问题 首先我们假设需要移动64层那么思路如下附截图 此时需要解决两个问题附截图 一直这样类推知道最后从begin(开始柱子)-end(目标柱子)。 按照第一张截图我们可以写出来函数里面else的递归部分。并且每次输出的时候就对应着思路里面的移动而不是分治此时step步数需要加。 #includeiostream
#includealgorithm
using namespace std;
void Hanoi(int num,char begin,char by,char end,int step){if(num1){coutbegin--endendl;step;}else{Hanoi(num-1,begin,end,by,step);coutbegin--endendl;step;Hanoi(num-1,by,begin,end,step);}
}
int main(){int step 0;int num;cout汉诺塔层数是: ;cinnum;Hanoi(num,X,Y,Z,step);cout一共有step步数endl; return 0;
} 八皇后问题 在8×8格的国际象棋上摆放八个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜线上问有多少种摆法。正规的方法是递归如果不考虑效率这里采用递归实现。假设从第一行开始每一行都找到符合条件的一个位置而条件就是新的一行的新位置符合要求以此类推就可以写出来递归函数。 #includeiostream
using namespace std;const int Q_NUM 8;
int queens[Q_NUM][Q_NUM] {0};
int RESULT 0;void print(){for(int i0;iQ_NUM;i){for (int j0;jQ_NUM;j)coutqueens[i][j] ;coutendl;}coutendlendl;
}
bool IfQueen(int row,int col){if(row0){//当第一行时候随便摆放 queens[row][col] 1;return true;}/**************其他时候需要考虑上面的同一列、左上角斜线、右上角斜线以下分别实现*****/ for(int i0;irow;i)if(queens[i][col]1)return false;for (int irow-1,j col-1;i0 j0;--i,--j)if(queens[i][j]1)return false;for(int irow-1,jcol1;i0 jQ_NUM;--i,j)if(queens[i][j]1)return false;/******当所有情况都满足********/queens[row][col] 1;return true;
}
void Queen(int row){if(rowQ_NUM){ //注意row是从0开始到Q_NUM-1结束。这样当rowQ_NUM时已经排完所有情况 RESULT; //这样当rowQ_NUM时已经排完所有情况进行输出就可以了。 print();return ;} for(int i0;iQ_NUM;i){ //i代表列数 if(IfQueen(row,i)) //如果row行i列可以放得话判断下一行 Queen(row1);queens[row][i] 0; //重置为0防止下次结果干扰 }
}int main(){Queen(0);cout一共RESULT种摆法\n;return 0;
} 更多 毫无疑问递归以及分治思想还有很多用法斐波那契数列、快速排序、文件查找、字典树的建立等等。理论上递归可以解决任何问题而作为我们只需要提供思路其他的交给计算机解决。所以听人说过计算机最适合解决递归问题。但是有利有弊递归同样会消耗更多的内存。在初步实现阶段将大问题分而治之分装成递归函数还是逻辑代码化的最佳表达。 欢迎进一步交流本博文相关内容 博客园地址 : http://www.cnblogs.com/AsuraDong/ CSDN地址 : http://blog.csdn.net/asuradong 也可以致信进行交流 : xiaochiyijiu163.com 欢迎转载 , 但请指明出处 : ) 转载于:https://www.cnblogs.com/AsuraDong/p/7045141.html
