- 浏览: 10512 次
- 性别:
- 来自: 武汉
最新评论
-
windshome:
项目中文件多,怎么就会乱呢?,怎么就不利用阅读和调试?脑子不清 ...
java语法上最期待的改进 -
linliangyi2007:
让人很无语的想法,太肤浅了,投你个隐藏
java语法上最期待的改进 -
aws:
给接口加默认实现,那还要抽象类干嘛?
java语法上最期待的改进 -
delphixp:
给接口加默认实现 ---- 画蛇添足。将 void 当作 th ...
java语法上最期待的改进 -
01404421:
icefire 写道kobevaliant 写道我想要:多继承 ...
java语法上最期待的改进
三只大老虎和三只小老虎过河
三只大老虎分别是A.B.C三只小老虎分别是1.2.3,只有一条船,一次只能坐两只,A和1是母子俩,B和2是母子俩,C和3母子俩,只要任何一个母亲离开小老虎,小老虎都会被吃掉.
问题补充:大老虎都会划船 三只小老虎中只有1会划船
设大老虎为ABC,相应的小老虎为abc,其中c会划船。
package test;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TigerRiver {
public static int[]tigersteps=new int[27*27*3] ;
public static Map<Integer,Status> map = new HashMap<Integer,Status>();
int i=0;
public TigerRiver() {
Status status = new Status(2, 2, 2, 2, 2, 2,false);
for(int i=0;i<tigersteps.length;i++){
tigersteps[i]=-1;
}
map.put(status.hashCode(), status);
tigersteps[status.hashCode()]=0;
}
public int minStep(Status status) throws IllegalArgumentException, IllegalAccessException {
int hascode=status.hashCode();
int minstep = tigersteps[hascode];
if (minstep != -1)
return minstep;
minstep = Integer.MAX_VALUE;
map.put(hascode, status);
List<Status> steps = status.getAllStep();
for (Status status2 : steps) {
int temhascode=status2.hashCode();
if(tigersteps[temhascode]==-1 && map.get(temhascode)!=null)continue;
int temstep = minStep(status2);
if (temstep < minstep-1) {
minstep = temstep+1;
status.setNextStatus(map.get(temhascode));
}
}
tigersteps[hascode]=minstep;
return minstep;
}
public static void print(Status status){
System.out.println(status);
while (status.getNextStatus()!=null) {
status=status.getNextStatus();
System.out.println(status);
}
}
public static void main(String[] args) {
Status status = new Status(0, 0, 0, 0, 0, 0,true);
TigerRiver tigerRiver=new TigerRiver();
try {
System.out.println("steps:"+tigerRiver.minStep(status));
} catch (IllegalArgumentException e) {
e.printStackTrace();
} catch (IllegalAccessException e) {
e.printStackTrace();
}
print(status);
}
}
package test;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;
import org.apache.poi.hssf.record.ContinueRecord;
public class Status {
public int A;
public int a;
public int B;
public int b;
public int C;
public int c;
private boolean left;
private Status nextStatus;
public Status(int big1, int small1, int big2, int small2, int big3,
int small3, boolean left) {
super();
this.A = big1;
this.a = small1;
this.B = big2;
this.b = small2;
this.C = big3;
this.c = small3;
this.left = left;
}
public Status(Status status) {
super();
this.A = status.A;
this.a = status.a;
this.B = status.B;
this.b = status.b;
this.C = status.C;
this.c = status.c;
this.left = status.left;
}
public List<Status> getAllStep() throws IllegalArgumentException,
IllegalAccessException {
List<Status> steps = new ArrayList<Status>();
if (left) {
List<Status> atob = getOneStepTrigers(0, 1);
for (Status status : atob) {
if (status.check())
steps.add(status);
}
List<Status> btoa = getOneStepTrigers(1, 0);
for (Status status : btoa) {
if (status.check())
steps.add(status);
}
if(getCount(0)>=2){
List<Status> atwob = getTwoStepTrigers(0, 1);
for (Status status : atwob) {
if (status.check())
steps.add(status);
}
}
if(getCount(1)>=2){
List<Status> btwoa = getTwoStepTrigers(1, 0);
for (Status status : btwoa) {
if (status.check())
steps.add(status);
}
}
} else {
List<Status> ctob = getOneStepTrigers(2, 1);
for (Status status : ctob) {
if (status.check())
steps.add(status);
}
List<Status> btoc = getOneStepTrigers(1, 2);
for (Status status : btoc) {
if (status.check())
steps.add(status);
}
if(getCount(2)>=2){
List<Status> ctwob = getTwoStepTrigers(2, 1);
for (Status status : ctwob) {
if (status.check())
steps.add(status);
}
}
if(getCount(1)>=2){
List<Status> btwoc = getTwoStepTrigers(1, 2);
for (Status status : btwoc) {
if (status.check())
steps.add(status);
}
}
}
if (A == 1 || B == 1 || C == 1 || c == 1) {
Status status = new Status(this);
status.left = !left;
steps.add(status);
}
return steps;
}
public boolean check() {
if (A < 0 || B < 0 || C < 0 || a < 0 || b < 0 || c < 0)
return false;
if (a == 0 && A != 0 || b == 0 && B != 0 || c == 0 && C != 0) {
if (A == 0 || B == 0 || C == 0) {
return false;
}
}
if (getCount(1) > 2)
return false;
if (a == 1 && A != 1 || b == 1 && B != 1 || c == 1 && C != 1) {
if (A == 1 || B == 1 || C == 1) {
return false;
}
}
if (a == 2 && A != 2 || b == 2 && B != 2 || c == 2 && C != 2) {
if (A == 2 || B == 2 || C == 2) {
return false;
}
}
return true;
}
private List<Field> getTrigers(int point) throws IllegalArgumentException,
IllegalAccessException {
List<Field> trigers = new ArrayList<Field>();
Field[] fields = this.getClass().getFields();
for (Field field : fields) {
if (((Integer) field.get(this)).intValue() == point) {
trigers.add(field);
}
}
return trigers;
}
private List<Status> getOneStepTrigers(int from, int to)
throws IllegalArgumentException, IllegalAccessException {
List<Status> trigers = new ArrayList<Status>();
List<Field> fList = getTrigers(from);
for (Field field : fList) {
Status status = new Status(this);
field.set(status, to);
trigers.add(status);
}
return trigers;
}
private List<Status> getTwoStepTrigers(int from, int to)
throws IllegalArgumentException, IllegalAccessException {
List<Status> trigers = new ArrayList<Status>();
List<Field> fList = getTrigers(from);
for (int i = 0; i < fList.size() - 1; i++) {
for (int j = i + 1; j < fList.size(); j++) {
Field fielda = fList.get(i);
Field fieldb = fList.get(j);
Status status = new Status(this);
fielda.set(status, to);
fieldb.set(status, to);
trigers.add(status);
}
}
return trigers;
}
private int getCount(int point) {
int count = 0;
if (A == point)
count++;
if (B == point)
count++;
if (C == point)
count++;
if (a == point)
count++;
if (b == point)
count++;
if (c == point)
count++;
return count;
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
if (A == 0)
sb.append("A");
if (B == 0)
sb.append("B");
if (C == 0)
sb.append("C");
if (a == 0)
sb.append("a");
if (b == 0)
sb.append("b");
if (c == 0)
sb.append("c");
for (int i = getCount(0); i < 6; i++) {
sb.append(" ");
}
sb.append(" | ");
if (!left) {
sb.append(" ");
}
if (A == 1)
sb.append("A");
if (B == 1)
sb.append("B");
if (C == 1)
sb.append("C");
if (a == 1)
sb.append("a");
if (b == 1)
sb.append("b");
if (c == 1)
sb.append("c");
for (int i = getCount(1); i < 2; i++) {
sb.append(" ");
}
if (left) {
sb.append(" ");
}
sb.append(" | ");
if (A == 2)
sb.append("A");
if (B == 2)
sb.append("B");
if (C == 2)
sb.append("C");
if (a == 2)
sb.append("a");
if (b == 2)
sb.append("b");
if (c == 2)
sb.append("c");
for (int i = getCount(0); i < 6; i++) {
sb.append(" ");
}
return sb.toString();
}
public Status getNextStatus() {
return nextStatus;
}
public void setNextStatus(Status nextStatus) {
this.nextStatus = nextStatus;
}
@Override
public int hashCode() {
int prime = 1;
int result = 0;
result += prime * A;
prime *= 3;
result += prime * a;
prime *= 3;
result += prime * B;
prime *= 3;
result += prime * b;
prime *= 3;
if (left) {
result += prime * 1;
} else {
result += prime * 2;
}
prime *= 3;
result += prime * C;
prime *= 3;
result += prime * c;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Status other = (Status) obj;
if (A != other.A)
return false;
if (B != other.B)
return false;
if (C != other.C)
return false;
if (left != other.left)
return false;
if (nextStatus == null) {
if (other.nextStatus != null)
return false;
} else if (!nextStatus.equals(other.nextStatus))
return false;
if (a != other.a)
return false;
if (b != other.b)
return false;
if (c != other.c)
return false;
return true;
}
}
steps:27
ABCabc | |
ABab | Cc |
ABab | Cc |
ABab | C | c
ABab | C | c
ABCab | | c
ACa | Bb | c
ACa | Bb | c
ACa | B | bc
ACa | B | bc
Aa | BC | bc
Aa | BC | bc
Aa | | BCbc
Aa | Bb | Cc
Aa | Bb | Cc
ABab | | Cc
ab | AB | Cc
ab | AB | Cc
ab | A | BCc
ab | A | BCc
b | Aa | BCc
b | Aa | BCc
b | | ABCac
b | B | ACac
b | B | ACac
| Bb | ACac
| Bb | ACac
| | ABCabc
这是第一版本,没有考虑主动进攻,第二版已经修正了
steps:38
ABCabc | |
ACac | Bb |
ACac | Bb |
ACac | B | b
ACac | B | b
ABCac | | b
ABC | ac | b
ABC | ac | b
ABC | c | ab
ABC | c | ab
ABCc | | ab
Cc | AB | ab
Cc | AB | ab
Cc | | ABab
Cc | Aa | Bb
Cc | Aa | Bb
ACc | a | Bb
AC | ac | Bb
ACa | c | Bb
Aa | Cc | Bb
Aa | Cc | Bb
Aa | c | BCb
Aa | bc | BC
Aa | b | BCc
Aa | Bb | Cc
Aa | Bb | Cc
ABab | | Cc
ab | AB | Cc
ab | AB | Cc
ab | | ABCc
ab | c | ABC
ab | c | ABC
b | ac | ABC
b | ac | ABC
b | c | ABCa
b | c | ABCa
| bc | ABCa
| bc | ABCa
| | ABCabc
图是比较好的思路
先解析所有的状态 如ABCabc| , BCbc|Aa , ...... ,|ABCabc
从ABCabc| -> 中间状态 ->....->|ABCabc
这就变成了找到可行路径,最小路径的问题了
不过反正都是从开始找起,一边搜一边找孩子也一样了,
注意不要走进 x->y->z->x.....-z-x->y->z....这样的循环
三只大老虎分别是A.B.C三只小老虎分别是1.2.3,只有一条船,一次只能坐两只,A和1是母子俩,B和2是母子俩,C和3母子俩,只要任何一个母亲离开小老虎,小老虎都会被吃掉.
问题补充:大老虎都会划船 三只小老虎中只有1会划船
设大老虎为ABC,相应的小老虎为abc,其中c会划船。
package test;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TigerRiver {
public static int[]tigersteps=new int[27*27*3] ;
public static Map<Integer,Status> map = new HashMap<Integer,Status>();
int i=0;
public TigerRiver() {
Status status = new Status(2, 2, 2, 2, 2, 2,false);
for(int i=0;i<tigersteps.length;i++){
tigersteps[i]=-1;
}
map.put(status.hashCode(), status);
tigersteps[status.hashCode()]=0;
}
public int minStep(Status status) throws IllegalArgumentException, IllegalAccessException {
int hascode=status.hashCode();
int minstep = tigersteps[hascode];
if (minstep != -1)
return minstep;
minstep = Integer.MAX_VALUE;
map.put(hascode, status);
List<Status> steps = status.getAllStep();
for (Status status2 : steps) {
int temhascode=status2.hashCode();
if(tigersteps[temhascode]==-1 && map.get(temhascode)!=null)continue;
int temstep = minStep(status2);
if (temstep < minstep-1) {
minstep = temstep+1;
status.setNextStatus(map.get(temhascode));
}
}
tigersteps[hascode]=minstep;
return minstep;
}
public static void print(Status status){
System.out.println(status);
while (status.getNextStatus()!=null) {
status=status.getNextStatus();
System.out.println(status);
}
}
public static void main(String[] args) {
Status status = new Status(0, 0, 0, 0, 0, 0,true);
TigerRiver tigerRiver=new TigerRiver();
try {
System.out.println("steps:"+tigerRiver.minStep(status));
} catch (IllegalArgumentException e) {
e.printStackTrace();
} catch (IllegalAccessException e) {
e.printStackTrace();
}
print(status);
}
}
package test;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;
import org.apache.poi.hssf.record.ContinueRecord;
public class Status {
public int A;
public int a;
public int B;
public int b;
public int C;
public int c;
private boolean left;
private Status nextStatus;
public Status(int big1, int small1, int big2, int small2, int big3,
int small3, boolean left) {
super();
this.A = big1;
this.a = small1;
this.B = big2;
this.b = small2;
this.C = big3;
this.c = small3;
this.left = left;
}
public Status(Status status) {
super();
this.A = status.A;
this.a = status.a;
this.B = status.B;
this.b = status.b;
this.C = status.C;
this.c = status.c;
this.left = status.left;
}
public List<Status> getAllStep() throws IllegalArgumentException,
IllegalAccessException {
List<Status> steps = new ArrayList<Status>();
if (left) {
List<Status> atob = getOneStepTrigers(0, 1);
for (Status status : atob) {
if (status.check())
steps.add(status);
}
List<Status> btoa = getOneStepTrigers(1, 0);
for (Status status : btoa) {
if (status.check())
steps.add(status);
}
if(getCount(0)>=2){
List<Status> atwob = getTwoStepTrigers(0, 1);
for (Status status : atwob) {
if (status.check())
steps.add(status);
}
}
if(getCount(1)>=2){
List<Status> btwoa = getTwoStepTrigers(1, 0);
for (Status status : btwoa) {
if (status.check())
steps.add(status);
}
}
} else {
List<Status> ctob = getOneStepTrigers(2, 1);
for (Status status : ctob) {
if (status.check())
steps.add(status);
}
List<Status> btoc = getOneStepTrigers(1, 2);
for (Status status : btoc) {
if (status.check())
steps.add(status);
}
if(getCount(2)>=2){
List<Status> ctwob = getTwoStepTrigers(2, 1);
for (Status status : ctwob) {
if (status.check())
steps.add(status);
}
}
if(getCount(1)>=2){
List<Status> btwoc = getTwoStepTrigers(1, 2);
for (Status status : btwoc) {
if (status.check())
steps.add(status);
}
}
}
if (A == 1 || B == 1 || C == 1 || c == 1) {
Status status = new Status(this);
status.left = !left;
steps.add(status);
}
return steps;
}
public boolean check() {
if (A < 0 || B < 0 || C < 0 || a < 0 || b < 0 || c < 0)
return false;
if (a == 0 && A != 0 || b == 0 && B != 0 || c == 0 && C != 0) {
if (A == 0 || B == 0 || C == 0) {
return false;
}
}
if (getCount(1) > 2)
return false;
if (a == 1 && A != 1 || b == 1 && B != 1 || c == 1 && C != 1) {
if (A == 1 || B == 1 || C == 1) {
return false;
}
}
if (a == 2 && A != 2 || b == 2 && B != 2 || c == 2 && C != 2) {
if (A == 2 || B == 2 || C == 2) {
return false;
}
}
return true;
}
private List<Field> getTrigers(int point) throws IllegalArgumentException,
IllegalAccessException {
List<Field> trigers = new ArrayList<Field>();
Field[] fields = this.getClass().getFields();
for (Field field : fields) {
if (((Integer) field.get(this)).intValue() == point) {
trigers.add(field);
}
}
return trigers;
}
private List<Status> getOneStepTrigers(int from, int to)
throws IllegalArgumentException, IllegalAccessException {
List<Status> trigers = new ArrayList<Status>();
List<Field> fList = getTrigers(from);
for (Field field : fList) {
Status status = new Status(this);
field.set(status, to);
trigers.add(status);
}
return trigers;
}
private List<Status> getTwoStepTrigers(int from, int to)
throws IllegalArgumentException, IllegalAccessException {
List<Status> trigers = new ArrayList<Status>();
List<Field> fList = getTrigers(from);
for (int i = 0; i < fList.size() - 1; i++) {
for (int j = i + 1; j < fList.size(); j++) {
Field fielda = fList.get(i);
Field fieldb = fList.get(j);
Status status = new Status(this);
fielda.set(status, to);
fieldb.set(status, to);
trigers.add(status);
}
}
return trigers;
}
private int getCount(int point) {
int count = 0;
if (A == point)
count++;
if (B == point)
count++;
if (C == point)
count++;
if (a == point)
count++;
if (b == point)
count++;
if (c == point)
count++;
return count;
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
if (A == 0)
sb.append("A");
if (B == 0)
sb.append("B");
if (C == 0)
sb.append("C");
if (a == 0)
sb.append("a");
if (b == 0)
sb.append("b");
if (c == 0)
sb.append("c");
for (int i = getCount(0); i < 6; i++) {
sb.append(" ");
}
sb.append(" | ");
if (!left) {
sb.append(" ");
}
if (A == 1)
sb.append("A");
if (B == 1)
sb.append("B");
if (C == 1)
sb.append("C");
if (a == 1)
sb.append("a");
if (b == 1)
sb.append("b");
if (c == 1)
sb.append("c");
for (int i = getCount(1); i < 2; i++) {
sb.append(" ");
}
if (left) {
sb.append(" ");
}
sb.append(" | ");
if (A == 2)
sb.append("A");
if (B == 2)
sb.append("B");
if (C == 2)
sb.append("C");
if (a == 2)
sb.append("a");
if (b == 2)
sb.append("b");
if (c == 2)
sb.append("c");
for (int i = getCount(0); i < 6; i++) {
sb.append(" ");
}
return sb.toString();
}
public Status getNextStatus() {
return nextStatus;
}
public void setNextStatus(Status nextStatus) {
this.nextStatus = nextStatus;
}
@Override
public int hashCode() {
int prime = 1;
int result = 0;
result += prime * A;
prime *= 3;
result += prime * a;
prime *= 3;
result += prime * B;
prime *= 3;
result += prime * b;
prime *= 3;
if (left) {
result += prime * 1;
} else {
result += prime * 2;
}
prime *= 3;
result += prime * C;
prime *= 3;
result += prime * c;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Status other = (Status) obj;
if (A != other.A)
return false;
if (B != other.B)
return false;
if (C != other.C)
return false;
if (left != other.left)
return false;
if (nextStatus == null) {
if (other.nextStatus != null)
return false;
} else if (!nextStatus.equals(other.nextStatus))
return false;
if (a != other.a)
return false;
if (b != other.b)
return false;
if (c != other.c)
return false;
return true;
}
}
steps:27
ABCabc | |
ABab | Cc |
ABab | Cc |
ABab | C | c
ABab | C | c
ABCab | | c
ACa | Bb | c
ACa | Bb | c
ACa | B | bc
ACa | B | bc
Aa | BC | bc
Aa | BC | bc
Aa | | BCbc
Aa | Bb | Cc
Aa | Bb | Cc
ABab | | Cc
ab | AB | Cc
ab | AB | Cc
ab | A | BCc
ab | A | BCc
b | Aa | BCc
b | Aa | BCc
b | | ABCac
b | B | ACac
b | B | ACac
| Bb | ACac
| Bb | ACac
| | ABCabc
评论
31 楼
zookie
2009-01-27
哈哈哈哈哈
30 楼
sonic39
2009-01-25
很有问题!
ACa | Bb | c
ACa | Bb | c
ACa | B | bc
这一步难道B不会吃掉c?
ACa | Bb | c
ACa | Bb | c
ACa | B | bc
这一步难道B不会吃掉c?
29 楼
孤灯渡漠
2009-01-23
这样的题好像蛮多的啊,农民、羊、草也是这样类的问题好像
28 楼
ant_miracle
2009-01-23
http://www.blogjava.net/xmatthew/archive/2008/11/16/240766.html
这个是本人用Java的实现。
这个是本人用Java的实现。
27 楼
regale
2009-01-21
liuzhaodong89 写道
ab | A | BCc
ab | A | BCc
b | Aa | BCc
这种情况b不会被吃掉么....
ab | A | BCc
b | Aa | BCc
这种情况b不会被吃掉么....
这是第一版本,没有考虑主动进攻,第二版已经修正了
steps:38
ABCabc | |
ACac | Bb |
ACac | Bb |
ACac | B | b
ACac | B | b
ABCac | | b
ABC | ac | b
ABC | ac | b
ABC | c | ab
ABC | c | ab
ABCc | | ab
Cc | AB | ab
Cc | AB | ab
Cc | | ABab
Cc | Aa | Bb
Cc | Aa | Bb
ACc | a | Bb
AC | ac | Bb
ACa | c | Bb
Aa | Cc | Bb
Aa | Cc | Bb
Aa | c | BCb
Aa | bc | BC
Aa | b | BCc
Aa | Bb | Cc
Aa | Bb | Cc
ABab | | Cc
ab | AB | Cc
ab | AB | Cc
ab | | ABCc
ab | c | ABC
ab | c | ABC
b | ac | ABC
b | ac | ABC
b | c | ABCa
b | c | ABCa
| bc | ABCa
| bc | ABCa
| | ABCabc
26 楼
liuzhaodong89
2009-01-21
ab | A | BCc
ab | A | BCc
b | Aa | BCc
这种情况b不会被吃掉么....
ab | A | BCc
b | Aa | BCc
这种情况b不会被吃掉么....
25 楼
justcol
2009-01-20
写来写去都成了2只小老虎会划船了,貌似原题是只有一只小老虎会划船吧?
24 楼
cloverprince
2009-01-20
这是典型的图论搜索问题。建立一个“图”,每个节点是一个状态(每只老虎在哪侧,船在哪侧)
两个节点之间有边,边表示一个状态调走一只或几只老虎,可以转换到另一个状态。
初始状态是6只老虎都在原侧,终结状态就是6只老虎都被转移到对侧。
解法就是找到从初始状态到终结状态的一条路径(最好是最短路径)。
状态分合法状态和非法状态。非法状态就是会有老虎被吃掉。因此搜索的时候,需要避免走到非法状态。
转移需要满足:最多转移两只老虎,而且必须有一只会划船。
这样用简单的BFS就可以了。
最优解法可能有多个,都是13步。
我的实现
两个节点之间有边,边表示一个状态调走一只或几只老虎,可以转换到另一个状态。
初始状态是6只老虎都在原侧,终结状态就是6只老虎都被转移到对侧。
解法就是找到从初始状态到终结状态的一条路径(最好是最短路径)。
状态分合法状态和非法状态。非法状态就是会有老虎被吃掉。因此搜索的时候,需要避免走到非法状态。
转移需要满足:最多转移两只老虎,而且必须有一只会划船。
这样用简单的BFS就可以了。
最优解法可能有多个,都是13步。
我的实现
module Main where import List import Maybe import Text.Printf main = putStrLn $ prettyPrintPath $ fromJust $ bfs data Tiger = BigA | BigB | BigC | SmallA | SmallB | SmallC deriving (Show,Eq,Ord) -- SmallC can drive boat -- A helper logical function: a implies b implies :: Bool -> Bool -> Bool implies a b = (not a) || b data State = State Place [Tiger] deriving (Show,Eq) data Trans = Trans [Tiger] deriving (Show,Eq) data Place = Local | Remote deriving (Show,Eq) allTigers = [BigA,BigB,BigC,SmallA,SmallB,SmallC] bigTigers = [BigA,BigB,BigC] smallTigers = [SmallA,SmallB,SmallC] driverTigers = [BigA,BigB,BigC,SmallC] startingState = State Local allTigers finalState = State Remote [] -- A state is valid if both side of river is valid stateValid :: State -> Bool stateValid (State _ tigers) = localStateValid tigers && localStateValid (allTigers\\tigers) where -- A state is valid on one side of river means -- Either there are no big tigers or all small tigers are protected by their mothers localStateValid tigers = (noBigTiger tigers) || (allProtected tigers) noBigTiger tigers = all (`notElem` tigers) bigTigers allProtected tigers = all protected (zip smallTigers bigTigers) where protected (small,big) = (small `elem` tigers) `implies` (big `elem` tigers) -- A transition is valid if there is at most 2 tigers on the boat -- and at least one of them can drive the boat. transValid :: Trans -> Bool transValid (Trans tigers) = length tigers <=2 && any (`elem` tigers) driverTigers -- Find all possible transition from one state, -- no matter whether the target state is valid. findAllTrans :: State -> [Trans] findAllTrans (State place tigers) = map Trans (if place==Local then allTransLocal tigers else allTransLocal (allTigers\\tigers) ) where allTransLocal :: [Tiger] -> [[Tiger]] allTransLocal tigers = let (drivers,others) = partition (`elem` driverTigers) tigers in [[one] | one <- drivers] ++ [[one,another] | one <- drivers, another <- others] ++ anyTwo drivers where anyTwo [] = [] anyTwo [x] = [] anyTwo (x:xs) = [[x,another] | another <- xs] ++ anyTwo xs -- Actually perform one transition on a state, return the target state. -- Tiger lists are sorted for easy comparison. doTrans :: State -> Trans -> State doTrans (State Local tigers) (Trans goTigers) = State Remote (sort (tigers\\goTigers)) doTrans (State Remote tigers) (Trans comeTigers) = State Local (sort (tigers++comeTigers)) -- Breadth first search. -- Search from the initial state to the final state bfs :: Maybe [(State,Trans,State)] bfs = bfs' [startingState] [] [] -- Inside algorithm bfs' :: [State] -> [State] -> [(State,Trans,State)] -> Maybe [(State,Trans,State)] bfs' [] _ _ = Nothing -- When queue empty, fail. bfs' (s:ss) visited transes = -- s is current state, ss are other states. if s == finalState -- When final state reached, success. then Just (extractPath transes) else if s `elem` visited -- If state visited or visited, discard. then bfs' ss visited transes else let newVisited = s:visited -- Otherwise mark this state visited. allValidTransition = -- Find all transitions from current state (s), filtered. let allTrans = findAllTrans s allNewStates = map (doTrans s) allTrans in filter (\(s,t,s') -> (stateValid s' && s' `notElem` newVisited)) (zip3 (repeat s) allTrans allNewStates) -- only keep valid and unvisited newFrontier = ss ++ (map (\(s,t,s') -> s') allValidTransition) -- update queue newTranses = allValidTransition ++ transes -- update transition tree in bfs' newFrontier newVisited newTranses -- next round -- Given a resulting transition tree (a list of (State,Trans,State)) -- Output a path from startingState to finalState extractPath sts = reverse $ extractPath' sts finalState extractPath' _ curState | curState == startingState = [] extractPath' sts curState = let (prevState,trans,_) = (fromJust $ find (\(s,t,s') -> s' == curState) sts) in (prevState,trans,curState):(extractPath' sts prevState) -- Pretty print path: print all step and the final state prettyPrintPath sts = unlines $ ((map prettyPrintStep sts) ++ [prettyPrintStateLine $ (\(_,_,s') -> s') $ last sts]) -- Each step consists of the old state and the transition prettyPrintStep (s,t,s') = (prettyPrintStateLine s) ++ "\n" ++ (prettyPrintTransLine s t) prettyPrintStateLine (State place tigers) = let lhs = prettyPrintTigers tigers rhs = prettyPrintTigers (allTigers\\tigers) stateLine = printf "[%6s] | | [%6s]\n" lhs rhs :: String in stateLine prettyPrintTransLine (State place oldTigers) (Trans movingTigers) = let moves = prettyPrintTigers movingTigers transLine = case place of Local -> printf " %2s --->" moves :: String Remote -> printf " <--- %2s" moves :: String in transLine prettyPrintTigers = map prettyPrintTiger prettyPrintTiger tiger = case tiger of BigA -> 'A' BigB -> 'B' BigC -> 'C' SmallA -> '1' SmallB -> '2' SmallC -> '3'
23 楼
tiandeyu188
2009-01-19
还不如叫斑马母子或者角马母子
22 楼
xbmujfly
2009-01-17
这个好像是最优问题吧,利用最优控制和遗传算法或者蚁群算法都应该可以求出,不好意思,上学没好好学呀!
21 楼
kenken0y
2009-01-16
ABCabc<
---Aa--> BCbc>Aa
<-- A--- ABCbc<a
---bc--> ABC>abc
<-- c--- ABCc<ab
---AB--> Cc>ABab
<--Aa--- ACac<Bb
---Cc--> Aa>BCbc
<--Bb--- ABab<Cc
---AB--> ab>ABCc
<-- c--- abc<ABC
---ac--> b>ABCac
<-- B--- Bb<ACac
---Bb--> >ABCabc
按有限状态机的思路写了个,深度优先遍历.代码好像比楼主的复杂多了,就不贴了
---Bb--> 表示 Bb坐船往右边划
Aa>BCbc 表示Aa在左边,BCbc在右边,>表示船在右边,<表示船在左边
---Aa--> BCbc>Aa
<-- A--- ABCbc<a
---bc--> ABC>abc
<-- c--- ABCc<ab
---AB--> Cc>ABab
<--Aa--- ACac<Bb
---Cc--> Aa>BCbc
<--Bb--- ABab<Cc
---AB--> ab>ABCc
<-- c--- abc<ABC
---ac--> b>ABCac
<-- B--- Bb<ACac
---Bb--> >ABCabc
按有限状态机的思路写了个,深度优先遍历.代码好像比楼主的复杂多了,就不贴了
---Bb--> 表示 Bb坐船往右边划
Aa>BCbc 表示Aa在左边,BCbc在右边,>表示船在右边,<表示船在左边
20 楼
ayaga
2009-01-16
先过一对子不会划船的母子;
再过剩下两只大老虎;
最后过剩下两只小老虎。
再过剩下两只大老虎;
最后过剩下两只小老虎。
19 楼
pinnacle
2009-01-15
qianjigui 写道
感觉像操作系统的东西。
印象中可以使用图算法中的有向图、最小二分图覆盖等等。
印象中可以使用图算法中的有向图、最小二分图覆盖等等。
图是比较好的思路
先解析所有的状态 如ABCabc| , BCbc|Aa , ...... ,|ABCabc
从ABCabc| -> 中间状态 ->....->|ABCabc
这就变成了找到可行路径,最小路径的问题了
不过反正都是从开始找起,一边搜一边找孩子也一样了,
jjcang 写道
盲目搜索就够了。
注意不要走进 x->y->z->x.....-z-x->y->z....这样的循环
public class Status { String status; List<Status> children; Status(String s){ status = s; } public void getAllChildrenStatus(){ //解析status字符串,找到其所有下一步 //放入到children队列中 ....... } public eques(){...} public hashcode(){...} } public class StatusManager{ private Status startStatus; private Status endStatus; StatusManager(Status start,Status end){ startStatus = start; endStatus = end; } // 记录当前所走过的路径,避免重复 // 如 A->B->C->....A->B->C->A // 每一种状态最多只出现一次 private static List moveRecord<Status> = new ArrayList(); //判断当前状态是否已经走过 public boolean RecordHave(Status s){...} public void StatusSearch(){ StatusSearch(startStatus); } public void StatusSearch(Status currentNode){ moveRecord.add(curstatus); currentNodegetAllChildrenStatus(); //遍历所有孩子 for(Status s : currentNode.children){ // 如果孩子已经在moveRecord中,那么我们之前走到过这一步 // 如果和endNode相等,则为所求路径,打印 :) // 递归 if(!RecordHave(s)){ if(s.equals(endNode){ // print all value in current list; // 找到所有的路径,这可能只是其中一种 ........ continue; } StatusSearch(s); } } //回到上一步 moveRecord.remove(moveRecord.size()); } }
18 楼
pinnacle
2009-01-15
呵呵,楼主很会玩哦~
17 楼
flypeace
2009-01-15
以前做的题目,好象是3只小老虎都不会划船啊.
16 楼
liqiangxia
2009-01-15
不错!!!!!
15 楼
ailu5949
2009-01-14
这个网上有个flash游戏的 。。。 当时觉得好难 多玩几次就过了
14 楼
Snow_Young
2009-01-14
呀,这不是狼和羊过河的那个吗~挺有意思,回去自己也写个算法试试~
13 楼
xueyinglan
2009-01-14
看不太懂,能加上点注释就好了。
12 楼
jjcang
2009-01-14
盲目搜索就够了
相关推荐
在本文中,我们将深入探讨如何使用STM32F103C8T6微控制器来实现无源蜂鸣器播放“两只老虎”这首经典儿歌。STM32是一款基于ARM Cortex-M3内核的高性能、低功耗的微控制器,广泛应用于嵌入式系统设计。无源蜂鸣器是一...
小老虎完美破解绝对真实可用,谢谢!
《一只窝囊的大老虎》说课稿.doc
在本文中,我们将深入探讨如何使用STM32微控制器来驱动蜂鸣器并播放音乐,以实现"两只老虎"这首儿歌。STM32是一款基于ARM Cortex-M内核的高性能微控制器,广泛应用于嵌入式系统设计。我们将从以下几个方面进行讲解:...
《小老鼠和大老虎》.ppt
"监控工具三只老虎眼网管工具"是一款专为网络管理员设计的强大监控软件,它集成了多种功能,帮助用户有效地管理和监控网络运行状态。作为网管的得力助手,这款工具能够提供实时、准确的数据反馈,确保网络稳定、高效...
C51蜂鸣器播放两只老虎和小星星代码,怎么根据谱子打表呢。。。自己摸索吧
这篇文档是关于小学四年级语文课程的一个教学设计,主要针对部编版教材第六单元的《一只窝囊的大老虎》这一课题。课程难点在于引导学生理解并分析主角在排练和演出过程中心情的变化及其原因,同时体验童年生活的丰富...
5. 在课文整体梳理中,明确文章分为期盼参加演出、饰老虎没成功、寻找失败根源三个部分,同时揭示了老师和演“哥哥”的小朋友在表演理念上的不同。 6. 重点段落品析环节,通过分析作者在舞台上表演时的心理状态和...
在活动中,教师首先通过展示图片引出故事,以一只流口水的大老虎和三只小猪为角色,引发幼儿的兴趣。大老虎是故事中的反派角色,但其形象设计有趣,增加了故事的幽默感。教师通过模仿大老虎的声音和动作,使幼儿更...
3. 因为这只窝囊的大老虎,动作虽然笨拙,但是却很可爱,很有趣。 - 七、略 以上内容详细阐述了文本中的关键知识点,包括词语学习、成语运用、文本结构分析、角色心理和情节理解,以及思维拓展训练。这些知识点对于...
这篇PPT教案主要围绕一个儿童故事展开,讲述的是北京动物园里的一只大老虎因为生病无法照顾自己的三只小老虎,于是饲养员找来了一只大花狗代替老虎妈妈的角色,来喂养和照顾小老虎。这个故事教育孩子们关于爱心、...
《汇编音乐程序--两只老虎》 在计算机科学领域,汇编语言是一种低级编程语言,它是计算机硬件能够直接理解的指令集的符号表示。汇编语言与机器语言紧密相关,但比机器语言更易读,因为它使用了助记符来代表机器指令...
【小老虎的名片(语言)】是一个以教育儿童理解名片功能为主题的学习活动,旨在通过一个生动的故事引导孩子们认识名片在日常生活中的重要性。这个活动主要包含三个部分:故事讲述、幼儿讨论和家庭作业。 首先,教师...
用Python画一只可爱的小老虎,祝你虎年大吉!
这篇PPT课件是关于语文课程的一份教学材料,标题为"一只窝囊的大老虎",适合四年级上册的学生学习。课件内容主要围绕一篇课文展开,课文出自叶至善的作品,他是著名作家叶圣陶的儿子。课文的主角是一只被描绘成不太...
这篇教学设计针对的是小学四年级语文课程,课文《一只窝囊的大老虎》,主要讲述了作者参与校园剧表演,扮演老虎却因未完成“豁虎跳”而感到窝囊的故事。教学设计围绕以下几个方面展开: 1. **教材内容分析**:课文...
这篇文档主要介绍了一篇以"一只窝囊的大老虎"为题的课文,它属于小学四年级上册的人教版语文教材。这篇课文的教学目标主要包括以下几个方面: 1. 学习汉字:学生需要学会识别和书写9个生字,如"囊、羡",并掌握12个...
第三段中,大老虎采取行动改正错误,尝试修复与小老鼠的友情,孩子们被问及小老鼠对此的反应,以此深化理解道歉和原谅的重要性。 在完整欣赏故事后,教师邀请孩子们分享自己与朋友之间的矛盾和解决方法,以此强化...
在这个看似简单的儿童故事《小老鼠和大老虎 (4).ppt》中,其实蕴含了一些重要的教育理念和生活哲理,同时也可引发对信息技术在儿童教育中应用的思考。 首先,故事中的"小老鼠"和"大老虎"是常见的动物角色,常常被...