✔ Hilfe bei einem Algorithmus

[zunamy]

Hallo, ich hoffe ich poste hier ins richtige Forum. Hab ein Problem bei einer Übung

Eine einfach verkette Liste ist eine dynamische Datenstruktur, welche eine im vorhinein unbestimmte Anzahl an Elementen speichert. Jedes Element enthält dabei einen Zeiger auf das nächste Element (next), der Zeiger des letzen Elements zeigt auf den Wert null. Folgende Grafik veranschaulicht eine einfach verkette Liste, welche als Elemente int-Werte enthält:

Uploaded with ImageShack.us

Folgende Knotendefinition können Sie für dieses Beispiel benutzen:

type Node = {
int value
Node next
}

Der folgende rekursive Algorithmus printReversed(?Node n) gibt eine Liste (wobei n der Anfangsknoten ist) verkehrt herum aus (für obige Liste würde also die Zahlenfolge 5 4 3 2 1 ausgegeben werden).
printReversed(?Node n) {
if(n != null) {
printReversed(?n.next)
write(?n.value)
}
}
a) Bauen Sie den oben angegebenen Algorithmus printReversed(?Node n) so um, dass nur die letzte Hälfte der Liste ausgegeben wird. Sollte die Länge der Liste ungerade sein, so soll das mittlere Element mitausgegeben werden. Für das obige Beispiel sollte die Ausgabe folgendermaßen aussehen: 5 4 3
Hinweise: Sie dürfen die Aufrufschnittstelle des Algorithmus verändern (also z.B. einen Rückgabewert oder zusätzliche Parameter einführen). Allerdings soll Ihr Algorithmus die Listenelemente nicht vor dem Ausgeben abzählen, auch ist die Länge der Liste beim Aufruf des Algorithmus nicht bekannt (die Länge der Liste kann also nicht als Parameter übergeben werden)

Kann mir da jemand helfen?

Mein Vorschlag:

printReversed(?Node n ?int i ?int last){
if(n!=null){
printReversed(?n.next ?i+1 ?last)
if(i?last/2){
write(?n.next)
}
i=i-1
}else{
last=i
}
}

Hätt jemand eine Idee wie man das ganze mit einem endrekursiven Algorithmus lösen kann ?

thx für Tipps und Greetz

 

[NeonXT]

Nabend

Na dann will ich dir mal versuchen zu helfen.
Da du ja pseudocode gepostet hast aber sagst es soll in java sein habe ich dir mal was in java gebaut, hoffe es hilft. Wenn sich noch fragen ergeben sollten frag ruhig.

public class Node
{
    private int value;
    private Node next;
    
    public Node(int value,Node next)
    {
        this.value = value;
        this.next = next;
    }

    public static int printReserved(Node n,int position)
    {
        if(n != null)
        {
            int wert = Node.printReserved(n.next,position+1);
            if(wert>0)
                System.out.println(n.value);

            return wert-1;
        }
        else
        {
            if(position%2 == 0)
            {
                return (position/2);
            }
            else
            {
                return (position/2+1);
            }
        }
    }

    public static void main(String argv[])
    {
        Node start = new Node(1,new Node(2,new Node(3,new Node(4,new Node(5,null)))));

        Node.printReserved(start,0);

    }
}

 

[Maik]

Wenn sich noch fragen ergeben sollten frag ruhig.

Und bitte unter Beachtung unserer Netiquette bzgl. der erwünschten Groß- und Kleinschreibung - vielen Dank!

mfg Maik

 

[zunamy]

Da du ja Pseudocode gepostet hast aber sagst es soll in java sein habe ich dir mal was in java gebaut, hoffe es hilft.

Naja wir benutzen son Pseudocode namens JANA (Java-based Abstract Notation for Algorithms), hab aber nichts passendes gefunden. Und da ich in Java das Grundlegende kenn, is kein Problem für mich das Wesentliche rauszulesen.

Vielen dank für deinen Vorschlag, werd mich dann mal damit befassen

 

[NeonXT]

@ Maik:
Zu meiner Rechtschreibung in der Antwort gebe ich dir 100% Recht, war aber schon spät und wollte zunamy schnell helfen.

@zunamy:
Also von JANA habe ich noch nichts gehört, man lernt halt nie aus.
Eine Frage hätte ich noch, wann musst du den die Aufgabe abgeben? Es gäbe da nähmlich noch eine kleine Änderung die ich vornehmen würde, bzw würde man das ganze Vorhaben deines Profs anders Angehen. JAVA LinkedList zur kannste dir ja mal ansehen.
Aber euer Prof möchte ja das ihr die Struktur versteht. Deswegen müssen viele viele Studenten die Struktur immer wieder neu Erfinden:suspekt:

 

[Maik]

@ Maik:
Zu meiner Rechtschreibung in der Antwort gebe ich dir 100% Recht, war aber schon spät und wollte zunamy schnell helfen.

Meine Bitte war überhaupt nicht an dich gerichtet, denn wegen einem oder zwei kleingeschriebenen Wörtern melde ich mich gewiss nicht zu Wort

mfg Maik

 

[NeonXT]

Meine Bitte war überhaupt nicht an dich gerichtet, denn wegen einem oder zwei kleingeschriebenen Wörtern melde ich mich gewiss nicht zu Wort

