2026年编程兔冬令营集训第五场作业

1、枚举

2、递归

1、常规按题面来进行枚举找出所有4*4的矩阵，逐一判断是否符合条件。
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s[105];
bool check(int x,int y)
{
	for(int i=x;i<=x+3;i++)
	{
		for(int j=y;j<=y+3;j++)
		{
			if(i==x||i==x+3||j==y||j==y+3)
			{
				if(s[i][j]!='0') return 0;
			}
			else if(s[i][j]!='1') return 0;
		}
	}
	return 1;
}
signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>s[i];
		bool f=0;
		for(int i=1;i<=n-3;i++)
		{
			for(int j=0;j<m-3;j++)
			{
				if(check(i,j))
				{
					cout<<"Yes\n";
					f=1;
					break;
				}
			}
			if(f==1) break;
		}
		if(f==0) cout<<"No\n";
	}
	return 0;
}


2、枚举进阶：全排列问题。问题：枚举 n 个不同元素的所有全排列（每个元素出现且仅出现一次的排列）。n 个元素的全排列共有 n! 种，时间复杂度为 O (n!)。该方法适用于 n≤10 的场景（10!≈360 万，可接受）。
思路：
• 递归枚举：固定第 k 个位置的元素，递归枚举剩余位置的元素。
• 去重处理：通过交换元素避免重复（确保每个位置的元素唯一）。
#include<bits/stdc++.h>
using namespace std;
int a[20],n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) a[i] = i;
	do{
		for(int i = 1;i <= n;i++) cout << a[i] << ' ';
		cout << "\n";
	}while(next_permutation(a + 1,a + n + 1));
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[11],b[11],n;
void dfs(int x)
{
	if(x==n+1)
	{
		for(int i=1;i<=n;i++)cout<<a[i]<<" ";
		cout<<endl;
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0)
		{
			a[x]=i;
			b[i]=1;
			dfs2(x+1);
			b[i]=0;
		}
	}
}
int main()
{
	cin>>n;
	dfs(1);
	return 0;
}


3、单子集枚举问题，二进制表示法。
问题：给定 n (n≤20)个元素的集合，枚举其所有可能的子集（包括空集和全集）。
思路：
• 用二进制数表示子集：n 个元素对应二进制数的 n 位，第 i 位为 1 表示子集包含第 i 个元素，为 0 则不包含。
• 解空间：二进制数从 0 到 2^n - 1，共 2^n 个可能解。
• 遍历方式：枚举每个二进制数，通过位运算判断每位是否为 1，确定子集中的元素。
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int n,a[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=(1<<n);i++){
		int m=i;
		for(int j=1;j<=n;j++){
			if((m)&1) cout<<a[j]<<' ';
			m=(m>>1);
		}
		cout<<'\n';
	}
	return 0;
}

4、将一个大型复杂问题转化为一个或多个规模更小、结构相同的子问题。计算阶乘 n! 可以分解为 n×(n−1)!，其中 (n−1)! 是规模更小的相同问题。
#include<bits/stdc++.h>
using namespace std;
int f(int x)
{
	if (x == 0) return 1;
	else return x * f(x - 1);
	
}
int main(){
	int n;
	cin >> n;
	cout << f(n);
	return 0;
}
5、sqrt函数使用，递归方式跟上题差不多，输出注意小数点后几位。
#include<bits/stdc++.h>
using namespace std;
double q(double a,double b)
{
	if(b==1)
	{
		return sqrt(1+a);
	}
	return sqrt(b+q(a,b-1));
}
int main()
{
	double a,b;
	cin>>a>>b;
	printf("%.2f",q(a,b));
	return 0;
}


6、先整理出f函数,f(n)=len(n)+f(n/2)。len(n)函数是求n的位数。
#include<bits/stdc++.h>
using namespace std;
int len(int n){
	int l=0;
	while(n>0){
		l++;
		n/=10;
	}
	return l;
}
int f(int n){
	if (n==0) return 0;
	int t=len(n);
	return t+f(n/2);
}
int main(){
	int n;
	cin>>n;
	cout<<f(n)<<endl;
	return 0;
}