|
#2
jinh2011-11-18 22:17
|
只有本站会员才能查看附件，请 登录
上图为手机锁的简易图:它是三行三列,规则的,本人画的不太好
我们把它编号为:
0 1 2
3 4 5
6 7 8
解锁原理:随便从一个开始,连接下一个,再连下一个,再下一个.就可以了(不能有重复的四个)但不能从0直接连到8,他们的直线经过了4,比如你开始时设置的锁是:0-4-8-1;解锁时必须是一样的顺序,否则进不去;比如还有一些连接:0-7-6-3,4-8-7-5,等等.但不能出现:0-2,因为他穿过1才能到.0-0不行所以我们用邻接矩阵方法构造时edge[i][i]=0表示同个数字不能相互连接,edge[0][2]=0表示0不能与2直接相连,矩阵中等于1的表示下标之间的两个图形能连接;
用邻接矩阵方法构造:
edge[9][9]={{0,1,0,1,1,1,0,1,0},
{1,0,1,1,1,1,1,0,1},
{0,1,0,1,1,1,0,1,0},
{1,1,1,0,1,0,1,1,1},
{1,1,1,1,0,1,1,1,1},
{1,1,1,0,1,0,1,1,1},
{0,1,0,1,1,1,0,1,0},
{1,0,1,1,1,1,1,0,1},
{0,1,0,1,1,1,0,1,0}};
关于这个锁的有多少种.算出来是152
代码如下:
程序代码：#include<iostream>
using namespace std;
void main(){
int i,j,k,l,z,count;
//char vex[9];//顶点表
int edge[9][9]={{0,1,0,1,1,1,0,1,0},{1,0,1,1,1,1,1,0,1},{0,1,0,1,1,1,0,1,0},{1,1,1,0,1,0,1,1,1},{1,1,1,1,0,1,1,1,1},{1,1,1,0,1,0,1,1,1},{0,1,0,1,1,1,0,1,0},{1,0,1,1,1,1,1,0,1},{0,1,0,1,1,1,0,1,0}};//邻接矩阵,即边表
int vnum=9;
count=0;
int visited[9];//定义~~~^^^^^^^^^^^^^^^^^^^
for(i=0;i<vnum;i++){
for(int a=0;a<vnum;a++)
visited[a]=0;
visited[i]=1;//标志向量初始化
for(j=0;j<vnum;j++){
if(visited[j]==0&&edge[i][j]==1&&(j!=i)){
visited[j]=1;
for(k=0;k<vnum;k++){
if(visited[k]==0&&edge[j][k]==1&&k!=j&&k!=i){
visited[k]=1;
for(l=0;l<vnum;l++){
if(visited[l]==0&&edge[l][k]==1&&(l!=k)&&(l!=i)&&(l!=j))
count=count+1;
}
}
}
}
}
}
cout<<"此算法有"<<count<<"种"<<endl;
}
using namespace std;
void main(){
int i,j,k,l,z,count;
//char vex[9];//顶点表
int edge[9][9]={{0,1,0,1,1,1,0,1,0},{1,0,1,1,1,1,1,0,1},{0,1,0,1,1,1,0,1,0},{1,1,1,0,1,0,1,1,1},{1,1,1,1,0,1,1,1,1},{1,1,1,0,1,0,1,1,1},{0,1,0,1,1,1,0,1,0},{1,0,1,1,1,1,1,0,1},{0,1,0,1,1,1,0,1,0}};//邻接矩阵,即边表
int vnum=9;
count=0;
int visited[9];//定义~~~^^^^^^^^^^^^^^^^^^^
for(i=0;i<vnum;i++){
for(int a=0;a<vnum;a++)
visited[a]=0;
visited[i]=1;//标志向量初始化
for(j=0;j<vnum;j++){
if(visited[j]==0&&edge[i][j]==1&&(j!=i)){
visited[j]=1;
for(k=0;k<vnum;k++){
if(visited[k]==0&&edge[j][k]==1&&k!=j&&k!=i){
visited[k]=1;
for(l=0;l<vnum;l++){
if(visited[l]==0&&edge[l][k]==1&&(l!=k)&&(l!=i)&&(l!=j))
count=count+1;
}
}
}
}
}
}
cout<<"此算法有"<<count<<"种"<<endl;
}