mfg Maik

Aber so ganz falsch wars ja nicht hatte ja ein paar Fehler im Text, von daher haste mit einer Bitte 2 Fehler berichtigt. Habs dir, auch wenn es nicht an mich adressiert war, nicht böse genommen

 

[zunamy]

Ja das ganze soll auch dann entrekursiviert werden laut Schema F und da is dein Algorithmus genau passend

Und wegen meiner Groß/Kleinschreibzung entschuldigt bitte, habs da manchmal nicht so genau

Mach mich jedenfalls jetzt dran den zu entrekursivieren, vielen Dank Rancid

Ach ja, hätt mien Algorithmus eigentlich gepasst? Wärs so auch gegeangen?

 

[NeonXT]

Ach ja, hätt mien Algorithmus eigentlich gepasst? Wärs so auch gegeangen?

Würde da Pauschal mal Nein sagen, denn erstents verstehe ich nicht so ganz den Sinn der Variable last, denn eigentlich brauchste die nicht, denn in einer Liste ist der letzte Wert welcher der auf ein NULL zeigt.
Richtig war das du bei jemdem Aufrufen der Funktion eine Variable übergibst die bei jedem Aufruf Inkrementiert wird.
Ein weiteres Problem wäre die Ausgabelänge den da die Variable die Inkrementiert wird int sein sollte und und 5/2 als int 2 ergibt, stände da nur 5 4 und die 3 würde wegfalllen darum auch bei mir die Fallunterscheidung,ob durch 2 Ohne rest Teilbar, mit dem Modulo.
Und irgendwie fehlen dir auch die Rückgabewerte der von PrintReserved, mit welchem man steuert wie weit ausgegeben wird. Kann natürlich auch sein da ich JANA nicht kenne das man diesen nicht mit Angeben muss. Habe mich auch mal im Bezug auf JANA schlau gemacht wird wohl nicht viel verwenden, eigentlich nur in Linz ander Uni als Sprache in den Einführungsveranstaltungen.

Freu mich aber das es dir hilft und das dein Prof die Lösung auch mag

PS: Würde dir empfehlen solche Algorithmen immer mal richtig zu Programmieren, kann hilfreich sein um sie besser zu Verstehen und auch mal Zwischenausgaben zu machen.

 

[zunamy]

Und wieder mal fehlt mir der richtige Ansatz

Würfel mit Gedächtnis

Bei einem herkömmlichen Spielwürfel von 1 bis 6 ist die Wahrscheinlichkeit für das Auftreten einer Seite immer gleich 1/6, egal welche Würfe bisher ausgeführt wurden.
Der allgemeine Volksglaube geht dennoch davon aus, dass bei einem (unmanipulierten) Würfel mit den Augenzahlen von 1 bis 6 die Historie der bisher gewürfelten Augenzahl das aktuelle Ergebnis beeinflusst.
Wird etwa längere Zeit die Würfelseite mit der Augenzahl 6 nicht geworfen, ist man versucht anzunehmen, dass diese Augenzahl beim nächsten Wurf mit einer höheren Wahrscheinlichkeit auftritt als andere Augenzahlen.

Ihre Aufgabe ist es nun, einen Würfelzahlengenerator mit Gedächtnis zu entwerfen, der die Wahrscheinlichkeiten der Augenzahlen nach folgendem Schema verändert:
- Zu Beginn hat jede Augenzahl die Wahrscheinlichkeit 1/6.
- Wird die Augenzahl x geworfen, sinkt ihre Wahrscheinlichkeit für den Folgewurf auf die Hälfte der aktuellen Wahrscheinlichkeit.
- Die Wahrscheinlichkeiten aller anderen Augenzahlen werden entsprechend erhöht, wobei
- die Summe der Wahrscheinlichkeiten zu jedem Zeitpunkt 1 sein muss.

a) Beschreiben Sie die vollständige Berechnungsvorschrift und zeigen Sie in einer Tabelle, wie sich die Wahrscheinlichkeiten verändern, wenn hintereinander die Zahlenfolge 1, 2, 3, 4, 5, 6 gewürfelt wird.

b) Implementeren Sie den Algorithmus int rollTheDice() in Jana, der die Methode implementiert. Überlegen Sie sich genau, welche Variablen Sie benötigen, und wie Sie die veränderlichen Wahrscheinlichkeiten in die Erzeugung der gewürfelten Augenzahlen einbeziehen können. Es stehen Ihnen die beiden in der Vorlesung vorgestellten Zufallszahlengeneratoren int smallRand (liefert eine ganzzahlige Zufallszahl im Intervall [0,n-1]) und float fRand() (liefert eine Zufallszahl aus dem Intervall [0,1[) zur Verfügung.

also die Berechnung sieht glaub ich so aus

Wird eine Zahl gewürfelt, sinkt die Wahrscheinlichkeit dieser Zahl noch einmal gewürfelt zu werden um die Hälfte (zB 1?6 ? 1?12). Die andere Hälfte der Wahrscheinlichkeit wird auf die übrigen Zahlen gleichmäßig verteilt (zB 1?6 ?1?6+(1?12)/5=11?60).

aber wie ich die Wahrscheinlichkeit auf die Random-Zahlen anwende ist mir bis jetzt ein Rätsel....

Vielleich hat jemand eine Idee