Mindestanzahl der Schritte zum Erreichen des Ziels?

Ich lerne Datenstrukturen von wenigen Tagen. Nehmen wir an, wir haben eine Datenstruktur, die aus Knotenschichten aufgebaut ist. Alle Layer beginnen mit dem Knoten 'start' und enden mit einem Nullwert anstelle des letzten Knotens. Jeder Knoten hat einen "Wert", einen "Foll" -Zeiger auf den nächsten Knoten und einen "Abwärts" -Zeiger auf den nächsten Knoten in der gleichen Schicht. Auf jeder Ebene sind die Werte in aufsteigender Reihenfolge sortiert.Mindestanzahl der Schritte zum Erreichen des Ziels?

Beispiel:

S ---- 9 ------------------------------- -------> NULL
```
 | 
```
S ----- 9 --------- 27 --------- 51 ------ --------> NULL
```
 |  |  | 
```
S ----- 9 --- 23 --- 27--29 --- 51 ---- 53 ------ -> NULL

Datenstruktur für Knoten:

`  Class Node { 
        int value; 
        Node foll; 
         Node down; 
        }     `

Schreiben Sie eine Funktion FindNode, die einen Startknoten Kopf und einen Suchwert Wert erhalten und wird die minimale Anzahl von Sprüngen zurück, die notwendig sind, um zu entweder den Knoten mit diesem Wert erreichen oder feststellen, dass er in der Datenstruktur nicht existiert.

Eingabe: Anzahl der Schichten, gefolgt von einer Liste neuer Knoten für jede Schicht und schließlich die Nummer, die gefunden werden soll. Alle Werte sind ganze Zahlen größer als Null.

4 

7 

27 51 

24 80 

4 32 54 69 82 

54

werden in der Datenstruktur zur Folge haben oben und Wert beschrieben zu finden ist 54

Ausgabe

Kann jemand bitte sagen Sie mir, was in Java folgende Funktion werden sollte?

static int findNode(Node start, int value) { }

Quelle

2017-02-16 SolakiR

ein kurzer Hinweis: Rekursion –

Visualisierung der verbundenen Schichten als Baum kann helfen. Der erste Knoten der ersten Schicht ist der Stamm mit linken und rechten Unterbäumen. Jede Wurzel eines Unterbaums hat ihre eigenen linken und rechten Unterbäume. Typischerweise können mit einfachen Bäumen, die alle Knoten abdecken, die Baumknoten, wenn sie nicht geordnet sind, zuerst in der Breite oder zuerst in der Tiefe ausgeführt werden und benötigen im schlimmsten Fall etwa O (n) Zeit. –

Der einfachste Weg, um dieses Problem zu nähern mit einer rekursiven Lösung wäre. Stellen Sie sich dieses Problem vor, wenn Sie bei einem Knoten beginnen und dann in jede mögliche Richtung expandieren, bis Sie den Knoten erreichen, nach dem Sie suchen.

Das erste, was Sie in einer rekursiven Funktion benötigen, ist ein Basisfall, oder was tun, wenn es nicht weiter gehen kann. In unserem Fall, wenn wir das Ende erreichen, ohne den Knoten zu finden, den wir wollen, könnten wir brechen oder 1 zurückgeben, wenn wir den Knoten finden, den wir wollen.

Der nächste Teil ist der rekursive Aufruf. Wenn wir also nicht gefunden haben, was wir wollen, und wir mehr Plätze haben, können wir weiter zu den umliegenden Knoten gehen und bei jedem Anruf 1 zu unserer Tiefe hinzufügen.

In Code, wäre dies etwas Ähnliches wie diesen:

static int findNode(Node start, int value){ 
    if(start.value == value) 
     return 1; 
    else if(Node == null) 
     break; 

    return Math.min(findNode(start.foll) + 1, findNode(start.down) + 1); 
}

Sie könnten mit einem anderen Weg, um diese ein wenig und Austausch Pause ändern müssen stoppen, aber hoffentlich geben Ihnen die Idee.

Quelle

2017-02-16 05:50:03 ejmejm

Ein rekursiver Ansatz, der "in jede mögliche Richtung expandiert", wenn ich Sie richtig verstehe, muss sich vor redundanten rekursiven Aufrufen schützen. Ohne sicherzustellen, dass zwei Knoten nicht zweimal abgedeckt werden, wäre eine rekursive Tiefensuche schneller und benötigt auch weniger Speicherplatz. –

@AdrianM. Bitte posten Sie Ihre Lösung wenn möglich. – SolakiR

@ejmejm Ich schätze deine Hilfe sehr. Bitte posten Sie die genaue Lösung wenn möglich. Außerdem sollte der zweite Parameter in findNode von return Math.min sein (findNode (start.foll) + 1, findNode (start.down) + 1); ? – SolakiR

Mindestanzahl der Schritte zum Erreichen des Ziels?

Antwort

Verwandte Themen