首页
社区
课程
招聘
[原创]第一阶段第二题提交源码
发表于: 2010-10-20 22:32 3687

[原创]第一阶段第二题提交源码

2010-10-20 22:32
3687
#include<iostream>
#include<fstream>
#include<iomanip>
int pailie[6000][10];//这个数组用来存放得到的所有全排列,为了方便操作,定义为全局变量。
int jiaohuan(int &,int ,int &);//通过这个函数实现一一交换。
using namespace std;

int main() {
        int i,j,k,n,shu,shengshu,shengflag=0,zongshu=0,qianwei,pai,qushu[15000][8],flag=0,ab[5][5],ishu,ipai,youxushu[8];
        shu=1;
        n=7;
        pai=1;//pai是标记数组pailie的第一个下标,记录7的全排列有多少个。
        k=1;//K是一个特殊的变量。用来控制,对jiaohuan函数的循环次数。
        for(i=1;i<=n;i++)
                pailie[pai][i]=i;
        while(k<n)
                jiaohuan(k,n,pai);//得到7!种排列。

        for(i=1;i<=7;i++)///////////////////找到在1到16中任取7个数所有的取法。
                qushu[shu][i]=i;

star: while(qushu[shu][7]<16){
        shu++;
        for(i=1;i<=6;i++)
                qushu[shu][i]=qushu[shu-1][i];
        qushu[shu][7]=qushu[shu-1][7]+1;
          }

          if(qushu[shu][7]==16)
                  for(qianwei=6;qianwei>=1;qianwei--){
                          if(qushu[shu][qianwei]==qianwei+9){
                                  flag=0;
                                  continue;
                          }
                          shu++;
                          for(i=1;i<qianwei;i++)
                                  qushu[shu][i]=qushu[shu-1][i];
                          qushu[shu][qianwei]=qushu[shu-1][qianwei]+1;
                          for(i=1+qianwei;i<=7;i++)
                                  qushu[shu][i]=qushu[shu][i-1]+1;

                          flag=1;
                          break;   
                  }

                  if(flag)
                          goto star;///////////////////找到在1到16中任取7个数所有的取法。

                  for(ishu=1;ishu<=shu;ishu++)//////对每一次取法中对应的7个数的全排列进行操作。
                          for(ipai=1;ipai<=pai;ipai++)//shu记录了16取7的全部取法的个数,pai记录了7!的排列数。ishu,ipai,是一般的循环控制变量。
                          {
                                  for(i=1;i<=7;i++)
                                          switch(pailie[ipai][i])//把每一种取法得到的7个数,进行全排列。
                                  {
                                          case 1:youxushu[i]=qushu[ishu][1];break;
                                          case 2:youxushu[i]=qushu[ishu][2];break;
                                          case 3:youxushu[i]=qushu[ishu][3];break;
                                          case 4:youxushu[i]=qushu[ishu][4];break;
                                          case 5:youxushu[i]=qushu[ishu][5];break;
                                          case 6:youxushu[i]=qushu[ishu][6];break;
                                          case 7:youxushu[i]=qushu[ishu][7];break;
                                  }
                                  ab[1][2]=youxushu[1];
                                  ab[1][4]=youxushu[2];
                                  ab[2][1]=youxushu[3];
                                  ab[2][2]=youxushu[4];
                                  ab[3][3]=youxushu[5];
                                  ab[3][4]=youxushu[6];
                                  ab[4][1]=youxushu[7];
                                  for(shengshu=1;shengshu<=16;shengshu++)//寻找除去取走的那7个数之外的9个数,分九次填入ab[1][1];
                                  {
                                          for(i=1;i<=7;i++)
                                                  if(shengshu==youxushu[i]){
                                                          shengflag=1;
                                                          break;
                                                  }
                                                  if(shengflag) {
                                                          shengflag=0;
                                                          continue;
                                                  }
                                                  ab[1][1]=shengshu;
                                                  ab[1][3]=34-ab[1][1]-ab[1][2]-ab[1][4];//填充2
                                                  ab[3][1]=34-ab[1][1]-ab[2][1]-ab[4][1];//填充2
                                                  ab[4][4]=34-ab[1][1]-ab[2][2]-ab[3][3];//填充2
                                                  if(ab[1][3]<1||ab[1][3]>16||ab[3][1]<1||ab[3][1]>16||ab[4][4]<1||ab[4][4]>16)///////////////////////////对2位置判断。
                                                          continue;
                                                  if(ab[1][3]==ab[3][1]||ab[1][3]==ab[4][4]||ab[4][4]==ab[3][1])
                                                          continue;
                                                  if(ab[1][3]==ab[1][2]||ab[1][3]==ab[1][4]||ab[1][3]==ab[2][1]||ab[1][3]==ab[2][2]||ab[1][3]==ab[3][3]||ab[1][3]==ab[3][4]||ab[1]

                                                  [3]==ab[4][1])
                                                          continue;
                                                  if(ab[3][1]==ab[1][2]||ab[3][1]==ab[1][4]||ab[3][1]==ab[2][1]||ab[3][1]==ab[2][2]||ab[3][1]==ab[3][3]||ab[3][1]==ab[3][4]||ab[3]

                                                  [1]==ab[4][1])
                                                          continue;
                                                  if(ab[4][4]==ab[1][2]||ab[4][4]==ab[1][4]||ab[4][4]==ab[2][1]||ab[4][4]==ab[2][2]||ab[4][4]==ab[3][3]||ab[4][4]==ab[3][4]||ab[4]

                                                  [4]==ab[4][1])///////////////////////////对2位置判断。
                                                          continue;
                                                  ab[3][2]=34-ab[3][1]-ab[3][4]-ab[3][3];//填充3
                                                  ab[2][4]=34-ab[1][4]-ab[3][4]-ab[4][4];//填充3
                                                  if(ab[3][2]<1||ab[3][2]>16||ab[2][4]<1||ab[2][4]>16)///////////////////////////对3位置判断。
                                                          continue;
                                                  if(ab[3][2]==ab[2][4])
                                                          continue;

                                                  if(ab[3][2]==ab[1][1]||ab[3][2]==ab[1][2]||ab[3][2]==ab[1][3]||ab[3][2]==ab[1][4]||ab[3][2]==ab[2][1]||ab[3][2]==ab[2][2]||ab[3]

                                                  [2]==ab[3][1]||ab[3][2]==ab[3][3]||ab[3][2]==ab[3][4]||ab[3][2]==ab[4][1]||ab[3][2]==ab[4][4])
                                                          continue;
                                                  if(ab[2][4]==ab[1][1]||ab[2][4]==ab[1][2]||ab[2][4]==ab[1][3]||ab[2][4]==ab[1][4]||ab[2][4]==ab[2][1]||ab[2][4]==ab[2][2]||ab[2]

                                                  [4]==ab[3][1]||ab[2][4]==ab[3][3]||ab[2][4]==ab[3][4]||ab[2][4]==ab[4][1]||ab[2][4]==ab[4][4])
                                                          continue;
                                                  if(34-ab[2][1]-ab[2][2]-ab[2][4]!=34-ab[1][4]-ab[3][2]-ab[4][1])
                                                          continue;///////////////////////////对3位置判断。
                                                  ab[2][3]=34-ab[2][1]-ab[2][2]-ab[2][4];//填充4
                                                  ab[4][2]=34-ab[1][2]-ab[2][2]-ab[3][2];//填充4
                                                  if(ab[2][3]<1||ab[2][3]>16||ab[4][2]<1||ab[4][2]>16)///////////////////////////对4位置判断。
                                                          continue;
                                                  if(ab[2][3]==ab[4][2])
                                                          continue;
                                                  if(ab[2][3]==ab[1][1]||ab[2][3]==ab[1][2]||ab[2][3]==ab[1][3]||ab[2][3]==ab[1][4]||ab[2][3]==ab[2][1]||ab[2][3]==ab[2][2]||ab[2]

                                                  [3]==ab[2][4]||ab[2][3]==ab[3][1]||ab[2][3]==ab[3][2]||ab[2][3]==ab[3][3]||ab[2][3]==ab[3][4]||ab[2][3]==ab[4][1]||ab[2][3]==ab

                                                          [4][4])
                                                          continue;
                                                  if(ab[4][2]==ab[1][1]||ab[4][2]==ab[1][2]||ab[4][2]==ab[1][3]||ab[4][2]==ab[1][4]||ab[4][2]==ab[2][1]||ab[4][2]==ab[2][2]||ab[4]

                                                  [2]==ab[2][4]||ab[4][2]==ab[3][1]||ab[4][2]==ab[3][2]||ab[4][2]==ab[3][3]||ab[4][2]==ab[3][4]||ab[4][2]==ab[4][1]||ab[4][2]==ab

                                                          [4][4])
                                                          continue;///////////////////////////对4位置判断。

                                                  if(34-ab[1][3]-ab[2][3]-ab[3][3]!=34-ab[4][1]-ab[4][2]-ab[4][4])///////////////////////////对5位置判断。
                                                          continue;
                                                  ab[4][3]=34-ab[1][3]-ab[2][3]-ab[3][3];//填充5
                                                  if(ab[4][3]<1||ab[4][3]>16)///////////////////////////对5位置判断。
                                                          continue;
                                                  if(ab[4][3]==ab[1][1]||ab[4][3]==ab[1][2]||ab[4][3]==ab[1][3]||ab[4][3]==ab[1][4]||ab[4][3]==ab[2][1]||ab[4][3]==ab[2][2]||ab[4]

                                                  [3]==ab[2][3]||ab[4][3]==ab[2][4]||ab[4][3]==ab[3][1]||ab[4][3]==ab[3][2]||ab[4][3]==ab[3][3]||ab[4][3]==ab[3][4]||ab[4][3]==ab

                                                          [4][1]||ab[4][3]==ab[4][2]||ab[4][3]==ab[4][4])
                                                          continue;///////////////////////////对5位置判断。
                                                  //cout<<zongshu;

                                                  cout<<"case "<<setw(3)<<zongshu + 1<<endl;
                                                  zongshu++;

                                                  for(i=1;i<=4;i++) {
                                                          for(j=1;j<=4;j++)
                                                                  cout<<setw(3)<<ab[i][j];
                                                          cout<<endl;
                                                  }

                                                  cout<<endl;
                                                  //cout<<endl;
                                  }
                          }
                          cout<<"总共有:"<<zongshu;
                          cout<<"总共有:"<<zongshu;
                          return 0;

}
int jiaohuan(int &k,int n,int &j)////////////jiaohuan定义
{
        int sk,sn,exe,si,sj,sjj;//exe交换时做暂时的媒介。
        sk=k;//sk,sn,sj,用来接收来自main的k,n,j的值,
        sn=n;//由于,jiaohuan 需要操作j,k ,还需要记录刚传过来时的j,k的值。为了不混淆,设立了sk,sj,sn;
        sj=j;

        for(sjj=1;sjj<=sj;sjj++) {
                while((n-sk)<sn) {
                        j++;

                        for(si=1;si<=n;si++)
                                pailie[j][si]=pailie[sjj][si];

                        exe=pailie[j][n-sk];
                        pailie[j][n-sk]=pailie[j][sn];
                        pailie[j][sn]=exe;
                        sn--;
                }
                sn=n;
        }

        k++;//改变k,
        return 0;
}

