C :: Aufgabe #170
1 Lösung
Ermittlung der Periodenlänge einer unendlichen Zahlenfolge
Anfänger - C
von hollst
- 12.09.2017 um 12:58 Uhr
Wir betrachten eine Zahlenfolge N mit den Parametern n0, a, b und m (alles natürliche Zahlen > Null),
die iterativ definiert ist durch
N(i + 1) = (a * N(i) + b) mod m
und
N(0) = n0.
Diese Zahlenfolge wird naturgemäß ab einem bestimmten Startglied periodisch weiterverlaufen mit einer
Periodenlänge F, wobei immer 0 < F < m + 1 sein wird.
Man schreibe ein Program, das die Parameter n0, a, b und m als natürliche Zahlen entgegennimmt und
die Periodenlänge F rückgibt.
Anmerkung: Im Falle F = m stellen die Glieder einer Periode von N Pseudo-Zufallszahlen mit dem Bereich 0 ... m - 1 dar,
man kann somit seinen eigenen Zufallsgenerator kreiren (ist allerdings nicht (kaum) geeignet für kryptische Verschlüsselungen,
da relativ leicht "knackbar").
die iterativ definiert ist durch
N(i + 1) = (a * N(i) + b) mod m
und
N(0) = n0.
Diese Zahlenfolge wird naturgemäß ab einem bestimmten Startglied periodisch weiterverlaufen mit einer
Periodenlänge F, wobei immer 0 < F < m + 1 sein wird.
Man schreibe ein Program, das die Parameter n0, a, b und m als natürliche Zahlen entgegennimmt und
die Periodenlänge F rückgibt.
Anmerkung: Im Falle F = m stellen die Glieder einer Periode von N Pseudo-Zufallszahlen mit dem Bereich 0 ... m - 1 dar,
man kann somit seinen eigenen Zufallsgenerator kreiren (ist allerdings nicht (kaum) geeignet für kryptische Verschlüsselungen,
da relativ leicht "knackbar").
Lösungen:
C-Code
/********************************************
* plen.c Periodenlänge ermitteln
********************************************/
#include <stdlib.h>
#include <stdio.h>
#define NMAX 10000
unsigned long N[NMAX];
int plength(unsigned long n) {
static int next=0;
int k;
if (next >= NMAX)
return -1;
for (k=0; k<next; k++)
if (n==N[k]) break;
if (k==next) {
N[next++] = n;
return 0;
}
return next-k;
}
int main() {
unsigned long a, b, m;
unsigned long n, n0, n1;
int plen;
printf("n0 : ");
scanf("%lu", &n0);
printf(" a : ");
scanf("%lu", &a);
printf(" b : ");
scanf("%lu", &b);
printf(" m : ");
scanf("%lu", &m);
do {
n1 = (a*n+b)%m;
n = n1;
printf("%lu\n", n);
} while ((plen=plength(n)) == 0);
printf("Periodenlänge %c %d\n", (plen<0)?'>':'=', (plen<0)?NMAX:plen);
return 0;
}