vlambda博客
学习文章列表

问题 A: 【递归入门】全排列 

题目描述       

     排列与组合是常用的数学方法。
先给一个正整数 ( 1 < = n < = 10 )
例如n＝3，所有组合,并且按字典序输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 

 输入

输入一个整数n(  1<=n<=10)

输出

输出所有全排列

每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格）

代码：

 #include<iostream> #include<cmath> #include<cstdio> using namespace std;
 int p[10]={0}; bool vis[10]={0}; int n; void dfs(int x){ if (x==n+1) { for(int i=1;i<=n;i++) printf("%d ",p[i]); printf("\n"); return ; }
 for (int i=1;i<=n;i++) { if (vis[i]==false ) { p[x] = i; vis[i] = true; dfs(x+1); vis[i] = false; } } }
 int main(){
 scanf("%d",&n); dfs(1); return 0; }

问题 B: 【递归入门】组合的输出 

 题目描述

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r < ＝ n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你不用递归的方法输出所有组合。
例如n ＝ 5 ，r ＝ 3 ，所有组合为：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5 

输入

一行两个自然数n、r ( 1 < n < 21，1 < ＝ r < ＝ n )。

 输出

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，所有的组合也按字典顺序。

代码：

#include<cstdio>#include<iostream>using namespace std;bool vis[22]={0};int p[22]={0};int n,r;void dfs(int x){ if(x==r+1) { for(int i=1;i<=r;i++) { printf("%d ",p[i]); } printf("\n"); return ; }
 for(int i=1;i<=n;i++) { if(vis[i]==false&&i>p[x-1]) { p[x]=i; vis[i]=true; dfs(x+1); vis[i]=false; } }}int main(){ scanf("%d %d",&n,&r); dfs(1); return 0;}

问题 C: 【递归入门】组合+判断素数

         题目描述

已知 n 个整数b1,b2,…,bn

以及一个整数 k（k＜n）。

从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。

例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
　　　　3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。
　　现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3＋7＋19＝29。

输入

第一行两个整数：n , k （1<=n<=20，k＜n） 
第二行n个整数：x1,x2，…,xn （1<=xi<=5000000） 

输出

一个整数（满足条件的方案数）。 

样例输入 Copy

4 3
3 7 12 19

样例输出 Copy

1

代码：

#include<cstdio>#include<cmath>#include<iostream>#include<cstring>using namespace std;bool vis[22]={0};int p[22];int a[22];int n,k;int sum,ans;bool is_prime(int n){ if(n<=1) return 0; else { int sq=(int)sqrt(n*1.0); for(int i=2;i<=sq;i++) { if(n%i==0) return 0; } return 1; }}void dfs(int x){ if(x==k+1) { if(is_prime(sum)) ans++; return ;
 }
 for(int i=1;i<=n;i++) { if(vis[i]==false&&i>p[x-1]) { vis[i]=true; p[x]=i; sum+=a[i]; dfs(x+1); vis[i]=false; sum-=a[i];
 } }}int main(){ memset(vis,0,sizeof(vis)); cin>>n>>k; int j; for(j=1;j<=n;j++) { scanf("%d",&a[j]); } dfs(1); cout<<ans<<endl; return 0;}

问题 D: 【递归入门】n皇后 问题（原始的8皇后问题）

         题目描述

       会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 

         输入

一个整数n（ 1 < = n < = 10 ) 

输出

每行输出对应一种方案，按字典序输出所有方案。每种方案顺序输出皇后所在的列号，相邻两数之间用空格隔开。如果一组可行方案都没有，输出“no solute!”

样例输入 Copy

4

样例输出 Copy

2 4 1 3
3 1 4 2

代码：