//说明:在写这个程序之前我先对4*4幻方进行了分析,发现,只要事先填好16个中的7个位置,
//其他位置就可以利用和为34,让电脑自动填充并判断。那7个位置就是:ab[1][2],ab[1][4],ab[2][1],ab[2][2],
//ab[3][3],ab[3][4],ab[4][1]。这7个位置不唯一。这7个位置填充从16个取的7个数,并且填充之前要对他们进行全排列。
//即每一组数有7!种可能,填完7为以后,只要再往ab[1][1]那里填一个数,就能算出剩下的所有数。ab[1][1]也有9种可能。
//填完ab[1][1]后,即可算出ab[1][3],ab[3][1],ab[4][4].对他们进行判断是否与已经填好的有重复或者是否在1-16之间。
//只要有一种不符合,便continue掉这次循环继续下次循环。注释中的填充2就是算ab[1][3],ab[3][1],ab[4][4]。填充3,4,5以此类推
//此代码中用了大量的continue和if语句,并且在算法上用了全排列和在16中任取7个数这两种算法。过程比较复杂。

//程序思路:先找到16个数中取7个数的所有可能,利用全排列和switch对他们进行全排列。然后对上面得到的每一组数处理。
//对每组数:按事先找好的7个位置填入排好的数。
//对剩余的位置进行处理:先填ab[1][1],然后算剩下的8个,只要不符合幻方的条件便continue掉。
//输出符合条件的输出。

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

上传的附件:
收藏
免费 0
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回
//