UC知道c++菜鸟算法一道题帮忙做一下---互质环
来源：百度知道 编辑：UC知道 时间：2024/06/04 01:01:23
路路给你n个数，你的任务是将这n个整数摆成一个环，使得每个数与它相邻的两个数互质。
【输入文件】
输入文件circle.in第一行是n，有几个数。第二行有n个整数。
【输出文件】
输出文件circle.out包括一行。包含n整数，中间用空格隔开，即按顺时针或逆时针输出环上的每个数，如果存在多个环或多种输出，那么输出其中字典序最小的那一个。如果无解，请输出-1。
【输入样例1】
5
4 3 5 6 5
【输出样例1】
3 4 5 6 5
【输入样例2】
5
4 2 3 8 7
【输出样例2】
-1
【数据规模】
对于50%的数据，保证n <= 10
对于100%的数据，保证n <= 30
【输入文件】
输入文件circle.in第一行是n，有几个数。第二行有n个整数。
【输出文件】
输出文件circle.out包括一行。包含n整数，中间用空格隔开，即按顺时针或逆时针输出环上的每个数，如果存在多个环或多种输出，那么输出其中字典序最小的那一个。如果无解，请输出-1。
【输入样例1】
5
4 3 5 6 5
【输出样例1】
3 4 5 6 5
【输入样例2】
5
4 2 3 8 7
【输出样例2】
-1
【数据规模】
对于50%的数据，保证n <= 10
对于100%的数据，保证n <= 30
//circle.in 和 circle.out用记事本打开
#include<fstream>
#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 n;
ifstream in("C:\\circle.in",ios::in);
if(!in)
return -1; //没有找到输入文件
in>>n;
int *a=new int[n];
for(int i=0;i<n;i++)
in>>a[i];
printa(a,n);
delete[] a;
}
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)
{
ofstream out("C:\\circle.out",ios::out);
sort(a,a+n);
do
{
if(test(a,n) == true)
{
copy(a,a+n,ostream_iterator<int>