算法笔记 第四章-算法初步 | 4.3递归——谢尔宾斯基地毯、自然数分解之最大积、自然数分解之方案数、01串

谢尔宾斯基地毯

题目描述：

题目链接：

谢尔宾斯基地毯

解题思路：

和盒分形的做法类似，用一个二维数组打印图形，注意二维数组要为外圈的”+”留位置。

具体的递归就依照图中所画规律实现即可，递归的出口是n=1。

做题过程：

打印的时候总是错误，一步步排查发现是在输入’X’的时候j的初始值赋了x+len，改为y+len就顺利通过了。

#include
#include

//n最大为7，所以边长最长为3^6+2（2是给'+'留下的位置）
#define MAX 3*3*3*3*3*3+2
char blanket[MAX][MAX];

//n是递归层数，x、y是左上角坐标
void BLANKET(int n,int x,int y){
    //递归出口
    if(n==1){
        blanket[x][y]=' ';
    }else {
        //F(n-1)的边长是3的n-2次方
		int len=(int)pow(3,n-2); 
        //左上
		BLANKET(n-1,x,y);
		//上
        BLANKET(n-1,x+len,y);
		//右上
        BLANKET(n-1,x+2*len,y);
		//左
        BLANKET(n-1,x,y+len);
		//中
        for(int i=x+len;i<x+2*len;i++){
			for(int j=y+len;j<y+2*len;j++){
				blanket[i][j]='X';
			}
		}
        //右
		BLANKET(n-1,x+2*len,y+len);
		//左下
        BLANKET(n-1,x,y+2*len);
		//下
        BLANKET(n-1,x+len,y+2*len);
		//右下
        BLANKET(n-1,x+2*len,y+2*len);
    }
}

int main(){
    int n;
    scanf("%d",&n);
    //地毯从（1.1）开始，因为外圈还要放'+'
	BLANKET(n,1,1);
    //F(n)的边长
	int k=(int)pow(3,n-1);
	//绘制外圈的'+'
    for(int j=0;j<k+2;j++){
		blanket[0][j]='+';
	}
	for(int i=0;i<k+2;i++){
		blanket[i][0]='+';
	}
	for(int i=0;i<(int)pow(3,n-1)+2;i++){
		blanket[i][k+1]='+';
	}	
	for(int j=0;j<k+2;j++){
		blanket[k+1][j]='+';
	}
    //输出图形
	for(int i=0;i<k+2;i++){
		for(int j=0;j<k+2;j++){
			printf("%c",blanket[i][j]);
		}
		printf("\n");
	}	
    return 0;
}

归纳总结：

题解中没有把’+’写入二维数组，而是在需要的地方直接打印出来。我的做法是写入数组，这样递归的（x，y）从（1，1）出发，更方便我计算坐标。

自然数分解之最大积

题目描述：

题目链接：

自然数分解之最大积

解题思路：

先找积最大时的规律：n=2时，最大是1*1=1；n=3时，最大是1*2=2；n=4时，最大是2*2=4；n=5时，最大是2*3=6；n=6时，最大是3*3=9；n=7时，最大是3*2*2=12；n=8时，最大3*3*2=18…

可见在n大于3的时候应该优先分解出来3，不够的情况下分解出2，不要出现1。但是当n小于等于3的时候，不可避免要分解出来1，所以我对第一次进入递归时候的n进行了判断，如果n小于等于3，单独处理。

做题过程：

#include

int first=1;//first=1表示第一次

int max_mul(int n){
	if(first==1){//如果是第一次，单独处理
		if(n<3)
        	return 1;
        if(n==3)
        	return 2;
        first=0;//first=0，表示不是第一次
	}
    if(n<=3)//后面n小于等于3，直接返回n值即可，比如6递归调用了3*max_mul(3)
        return n;
    else{
        if(n%3==0){//如果能除尽3，就只分解为3的乘积
            return 3*max_mul(n-3);
        }else{
            return 2*max_mul(n-2);//如果不能除尽3，就分解出来一个2
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d",max_mul(n));
    return 0;
}

归纳总结：

本来想的做法是将n对半分，两边各调用一次递归，但是发现这样做的乘积不是最大的。

题解的代码没有注释也没写思路，没有看明白。我参考了其他人的非递归代码的思路写了这个代码，和题解的做法比起来，单独处理第一次的情况的代码确实丑陋了一点。

自然数分解之方案数

题目描述：

题目链接：

自然数分解之方案数

解题思路：

总结分解的规律，见下图：

2=1+1

3=1+1+1
3=1+2

4=1+1+1+1
4=1+1+2
4=1+3
4=2+2

5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3

6=1+1+1+1+1+1
6=1+1+1+1+2
6=1+1+1+3
6=1+1+2+2
6=1+1+4
6=1+2+3
6=2+2+2
6=1+5
6=2+4
6=3+3

可以看到第一步是从n个1开始划分，然后n的数量逐渐减少，n减少时去掉的值要分配到前面的数中，但是要注意始终要保持图中类似单调不减的关系才能确保不重复，n=1的时候退出递归。

做题过程：

#include 

//n是自然数，bound是上界
int f(int n, int bound) {
    //当n小于等于1或者上界小于等于0时，无法分解
    if (n <= 1 || bound <= 0) {
        return 0;
    } else {
        //记录方案数
        int ans = 0;
        //i从1到上界
        for (int i = 1; i  0 && n - i <= i && n - i <= bound) {
                ans++;
            }
        }
        //向上层返回方案数
        return ans;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    //至少要有两个加数，所以其中一个加数的初值最大是n-1
    printf("%d\n", f(n, n - 1));
    return 0;
}

归纳总结：

这题没太搞懂，看了一下提交数，果然提交的人也很少，只能看着题解来做题了。在网上查找资料，这是一种比较经典的DFS（深度优先遍历）例题，本质上DFS也是用递归实现的，但是还是只能说得多学，希望后面学到DFS章节，对这些内容的理解能深刻点。

01串

题目描述：

在一个长度为n的数组中填写0或者1，输出所有可能的结果。

题目链接：

01串

解题思路：

和上面的题目类似，有深度优先遍历的感觉。

用一个大小为n的数组存放所有数据，每层递归先将0放入数组末尾，当到达递归最底层时，输出数组的所有元素。然后返回上一层，返回后删掉最后一个0，将1放在数组末尾，然后进入下一层输出数组的所有元素。在从下一层返回，返回后删掉最后一个1，此时可以返回上上一层了。

做题过程：

#include
#include
using namespace std;

//存放所有字符
vector vec;

//n是字符串长度
void zero_one(int n){
	//n=0时到达字符串末尾，可以输出全部元素
    if(n==0){
		for(int i=0;i<vec.size();i++){
			cout<<vec[i];
		}
		cout<>n;
	zero_one(n);
	return 0;
}

归纳总结：

感觉和上题很类似，但是这题我倒是自己写出来了，大概因为这个的遍历过程很符合人的直觉，

一开始漏掉了最后一句vec.pop_back()，输出的字符参差不齐，还以为自己的思路错误了，还好后面补上后提交顺利通过。