Eigener Algorithmus liefert falsche Werte - Denkfehler?

NP1

Hallo,

ich habe versucht, eine Klasse von Problem mithilfe eines selbst geschriebenen Algorithmus, den ich in C implementiert habe, zu lösen:

Immer wenn ich irgendeine Mediadatei im Internet streamen lasse, will ich gerne wissen, welchen prozentualen Anteil der Medienlänge ich vorladen lassen muss, um das Medium ohne Unterbrechungen anschauen zu können.

Meine Vorüberlegungen hierfür waren:
- Ich habe einen Faktor kleiner 1, der mir angibt, welchen prozentualen Anteil einer Minute ich pro Minute laden kann (dieser Faktor ist also abhängig von der Bandbreite und der Größe des Mediums)
- Desweiteren wird die Dauer in Minuten übermittelt.
- pro Minuten werden dann faktor * 1 Minute = x geladen, wodurch sich wiederum x * faktor geladene Zeit ergeben, also faktor² * 1 Minute, dadurch wiederum faktor³ * 1 Minute usw. usf., da ja in der geladenen Minute, ich angeschaut werden kann, wiederum ein Teil des Mediums geladen wird, usw.
- Welchen "echten" Teil ich also pro Minute laden lasse, lasse ich berechnen (breche dann ab, wenn der Wert von 'x' kleiner als 0,01 ist) und wiederhole das so oft, bis ich die Folgenlaenge erreicht habe.

Programmiertechnisch habe ich das wie folgend umgesetzt:

#include <stdio.h>

double faktor_H(double faktor, int hochzahl) {
	int i;
	for(i=1;i<hochzahl;i++) {
		faktor *= faktor;
	}
	return(faktor);
}

int vorladezeit(double faktor, int laenge) {
	double summe = 0, wert;
	int minute = 1, minute_anpassen = 0, i = 0;

	while(summe < laenge) {
		do{
			i++;
			wert = faktor_H(faktor,i) * (minute - minute_anpassen);
			summe += wert;
			printf("\nZwischenstand: %lf (aktueller Wert) -- %lf (aktuelle Summe)\n",wert,summe); // fuer's debugging
		} while(wert > 0.01 && summe < laenge);
		i = 0;
		minute_anpassen++;
		minute++;
	}

	return(minute);
}

void new_page(void) {
	int i;
	for(i=1;i<=500;i++) {
		printf("\n");
	}
}

int main(void) {
	double faktor;
	int laenge;

	printf("\n\tNoetige Vorladezeit berechnen.\n\n");

	do{
		printf("## Bitte Faktor eingeben (z.B. 0.81 -- kein Komma, Punkt benutzen!):\n");
		printf("(Hinweis: Der Faktor gibt an, welcher dezimale Anteil einer Minute pro Minute geladen wird.)\n> ");
		scanf("%lf",&faktor);
		printf("## Bitte Laenge in Minuten definieren (z.B. 42 -- bitte eine Ganzzahl!)\n> ");
		scanf("%i",&laenge);
		if(faktor >= 1 || faktor <= 0 || laenge <= 0) {
			new_page();
			printf("\t→ Bitte Eingaben korrigieren:\n\t(Hinweis: Das Programm kann wahlweisse mit Strg + C beendet werden.)\n\n");
		}
		if(faktor >= 1 || faktor <= 0) printf("[] Faktor darf nicht kleiner o. gleich 0 sein\n[] Faktor darf nicht groesser o. gleich 1 sein.\n\t[In diesem Fall ist ein Vorladen unsinnig (kleiner gleich 0)\n\tbzw. unnoetig (groesser gleich 1)].\n\n");
		if(laenge <= 0) printf("[] Laenge darf nicht kleiner o. gleich 0 sein.\n\n");
		if(laenge > 1000000) printf("\nHinweis: Die Eingabe einer Laenge von ueber 1.000.000 Minuten (Tippfehler??)\nkann unter Umstaenden laengere Laufzeiten verursachen!\n");
	} while(faktor >= 1 || faktor <= 0 || laenge <= 0);

	double ergebnis = vorladezeit(faktor,laenge);

	printf("\n### Die noetige Mindestvorladezeit betraegt ca. %.0lf Minuten (%.0lf %%).\n",ergebnis,(ergebnis/laenge)*100);
	printf("### Bei der gegebenen Bandbreite nimmt das etwa %.0lf Minuten in Anspruch.\n\n",ergebnis/faktor);

	return(0);
}

