Einfacher Algorithmus möglich?

1

#include <stdio.h>

2

#include <stdlib.h>

3

4

void generate (unsigned int n, unsigned int m) {

5

  unsigned int cn = 0, cm = 0;

6

7

  while (cn < n || cm < m) {

8

    if (cn < n && (cn * m <= n * cm)) {

9

      fputs ("0, ", stdout);

10

      ++cn;

11

    } else {

12

      fputs ("1, ", stdout);

13

      ++cm;

14

    }

15

  }

16

  puts ("");

17

}

18

19

int main (int argc, char* argv []) {

20

  if (argc != 3) {

21

    fprintf (stderr, "Usage: %s Zeroes Ones\n", argv [0]);

22

    return 1;

23

  }

24

  generate (atoi (argv [1]), atoi (argv [2]));

25

}

So?

Bresenham-Algorithmus zum Zeichnen einer Linie: Die Bilder entsprechen 
den Pixeln einer zu zeichnenden Linie mit rationaler Steigung y/x. Z.B. 
entspricht ein Schritt in x dem Darstellen eines Bildes und Schritt in y 
dem Auslassen bei ursprünglich x+y Bildern.

Hallo Quixy,

Du lässt einfach alle (n+m)/n Frames einen Frame fallen.

Mit ein bisschen Optimierung kannst Du anstelle der Rundung auf ganze 
Frame-Nr. die Löschungen so verteilen, dass die ersten Frames alle

abgerundet[(n+m)/n] eine Löschung bekommen, und dahinter alle Frames mit

aufgerundet[(n+m)/n]

Dann ändert sich der Abstand der gelöschten Frames im gesamten Video nur 
an einer Stelle.
Bei der Berechnung der Standardabweichung des Löschungsabstandes macht 
das jedoch keinen Unterschied.

P.S.:
Haftungsausschluss: Bin kein Superhirn.

zitter_ned_aso schrieb:
> Hier stehen zwei Einsen direkt nebeneinander.

Oh, stimmt. Das liegt an dem "<=" - bei der ersten Ziffer wird der 0 die 
Vorzug gegeben. Bei "<" hätte man das umgekehrte Problem. Der erste Teil 
der Bedingung ist wohl auch überflüssig. Außerdem kann man die 
wiederholte Multiplikation vermeiden, indem man direkt um n bzw. m 
inkrementiert. So geht es:

1

void generate (unsigned int n, unsigned int m) {

2

  unsigned int cn = 0, cm = 0;

3

4

  while (cn < n*m || cm < n*m) {

5

    if (cn < cm || (cn == cm && n >= m)) {

6

      fputs ("0, ", stdout);

7

      cn += m;

8

    } else {

9

      fputs ("1, ", stdout);

10

      cm += n;

11

    }

12

  }

13

  assert (cm == n*m);

14

  assert (cn == n*m);

15

  puts ("");

16

}

17

18

int main (int argc, char* argv []) {

19

  if (argc != 3) {

20

    fprintf (stderr, "Usage: %s Zeroes Ones\n", argv [0]);

21

    return 1;

22

  }

23

  generate (atoi (argv [1]), atoi (argv [2]));

24

}

Die Folge wird also bei ausgeglichenem Verhältnis (u.a. am Anfang) mit 
der Ziffer fortgesetzt, von der es mehr geben soll, wobei 0 Vorzug hat 
wenn n=m.

Mit dem Algorithmus könnte man auch einen Takt durch einen gebrochenen 
Faktor teilen - wenn man die Funktion im Takt der Eingabefrequenz 
aufruft, man bei "1" einen Puls ausgibt und bei "0" nicht, ist der 
Teilungsfaktor (n+m)/m. Jittert natürlich ziemlich, der Duty-Cycle ist 
komisch, aber alle n+m Takte stimmt das Teiler-Verhältnis wieder, d.h. 
der Fehler ist nicht kumulativ.

zitter_ned_aso schrieb:
> Dabei wäre 11011011 besser.

Aber nicht wenn sich die Folge wiederholen soll, denn dann kommt 4x eine 
1 hintereinander...

zitter_ned_aso schrieb:
> und für die Parameter 2 6 kriegst du auch "1, 0, 1, 1, 1, 0, 1, 1"
>
> Dabei wäre 11011011 besser.

Warum eigentlich? Die Anforderung war, dass möglichst wenige gleiche 
Ziffern aufeinander folgen sollen. In beiden Fällen ist die Anzahl der 
Ziffern, die auf eine gleiche Ziffer folgt, 3.

zitter_ned_aso schrieb:
> Ich habe es so verstanden:

Okay, das wäre das Maximum der Folgen-Längen, dann sieht das ganze 
anders aus.

Es geht doch um x Fps, und davon möglichst gleichmäßig, y Frames raus 
zuwerfen?!

Quixy schrieb:
> PS: Worum geht es hier eigentlich? Es sollen aus Blöcken von
> Video-Frames einige Frames entfernt werden.
das heißt aber dass es nicht nur einmal stattfindet sondern Ende=Anfang 
ist

zitter_ned_aso schrieb:
> Ich habe es so verstanden:
>
> 1 0  111 0 1 1
>
> --> max. Länge = 3
>
> 11 0 11 0 11
>
> --> max. Länge = 2

damit stimmt das nicht mehr, dann ist:

10111011-10111011
-> max Länge = 3

11011011-11011011
-> max Länge = 4

zitter_ned_aso schrieb:
> Denn n=6, m=2 würde 10111011 liefern. Und 11011011 wäre besser!  Meine
> Güte, das ist vielleicht eine Aufgabe....
ist dann auch nicht mehr so schlecht, denn:
10111011-10111011
-> immer noch max Länge 3
und das "bessere":
11011011-11011011 hat dann max Länge 4

von weiter oben:
zitter_ned_aso schrieb:
> wenn ich dein Programm mit Parametern 3 4 aufrufe, dann bekomme ich als
> Lösung:0, 1, 1, 0, 1, 0, 1,
>
> Hier stehen zwei Einsen direkt nebeneinander. Man kann aber die
> Kombination
> 1010101
wenn man die Lösungen "Ringförmig" betrachtet sind sie wieder identisch

heut ist mir zu spät um darüber weiter nachzudenken, aber ich glaube die 
Lösung schlägt hier grad nen falschen Weg ein. Außer ein Block 
entspricht dem gesammten Video, aber dafür sind die Zahlen etwas klein, 
niemand hat nur 20 Frames in einem Video. Wenn es nur 2-3 Blöcke gibt 
sollte man natürlich Anfang+Ende als solche betrachtet optimieren, aber 
bei mehreren Sekunden-Minuten Video ist es ausreichend davon auszugehen 
dass jeder Block einen Vorgänger und Nachfolger hat.