admin 管理员组

文章数量: 887053

巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数

巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。

排序方法：以贪心算法进行搜索，由于两个数字之和是一个素数，且首尾两数字之和也为一个素数，因此只需要找出以1开头的排列就可以了。使用贪心算法的同时使用回溯法，当遇到相邻两个数的时候就回溯到上一步从新搜索。

ofstream fout("D://Prime.txt",ios::app);
bool ISPrime(int n)
{for(int i=2;i<=sqrt((double)n);i++)if(n%i==0)return false;return true;
}
void PrimeArrange(int *arr,int begin,int length)
{if(begin==length){if(ISPrime(arr[begin-1]+arr[0])){copy(arr,arr+length,ostream_iterator<int,char>(fout,"  "));fout<<"\n";cout<<endl;}return;}else if(begin>1&&!ISPrime(arr[begin-1]+arr[begin-2]))//截枝和回溯{return;}else{for(int i=begin;i<length;i++){swap(arr[begin],arr[i]);PrimeArrange(arr,begin+1,length);//搜索swap(arr[begin],arr[i]);}}
}
void PrimeArrange(int *arr,int length)
{if(arr==NULL||length<=0){return;}PrimeArrange(arr,1,length);
}int main()
{int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};PrimeArrange(a,20);fout.close();cout<<"结束"<<endl;return 0;
}

部分结果如下（结果集太大）



本文标签： 巧排数字，将1 2 19 20这20个数字排成一排，使得相邻的两个数字之和为一个素数

版权声明：本文标题：巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1715765591h647244.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。