- //由1-9这九个数字组成的九位数(无重复数字)能被11整除,求最大,最小者
- #include<iostream>
- using namespace std;
- void main()
- {
- void swap(int &n1,int &n2);
- void swap1(int a[],int &i);
- void swap2(int a[],int &i);
- void swap3(int a[],int &i);
- void swap4(int a[],int &i);
- long f(int a[],long &num);
- void max();
- int a[]={1,2,3,4,5,6,7,8,9};
- long num=0;
- //如果123456789%11==0,输出这个数,并结束程序。
- if(f(a,num)%11==0){
- cout<<"The min number can be divisible by 11 is "<<num<<endl;
- max();
- return;
- }
- for(int i=7;;){
- if(a[i]>a[i+1]||a[i]==9) //如果当前项大于后一项,或者当前项=9,则项数前移;
- i--;
- else {
- if(a[i]<a[8]) //如果当前项小于最后一项,进行第一类交换,否则进行第二类交换
- swap1(a,i);
- else
- swap2(a,i);
- f(a,num); //将数组组合成一个9位数
- if(num%11==0){ //如果这个9位数是11的倍数,则输出,并结束程序;否则继续进行下一轮循环
- cout<<"The min number which be constituted by 1,2,3,4,5,6,7,8,9 can be divisible by 11 is :"<<endl<<num<<endl;
- max();
- return;
- }
- }
- }
- }
- void swap(int &n1,int &n2) //交换n1,n2的值
- {
- int n;
- n=n1;
- n1=n2;
- n2=n;
- }
- void swap1(int a[],int &i) //第一类交换,并将i重置为7
- {
- swap(a[i],a[8]);
- for(int m=8,n=i+1;n<m;m--,n++)
- swap(a[n],a[m]);
- i=7;
- }
- void swap2(int a[],int &i) //第二类交换,并将i重置为7
- {
- int k=8;
- for(;a[i]>a[k];k--);
- swap(a[i],a[k]);
- for(int m=8,n=i+1;m>k;m--,n++)
- swap(a[n],a[m]);
- i=7;
- }
- long f(int a[],long &num) //将已知顺序的数组组合成一个9位数
- {
- num=0;
- for(int i=8,k=1;i!=-1;i--,k*=10)
- num+=a[i]*k;
- return num;
- }
- //swap3,4分别改自swap1,2
- void swap3(int a[],int &i) //第一类交换,并将i重置为7
- {
- swap(a[i],a[8]);
- for(int m=8,n=i+1;n<m;m--,n++)
- swap(a[n],a[m]);
- i=7;
- }
- void swap4(int a[],int &i) //第二类交换,并将i重置为7
- {
- int k=8;
- for(;a[i]<a[k];k--);
- swap(a[i],a[k]);
- for(int m=8,n=i+1;m>k;m--,n++)
- swap(a[n],a[m]);
- i=7;
- }
- //测试最大值
- void max()
- {
- int a[]={9,8,7,6,5,4,3,2,1};
- long num=0;
- //如果987654321%11==0,输出这个数,并结束程序。
- if(f(a,num)%11==0){
- cout<<"The max number can be divisible by 11 is "<<num<<endl;
- return;
- }
- for(int i=7;;){
- if(a[i]<a[i+1]||a[i]==1) //如果当前项小于后一项,或者当前项=1,则项数前移;
- i--;
- else {
- if(a[i]>a[8]) //如果当前项大于最后一项,进行第一类交换,否则进行第二类交换
- swap3(a,i);
- else
- swap4(a,i);
- f(a,num); //将数组组合成一个9位数
- if(num%11==0){ //如果这个9位数是11的倍数,则输出,并结束程序;否则继续进行下一轮循环
- cout<<"The min number which be constituted by 1,2,3,4,5,6,7,8,9 can be divisible by 11 is :"<<endl<<num<<endl;
- return;
- }
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/080820135040.html
来源: http://www.codesnippet.cn/detail/080820135040.html