作者在 2011-11-08 23:11:56 发布以下内容
下面是一个手机锁的简便图形,
解锁原理:随便从一个开始,直线连接下一个,再连
下一个,再下一个.就可以了(不能有重复的)
连接四个就可以了,多了不能解锁,
顺序不对也不能解
我们分别从上标示:
0 1 2
3 4 5
6 7 8
比如:可以连0576,0512
但不能0876,0到8要经过4不行
用邻接矩阵方法构造:
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;
}