当前位置:   article > 正文

分成互质组【dfs】_dfs给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?

dfs给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?

蒜头君给定 n 个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?
输入格式

第一行是一个正整数 n。1≤n≤10。

第二行是 n 个不大于 10000 的正整数。
输出格式

一个正整数,即最少需要的组数。

输出时每行末尾的多余空格,不影响答案正确性

样例输入
6
14 20 33 117 143 175

样例输出
3

题目链接:https://nanti.jisuanke.com/t/T1216

解题思路:每个组开设一个数组存放,新的整数进行:1.如果与某个组的成员不影响互质性,那么就存放进这个组。 2.如果不存在1的情况,那么就另开一个组单独存放此整数。

/*
对每个数进行遍历:
1.和已有组的成员不影响互质性,就放进去
2.如果有影响,不能放入任何一个已有组,就自成一组
*/
#include <iostream>
#include <vector>
using namespace std;
int n;
int digits[15];
int groupcount;
vector <int> groups[15];
int gys(int a,int b){
    if( b == 0 )   return a;
    return   gys(b,a%b);
}

void dfs(int index){  //现在正在处理第index个数(第index还没处理)
    if(index == n)   return ;
    int t=0;
    int flag2=0;
    for(int i=0;i<groupcount;i++) //遍历已有的每个组,判断互质
    {
        int flag1=0;
        for(int j=0;j<groups[i].size();j++)
        {
            if(digits[index] <= groups[i][j])
                t=gys(groups[i][j],digits[index]); 
            else
                t=gys(digits[index],groups[i][j]);
            if( t !=1 )
            {
                flag1=1;
                break;
            }       
        }
    if(flag1 == 0)
    {
        flag2=1;
        groups[i].push_back(digits[index]);
        break;
    }    
    }
    if( flag2 == 0) groups[groupcount++].push_back(digits[index]);
    dfs(index+1);
    return ;
}
int main(){
    cin >> n ;
    for(int i=0;i<n;i++)
    {
        cin >> digits[i];
    }
    dfs(0);
    cout << groupcount << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/744346
推荐阅读
相关标签
  

闽ICP备14008679号