OJ 7834【深度优先搜索习题】 分成互质组
2024-01-03 04:23:28
目录
1. 题目描述
2. 思路解释
每次选择一个数进入所分好的组,比较这个数与分组中每个数是否互质,互质则进入此分组,否则新开辟一个分组
3. 代码实现(局部代码)
1. 变量定义
- n n个数
- p[20]? 存数
- group[20][20]??最多可能有N个组, 每个组可能有N个数 存的是数的序号(保证可以连续性访问)
- st[20]? 标记每个数是否用过
- res=20??组数的最大值是n个数两两互质
2. 主函数:输入+dfs+输出
int main ()
{
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];
dfs(1,0,0,0);
cout<<res<<endl;
return 0;
}
3. dfs函数
u -> 第几组
v -> 第几组中的第几个数
w -> 我用了多少个数
x -> 当前从哪个序列编号开始找下一个互质的数放入组中
void dfs(int u,int v,int w,int x) // 递归指数型枚举
{
if(u>=res) return ;
if(w==n)
{
res=u;
return ;
}
bool flag=1;
for(int i=x;i<n;i++)
if(!st[i] && check(u,v,i))
{
group[u][v]=i;
st[i]=1;
flag=0;
dfs(u,v+1,w+1,i+1);
st[i]=0;
}
if(flag) dfs(u+1,0,w,0);
}
我们此时的flag变量即标记是否互质变量,初始值赋值为1,如果被选了则被赋值为0,没被选则还是1,此时我们就要新开辟一个分组,因为这个数与其他分组中的数不互质,不符合题目要求。
4. check函数(检查是否互质)
bool check(int u,int v,int i)
{
for(int j=0;j<v;j++)
{
if(gcd(p[group[u][j]],p[i])>1) return 0;
}
return 1;
}
采用gcd函数判断分组内的每一个数是否与新加进来的数互质,互质返回1,否则返回0
5. gcd函数(求最大公约数)
int gcd (int a, int b)
{
return b?gcd(b,a%b):a;
}
判断这两个数的最大最大公约数,众所周知,当两个数互质时,最大公约数为1,否则肯定大于1,我们返回这两个数的最大公约数,在check函数中判断最大公约数是否大于1来判断是否互质
这一段代码为简写,此函数的正常写法和证明在下面这个链接中,大家自行阅览【模板代码】辗转相除法gcd(图像证明法)-CSDN博客
4. 完整代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int p[20];
int group[20][20];
bool st[20];
int res = 20;
int gcd (int a, int b)
{
return b?gcd(b,a%b):a;
}
bool check(int u,int v,int i)
{
for(int j=0;j<v;j++)
{
if(gcd(p[group[u][j]],p[i])>1) return 0;
}
return 1;
}
void dfs(int u,int v,int w,int x)
{
if(u>=res) return ;
if(w==n)
{
res=u;
return ;
}
bool flag=1;
for(int i=x;i<n;i++ )
if(!st[i] && check(u,v,i))
{
group[u][v]=i;
st[i]=1;
flag=0;
dfs(u,v+1,w+1,i+1);
st[i]=0;
}
if(flag) dfs(u+1,0,w,0);
}
int main ()
{
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];
dfs(1,0,0,0);
cout<<res<<endl;
return 0;
}
文章来源:https://blog.csdn.net/ckh001/article/details/135330786
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!