Das Problem besteht nun darin, dass die gelieferten Werte nicht stimmen. Ich habe es an einem Medium getestet und musste etwa 9 - 10 Minuten vorladen, das Programm meint aber, ich müsse 22 Minuten vorladen lassen. (Eingegeben habe ich 0.81 und 42.)

Auch liefert es bspw. für 0.56 und 3521 unrealistische Werte.

Der Algorithmus muss also irgendeinen logischen Fehler enthalten, nur komme ich aktuell nicht darauf, womöglich kann mir einer von euch auf die Sprünge helfen

lg

volkard

Du willst also wissen, wieviel Vorsprung die Schildkröte mit der Geschwindigkeit x (0<x<=1) braucht, um von Achilles mit der Geschwindigkeit 1 gerade erst am Ziel erreicht zu werden?

NP1

Genau (auch wenn ich an keinen Vergleich gedacht habe?)

CStoll

NP1 schrieb:

Hallo,

ich habe versucht, eine Klasse von Problem mithilfe eines selbst geschriebenen Algorithmus, den ich in C implementiert habe, zu lösen:

Immer wenn ich irgendeine Mediadatei im Internet streamen lasse, will ich gerne wissen, welchen prozentualen Anteil der Medienlänge ich vorladen lassen muss, um das Medium ohne Unterbrechungen anschauen zu können.

Meine Vorüberlegungen hierfür waren:
- Ich habe einen Faktor kleiner 1, der mir angibt, welchen prozentualen Anteil einer Minute ich pro Minute laden kann (dieser Faktor ist also abhängig von der Bandbreite und der Größe des Mediums)
- Desweiteren wird die Dauer in Minuten übermittelt.
- pro Minuten werden dann faktor * 1 Minute = x geladen, wodurch sich wiederum x * faktor geladene Zeit ergeben, also faktor² * 1 Minute, dadurch wiederum faktor³ * 1 Minute usw. usf., da ja in der geladenen Minute, ich angeschaut werden kann, wiederum ein Teil des Mediums geladen wird, usw.

Und das soll funktionieren? Wie kommst du überhaupt auf diese Formel?

Innerhalb einer Minute lädst du faktor Minuten von deinem Stream, also benötigst du für den kompletten Stream eine Ladezeit von Länge/Faktor. Wenn du das Ende des Videos genau zu dem Zeitpunkt sehen willst, wenn es geladen wird, mußt du Länge Minuten vorher auf den Play-Button drücken, d.h. Länge/Faktor-Länge = Länge*(1/Faktor-1) Minuten nach Start des Download.

volkard

NP1 schrieb:

Genau (auch wenn ich an keinen Vergleich gedacht habe?)

Der Vergleich erlaubt, es erstmal in Formel zu gießen, dorch den mathematischen Wolf zu drehen und eine direkte Formel zu finden.
Mach das doch mal.
Der Vergleich erlaubt auch, daß ich danach den Fehler im Code finde, wenn Du ihn an Achilles und die Schildkröte angepaßt hast.
Oder einfach einen Moment warten, CStoll kann sich wunderbar in fremden Code eindenken und Fehler auf den Punkt bringen.

edit: Zu spät, er hat schon eingegriffen, bevor ich ihn erwähnt hatte.

CStoll

volkard schrieb:

Oder einfach einen Moment warten, CStoll kann sich wunderbar in fremden Code eindenken und Fehler auf den Punkt bringen.

Den Code habe ich mir noch gar nicht vorgenommen - bringt nichts, wenn die Vorüberlegungen schon nicht passen

NP1

Die Formel hatte ich mir durch meine Vorüberlegungen hergeleitet, die ja offensichtlich falsch sind

Deine Formel hingegen scheint hinzuhauen, auch wenn ich sie nicht ganz nachvollziehen kann. Kannst du vielleicht nochmal ausführlicher erklären, wie du darauf gekommen bist? Danke

lg

CStoll

Wie volkard schon sagte, du willst den Vorsprung haben, den das Laden (die Schildkröte) gegenüber dem Abspielen (Archilles) benötigt, damit sie gleichzeitig ins Ziel kommen. Der Download benötigt Länge/Faktor Minuten, das Abspielen benötigt Länge Minuten, also brauchst du nur noch die Differenz ausrechnen.

NP1

Jetzt hab' ich's Danke, die Veranschaulichung ist echt gelungen

Ich hab' wohl eindeutig zu kompliziert gedacht