#include <iostream>#include<bits/stdc++.h>using namespace std;int a[11],c[11];int n;int book[11];int sum=0;void dfs(int step)//用step标记现在step行的皇后找到了列的位置{ int i,k; if(step==n+1)//n行皇后都找到了列的位置 { sum++; for(i=1; i<n; i++)//输出列的位置 printf("%d ",c[i]); printf("%d\n",c[n]); return; } for(i=1; i<=n; i++)//遍历每一列 { if(book[i]==0)//如果这一列还没有皇后 { int flag=1; for(k=1; k<step; k++)//遍历已经放好的皇后 { if(abs(k-step)==abs(c[k]-i))//判断在i这一列放一个皇后是否会与已经放好的皇后冲突这里判断的是是否在同一斜线上， //因为在每一行找一个列（没有放过的book标记为0的）放置皇后，皇后的行和列不会出现冲突，因此要判断是否在同一斜线上。 //判断是否在同一斜线上的方法：两点的斜率是否为+1或-1.即(x1-x2)/(y1-y2)=+1或(-1)。(x1-x2)=+1或(-1)*(y1-y2) //即abs(x1-x2)==abs(y1-y2) { flag=0; break; } } if(flag==1) { book[i]=1; c[step]=i;//第step行的皇后放在i dfs(step+1);//继续递归下一行 book[i]=0; } } }}int main(){ scanf("%d",&n); memset(book,0,sizeof(book)); dfs(1); if(sum==0)printf("no solute!\n"); return 0;}

问题 E: 【递归入门】出栈序列统计  

         题目描述

栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两•种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

输入

一个整数n（1<=n<=15） 

输出

一个整数，即可能输出序列的总数目。

样例输入 Copy

3

样例输出 Copy

5

提示

先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。 
用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。 

代码：

#include<stdio.h>#include<algorithm>#include<vector>#include<math.h>int cnt, n;void dfs(int push, int pop){ if(push==n && pop==n)//进栈次数和出栈次数都为n，则组成一个组合 { cnt++; return; } if(push<n) dfs(push+1, pop); if(pop<n && pop < push)//出栈次数小于进栈次数 dfs(push, pop+1);}int main(){ n; while(scanf("%d",&n)!=EOF) { cnt = 0; dfs(0,0); printf("%d\n", cnt); } return 0;}/**进栈和出栈次数都为n的时候，则形成一个组合。如果进栈次数小于n的时候进栈。如果出栈次数小于进栈次数且小于n的话出栈。**/

注意：该问题也可以采用卡特兰数的方法来解决（考研数据结构常考的一道题目）

n个数经历出栈和进栈后形成的总组合共有C(2n,n)/(n+1)种

问题 F: 【递归入门】走迷宫

         题目描述

　　有一个n*m格的迷宫(表示有n行、m列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这n*m个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。
　　请统一用 左上右下的顺序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)

         输入

第一行是两个数n，m( 1 < n ， m < 15 )，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。 

输出

　　所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“->”表示方向。 
　　如果没有一条可行的路则输出-1。

样例输入 Copy

5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

样例输出 Copy

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

         提示

【算法分析】 
　　用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表： 
　　　2 
1　　x,y　　3 
　　　4 
　　对应的位置为：(x, y-1)，(x-1, y)，(x, y+1)，(x+1, y)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。 
　　这个查找过程用search来描述如下： 
procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路} 
　begin 
　　　for i:＝1 to 4 do{分别对4个点进行试探} 
　　　begin 
　　　　　先记住当前点的位置，已走过的情况和走过的路； 
　　　　　如果第i个点(xl，y1)可以走，则走过去； 
　　　　　如果已达终点，则输出所走的路径并置有路可走的信息， 
　　　　　否则继续从新的点往下查找search(xl，y1，b1，p1)； 
　　　end； 
　end； 
　　有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜索速度。   

代码：

 #include<iostream> using namespace std; int a[20][20], endx, endy, m, n; bool no = true; int dx[4] = { 0,-1,0,1 }, dy[4] = { -1,0,1,0 };
 struct Route { int x, y; }route[5000];

 void DFS(int x, int y, int num) { if (x == endx&&y == endy) { for (int i = 0; i < num; i++) { cout << "(" << route[i].x << "," << route[i].y << ")->"; } cout << "(" << x << "," << y << ")" << endl; no = false; return; } route[num].x = x, route[num].y = y; for (int i = 0; i < 4; i++) { if (a[x + dx[i]][y + dy[i]] == 1 && 1 <= x + dx[i] <= m && 1 <= y + dy[i] <= n) { a[x][y] = 0; DFS(x + dx[i], y + dy[i], num + 1); a[x][y] = 1; } }
 }
 int main() { while (cin >> m >> n) { for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } int startx, starty; cin >> startx >> starty >> endx >> endy; DFS(startx, starty, 0); if (no) cout << -1 << endl; } return 0; }