首页 / 算法 / java – 家谱祖先查找算法
java – 家谱祖先查找算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – 家谱祖先查找算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4338字,纯文字阅读大概需要7分钟。
内容图文
![java – 家谱祖先查找算法](/upload/InfoBanner/zyjiaocheng/816/9d3c798668e34e44bcb21928966304c8.jpg)
我的方法无法通过单元测试.我盯着它看了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 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。