Eine andere Frage: Wie bist du an das Problem herangegangen, um es zu lösen?

lg

volkard

NP1 schrieb:

Jetzt hab' ich's

Zeigen!

volkard

NP1 schrieb:

Eine andere Frage: Wie bist du an das Problem herangegangen, um es zu lösen?

Falls Du mich meinst: Ich bin nicht herangegangen, sondern bei der Problembeschreibung, der ich nur ganz vage folgen konnte und der Folge x, x², x³... und der im Raum hängenden Konvergenz war es mir sonnenklar, daß es um Achilles und die Schildkröte geht. Die Ausarbeitung würde sicher zum Ziel führen, die wurde mir zum Glück abgenommen. Vielleicht sah ich es, weil ich jüngst den Hirnverwinder "Gödel, Escher, Bach" gelesen habe. Das ist ja voll von Spielen um die Schildkröten und Achilles.

CStoll

NP1 schrieb:

Eine andere Frage: Wie bist du an das Problem herangegangen, um es zu lösen?

Ganz einfach: Ich bin davon ausgegangen, daß Download und Abspielen unabhängig voneinander stattfinden. Da muß man sich dann nicht mit solchen Überlegungen rumplagen wie "während ich eine Minute ansehe, werden x Minuten geladen, um die zu sehen brauche ich x² Minuten,..." (an Archilles habe ich dabie allerdings nicht gedacht)

volkard

Das erinnert mich an ein Rätsel.

Zwei ehepartnerliche Wanderer A und B starten gleichzeitig 33km voneinander entfernt und wandern aufeinander zu. Sie haben einen gemeinsamen Hund H. Bei Wanderstart läuft auch der Hund H von A aus los zu B, sobald er B erreicht hat, dreht er sich um und läuft zu A, sobald er A und immer hin und her. H ist 12km/h schnell. A ist 6 km/h schnell. Und B ist 5km/h schnell. Wieviel Strecke hat H am Ende zurückgelegt, wenn sich A und B und H getroffen haben?

