逆流問題の解決構想


この問題は前にある会社を面接したときに出会ったもので、以前はこのような問題に出会ったことがなくて、急に上がってきて少しぼんやりしていました.しかし、数分で考えを整理していくつかの解題案があったが、一時的に考えた案の抜け穴はまだいくつかあり、考えがあった.大きな方向が正しい.コードを書くのは簡単だが、脳のカオス状態は本当に完璧なコードを書くとは限らない.
タイトル:
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