首页 > 代码库 > 算法笔记_152: 算法提高 扶老奶奶过街(Java)

算法笔记_152: 算法提高 扶老奶奶过街(Java)

目录

1 问题描述

2 解决方案

 


1 问题描述

 一共有5个红领巾,编号分别为A、B、C、D、E,老奶奶被他们其中一个扶过了马路。

  五个红领巾各自说话:

  A :我和E都没有扶老奶奶

  B :老奶奶是被C和E其中一个扶过大街的

  C :老奶奶是被我和D其中一个扶过大街的

  D :B和C都没有扶老奶奶过街

  E :我没有扶老奶奶


  已知五个红领巾中有且只有2个人说的是真话,请问是谁扶这老奶奶过了街?

  若有多个答案,在一行中输出,编号之间用空格隔开。


  例如
  A B C D E(这显然不是正确答案)

 

 


2 解决方案

 技术分享

 

具体代码如下:

import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static ArrayList<Integer> result = new ArrayList<Integer>();
    
    public void getResult(int i, int j) {
        //ans[i] = 0表示初始状态,ans[i] = -1表示一定没有扶
        //ans[i] = 1表示一定有扶,ans[i] = 2表示有可能扶
        int[] ans = new int[5];  
        
        //A说
        if(i == 0 || j == 0) {
            ans[0] = -1;
            ans[4] = -1;
        } else {
            ans[0] = 2;
            ans[4] = 2;
        }
        //B说
        if(i == 1 || j == 1) {
            ans[2] = 2;
            if(ans[4] == 2) {
                ans[4] = 1;
            } else if(ans[4] == -1)
                ans[2] = 1;
        } else {
            ans[2] = -1;
            if(ans[4] == 2) {
                ans[4] = -1;
                ans[0] = 1;
            }
        }
        //C说
        if(i == 2 || j == 2) {
            ans[3] = 2;
            if(ans[2] == 2)
                ans[2] = 1;
            else if(ans[2] == -1)
                ans[3] = 1;
        } else {
            if(ans[2] == 1)
                return;
            else 
                ans[2] = -1;
            ans[3] = -1;
        }
        //D说
        if(i == 3 || j == 3) {
            ans[1] = -1;
            if(ans[2] == 1)
                return;
            else if(i == 2 || j == 2) {
                ans[2] = -1;
                ans[3] = 1;
            } else if(i == 1 || j == 1) {
                ans[2] = -1;
                ans[4] = 1;
            }
        } else {
            ans[1] = 2;
            if(ans[2] == 2)
                ans[2] = 1;
            else if(ans[2] == -1)
                ans[1] = 1;
        }
        //E说
        if(i == 4 || j == 4) {
            if(ans[4] == 1)
                return;
            else
                ans[4] = -1;
        } else {
            if(ans[4] == -1)
                return;
            else
                ans[4] = 1;
        }
        int count = 0, temp = 0;
        for(int t = 0;t < 5;t++) {
            if(ans[t] == 1) {
                count++;
                temp = t;
            }
        }
        if(count == 1) {
            if(!result.contains(temp))
                result.add(temp);
        }
        return;
    }
    
    public static void main(String[] args) {
        Main test = new Main();
        for(int i = 0;i < 5;i++) {
            for(int j = i + 1;j < 5;j++) {
                test.getResult(i, j);
            }
        }
        Collections.sort(result);
        for(int i = 0;i < result.size();i++) {
            char temp = (char) (‘A‘ + result.get(i));
            System.out.print(temp+" ");
        }
    }
}

 

算法笔记_152: 算法提高 扶老奶奶过街(Java)