C++ Programm Kartenreihen

21.02.2016, 21:08

leoclid

C++ Programm Kartenreihen

Ich habe ein C++ Programm geschrieben.
Dieses Programm macht folgendes:
Man gibt einen Wert 1 ein.
Man gibt einen Wert 2 ein.

Das Programm generiert nun Wert2 Zufallsreihen der Länge Wert1 mit den Zahlen von 1 bis Wert1.
Dabei kommt jeder dieser Werte jeder der Zufallsreihen nur einmal vor.

Jeder Zufallsreihe wird nun eine Zahl zugeordnet, in dem man die Beträge der Differenzen aufeinanderfolgender Zahlen addiert.

Das Programm gibt anschließend aus, bei wieviel der Wert2 Zufallsreihen welche Zahl zugeordnet wurde.

Hier ist der Code:

Zitat:

#include <iostream>
#include <iomanip>
#include <math.h>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int get_length() // Länge der Kartenreihe eingeben
{
int length;
std::cout << "Geben Sie die gewuenschte Laenge der Kartenreihen ein." << std::endl;
std::cin >> length;
std::cout << std::endl;
return length;
}

int get_repeats() // Anzahl der Versuche eingeben
{
int repeats;
std::cout << "Geben Sie die gewuenschten Zahl an Versuchen ein." << std::endl;
std::cin >> repeats;
std::cout << std::endl;
return repeats;
}

int get_abssum(int length) // Wert einer Kartenreihe berechnen
{
int array[length]; // Array init.

int settonull; // Werte des Arrays auf Null setzen
for (settonull=0; settonull<length; settonull++)
{
array[settonull]=0;
}

int setcard; // Werte des Arrays auswuerfeln
for (setcard=0; setcard<length; setcard++)
{
bool test = false;
while (test != true)
{
test = true;
int x;
int placing = rand()%length+1;
for (x=0; x<setcard; x++)
{
if (array[x]==placing)
{
test = false;
}
}
if (test == true)
{
array[setcard]=placing;
}
}
}

int abssum = 0; // Wert der Kartenreihe berechnen
int q;
for (q=1; q<length; q++)
{
abssum=abssum+fabs(array[q]-array[q-1]);
}
return abssum; // Wert der Kartenreihe zurückgeben

}

int main()
{
int length = get_length(); // Funktion Länge Kartenreihe
int repeats = get_repeats(); // Funktion Zahl Wiederholungen
int count[length*(length-1)/2]; // Tabelle Treffer in Abhängigkeit von Zahl

int b; // Startwerte der Tabelle auf 0 setzen
for (b=0; b<length*(length-1)/2; b++)
{
count[b]=0;
}

time_t t; // Initialisierung Zufallsgenerator
time(&t);
srand((unsigned int)t);

int r; // Algorithmus
for (r=0; r<repeats; r++)
{
int abssum = get_abssum(length);
count[abssum-1]=count[abssum-1]+1;
}

int e; // Ausgabe der Werte
for (e=0; e<length*(length-1)/2+1; e++)
{
std::cout << count[e] << std::endl;
}
int all = 0; // Ausgabe der Summe
int ae;
for (ae=0; ae<length*(length-1)/2; ae++)
{
all = all + count[ae];
}
std::cout << all;
}

Das Problem.
Als Beispiel: Als erste Zahl wird 10, als zweite Zahl 100.000 eingegeben.
Das Programm generiert also 100.000 10er Zahlenreihen..

Am Ende gibt es aus, wie oft die 1, 2, 3, 4,5,6 ....., 45 ausgegeben wurde.
Addiert man aber alle diese Werte, kommt man nicht auf 100.000, sondern auf einen kleineren Wert.

Ich vermute, dass mein Fehler im mathematischen Teil liegt.

21.02.2016, 21:42

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von leoclid
Jeder Zufallsreihe wird nun eine Zahl zugeordnet, in dem man die Beträge der Differenzen aufeinanderfolgender Zahlen addiert.

Spät kommt sie, doch sie kommt - die Antwort auf meine diesbezügliche Nachfrage in diesem deinem Thread zum selben Thema:

Beste Programmiersprache für Einsteiger und Mathematik

Ich finde es schon sehr merkwürdig, deine Vergesslichkeit, um nicht zu sagen Ignoranz deiner früher gestarteten Threads. Ich sage das, weil mir das schon häufiger bei dir aufgefallen ist.

21.02.2016, 21:44

leoclid

Auf diesen Beitrag antworten »

Es tut mir leid Freude

Kann bitte ein Administrator den älteren Thread wieder schließen.

