You are not logged in.

  • Login

1

Monday, August 11th 2008, 4:18pm

Permutationen

Weiß jemand, wie folgendes Problem zu lösen ist? m Geldbeträge sind auf n Zeitpunkte zu verteilen.
Beispiel: m=2 (A,B) auf n=3 Zeitpunkte 1,2,3:
A B
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
Es gibt also k = n^m Möglichkeiten.

Für m=2 kann man alle Permutationen so erzeugen:

C/C++ Quellcode

1
2
3
4
5
6
7
8
9
10
k=0;
for(i=1;i<=n;i++) 
{ 
  for(j=1;j<=n;j++) 
  {
    k++;
    A[k] = i; 
    B[k] = j; 
  } 
}

Aber wie geht das allgemein? Ich kenne ja vorher nicht m, weiß also nicht, wieviele for-Schleifen ich brauche.

Gibt es eine iterative, NICHT-REKURSIVE Lösung zu diesem Problem?

This post has been edited 5 times, last edit by "osb" (Aug 11th 2008, 5:38pm)


2

Tuesday, August 12th 2008, 4:49pm

Hallo,

ich würde dir gerne helfen, allerdings verstehe ich das Programm nicht wirklich.
Also dass du mehrere Geldbeträge auf mehrere Zeitpunkte verteilen willst, habe ich verstanden,
aber wenn du 2 Geldbeträge hast, dann kann ja der eine einen Betrag von 50 und der abdere einen Betrag von 45,62 haben.
Jetzt haben wir dann noch 3 Zeitpunkte. das heißt dass die (insgesamt) 95,62 auf die 3 Zeitpunkte verteilt werden müssen...

Habe ich das soweit richtig verstanden?
Aus deiner kleinen Tabelle werde ich einfach nicht schlau.

Und sollen die Geldbeträge nur aus ganzen Zahlen (also int) bestehen oder dachtest du da an Kommazahlen (also float)?


MfG, Agent2

3

Wednesday, August 13th 2008, 2:27pm

Hallo, Danke für Deine Antwort. Unten ein Programm, welches das Problem SEHR UNELEGANT löst.

Es sind auch 10 "Geldbeträge", auf die das Problem dann begrenzt bleibt.

Ab Zeile 45 wird eine Testausgabe generiert. Daran siehst Du bestimmt, was ich meine.

Eine andere nicht-rekursive Lösung wäre super.

Gruß,

Oliver





C/C++ Quellcode

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int main(void) 
{ 
int A[N][100000]; 
int i, j, k; 
int z1, z2, z3, z4, z5, z6, z7, z8, z9, z10; 
 
k=0; 
for(z1=1;z1<=n;z1++) 
{ 
for(z2=1;z2<=n;z2++) 
{ 
for(z3=1;z3<=n;z3++) 
{ 
for(z4=1;z4<=n;z4++) 
{ 
for(z5=1;z5<=n;z5++) 
{ 
for(z6=1;z6<=n;z6++) 
{ 
for(z7=1;z7<=n;z7++) 
{ 
for(z8=1;z8<=n;z8++) 
{ 
for(z9=1;z9<=n;z9++) 
{ 
for(z10=1;z10<=n;z10++) 
{ 
k++; 
A[10][k] = z1; 
A[9] [k] = z2; 
A[8] [k] = z3; 
A[7] [k] = z4; 
A[6] [k] = z5; 
A[5] [k] = z6; 
A[4] [k] = z7; 
A[3] [k] = z8; 
A[2] [k] = z9; 
A[1] [k] = z10; 
} 
} 
} 
} 
} 
} 
} 
} 
} 
} 
 
for(i=1;i<=10;i++) 
{ 
for(j=1;j<=3;j++) 
{ 
printf("z%d[%d]=%d ", j, i, A[j]); 
} 
printf("\n"); 
} 
 
return EXIT_SUCCESS; 
}

4

Thursday, August 14th 2008, 9:41am

Hallo,
lise dir mal das Fallbeispiel hier durch, das ist super erklärt und auch für Leute die keine Mathematischen vorkenntnisse besitzen.
http://magazin.c-plusplus.de/artikel/Permutationen

Similar threads

Social bookmarks