搜索
把数码问题就是把一串数字变成下面这个样子:123804765实现方法1.过程表示源代码：#includestdio.hstaticintstyle[9]={1,2,3,6,7,4,5,8,0};//输入的数码//2,5,4,3,0,7,1,8,63,2,1,8,0,4,7,6,51,0,4,2,7,3,8,5,61,0,3,8,2,4,7,6,5staticintarrayStep41[6]={5,4,3,6,7,8};//第四步和第六步共用的数组，所以设为全局量staticintarrayStep71[4]={3,6,7,4};staticintlocal;//空格的位置inti,j;//所用到的变量intnumber=0;//记录移动步数voidprint();voidstep1();voidstep2();voidstep3();voidstep4();voidstep5();voidstep6();voidstep7();voidstep8();voidstep9();voidexchange(intx,inty);voidjudge();voidjudge()//判断空格位置{number=0;for(i=0;i9;i++){if(style[i]==0){local=i;return;}}}voidexchange(intx,inty)//交换两个数{inttemp;print();temp=style[x];style[x]=style[y];style[y]=temp;local=y;number++;}voidstep1(){intarrayStep11[5]={3,0,1,2,5};intarrayStep12[6]={6,7,8,5,2,1};if((style[2]!=0)&&style[2]!=1)return;else{if(local==2){if(style[1]==1)exchange(2,5);elseexchange(2,1);return;}else{if(local==4){exchange(4,1);i=2;while(local!=5){exchange(arrayStep11[i],arrayStep11[i+1]);i++;}return;}for(i=0;i3;i++){if(arrayStep11[i]==local){while(local!=5){exchange(arrayStep11[i],arrayStep11[i+1]);i++;}return;}}for(i=0;i4;i++){if(arrayStep12[i]==local){while(local!=1){exchange(arrayStep12[i],arrayStep12[i+1]);i++;}return;}}}}return;}voidstep2(){intarrayStep21[8]={0,3,6,7,8,5,4,1};for(i=0;i8;i++){if(arrayStep21[i]==local){while(style[0]!=1){exchange(arrayStep21[i%8],arrayStep21[(i+1)%8]);i++;}break;}}}voidstep3(){intarrayStep31[8]={2,1,4,3,6,7,8,5};for(i=0;i8;i++){if(arrayStep31[i]==local){while(style[1]!=2){exchange(arrayStep31[i%8],arrayStep31[(i+1)%8]);i++;}break;}}}voidstep4(){for(i=0;i6;i++){if(arrayStep41[i]==local){while((style[4]!=3)){exchange(arrayStep41[i%6],arrayStep41[(i+1)%6]);i=(i+1)%6;}while(local!=3){exchange(arrayStep41[i%6],arrayStep41[(i+5)%6]);i=(i+5)%6;}break;}}}voidstep5(){intarrayStep51[9]={3,0,1,4,5,2,1,0,3};i=0;do{exchange(arrayStep51[i],arrayStep51[i+1]);i++;}while(local!=3);}voidstep6(){for(i=0;i6;i++){if(arrayStep41[i]==local){while(style[5]!=4){exchange(arrayStep41[i%6],arrayStep41[(i+1)%6]);i++;}if(local==8)exchange(8,7);break;}}return;}voidstep7(){for(i=0;i4;i++){if(arrayStep71[i]==local){while(style[4]!=5){exchange(arrayStep71[i%4],arrayStep71[(i+1)%4]);i=(i+1)%4;}while(local!=3){exchange(arrayStep71[i%4],arrayStep71[(i+3)%4]);i=(i+3)%4;}break;}}}voidstep8(){intarrayStep81[13]={3,0,1,2,5,4,7,8,5,2,1,0,3};i=0;do{exchange(arrayStep81[i],arrayStep81[i+1]);i++;}while(local!=3);}voidstep9(){for(i=0;i4;i++){if(arrayStep71[i]==local){while(style[7]!=6){exchange(arrayStep71[i%4],arrayStep71[(i+1)%4]);i=(i+1)%4;}while(local!=4){exchange(arrayStep71[i%4],arrayStep71[(i+3)%4]);i=(i+3)%4;}break;}}}voidprint(){for(j=0;j9;j++){if(style[j]==0)printf(\t);elseprintf(%d\t,style[j]);if((j+1)%3==0)printf(\n);}printf(************%d***********\n,number);}voidloop(){printf(请输入数码：\n);for(i=0;i9;i++)scanf(%d,&style[i]);judge();step1();step2();step3();if(style[2]!=3){step4();step5();}step6();if(style[8]!=5){step7();step8();}step9();print();if(!((style[3]==8)&&(style[6]==7)))printf(用书上所给算法来看此数码错误！\n);}voidmain(){while(1)loop();}2.深度优先实现/***************说明***********************用宽度优先搜索算法实现八数码问题******************************************/#includeiostream#includestdio.h#includefstream#includestdlib.h#includestring.h#includeassert.h#includewindows.husingnamespacestd;intwholeStyle[9]={2,8,3,1,6,4,7,0,5};intstandard1[9]={1,2,3,8,0,4,7,6,5};intlocal,i,j;intstartKey=0,endKey=0,equalKey=1,tempSpace;structnode*openHead,*open;//open表structnode*closedHead,*closed;//closed表structnode*tempNode;//临时节点structnode*answer;//找到的路径intnum=0;structnode{intstyle[9];structnode*next;structnode*father;};voidupdateData()//更新要判断数据{inti;printf(请输入八数码原始状态：\n);for(i=0;i9;i++)scanf(%d,&wholeStyle[i]);printf(请输入八数码最终状态：\n);for(i=0;i9;i++)scanf(%d,&standard1[i]);}voidjudge1(structnode*head)//判断空格位置{for(i=0;i9;i++){if(head-style[i]==0){local=i;return;}}}intjudge2(structnode*head)//判断是否与标准八数码相等，不相等返回值为0{for(i=0;i9;i++){if(head-style[i]!=standard1[i]){if((i==3)&&(head-style[3]==standard1[6]));elseif((i==6)&&(head-style[6]==standard1[3]));elsereturn0;}}return1;}voidjudge3()//判断新生成的八数码是否就是最终状态或者在open、closed表中出现{if(judge2(tempNode))endKey=1;else{while(openHead-next-next-style[0]!=9){for(i=0;i9;i++){if(openHead-next-next-style[i]!=tempNode-style[i]){equalKey=1;break;}elseequalKey=0;}if(equalKey)//不相等openHead=openHead-next;elsebreak;}openHead=open-next;if(equalKey)//不相等{while(closedHead-next-style[0]!=9){for(i=0;i9;i++){if(closedHead-next-style[i]!=tempNode-style[i]){equalKey=1;break;}elseequalKey=0;}if(!equalKey)//相等break;elseclosedHead=closedHead-next;}closedHead=closed-next;}if(equalKey)//不相等{open-next=tempNode;tempNode-next=openHead;tempNode-father=openHead-next;open=open-next;}}}voidprint(structnode*temp)//输出八数码表{for(j=0;j9;j++){if(temp-style[j]==0)printf(\t);elseprintf(%d\t,temp-style[j]);if((j+1)%3==0)printf(\n);}}voidwrite2txt(){ofstreamout(F:\\out_details.txt,ios::app);if(out.fail()){cerr未找到文件endl;}out第++num步\n;outopentable：