Ich habe dass noch mal durchrechnen lassen, allerdings modifiziert.
Diesmal wird mir ausgegeben, wenn einer Zahlenreihe ein Wert größer als 46 zugeordnet wird.
Das passiert einige male.
Also steckt im Teil, in dem die Beträge berechnet werden irgendwo ein Fehler, da bei einer Zahlenreihe mit den Zahlen 1 2 3 4 5 6 7 8 9 10 dort das Maximum der Ausgabe bei 45 liegt.
Zahlenreihe: 1 10 2 9 3 8 4 7 5 6

21.02.2016, 21:56

HAL 9000

Auf diesen Beitrag antworten »

Wer sagt denn, dass das Maximum bei 45 liegt? Bei

6 1 10 2 9 3 8 4 7 5

kommt klar 49 heraus. unglücklich

P.S.: Dein Verfahren zur Erzeugung der Permutation ist äußerst ineffizient:

Beim letzten Element würfelst du u.U. sehr sehr lange, bis du das eine passende, noch nicht vorkommende Element erwürfelt hast.

Ersetze also besser die Sequenz

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

int settonull;																			// Werte des Arrays auf Null setzen
for (settonull=0; settonull<length; settonull++)
{
array[settonull]=0;
}

int setcard;																			// Werte des Arrays auswuerfeln
for (setcard=0; setcard<length; setcard++)
{
bool test = false;
while (test != true)
{
test = true;
int x;
int placing = rand()%length+1;
for (x=0; x<setcard; x++)
{
if (array[x]==placing)
{
test = false;
}	
}	
if (test == true)
{
array[setcard]=placing;
}
}
}

durch

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

int setcard;
for (setcard = 0; setcard < length; setcard++)
{
    array[setcard] = setcard+1;
}
setcard = length;
while (setcard > 1)
{
    int switchpos = rand() % setcard;
    setcard--;
    int placing = array[switchpos];
    array[switchpos] = array[setcard];
    array[setcard] = placing;
}

21.02.2016, 22:02

leoclid

Auf diesen Beitrag antworten »

Ich danke dir für deine Geduld.

Wie gesagt, wir hatten das Problem bei einer Modellierungswoche und wir sind echt alle davon ausgegangen, dass das Maximum bei 45 liegt.

Aber hast vollkommen recht.

Dumm, dass ich das nicht selbst gemerkt habe.

21.02.2016, 22:38

HAL 9000

Auf diesen Beitrag antworten »

Die Betragsdifferenzsumme bei solchen Permutationen bewegt sich zwischen $\begin{align*} n-1 \end{align*}$ und $\begin{align*} \left\lfloor \frac{n^2}{2}\right\rfloor -1 \end{align*}$ , wobei beide Grenzen scharf (d.h. auch tatsächlich erreichbar) sind.

code:
1: 2: 3:	int count[length*(length-1)/2]; // Tabelle Treffer in Abhängigkeit von Zahl ... count[abssum-1]=count[abssum-1]+1;

An der Stelle hätte das Programm übrigens crashen können: Da du im Fall length=10 nur Platz für 45 Feldelemente für count reserviert hast, wird in dem ja möglichen Fall abssum=49 auf Element count[48] zugegriffen - schreibend zugegriffen... Der berühmte "buffer overflow", verantwortlich für einen Gutteil der Einfallstore/Sicherheitslecks. Augenzwinkern

22.02.2016, 22:18

HAL 9000

Auf diesen Beitrag antworten »

Hab mal ein wenig zur Theorie dieser Summe der Betragsdifferenzen gerechnet:

Die entsprechende Zufallsgröße hat Erwartungswert $\begin{align*} \mu = \frac{(n+1)(n-1)}{3} \end{align*}$ und Varianz $\begin{align*} \sigma^2 = \frac{(n+1)(n-2)(4n-7)}{90} \end{align*}$ .

Für $\begin{align*} n=10 \end{align*}$ ergibt das $\begin{align*} \mu=33,\;\sigma\approx 5.68 \end{align*}$ .

Und für $\begin{align*} n=100 \end{align*}$ ist es $\begin{align*} \mu=3333,\;\sigma\approx 207.9 \end{align*}$ .

Für große $\begin{align*} n \end{align*}$ kann man gemäß ZGWS die Normalverteilung $\begin{align*} \mathcal{N}(\mu,\sigma^2) \end{align*}$ zur Approximation der Verteilung dieser Zufallsgröße anwenden.

Neue Frage »

Antworten »

C++ Programm Kartenreihen

Verwandte Themen