Algorytm znajdowania przodków.

Odpowiedz Nowy wątek
2014-12-26 00:19
0

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.

Pozostało 580 znaków

2014-12-26 00:34
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.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 1x, ostatnio: Shalom, 2014-12-26 00:35
Tak z ciekawości, czy można tu wykorzystać lekko zmodyfikowane drzewko binarne? proszę o wyrozumiałość - deadparty211 2014-12-26 06:09
No jeśli sobie wczytasz dane wejściowe do drzewa to jasne że można. Wtedy po prostu możesz wypisać węzły drzewa począwszy od zadanego "korzenia". Ale będzie wolniej, bo musisz zbudować całe drzewo. Zresztą sama budowa drzewa będzie wyglądać bardzo podobnie do algorytmu opisanego powyżej. - Shalom 2014-12-26 12:20

Pozostało 580 znaków

2014-12-26 05:57
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?

To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2014-12-26 11:30
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

edytowany 2x, ostatnio: furious programming, 2014-12-26 19:36
Wstawiaj kod w znaczniki kolorujące składnię; - furious programming 2014-12-26 19:36

Pozostało 580 znaków

2014-12-26 12:28
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.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 2x, ostatnio: bogdans, 2014-12-26 13:22
Pokaż pozostałe 2 komentarze
WTF? Ale skąd niby pomysł że program ma sobie radzić z niepoprawnymi danymi? Jesteś autorem zadania czy co? :D Zresztą w takich spojowych problemach zwykle dane z założenia są poprawne... - Shalom 2014-12-26 12:56
A skąd pomysł, że to spojowy problem. Zapytałem autora, czy można założyć poprawność danych, nie odpowiedział. Poza tym, czy brak w danych jednego z rodziców oznacza niepoprawne dane? - bogdans 2014-12-26 13:26
Bo wygląda na typowo algorytmiczne zadanie jak dla mnie ;] Brak jednego z rodziców wykluczałby możliwość poczęcia, ale ja biologiem nie jestem to sie nie będę wymądrzał :P Zresztą implementacja autora generalnie jest dość słaba, copy-pastowa i woła o pomstę do nieba ;) - Shalom 2014-12-26 13:28
A niepokalane poczęcie? Nieunikniony (pamięć jest skończona) jest brak obu rodziców, a wtedy jeszcze trudniej o poczęcie. Autor wyraźnie pisze o Javie, sugeruje to raczej zadanie szkolno-uczelniane. - bogdans 2014-12-26 13:43
@bogdans ech klasyczny przykład mylenia pojęć. Lekcja religii na dziś: niepokalne poczęcie Maryi jest związane z tym kiedy Maryja (!) została poczęta i odnosi się do faktu że Maryja była bez grzechu pierworodnego. Nie ma to właściwie nic wspólnego z faktem że Maryja była matką mimo iż pozostawała dziewicą. - Shalom 2014-12-26 13:50

Pozostało 580 znaków

2014-12-26 12:30
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...


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 1x, ostatnio: Shalom, 2014-12-26 12:32
@Shalom, "uczłowieczanie" kodu jest ważne, ale poprawne działanie ważniejsze. Poza przykładami, które podałem, program nie radzi sobie z poprawnymi danymi. Wystarczy wprowadzić rodzeństwo. - bogdans 2014-12-26 12:37
o_O? A możesz podać przykład sensownych danych dla których to nie zadziała? Bo te które podałeś wyżej nie mają sensu biologicznie... - Shalom 2014-12-26 12:40

Pozostało 580 znaków

2014-12-26 12:51
0

Wystarczy wprowadzić rodzeństwo

 
String[][] table=  {{"Mother", "child"},
{"Ania","Tomek"}};
    String[][] table2= {{"Father", "child"},
                        {"Tomek","Pat"},
                        {"Artur","Tomek"},
                        {"Tomek","Jasiu"}
                        };
    String a = "Tomek";

To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2014-12-26 12:58
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"...


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 1x, ostatnio: Shalom, 2014-12-26 12:59

Pozostało 580 znaków

2014-12-26 13:28
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ł.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0