Schleifen geschlossen

[marushin]

Hi Leute,

haben an der Uni grade Schleifen und deren Terminierung.
Folgender Code ist eine Zusatzaufgabe, die wunderschöne 100 Extrapunkte gibt
Allerdings hat der Prof schon angedeutet das es tendenziell gegen unmöglich ist die zu lösen.
Da mir die Punkte aber sehr gut tun würden und hier so viel Kompetenz rumschreibt dachte ich mir vllt hat ja hier jemand ne Idee oder selbe Aufgabe schonmal gehabt?

{x > 0}
while (x != 1) {
if (x%2 == 0) {
x = x / 2;
}
else {
x = 3 * x + 1;
}
}
{x=1}

Für alle Ideen bin ich sehr dankbar.

M.f.G.

 

[sambo]

Erstmal 3 Fragen:

{x > 0} und {x=1} was sind das? Bedingungen, Kommentare ...

Ist dies Pseudocode oder kann man ihn einer Sprache zuordnen?

Was ist überhaupt die Frage?

 

[$chmiddi]

Moin,

das sieht mir sehr nach PHP aus.

Eine Idee von mir wäre erstmal das While rauszunehmen, dann ist es schonmal keine Endlosschleife mehr, aber wie man das dann so lösen kann, das man am ende x=1 hat, kp
Wenn das überhaupt die Fragestellung ist...

Gruß,
$chmiddi

 

[Stefan2k]

Sieht für mich auch aus wie Java oder auch C, die Syntax ist hier ähnlich. Ist aber letzendich egal, wichtig wäre zu wissen wie die genaue Aufgabenstellung lautet und was das Ziel sein soll. PHP ist es wohl eher nicht, da hier Variablen zwingend mit dem Vorzeichen $ gekennzeichnet werden müssen.

Wenn es eine Schleife bleiben soll, dann kann man wohl kaum einfach das While entfernen, man muss also eher dafür sorgen dass die Bedinung von x nicht mehr ungleich 1 ist.

Ich vermute mal, dass x=1 sowie x>0 an die richtigen stellen eingebaut werden sollen, x>0 ist ein vergleich und x=1 eine Zuweisung von dem Wert 1 zu x.

 

[Yoda2003]

Ich glaube die kompetentesten Coder findest du hier:
Coding - Freesoft-Board

 

[Falves]

Lulz. Das ist das 3n+1 Problem. Ganz einfach.

Du hast einen AnfangsWert, zum Beispiel 33. Wenn diese Zahl ungerade ist, wird sie mal 3 genommen und 1 addiert. Ist sie allerdings gerade, wird sie durch 2 geteilt. Dies passiert solange, bis die Zahl 1 ist, was sie laut der Theorie immer wird, kommt bloss auf die Anzahl der Durchläufe an.

Kurzer Hinweis: x%2 gibt den Rest aus, also ob sie gerade/ungerade ist.

Beispiel:
x=33
ungerade, daher *3+1=100.
100/2=50
50/2=25
25*3+1=76
76/2=38
38/2=19
19*3+1=58
58/2=29
29*3+1=88
88/2=44
44/2=22
22/2=11
11*3+1=34
34/2=17
17*3+1=52
52/2=26
26/2=13
13*3+1=40
40/2=20
20/2=10
10/2=5
5*2+1=16 16/2=8
8/2=4
4/2=2
2/2=1

Siehe auch hier.

Aber was war jetzt genau die Aufgabe?

 

[marushin]

Oh entschuldigt, war heute morgen nicht so auf der höhe

Die Aufgabe lautet:

Zeigen Sie, dass die folgende Schleife terminiert

Als "Sprache" würde ich Schleife/LOOP sagen, da das gerade unser Thema ist.
Danke euch schonmal, werde mir die Links von Falves mal genauer angucken.

Falls noch jemand was interessantes hat, gerne her damit

 

[KasperIII]

Hi, also wenn du zeigen sollst, dass die sdchleife terminiert sollst du ja (so wie ich das verstanden habe), zeigen, dass x=1 nach einer endlichen Anzahl von durchläufen ist.

Wenn das die Aufgabe ist, kannst du sie nahezu vergessen, da diese Folge auch heute noch ein "Rätsel" für Mathematiker darstellt. Hier noch ein Zitat von nem Blatt, bei der die aufgabe kam, diese Folge zu Programieren:

Bemerkung: Diese Folge hat L. Collatz im Jahr 1937 zuerst studiert und die Vermutung aufgestellt, dass für jeden Startwert die Folge die Zahl 1 erreicht. Dies ist immernoch ein offenes mathematisches Problem.

Gruß

KasperIII

 

[Stefan2k]

Die Schleife terminiert, sobald x den Wert 1 bekommt. Du initialisierst die Variable x mit einem Startwert (wie schon gesagt wrude) z.b. 15, die Schleife läuft durch und prüft auf die Bedingung "x Modulo 2 = 0", wenn diese Bedingung von x dann wird x durch 2 dividiert. Wenn nicht dann wird 3 mit x multipliziert und dann noch 1 addiert.

So durchläuft x bei dem Startwert von 15 die Werte "46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1", da dann die 1 erreicht wird ist die Schleife terminiert.

Du musst also als Erklärung für die Terminierung liefern, dass die Schleife bei dem Wert von 1 terminiert wird. Der Wert 1 wird "mit hoher Wahrscheinlichkeit" immer erreicht, wobei es sein könnte, dass das nicht der Fall ist, da nicht garantiert werden kann dass jede Zahl wirklich mit 1 endet (das ist noch unbewiesen). Jedoch mit jeder Zahl mit der es bisher probiert wurde, gab kam man immer auf 1.

Also noch mal grob zusammen gefasst:
-Man gibt x eine Zahl als Startwert
-Die Schleife läuft
-Ist die Zahl gerade, wird sie durch 2 geteilt.
-Ist die Zahl ungerade wird sie mal 3 genommen und 1 dazu gezählt.
-Erreicht x irgendwann 1, dann endet die Schleife

Der Grund warum bisher alle Zahlen irgendwann bei 1 enden mag zwar ein Rätsel sein, jedoch ist es kein Rätsel warum die Schleife dann beendet wird.

 

[Falves]

Es ist ein ungelöstes Matheproblem, und wenn du das schaffst, bekommst du nicht nur 100 Punkte, sondern genug Geld der Mathematiker

Also vergiss das lieber

 

[McKilroy]

'Erledigt und closed