逆流問題の解決構想
5224 ワード
この問題は前にある会社を面接したときに出会ったもので、以前はこのような問題に出会ったことがなくて、急に上がってきて少しぼんやりしていました.しかし、数分で考えを整理していくつかの解題案があったが、一時的に考えた案の抜け穴はまだいくつかあり、考えがあった.大きな方向が正しい.コードを書くのは簡単だが、脳のカオス状態は本当に完璧なコードを書くとは限らない.
タイトル:
2つの容器A Bをあげて、限られたステップで水を注いで、容量Cの水を得ることができるかどうかを聞いてみましょう.
最小ステップ数を出力し、各ステップの操作を出力します.
目標状態に達しない場合はimpossibleを出力
考え方:
総状態はそれだけであり,いずれにしてもステップ毎に6種類の操作が明らかなBFSキーのみがステップ毎の経路の記録である.
実はA星アルゴリズムです
各層の操作は6つの可能性があります.
一:池の水でAを満たす
二:池の水でBを満たす
三:Aの水を全部廃水池に入れる
四:Bの水を全部廃水池に入れる
五:Aの水をBに注ぐ【こぼれない】
A中の水をk 1、B中の水をk 2で表す場合があります
k 1+k 2<=Bの場合、k 2=k 1+k 2となる.k 1=0【容器Bを満タンにできない】注意手順
そうでなければk 1=k 1+k 2-B;k 2=B【容器Bを満タンにできる】
六:Bの水をAに注ぐ【こぼれない】
二つのケースもあり、分析は同じです.
k 1+k 2<=Aの場合、k 1=k 1+k 2となる.k2 = 0;
そうでなければk 2=k 1+k 2-A;k1 = A
前にもネット上のいくつかのコードを参考にして、書いたのはまだ少しカオスですが、正直に言うと私のほうがはっきりしているような気がします.
当時参考にしていたurlを添付します.https://www.bbsmax.com/A/n2d99RL6dD/
ポイントを作るのは容易ではありません.興味のあるダウンロードをしてください.https://download.csdn.net/download/a925907195/11173095
タイトル:
2つの容器A Bをあげて、限られたステップで水を注いで、容量Cの水を得ることができるかどうかを聞いてみましょう.
最小ステップ数を出力し、各ステップの操作を出力します.
目標状態に達しない場合はimpossibleを出力
考え方:
総状態はそれだけであり,いずれにしてもステップ毎に6種類の操作が明らかなBFSキーのみがステップ毎の経路の記録である.
実はA星アルゴリズムです
各層の操作は6つの可能性があります.
一:池の水でAを満たす
二:池の水でBを満たす
三:Aの水を全部廃水池に入れる
四:Bの水を全部廃水池に入れる
五:Aの水をBに注ぐ【こぼれない】
A中の水をk 1、B中の水をk 2で表す場合があります
k 1+k 2<=Bの場合、k 2=k 1+k 2となる.k 1=0【容器Bを満タンにできない】注意手順
そうでなければk 1=k 1+k 2-B;k 2=B【容器Bを満タンにできる】
六:Bの水をAに注ぐ【こぼれない】
二つのケースもあり、分析は同じです.
k 1+k 2<=Aの場合、k 1=k 1+k 2となる.k2 = 0;
そうでなければk 2=k 1+k 2-A;k1 = A
前にもネット上のいくつかのコードを参考にして、書いたのはまだ少しカオスですが、正直に言うと私のほうがはっきりしているような気がします.
/**
*
* @Author:
* @Description:
* 1:->a
* 2:->b
* 3:a->
* 4:b->
* 5:a->b
* 6:b->a
* @Date: Created in :2019
* @Modified by:
*/
public class CurrStatus {
public int ka=0,kb=0;
public int op=0;
public CurrStatus pre;
}
package com.fjsh.mnp;
import com.fjsh.mnp.models.CurrStatus;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* @Author:
* @Description:
* @Date: Created in :2019
* @Modified by:
*/
public class SelfMain {
public static void main(String[] args) {
final CurrStatus head = new CurrStatus();
List currStatusList=new LinkedList(){{add(head);}};
int a = 3, b = 5, c = 4;
CurrStatus tail = dealPool(currStatusList, a, b, c);
if (tail == null) {
System.out.println("impossible");
} else {
List ops=new ArrayList();
while (tail.op != 0) {
ops.add(tail.op);
tail = tail.pre;
}
for(int i=ops.size()-1;i>=0;i--){
if(ops.get(i)==1){
System.out.println(" a");
}
if(ops.get(i)==2){
System.out.println(" b");
}
if(ops.get(i)==3){
System.out.println(" a");
}
if(ops.get(i)==4){
System.out.println(" b");
}
if(ops.get(i)==5){
System.out.println("a b");
}
if(ops.get(i)==6){
System.out.println("b a");
}
}
}
}
public static CurrStatus dealPool(List currStatusList, int a, int b, int pool) {
if(a+b currStatuses = new LinkedList();
for (CurrStatus currStatus : currStatusList) {
//
for (int i = 1; i <= 6; i++) {
CurrStatus item = new CurrStatus();
item.op = i;
item.pre = currStatus;
if (i == 1) {
item.ka = a;
item.kb = currStatus.kb;
} else if (i == 2) {
item.kb = b;
item.ka = currStatus.ka;
} else if (i == 3) {
item.ka = 0;
item.kb = currStatus.kb;
} else if (i == 4) {
item.kb = 0;
item.ka = currStatus.ka;
} else if (i == 5) {
if (currStatus.ka + currStatus.kb <= b) {
item.ka = 0;
item.kb = currStatus.ka + currStatus.kb;
} else if (currStatus.ka + currStatus.kb > b) {
item.kb = b;
item.ka = (currStatus.ka + currStatus.kb) - b;
}
} else if (i == 6) {
if (currStatus.ka + currStatus.kb <= a) {
item.kb = 0;
item.ka = currStatus.ka + currStatus.kb;
} else if (currStatus.ka + currStatus.kb > a) {
item.ka = a;
item.kb = (currStatus.ka + currStatus.kb) - a;
}
}
if (item.ka == pool || item.kb == pool || item.ka
+ item.kb == pool) {
return item;
}
currStatuses.add(item);
}
}
max++;
currStatusList=currStatuses;
}
return null;
}
}
当時参考にしていたurlを添付します.https://www.bbsmax.com/A/n2d99RL6dD/
ポイントを作るのは容易ではありません.興味のあるダウンロードをしてください.https://download.csdn.net/download/a925907195/11173095