UC知道互质环问题
来源：百度知道 编辑：UC知道 时间：2024/06/21 22:58:44
将n个数摆成一个环，，使得每个数与它相邻的两个数互质。
求解题方法 注意：使用c++算法实现
求解题方法 注意：使用c++算法实现
3 5
两个数组成组成了一个环
这两个数是互质的
//C++实现 不是最优方法
#include<iostream>
#include<algorithm>
using namespace std;
bool test(int[],int);
void printa(int a[],int n);
bool huzhi(int a,int b)
{
while(a%b!=0)
{
int r=b;
b=a%b;
a=r;
}
return b==1;
}
int main()
{
int a[7]={12,9,8,4,5,15,7};
printa(a,sizeof a /sizeof a[0]);
}
bool test(int a[],int n)
{
for(int i=0;i<n;i++)
{
if(huzhi(a[i],a[(i+1)%n])==false)
return false;
}
return true;
}
void printa(int a[],int n)
{
sort(a,a+n);
do
{
if(test(a,n) == true)
{
copy(a,a+n,ostream_iterator<int>(cout," "));
cout<<endl;
}
}while(next_permutation(a,a+n));
}