C#: Problem mit der Schleife in der Primfaktorzerlegung?
Hallo zusammen,
ich programmiere gerade mit ASP.NET eine Anwendung, die eine Primfaktorzerlegung durchführt. Um ASP:NET-Anwendungen zu erstellen, wird eine .NET-Programmiersprache benötigt. In meinem Fall ist es C#.
Meine Frage:
Bei manchen Zahlen hört die Schleife nicht auf zu rechnen. In meinem Fall ist immer dann, wenn ich die Zahl 2, 4 8, 9, 16, ... eingebe. Bei den anderen Zahlen klappt die Zerlegung.
Es wäre nett, wenn sich jemand die Schleife anschauen und mir sagen könnte, was ich ändern muss.
Danke im Voraus.
Luca
@page
@{
var zahl = 0;
int teiler = 1;
if (Request.Method == "POST")
{
zahl = Convert.ToInt32(Request.Form["zahl"]);
}
}
<html>
<head>
<meta charset="utf-8" />
<title>Primfakorzerlegung</title>
</head>
<body>
<div style="font-family: Courier">
<h1>Primfaktorzerlegung</h1>
<form action="" method="POST">
Zahl: <input name= "zahl">
<p>
<br>
<input type="submit" value="Primfaktorzerlegung">
</form>
@if (Request.Method == "POST")
{
<nobr>@zahl = </nobr>
}
@{ Console.Write(zahl + " = "); }
@{
do
{
teiler++;
while (zahl % teiler == 0)
{
zahl = zahl / teiler;
<nobr>@teiler * </nobr>
Console.Write((teiler) + "*");
}
}
while ((zahl/teiler != 1) && (zahl%teiler != 0));
}
@{ Console.WriteLine(zahl); }
@if (Request.Method == "POST")
{
@zahl
}
</body>
</html>
2 Antworten
Was soll diese Zeile machen:
while ( (zahl/teiler != 1) && (zahl%teiler != 0));
... die hat keinen Body und macht nichts, d.h. wenn die Bedingung erfüllt ist, bleibt sie auch erfüllt, und du hast eine Endlosschleife.
Ah, sorry, verlesen - do... while. Ja, das kannst du machen.
Aber mal zur Zahl 2...
Du teilst die 2 erst durch teiler (mit dem Wert 2), dann ist zahl danach auf dem Wert 1.
Die innere While-Schleife terminiert dann, weil der Rest von 1 (mod 2) nicht Null ist.
Die äußere do..while-Schleife terminiert nicht, weil zahl/teiler ungleich 1 ist (in Integer-Arithmetik ist 1/2=0), und zahl%teiler is wie oben 1, was nicht Null ist. Damit ist diese Bedingung für teiler=2 erfüllt, und dasselbe gilt auch für alle größeren Werte von teiler.
Wenn du da noch "&& (teiler < zahl)" in die Abbruchbedingung schreibst, sollte das funktionieren. Ist nicht schön und nicht optimal, was die Laufzeit angeht, tut aber.
Hat geklappt, vielen Dank.
Ja, muss mir nochmal die gesamte Schleife anschauen und sie optimieren, so dass die Laufzeit kürzer wird.
Gruß Luca
Beachte im Übrigen, dass in deinem HTML-Dokument mehrere Fehler enthalten sind.
1) Der Doctype fehlt.
<!doctype html>
2) Das action-Attribut darf keinen leeren Wert haben. Wenn du es nicht brauchst / es auf dieselbe URL verweisen soll, lass es komplett weg.
3) Das div-Element wird nicht geschlossen.
4) Das nobr-Element gehört nicht zum Standard. Verwende CSS stattdessen.
<span style="white-space: nowrap;">Your text ...</span>
do
{
teiler++;
// ...
}
while ((zahl/teiler != 1) && (zahl%teiler != 0));
Diese Schleifenbedingung ist hoffnungslos fehlerhaft. Was bei zahl==2 passiert, hat ShimaG ja schon aufgedröselt.
Korrekt wäre:
while (zahl > 1);
denn dann wurden alle Teiler von zahl in der Schleife gefunden und heraus-dividiert.
Zur Sicherheit würde ich stattdessen sogar
while (zahl > teiler);
schreiben. Das wird auch dann abbrechen, wenn irgendwas in der Schleife schief lief und ein Teiler vergessen wurde (z.B. weil teiler nicht sauber initialisiert wird).
Und wenn es schneller gehen soll, prüfe nur die echten Primteiler:
while (zahl > teiler*teiler);
Wenn zahl überhaupt noch einen größeren Teiler hat, dann nur sich selbst. Jetzt kann die Schleife tatsächlich korrekt mit zahl>1 enden, und das ist dann der letzte Faktor.
Im Augenblick gibst Du nach der Schleife sowieso "*zahl" aus, was bei Dir momentan immer "*1" produziert. Mit obiger Abkürzung kann da auch der letzte Primfaktor erscheinen.
Beispiel: zahl = 6126
- Ohne Optimierung erscheint nach 1020 Durchläufen 6126=2*3*1021*1.
- Mit Optimierung erscheint schon nach 31 Durchläufen 6126=2*3*1021.
Danke für Deine Antwort.
Ich habe mich da an folgendes Beispiel orientiert:
Kann man das so nicht machen?