Go语言视频零基础入门到精通

javalearner · 发表于 2014-12-1 00:05:53

农夫过河问题dfs算法的java版本
自己做的不足之处希望指出.232136813@qq.com

public class manriver {
private int[][] maxtri=new int[16][16];//邻接矩阵
private int[][] order={{0,0},
{1,0},
{2,0},
{3,0},
{4,0},
{5,0},
{6,0},
{7,0},
{8,0},
{9,0},
{10,0},
{11,0},
{12,0},
{13,0},
{14,0},
{15,0}};// 状态是否被访问过的数组
private stack stack=new stack();
/**
* judge the adjacency matrix elements true or false(1 or 0)
*
*/
private boolean isConnected(int x,int y){
String X=getformatString(x);
String Y=getformatString(y);
if(X.charAt(0)==Y.charAt(0))
return false;
else{
if(X.charAt(1)!=Y.charAt(1)&&X.charAt(2)!=Y.charAt(2)&&X.charAt(3)!=Y.charAt(3)){
return false;
}
else if(X.charAt(1)!=Y.charAt(1)&&X.charAt(2)!=Y.charAt(2)){
return false;
}
else if(X.charAt(1)!=Y.charAt(1)&&X.charAt(3)!=Y.charAt(3)){
return false;
}
else if(X.charAt(2)!=Y.charAt(2)&&X.charAt(3)!=Y.charAt(3)){
return false;
}
else if(((X.charAt(0)!=X.charAt(1))&&(X.charAt(1)!=Y.charAt(1)))||((X.charAt(0)!=X.charAt(2))&&
(X.charAt(2)!=Y.charAt(2)))||((X.charAt(0)!=X.charAt(3))&&(X.charAt(3)!=Y.charAt(3)))){
return false;
}
return true;
}
}
/**
*
* produce the adjacency matrix
*
*/
public void makeMaxtri(){
for(int i=0;i< 16;i++){
for(int j=0;j< 16;j++){
if(isConnected(i, j))
{ maxtri[i][j]=1;
}
else maxtri[i][j]=0;
}
}
}
/**
*
* 得到状态的字符串表示
* 0000 四位分别代表人羊草狼
*
* */
public String getformatString(int x){
String X=Integer.toBinaryString(x);
if(X.length()< 4&&X.length()>=3){
X="0"+X;
}
else if(X.length()< 3&&X.length()>=2){
X="00"+X;
}
else if(X.length()< 2&&X.length()>=1){
X="000"+X;
}
return X;
}
/**
*
* dfs arithmetic
* dfs算法
*
*/
public void dfs(){
stack.push(0);
order[0][1]=1;
while(!stack.isEmpty()){
if(stack.peek()==15){
break;
}
int v=getUnvisitedVetex(stack.peek());
if(v==-1){
try{stack.pop();
}catch(Exception e){
e.printStackTrace();
}
}
else{
stack.push(v);
order[v][1]=1;
}
}
}
/**
*
*得到与输入节点相连的一个结点
*
*/
public int getUnvisitedVetex(int x){
for(int j=0;j< 16;j++){
if(maxtri[x][j]==1&ℴ[j][1]==0){
String X=getformatString(j);
//合法性判断
if((X.charAt(0)!=X.charAt(1)&&X.charAt(1)==X.charAt(3))||
(X.charAt(0)!=X.charAt(1)&&X.charAt(1)==X.charAt(2))){
continue;
}
else {
return j;}
}
}
return -1;
}
/**
*
* make order
*
*/
public void printOrder() throws Exception{
for(int i=0;i< stack.length()-1;i++){
int x=stack.peekByIndex(i);
int y=stack.peekByIndex(i+1);
String X=getformatString(x);
String Y=getformatString(y);
String type="";
if(X.charAt(0)=="0"){
type="过河";
}
if(X.charAt(0)=="1"){
type="回来";
}
if(X.charAt(1)!=Y.charAt(1)){
System.out.println("人带羊"+type);
}
else if(X.charAt(2)!=Y.charAt(2)){
System.out.println("人带草"+type);
}
else if(X.charAt(3)!=Y.charAt(3)){
System.out.println("人带狼"+type);
}
else{
System.out.println("人自己"+type);
}
}
}
public static void main(String[] args){
manriver manriver=new manriver();
manriver.makeMaxtri();
manriver.dfs();
try{
manriver.printOrder();
}catch(Exception e){
e.printStackTrace();
}
}
}
/**
*
* 堆栈简单实现类
*
*/
class stack{
private int[] num;
private int value;
public stack(){
num=new int[20];
value=-1;
}
public int peek(){
return num[value];
}
public int pop() throws Exception{
if(value>=0){
return num[value--];
}
else throw new Exception("无元素！");
}
public void push(int xx){
if(value==-1){
value=0;
num[value]=xx;
}
else{
num[++value]=xx;
}
}
public int getSize(){
return value;
}
public boolean isEmpty(){
return(value< 0);
}
public int length(){
return value+1;
}
public int peekByIndex(int i)throws Exception{
if(i< value+1&&i>=0){
return num[i];
}
else throw new Exception("未找到合适元素！");
}
}

复制代码

C: est>java manriver
人带羊过河
人自己回来
人带狼过河
人带羊回来
人带草过河
人自己回来
人带羊过河















源码下载：http://file.javaxxz.com/2014/12/1/000552781.zip

		自动登录	找回密码
密码			立即注册

JAVA高级面试进阶视频教程	Java架构师系统进阶VIP课程	分布式高可用全栈开发微服务教程	Go语言视频零基础入门到精通	Java架构师3期(课件+源码)
Java开发全终端实战租房项目视频教程	SpringBoot2.X入门到高级使用教程	大数据培训第六期全套视频教程	深度学习（CNN RNN GAN）算法原理	Java亿级流量电商系统视频教程
互联网架构师视频教程	年薪50万Spark2.0从入门到精通	年薪50万！人工智能学习路线教程	年薪50万！大数据从入门到精通学习路线	年薪50万！机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程	深度学习数据分析基础到实战	最新黑马javaEE2.1就业课程	从 0到JVM实战高手教程	MySQL入门到精通教程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

Java亿级流量电商系统视频教程

年薪50万Spark2.0从入门到精通

年薪50万！人工智能学习路线教程

[算法学习]农夫过河问题(深度优先算法)java版

相关帖子