23 递归

理论说明

本部分梳理递归，递归是一种非常常用的技巧，所谓递归即函数调用函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归调用。同时，为了不使这样的递归无限的发生下去，我们必须设定递归的出口，即当函数到达某种条件时停止递归。如求n阶层的递归程序如下：

int f(int x) {
	if(x==0) return 1;
   else return x*F(x-1);
}

其递归方式为，每次递归调用时函数的参数减1，每一个函数在等待递归函数返回时将其返回值与本函数的参数相乘后返回给上一层函数。为了防止这样的递归无限发生，我们设定了一个递归出口，即当参数变为0时停止递归，直接返回1.其递归过程如下图：

递归方式和递归出口是递归函数的两个重要的要素，只要明确了着两个要素，那么递归函数就比较容易编写了。

题目描述

约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？

输入说明

包含多组数据，每次输入一个N值(1<=N=35)。

输出说明

对于每组数据，输出移动最小的次数。

样例展示

输入：
1
3
12
输出：
2
26
531440

问题分析

与原始的汉诺塔问题不同，这里对圆盘的移动做了更多的限制，即每次只允许将圆盘移动到中间柱子上或者从中间柱子移出，而不允许从第一根柱子直接移动圆盘到第三根柱子上。

1.确定递归式

F[k]表示K个圆盘从1移动到3所需要的次数。它的组成方式为，先移动K-1个圆盘到第三根柱子上需要F[k-1]次移动，然后将最大的圆盘移动到中间柱子上需要移动1次，然后将K-1个圆盘移动回第一根柱子同样需要F[k-1]，移动最大的盘子到第三根柱子上需要1次移动，最后将K-1个圆盘移动到第三根圆盘需要F[k-1]次移动，这样F[k]=3 * F[k-1]+2.

2. 确定递归出口

当x=1时，即移动一个盘子从第一根柱子到第三根柱子，其所需要移动的次数显而易见，为2.即F[1]=2

C++代码

#include<iostream>
#include<cstring>
using namespace std;

typedef long long ll;
ll F(int num) {
    if(num==1) return 2;
    else {
        return 3*F(num-1)+2;
    }
}
int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        printf("%lld\n",F(n));
    }
    return 0;
}

Prime Ring Problem

题目描述

A ring is compose of n circles as shown in diagram. Put natural number 1,2,....,n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

输入说明

n(1<n<17)

输出说明

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process Print a blank line after each case

样例说明

样例输入：
6
8
样例输出：
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

问题分析

题目大意为由给定的1到n数字中，将数字一次填入环中，使得环中任意两个相邻的数字间的和为素数。对于给定的n，按照字典序由小到大输出所有符合条件的。这就是又名的素数环问题。

为了解决这类问题，我们可以使用回溯法枚举每一个值。当第一个数位为1时，我们尝试放入第二个数字，使其和1的和为素数，放入后在尝试放入第三个数字，使其于第二个数的和为素数，直到所有的数字全部被放入环中，且最后一个数字于1的和也是素数，那么这个方案即是答案，输出；若在尝试放数的过程中，发现当前位置无论防止任何数都均不能满足条件，那么我们回溯改变其上一个数字，直到产生我们所需的答案。

为了实现这一枚举过程，我们采用递归的形式

C++代码

#include<iostream>
using namespace std;
int n;
int ans[22]; //保存环中每一个被存放的数字
int mark[22]; //标记之前已经被放入环中的数字

int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};
bool judge(int x) {
    for(int i=0;i<13;i++) {
        if(prime[i]==x) return true;
    }
    return false;
}

void check() {
    if(judge(ans[n]+ans[1])==false) return;
    for(int i=1;i<=n;i++) {
        if(i!=1) printf(" ");
        printf("%d",ans[i]);
    }
    printf("\n");
}
void dfs(int u) { //u表示已经放入ans中的数字
    if(u==n) { //若已经放入n个数字
        check(); //检查输出
        return;
    }
    for(int i=2;i<=n;i++) {
        if(mark[i]==false && judge(ans[u]+i)) {
            mark[i]=true;
            ans[u+1]=i;
            dfs(u+1);
            mark[i]=false;
        }
    }
}
int main() {
    int cas=0;
    while(scanf("%d",&n)!=EOF) {
        cas++;
        for(int i=0;i<22;i++) mark[i]=false;
        
        ans[1]=1;
        mark[1]=true;
        printf("Case %d:\n",cas);
        dfs(1);
        printf("\n");
    }
}

Oil Deposit

问题描述

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

输入说明

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *', representing the absence of oil, or @', representing an oil pocket.

输出说明

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

样例说明

样例输入：
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
样例输出：
0
1
2
2

问题分析

题目的大意是：在给定的n * m图中，确定由几个@的块。块符合以下条件，其中的任意对@均互相直接或间接连通，两个@块直接相邻或者对角线相邻即被是为连通。

我们可以这样解决这个问题，首先对图上所有位置有一个标记位，表示该位置是否已经被计算过，且该标记仅对地图上为@的点有效。这样我们按从左往右、从上到下的顺序依次遍历地图上所有位置，若遍历到@，且该点未被标记，则所有与其直接相联或者间接相联的@与其一起组成一个块，该块即为一个我们需要计算的块，将该块中所有的@位置标记为已经计算。这样，当所有的位置被遍历过后，我们即可得到最后的答案。

C++代码

#include<iostream>
char maze[101][101];
bool mark[101][101];
using namespace std;

int n,m;
int go[][2]={
    {1,0},
    {-1,0},
    {0,1},
    {0,-1},
    {1,1},
    {1,-1},
    {-1,1},
    {-1,-1}
};

void dfs(int x,int y) {
    for(int i=0;i<8;i++) {
        int nx=x+go[i][0];
        int ny=y+go[i][1];
        if(nx<1 || nx>n || ny<1 ||ny>m) continue;
        if(maze[nx][ny]=='*') continue;
        if(mark[nx][ny]==true) continue;
        mark[nx][ny]=true;
        dfs(nx,ny);
    }
    return;
}
int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        if(n==0&&m==0) break;
        for(int i=1;i<=n;i++) {
            scanf("%s",maze[i]+1);
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                mark[i][j]=false;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(mark[i][j]==true) continue;
                if(maze[i][j]=='*') continue;
                dfs(i,j);
                ans++;
            }
        }
        printf("%d\n",ans);
    }
}

全排列

题目描述

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有’a’ < ‘b’ < … < ‘y’ < ‘z’，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入说明

输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

输出说明

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义： 已知S = s1s2…sk , T = t1t2…tk，则S < T 等价于，存在p (1 <= p <= k)，使得 s1 = t1, s2 = t2, …, sp - 1 = tp - 1, sp < tp成立。

样例说明

样例输入： abc
样例输出：

abc
acb
bac
bca
cab
cba

C++代码

#include<iostream>
#include<string.h>
using namespace std;
int n;
char str[10];
char res[10];
bool st[10];
void dfs(int u) {
    if(u==n) {
      for(int i=0;i<n;i++) printf("%c",res[i]);
      puts("");
      return;
    }
    for(int i=0;i<n;i++) {
        if(!st[i]) {
            res[u]=str[i];
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }
    }
    
}
int main() {
    cin>>str;
    n=strlen(str);
    dfs(0);
}