java – 家谱祖先查找算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 家谱祖先查找算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4338字，纯文字阅读大概需要7分钟。

内容图文

我的方法无法通过单元测试.我盯着它看了5个小时是徒劳的.有人可以帮我看看它有什么问题吗？

PS：我的代码中的getAllRelations()方法是将格式化的输入分离为字符串ArrayList的arraylists,例如,如果我有这样的格式化输入(我在我的测试用例中使用它无法通过)

String format = "John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson";

在每一行中,第一个人是第二个人的父母.
getAllRelations()方法将这个格式化的字符串拆分为arraylists,每个列表只包含每行中的两个名称字符串(在名称之前或之后没有空格)作为其元素.例如arraylist1将是一个包含“John”和“Mary Smith”的列表.

这是我的方法,我无法弄清楚什么是错的,我想用这种方法来检查两个人是否共享同一个祖先.

private boolean hasSameAncestor(String person1, String person2){
    ArrayList<ArrayList<String>> allRelations = allRelations();
    int i = 0;
    int j = 0;
    String name1 = person1;
    String name2 = person2;
    String parent1;
    String parent2;
    for(i = 0, parent1 = ""; i < allRelations.size(); i++){
        if(name1.equals(allRelations.get(i).get(1))){
            parent1 = allRelations.get(i).get(0);
            for(j = 0, name2 = person2, parent2 = ""; j < allRelations.size(); j++){
                if(name2.equals(allRelations.get(j).get(1))){
                    parent2 = allRelations.get(j).get(0);
                    if(parent2.equals(parent1)){
                        return true;
                    }
                    else{
                        name2 = parent2;
                        j = 0;
                    }
                }
            }
            name1 = parent1;
            i = 0;
        }
    }
    return false;
}

我无法通过的测试用例就是这样.

    @Test
    public void testHasSameAncestor()
    FamilyTree familyTree4 = new FamilyTree("John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson");
    assertEquals(true, format.hasSameAncestor("Max Jackson", "Robert Andrew"));
}

我无法弄清楚我的功能有什么问题,有人可以帮帮我吗？非常感谢你.

可以粘贴到eclipse以获得调试帮助的代码

package test;

import java.util.ArrayList;
import java.util.Arrays;


public class Test1 {

    String test;

    public Test1(String test){
        this.test = test;
    }


    private ArrayList<String> lineRelations(){
        int i;
        ArrayList<String> lineRelations = new ArrayList<String>();
        String[] lines = test.split("\n");
        for(i = 0; i < lines.length; i++){
            lineRelations.add(lines[i]);
        }
        return lineRelations;
    }

    private ArrayList<ArrayList<String>> allRelations(){
        int i;
        ArrayList<ArrayList<String>> allRelations = new ArrayList<ArrayList<String>>();
        ArrayList<String> lineRelations = lineRelations();
        for(i = 0; i < lineRelations.size(); i++){
            ArrayList<String> eachLine = new ArrayList<String>(Arrays.asList(lineRelations.get(i).split("\\s*,\\s*")));
            allRelations.add(eachLine);
        }
        return allRelations;
    }

    public boolean hasSameAncestor(String person1, String person2){
        ArrayList<ArrayList<String>> allRelations = allRelations();
        int i = 0;
        int j = 0;
        String name1 = person1;
        String name2 = person2;
        String parent1;
        String parent2;
        for(i = 0, parent1 = ""; i < allRelations.size(); i++){
            if(name1.equals(allRelations.get(i).get(1))){
                parent1 = allRelations.get(i).get(0);
                for(j = 0, name2 = person2, parent2 = ""; j < allRelations.size(); j++){
                    if(name2.equals(allRelations.get(j).get(1))){
                        parent2 = allRelations.get(j).get(0);
                        if(parent2.equals(parent1)){
                            return true;
                        }
                        else{
                            name2 = parent2;
                            j = 0;
                        }
                    }
                }
                name1 = parent1;
                i = 0;
            }
        }
        return false;
    }
}

测试用例

package test;
import static org.junit.Assert.*;
import test.Test1;

import org.junit.Test;


public class Test1Test {

    @Test
    public void testHasSameAncestor(){
        Test1 test1 = new Test1("John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson");
        assertEquals(true, test1.hasSameAncestor("Max Jackson", "Robert Andrew"));
    }
}

解决方法:

首先找到两个人的基本祖先,然后比较它们.

请检查一下 ：)

public boolean hasSameAncestor(String person1, String person2) {
        ArrayList<ArrayList<String>> allRelations = allRelations();
        int i = 0;
        String name1 = person1;
        String name2 = person2;
        String parent1;
        String parent2;

        //Find first person's ancestor
        for (i = 0, parent1 = ""; i < allRelations.size(); i++) {
            if (name1.equals(allRelations.get(i).get(1))) {
                parent1 = allRelations.get(i).get(0);
                name1 = parent1;
                i = -1; // because i will increase before start new loop
            }
        }

        //Find second person's ancestor
        for (i = 0, parent2 = ""; i < allRelations.size(); i++) {
            if (name2.equals(allRelations.get(i).get(1))) {
                parent2 = allRelations.get(i).get(0);
                name2 = parent2;
                i = -1;
            }
        }
        System.out.println(parent1);
        System.out.println(parent2);
        if (parent1.equals(parent2)) {
            return true;
        }
        return false;
    }

最好的祝愿.

内容总结

以上是互联网集市为您收集整理的java – 家谱祖先查找算法全部内容，希望文章能够帮你解决java – 家谱祖先查找算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---