Witam
Mam taki problem z algorytmem w Javie. Mam dwie tabele jedna tabela ma dwie kolumny 1matka 2dziecko. Druga tabela ma dwie kolumny 1ojciec 2dziecko. Teraz mam znaleźć wszystkich przodków i potomków danej osoby. Nie za bardzo rozumiem jak to mogę rozpisać, żeby znalazło mi wszystkich przodków lub potomków. Z jedną tabelą nie widzę problemu napisać taki algorytm, ale problem jest jak w przypadku dwóch. Mógłby mi ktoś coś podpowiedzieć w sprawie tego algorytmu?
Słyszałem, że najlepiej jest to zrobić za pomocą 3 tabeli, która będzie łączyć pierwsze dwie.
0
0
A ja zupełnie nie rozumiem problemu. Napisz sobie funkcje która dla danej osoby zwraca parę (Ojciec, Matka) korzystając z obu tablic. Teraz z użyciem tej funkcji twój problem jest zupełnie trywialny. Tworzysz sobie listę "do sprawdzenia" oraz zbiór znalezionych przodków. Do listy wrzucasz to twoje pierwsze dziecko dla którego leci algorytm. I teraz masz:
while lista nie jest pusta:
pobierz pierwszy element z listy
wyszukaj ojca i matkę dla tego elementu
jeśli istnieją:
wrzuć ojca i matkę do listy
wrzuć ojca i matkę do zbioru przodków
I tyle. W ten sposób w pierwszym obiegu pętli znajdziesz rodziców. W drugim obiegu znajdziesz rodziców ojca, w trzecim rodziców matki i tak dalej. A algorytm skończy sie kiedy dla danych osób nie będziesz mógł znaleźć już przodków i lista powoli się wyludni bo sprawdzisz wszystkich.
1
Co wiadomo na temat poprawności (spójności) danych w tych tabelach.
- czy zawsze są znani oboje rodzice?
- czy może się zdarzyć wielu rodziców, np. dwóch ojców i trzy matki?
- czy mogą wystąpić zapętlenia,
10 jest ojcem dla 9,
9 jest ojcem dla 8,
...
2 jest ojcem dla 1,
1 jest ojcem dla 10?
0
dzięki wielkie, program działa, ale mam pytanie czy jest możliwe skrócenie takiego kodu?
import java.util.ArrayList;
public class task
{
ArrayList<String> chart = new ArrayList<String>();
ArrayList<String> chart2 = new ArrayList<String>();
void recursion(String a,String table[][], String table2[][]){
for(int i=1;i<table.length;i++){
if(table[i][1]==a ){
chart.add(table[i][0]);
}
if(table2[i][1]==a){
chart.add(table2[i][0]);
}
}
}
void recursion2(String a,String table[][], String table2[][]){
for(int i=1;i<table.length;i++){
if(table[i][0]==a){
chart2.add(table[i][1]);
}
if(table2[i][0]==a){
chart2.add(table2[i][1]);
}
}
}
static void list(ArrayList<String> list){
for (String s: list){
System.out.print(s + " ");
}
}
public static void main(String[] args)
{
String[][] table= {{"Mother", "child"},
{"Krystyna","Tomek"},
{"Wiesława","Bronek"},
{"Maria","Artur"},
{"Pat","Genowefa"},
{"Genowefa","Katarzyna"},
};
String[][] table2= {{"Father", "child"},
{"Tomek","Pat"},
{"Artur","Tomek"},
{"Pat","Miranda"},
{"Bronek","Krystyna"},
{"Patrycja","Anka"},
};
String a = "Tomek";
String z = a;
task tusk = new task();
tusk.recursion(a,table,table2);
tusk.recursion2(a,table, table2);
ArrayList<String> przodkowie = new ArrayList<String>();
ArrayList<String> potomkowie = new ArrayList<String>();
while(tusk.chart.isEmpty() == false){
a = tusk.chart.get(0);
przodkowie.add(tusk.chart.get(0));
tusk.chart.remove(0);
tusk.recursion(a,table,table2);
}
while(tusk.chart2.isEmpty() == false){
a = tusk.chart2.get(0);
potomkowie.add(tusk.chart2.get(0));
tusk.chart2.remove(0);
tusk.recursion2(a,table,table2);
}
System.out.print("Przodkowie dla " + z + " to: ");
list(przodkowie);
System.out.println();
System.out.print("Potomkowie dla " + z + " to: ");
list(potomkowie);
}
}
dodanie znacznika <code class="java"> - @furious programming
0
Chyba za wcześnie się cieszysz. Dla tablic
String[][] table= {{"Mother", "child"}};
String[][] table2= {{"Father", "child"},
{"Tomek","Pat"},
{"Artur","Tomek"},
{"Pat","Miranda"},
{"Bronek","Krystyna"},
{"Patrycja","Anka"},
};
dowiedziałem się, że Tomek nie ma potomków i przodków. A ma ich.
A dla danych
String[][] table= {{"Mother", "child"},
{"Ania","Zosia"},
{"Zosia","Ania"}};
String[][] table2= {{"Father", "child"},
{"Tomek","Pat"},
{"Artur","Tomek"},
{"Pat","Miranda"},
{"Bronek","Krystyna"},
{"Patrycja","Anka"},
};
String a = "Ania";
program się wywalił z java.lang.OutOfMemoryError: Java heap space
Dziwne jest też to, że teraz znajduje potomka i przodka dla Tomka.
0
@tsuisou jasne że jest. Gdybyś napisał do dokładnie tak jak opisałem, to zajęłoby niewiele więcej niż mój pseudokod. Przy okazji: naucz się pisać kod DLA LUDZI a nie dla maszyn. Za nazwanie funkcji recursion i recursion2 powinieneś dostać zakaz używania komputera. Pokaż ten kod swojej mamie albo siostrze i spytaj czy wiedzą co robi. Jeśli nie wiedzą, to znaczy że jest źle napisany. Kod mógł wyglądać tak:
Deque<String> peopleToCheck = new LinkedList<String>();
Set<String> ancestors = new LinkedHashSet<String>();
peopleToCheck.add("Tomek");
while(!peopleToCheck.empty()){
String nextPerson = peopleToCheck.pop();
Parents parents = getParents(nextPerson);
peopleToCheck.push(parents.mother);
peopleToCheck.push(parents.father);
ancestors.add(parents.mother);
ancestors.add(parents.father);
}
Poza tym zamiast tych tablic stringów to ja bym tam zrobił Map<String, String> i wtedy nie trzeba żadnych śmiesznych pętli do szukania rodziców, tylko zwykłe mapa.get(dziecko) i juz masz rodzica...
0
Wystarczy wprowadzić rodzeństwo
String[][] table= {{"Mother", "child"},
{"Ania","Tomek"}};
String[][] table2= {{"Father", "child"},
{"Tomek","Pat"},
{"Artur","Tomek"},
{"Tomek","Jasiu"}
};
String a = "Tomek";
0
No i czemu algorytm dla tych danych wg ciebie miałby nie zadziałać? I nie pytam o tą śmieszną implementację, tylko o tą "moją". Bo ja nie widzę gdzie jest wg ciebie problem. Tylko błagam bez idiotyzmów w stylu "a co jak mamy dwie osoby o tych samych imionach" albo "a co jak mamy kazirodztwo"...
0
Nigdzie nie wypowiadałem się na temat Twojej wersji, pisałem o programie @tsuisou. Nie miałem siły go analizować, więc nie wiem dlaczego miałby nie zadziałać. Po prostu go uruchomiłem i nie zadziałał.