(Gerne würde ich NP1's Hirn qualmen sehen, vielleicht können die anderen ihre Lösungen einen Zweitag zurückhalten?)

NP1

@volkard: Deine Vorgehensweise ist eindeutig einzigartig

Dein Code:

void new_page(void) {
	int i;
	for(i=1;i<=500;i++) {
		printf("\n");
	}
}

int main(void) {
	double faktor;
	int laenge;

	printf("\n\tNoetige Vorladezeit berechnen.\n\n");

	do{
		printf("## Bitte Faktor eingeben (z.B. 0.81 -- kein Komma, Punkt benutzen!):\n");
		printf("(Hinweis: Der Faktor gibt an, welcher dezimale Anteil einer Minute pro Minute geladen wird.)\n> ");
		scanf("%lf",&faktor);
		printf("## Bitte Laenge in Minuten definieren (z.B. 42 -- bitte eine Ganzzahl!)\n> ");
		scanf("%i",&laenge);
		if(faktor >= 1 || faktor <= 0 || laenge <= 0) {
			new_page();
			printf("\t→ Bitte Eingaben korrigieren:\n\t(Hinweis: Das Programm kann wahlweisse mit Strg + C beendet werden.)\n\n");
		}
		if(faktor >= 1 || faktor <= 0) printf("[] Faktor darf nicht kleiner o. gleich 0 sein\n[] Faktor darf nicht groesser o. gleich 1 sein.\n\t[In diesem Fall ist ein Vorladen unsinnig (kleiner gleich 0)\n\tbzw. unnoetig (groesser gleich 1)].\n\n");
		if(laenge <= 0) printf("[] Laenge darf nicht kleiner o. gleich 0 sein.\n\n");
		//if(laenge > 1000000) printf("\nHinweis: Die Eingabe einer Laenge von ueber 1.000.000 Minuten (Tippfehler??)\nkann unter Umstaenden laengere Laufzeiten verursachen!\n");
	} while(faktor >= 1 || faktor <= 0 || laenge <= 0);

	double ergebnis = laenge/faktor-laenge;

	printf("\n### Die noetige Mindestvorladezeit betraegt ca. %.0lf Minuten (%.0lf %%).\n",ergebnis,(ergebnis/laenge)*100);
	printf("### Bei der gegebenen Bandbreite nimmt das etwa %.0lf Minuten in Anspruch.\n\n",ergebnis/faktor);

	return(0);
}

Wobei mir noch vorschwebt, mittels eines Kommandozeilenparamters eine Option aufrufbar zu machen, die es ermöglicht, den Faktor zu berechnen.

An das Rätsel geh' ich nachher gleich ran

@CStoll: Daran habe ich ehrlich gesagt gar nicht gedacht Wie einfach es doch sein kann. Ich dachte nur, dass ich die Abhängigkeit irgendwie berechnen muss und dann irgendwie auf eine passende Summe kommen kann

lg

volkard

NP1 schrieb:

@volkard: Deine Vorgehensweise ist eindeutig einzigartig

Danke, ich fühle mich gelobt.
Aber nein, das ist nix Besonderes. Gib CStoll auch das Buch und er faselt auch von Schildkröten. Wenn wir Glück haben. Wenn nicht, berichtet er uns von endlos verschlungenen Bändern.
Überhaupt Modelle zu machen, ist voll gut. Das machen doch alle hier.
Das machst Du auch dauernd, da würde ich wetten.
Wenn da so eine Mathe-Aufgabe ist, hast Du doch bestimmt meistens ruck zuck ein Modell parat und weißt einfach die Lösung oder wenigstens den Rechenweg. Es ist einfach klar. Während andere in der Klasse die Aufgabe nicht "begreifen" und in der Formelsammlung nach passenden Formeln suchen und eine nehmen, die den Buchstaben nach zu passen scheint. Und Du kannst ihnen einfach nicht begreiflich machen, daß die Lösung quasi schon in der Aufgabe stand.

NP1

Jetzt fühle ich mich aber geschmeichelt
Aber du hast es auf den Punkt gebracht, denn meistens tritt genau dieser Fall ein und wenn man Glück hat, präsentiert sich die Lösung der Aufgabe auf dem Silbertablett, wobei es natürlich mehr Vergnügen bereitet, wenn man doch erst etwas nachdenken darf, bevor man des Rätsels Lösung hat Und versuchen wir nicht vieles im Leben mithilfe von Modellen zu vereinfachen und es scheint ja meistens gut zu funktionieren. Übrigens, das Buch muss ich mir auch mal anschauen

volkard

NP1 schrieb:

Übrigens, das Buch muss ich mir auch mal anschauen

Verzeih mir, aber ich fürchte, das ist noch nicht gut für Dich. Die anderen Annahmen über Dich habe ich auch nur geschätzt. Falls sie einigermaßen gepaßt haben, dann verzögere das Buch auch noch ein Weilchen.
"Algorithmen in C" von Sedgewick empfehle ich Dir. Danach "Programming Pearls" von Bentley.

Den weiteren Weg darf ich hier nicht verraten.
(Nur in der Annahme, daß ich Dich richtig einschätze. Soo viele Zeilen habe ich vor Dir ja noch nicht gelesen. Aber ich habe ein recht sattes Gefühl, daß es paßt.)

ps: "Algos in C" ist vergriffen, also man kann es nicht mehr neu kaufen. Egal, ein gebrauchtes Buch funktioniert auch. Besser ein gutes gebrauchtes als ein schlechtes neues.

NP1

Danke für die Empfehlungen Ich schaue einfach, was sich ergibt und an welcher Stelle sie ihren Einsatz finden könnten

lg

hustbaer

volkard schrieb:

Das erinnert mich an ein Rätsel.

Zwei ehepartnerliche Wanderer A und B ...

Hihi, ja, das ist fies wenn man es noch nicht kennt.

Wobei ich bisher nur eine einfachere Variante davon kannte. Kennt man die einfachere Lösung, hat man die für deine Variante allerdings auch in ein paar Sekunden raus.

CStoll

volkard schrieb:

Aber nein, das ist nix Besonderes. Gib CStoll auch das Buch und er faselt auch von Schildkröten. Wenn wir Glück haben. Wenn nicht, berichtet er uns von endlos verschlungenen Bändern.

So schätzt du mich also ein
Ne, bei mir würden sich ein paar Erkenntnisse aus dem Buch festsetzen, aber ich bin kein so guter Geschichtenerzähler. Und in der Praxis versuche ich eher, mein Wissen auf die Situation anzuwenden als daß ich Anekdoten in den Raum werfe.
(das klappt nicht immer - auf Gregors Lösung hier bin ich auch nicht gekommen)

PS: Dein Rätsel kannte ich auch schon mit anderen Zahlenwerten, deshalb halte ich mich da mal zurück.