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:

http://img16.imageshack.us/img16/110...rvasivejku.png

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

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.

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

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);       } }

Zitat von NeonXT

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

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

@ 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

Zitat von NeonXT

@ 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

Zitat von Maik

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

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?

Zitat von zunamy

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.

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(n) (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

Hi

Die Berechnung der Wahrscheinlichkeiten ist soweit Richtig meiner Meinung nach zur Berechnung was Gewürfelt wird hätte ich auch eine Ideee muss dazu nur wissen ob

float fRand() (liefert eine Zufallszahl aus dem Intervall [0,1[) zur Verfügung.

stimmt oder ob du dich verschriebene hast und Intervall [0,1] da stehen sollte?

MFG NeonXT


PS: War die Lösung von der vorherigen aufgaben den richtig für den Prof

Nein ist schon richtig so, also 0<n<=1

Ich würd ja die jew. Wahrscheinlichkeiten in ein Array speichern und immer neu berechnen, aber wie das ganze auf den Würfel anwenden...?

Also meine Idee wäre du speicherst wie gesagt in ein Array mit der größe 6 die jeweiligen Prozentsätze für die Zahlen.

Daraus sollte sich dann nach deinem Beispiel so etwas ergeben, nehme mal dein Beispiel oben aus der rechneung nach einmal Würfeln in diesem Beispiel nehme ich mal die 4 die gewürfelt wurde.

Soll nur verdeutlichen was in dem Array steht
prozentwerte[0] = 0,1833333 //11/60
prozentwerte[1] = 0,1833333 //11/60
prozentwerte[2] = 0,1833333 //11/60
prozentwerte[3] = 0,0833333 //1/12
prozentwerte[4] = 0,1833333 //11/60
prozentwerte[5] = 0,1833333 //11/60

So wenn man die ganzen werte nun addiert bekommt man als Ergebnis 1,0.

Und jetzt kommt meine Idee:
Lass dir von fRand() eine Zahl geben.
Jetzt guckst du wo sich die Zahl befindet in dem du das array durchläufst.

Code :

1 2 3 4 5 6 7 8 9 10 11 12

int gewürfelteZahl = 0; int zaehler = 0; float dezimalwert = 0; float zufallsZahl = fRand(); do {     dezimalwert += prozentwerte[zaehler];     if(zufallsZahl<=dezimalwert)          gewürfeltezahl = zaehler+1;       zaehler++; }while(gewürfelteZahl ==0)

und hiernach musste wieder die Prozentwerte im Array ändern da man erst Würfelt und dann sich die Wahrscheinlich keiten ändern da die Veränderung der Wahrscheinlich keit des Würfelergebnisses abhängig ist. Hoffe das dir das ein bisschen hilft.

Es gibt auch noch die Möglichkeit mit Prozentwerten zu rechnen aber mit einem hohen 10er faktor also nicht 0,1833333 sondern 1833333 dann muss halt nur die andere Funktion benutzt werden.

Danke wieder mal für deine schnelle Antwort

Zitat von NeonXT

Code :

1 2 3 4 5 6 7 8 9 10 11 12

int gewürfelteZahl = 0; int zaehler = 0; float dezimalwert = 0; float zufallsZahl = fRand(); do {     dezimalwert += prozentwerte[zaehler];     if(zufallsZahl<=dezimalwert)          gewürfeltezahl = zaehler+1;       zaehler++; }while(gewürfelteZahl ==0)

Hmm das versteh ich nicht so ganz. Wenn jetzt beim ersten "Wurf" die Random-Zahl eine Zahl grösser 1/6 ist, dann geh ich doch gleich wieder aus der Schleife raus mit gewürfelteZahl=0 ...

Außerdem ist mir auch nicht klar wie hier die Wahrscheinlichkeiten Einfluss aufs Würfeln haben...

Zitat von zunamy

Danke wieder mal für deine schnelle Antwort



Hmm das versteh ich nicht so ganz. Wenn jetzt beim ersten "Wurf" die Random-Zahl eine Zahl grösser 1/6 ist, dann geh ich doch gleich wieder aus der Schleife raus mit gewürfelteZahl=0 ...

Außerdem ist mir auch nicht klar wie hier die Wahrscheinlichkeiten Einfluss aufs Würfeln haben...

Also der Quellcode stellt nur einen Wurf da gewürfelteZahl ist immer 0 außer die ZufallsZahl ist kleiner gleich dem Nächsten Definitionsbereich, sollte die Zeichnung erklären.

Die Zeichnung im Anhang sollte dir auch erklären was der Code mit der Wahrscheinlichkeit haben soll.

Es zeigt die Werte nach einmal Würfel einer 4, wobei der Balken für die 4 nun kleiner ist und somit auch ein kleinerer Bereich bzw WerteIntervall existiert, also auch eine kleinere chance eine 4 zu Würfeln.
.
Hoffe das dir diese Zugabe ein wenig mehr hilft meinen Ansatz zu verstehen.

Wenn sich noch fragen ergeben sollten dann wie immer einfach fragen .