Laden...

Zahl in drei zufällige Summanden aufteilen

Erstellt von Technologie100 vor 13 Jahren Letzter Beitrag vor 13 Jahren 12.366 Views
T
Technologie100 Themenstarter:in
24 Beiträge seit 2010
vor 13 Jahren
Zahl in drei zufällige Summanden aufteilen

Hallo,

Ich habe ein kleines Problem. Undzwar, ich habe eine feste Zahl (nehmen wir in diesem Fall die 100) nun möchte ich die 100 in 3 Zufalls zahlen splitten die 3 sollen am Ende 100 ergeben.

Ich hatte es schon mit mehrfachen versuchen versucht, doch leider kommt nie die Zahl am Ende raus, die ich gerne hätte. Sprich wenn ich 100 in 3 Zahlen splitte kommt manchmal mehr und manchmal weniger raus.

Jemand eine Idee?

Hab meinen Code jetzt leider gelöscht, deswegen kann ich ihn nicht mehr posten.

MfG

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo,

nimm 2 Zufallszahlen a,b aus dem Intervall [0,100] und berechne die 3. daraus.

BTW: Der Titel "Random Klasse" ist sehr ungünstig gewählt.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

U
1.688 Beiträge seit 2007
vor 13 Jahren

nimm 2 Zufallszahlen a,b aus dem Intervall [0,100] und berechne die 3. daraus.

Noch zu erwähnen: Man braucht ggf. mehrere Versuche, falls die so berechnete dritte Zahl ≤0 ist. Evtl. will man auch noch dafür sorgen, dass alle Zahlen unterschiedlich sind.

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo ujr,

die von dir angenommen Einschränkung wurde in der Frage nicht erwähnt 😉 Es geht nur im "3 Zahlen".

Ich gehe aber genauso wie du davon aus dass das gemeint ist.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

U
1.688 Beiträge seit 2007
vor 13 Jahren

die von dir angenommen Einschränkung wurde in der Frage nicht erwähnt 😉

Stimmt 😃 Ich bin wahrscheinlich aufgrund des Intervalls davon ausgegangen. Ist natürlich nicht zwangsläufig.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo ujr,

Man braucht ggf. mehrere Versuche

bevor man es darauf ankommen lässt, sollte man besser die erste Zahl a aus dem Intervall [0,100] und die zweite Zahl b dem Intervall [0,100-a] berechnen. Wenn die Zahlen alle > 0 sein sollen, die erste Zahl a aus dem Intervall [1,98] und die zweite aus dem Intervall [1,99-a].

herbivore

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo,

es fehlt generell noch die Info mit welcher Operation die 3 Zahlen wieder die ursprüngliche ergeben sollen.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo gfoidl,

im Prinzip hast du Recht, dass das noch nicht spezifiziert ist, aber ich denke, man kann mit an Sicherheit grenzender Wahrscheinlichkeit davon ausgehen, dass die gewünschte Operation die Addition ist. Ich hatte in der Zwischenzeit auch den von dir kritisierten Titel in diesem Sinne geändert.

herbivore

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo,

danke herbivore 😉

Was spricht gegen die erste Zufallszahl a € [0, 100/3] zu wählen, die zweite b € (100/3, 2100/3] und die dritte ~~c € (2100/3, 100]~~ berechnen? Ist das für diese Aufgabe zufällig genug?

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

795 Beiträge seit 2006
vor 13 Jahren

Hi.

Mir war langweilig, also:

using System;

public class Program
{
	static Random rand = new Random();
	
	static void Main()
	{
		while (true) {
			Console.Write("Bitte geben Sie eine Nummer ein: ");
			int number = Int32.Parse(Console.ReadLine());
			int sum1 = rand.Next(number / 8, number / 2);
			int sum2 = rand.Next(sum1 / 2, sum1);
			int sum3 = number - sum1 - sum2;
			int test = sum1 + sum2 + sum3;
			Console.WriteLine("Eingabe {0} | Summand1 {1} | Summand2 {2} | Summand3 {3} | Summe {4}", number, sum1, sum2, sum3, test);
		}
	}
}

Gruß, Christian.

`There are 10 types of people in the world: Those, who think they understand the binary system Those who don't even have heard about it And those who understand "Every base is base 10"`
6.911 Beiträge seit 2009
vor 13 Jahren

Hallo Schamese,

schöne Endlosschleife 😉

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

795 Beiträge seit 2006
vor 13 Jahren

Jupp^^ Ctrl+C hilft beim beenden :evil:

`There are 10 types of people in the world: Those, who think they understand the binary system Those who don't even have heard about it And those who understand "Every base is base 10"`
49.485 Beiträge seit 2005
vor 13 Jahren

Hallo gfoidl,

Was spricht gegen die erste Zufallszahl a € [0, 100/3] zu wählen, die zweite b € (100/3, 2100/3] und die dritte ~~c € (2100/3, 100]~~ berechnen?

wenn ich dich richtig verstehe, ist die (ursprüngliche) Idee, dass eine Zahl zwischen 0-33, die zweite zwischen 34-66 und die dritte zwischen 67-100 liegt. Das würde aber nicht sicherstellen, dass die Summe der Zahlen automatisch 100 ist (deshalb hast du ja auch den letzten Teil gestrichen). Aber selbst wenn man das sicherstellt, indem man c = 100-a-b berechnet, zeigt sich, dass c nicht unbedingt im Bereich von 67-100 liegt (sogar mit relativ großer Wahrscheinlichkeit nicht). Das zeigt m.E. schon, dass da irgendwas an der Grundidee nicht ganz stimmt. Außerdem erzwingt diese Lösung, dass eine der Zahlen zwischen 34 und 66 liegt. Damit werden aber Lösungen wie 3, 5, 92 ausgeschlossen. Es sind also nicht mehr alle Lösungen gleichwahrscheinlich.

Ist das für diese Aufgabe zufällig genug?

Das kann zwar nur der Aufgabensteller entscheiden 😃 aber in meinen Augen ist mein Vorschlag vorzuziehen. Jedenfalls stellt deine Lösung keine Gleichverteilung sicher.

Hallo Schamese,

letzteres gilt m.E. auch für deine Lösung.

herbivore

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo herbivore,

da hab ich wohl etwas gewaltig verwechselt. Wenn ich deine Antwort lese ist meine Vorschlag Bull....

Motiviert war der Vorschlag von einer möglichst einfachen Unterteilung ohne mehrfache Versuche und leider ist dein Vorschlag davor auch nicht ausgenommen.

Da ich mir nun das Ganze nochmals überlegt habe bin ich zu folgendem Vorschlag gekommen:


for (int j = 0; j < 5; j++)
{
	Random rnd = new Random(j);
	int x = 100;
	int n = 3;
	List<int> teile = new List<int>(n);				

	while (--n > 0)
	{
		int a = rnd.Next(0, x - teile.Sum());
		teile.Add(a);
	}
	teile.Add(x - teile.Sum());

	foreach (int i in teile)
		Console.WriteLine(i);
	Console.WriteLine("Summe: {0}\n", teile.Sum());
}

Angehängt ein Bild der Verteilung das sich bei 1000 Durchläufen ergeben hat. Es ist zwar keine Gleichverteilung, aber m.E. nach kann mit dieser Aufgabenstellung gar keine Gleichverteilung erreicht werden.

Wenn der auch nicht passt gebe ich auf 😉

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo gfoidl,

Motiviert war der Vorschlag von einer möglichst einfachen Unterteilung ohne mehrfache Versuche und leider ist dein Vorschlag davor auch nicht ausgenommen.

wie kommst du darauf? Mein Vorschlag ermöglicht doch gerade eine Unterteilung ohne mehrfache Versuche. Im Prinzip läuft doch mein Vorschlag so ziemlich auf deine Implementierung hinaus.

herbivore

1.002 Beiträge seit 2007
vor 13 Jahren

Hallo,

ungetestete Idee: 1.starte mit 2 Werten ~~Math.Floor(~~ n / 3 ~~)~~ und dem 3. Wert, der beide auf n = 100 ergänzt 1.ziehe einen zufälligen Betrag X von einem zufälligen Wert der 3 Werte ab 1.verteile diesen Betrag entweder (der Zufall entscheidet) zufällig auf beide verbleibende Werte oder addiere ihn zu nur einem Wert 1.wiederhole ab 2. ausreichend oft

Kann so näherungsweise eine Gleichverteilung erreicht werden? Oder sind nachher alle Werte ca. ein Drittel von n?

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo m0rius,

ob das gleichverteilt wäre, weiß ich nicht. Darüber nachzudenken halte ich aber für müßig, weil es ganz ohne Schleife (egal ob für mehrere Versuche oder für eine iterative Annäherung) geht.

Wenn die Zahlen ≥ 0 sein sollen:

Random rand = new Random ();
int n = 100;
int a = rand.Next (0, n + 1);
int b = rand.Next (0, n + 1 - a);
int c = n - a - b;
Console.WriteLine ("{0,3} + {1,3} + {2,3} = {3,3}", a, b, c, a + b + c);

Wenn die Zahlen > 0 sein sollen:

Random rand = new Random ();
int n = 100;
int a = rand.Next (1, n + 1 - 2);
int b = rand.Next (1, n + 1 - a - 1);
int c = n - a - b;
Console.WriteLine ("{0,3} + {1,3} + {2,3} = {3,3}", a, b, c, a + b + c);

Leicht zu programmieren, nach der obigen verbalen Lösung.

Dass die Werte für die rechte Schranke im Code eins höher sind als in der verbalen Lösung liegt daran, dass bei Random.Next der rechte Werte exklusiv ist, während er bei der Intervallschreibweise inklusiv ist.

herbivore

1.002 Beiträge seit 2007
vor 13 Jahren

Hallo herbivore,

ich habe oben genannten Algorithmus implementiert und die Ausgabe angehängt — man müsste allerdings noch untersuchen, inwiefern die Wert-Tupel nun gleichverteilt sind.

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo herbivore,

wie kommst du darauf?

Entschuldige - da hab ich dir bzw. deiner Lösung unrecht getan. Irgendwo hab ich beim Hinschauen immer ein +1 zuviel drin gehabt...

Somit hast du Recht dass deine Lösung als ideal angesehen werden kann - und ist auch ungleich effizienter 😉. Angehängt ein Histogramm der Verteilung.

Hallo m0rius,

Kann so näherungsweise eine Gleichverteilung erreicht werden?

Eine Gleichverteilung ist für diese Aufgabe gar nicht erreichbar - es wird statistisch gesehen immer eine Häufung bei den kleineren Zahlen geben.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo m0rius, hallo gfoidl,

ich habe doch nochmal über die Gleichverteilung nachgedacht und festgestellt, dass diese bei meiner obigen Lösung leider nicht gegeben ist.

Gleichverteilung bedeutet ja, dass jede mögliche Kombination gleichwahrscheinlich ist. Zuerst muss man man also überlegen, wieviele Kombinationen es gibt. Das hängt davon ab, ob es auf die Reihenfolge der Zahlen ankommt. Wenn es auf die Reihenfolge der gewählten Zahlen nicht ankommt, wenn also die Kombination 10+89+1 als mit der Kombination 1+10+89 identisch betrachtet wird, gibt es 833 verschiedene Lösungen, um die Zahl 100 in drei Summanden aufzuteilen. Wenn es jedoch auf die Reihenfolge der Zahlen ankommt, gibt es 4851 (= 1 + 2 + 3 + ... + 97 + 98) Kombinationen. Für den letzten Fall habe ich einen Algorithmus entwickelt, der eine Gleichverteilung aller Kombinationen sicherstellt.

Der Trick dabei ist, dass zuerst die Anzahl der möglichen Kombinationen berechnet wird, dann eine Zufallszahl zwischen 1 und der Anzahl der Kombinationen - also quasi die Nummer der Kombination - "gezogen" wird und dann aus der Nummer der Kombination die Zahlenwerte der Kombination ausgerechnet werden.

Hier meine Lösung mit Gleichverteilung:


using System;
using System.Collections.Generic;
using System.Linq;

static class App
{
   public static Random rand = new Random ();

   public static void SplitNumber (int n, out int a, out int b, out int c)
   {
      if (n < 3) {
         a = b = c = 0;
         return;
      }
      // Berechnen, wieviel unterschiedliche Kombinationen es gibt,
      // eine davon zufällig auswählen und aus der gewählten Nummer der
      // Kombination die drei Zahlenwerte der Kombination ausrechnen.
      int i = rand.Next (SumNaturalNumbers (n-2)) + 1;
      int m = ReverseSumAllNaturalNumbers (i);
      a = n - 1 - m;
      b = SumNaturalNumbers (m) - i + 1;
      c = n - a - b;
   }

   public static int SumNaturalNumbers (int n)
   {
      if (n <= 0) {
         return 0;
      }
      // n*(n+1)/2  berechnen,
      // allerdings kann n*(n+1) einen Overflow erzeugen, daher früher
      // halbieren und zwar den Wert, der durch zwei teilbar ist
      if ((n % 2) == 0) {
         return (n/2)*(n+1);
      }
      return n*((n+1)/2);
   }

   public static int ReverseSumAllNaturalNumbers (int i)
   {
      if (i <= 0) {
         return 0;
      }
      // Berechnen von n, so das gilt:
      // SumNaturalNumbers (n-1) < i <= SumNaturalNumbers (n)
      return (int)(Math.Sqrt(2.0 * (i-1) + 0.25) - 0.5) + 1;
   }

   public static void Main (string [] astrArg)
   {
      String strKey;
      Dictionary <String, int> combiLists = new Dictionary <String, int> ();
      int a, b, c;

      // Viele Versuche durchführen und die Häufigkeit der "gezogenen"
      // Kombinationen mitzählen
      for (int i = 0; i < 1000000; ++i) {
         SplitNumber (100, out a, out b, out c);
         strKey = "" + a + "+" + b + "+" + c;
         int tmp = 0;
         combiLists.TryGetValue (strKey, out tmp);
         combiLists [strKey] = tmp + 1;
      }

      // Anzahl der unterschiedlichen Kombination ausgeben
      Console.WriteLine (combiLists.Count);

      // Zu jeder Kombination die Häufigkeit ausgeben
      foreach (String str in combiLists.Keys.OrderBy (x=>x)) {
         Console.WriteLine ("{0,-8} {1,5}", str, combiLists [str]);
      }
   }
}

Mein Dank geht an zommi, der mir nicht nur die Formel für das Rückwärtsrechnen der Summe der ersten n natürlichen Zahlen N = floor(sqrt(2.0*i + 0.25) - 0.5) genannt hat, sondern auch getestet hat, dass die Implementierung der Formel in C# für alle möglichen Eingabewerte frei von Rundungsfehlern ist. Auch die Berechnung der Summe der ersten n natürlichen Zahlen ohne unnötigen Overflow stammt von zommi.

herbivore

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo herbivore,

das ist wirklich ein genial einfacher Trick 👍
Die Ergebnisse schauen sehr gleichverteilt aus.

Ich will noch anmerken wo die Formel in ReverseSumAllNaturalNumbers herkommt damit diese nicht so kryptisch dasteht:
Die Summe der natürlichen Zahlen von 1...n = s = n * (n+1) / 2 (von Gauss) und in der Formel wird für eine gegeben Summe die Zahl n berechnet - d.h. es ist die Lösung der quadratische Gleichung n^2 + n -2s = 0.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

G
45 Beiträge seit 2010
vor 13 Jahren

Hi!

Kann es sein, dass ihr das ein wenig kompliziert gemacht habt? Mann nimmt einfach zwei Zufallszahlen aus [0,100] dann speichert man diese in ein Array bestehend aus 0,z_1,z_2,100 und rechnet a=z_1-0, b=z_2-z_1, c=100-z_2. Allgemein also z_(i+1)-z_i.

Was man also macht, ist die Summe der Abstände aufsummieren.

Grüße, Marc

1.002 Beiträge seit 2007
vor 13 Jahren

Hallo gaussmath,

Mann nimmt einfach zwei Zufallszahlen aus [0,100] damit hast du es dir ein wenig zu einfach gemacht 😃. So kannst du nicht verhindern, dass beispielsweise 80 und 90 gewählt werden — in der Summe bist du da schon bei 170.
Weiter oben hat herbivore einen ähnlichen Ansatz gepostet, der aber sicher verhindert, dass die Obergrenze nicht überschritten wird. Der kompliziertere Ansatz dient hier nur einer annähernden Gleichverteilung bzw. der zufälligen Wahl korrekter Lösungen.

@dN!3L: Du hast Recht, das war natürlich Blödsinn, entschuldige.

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

2.891 Beiträge seit 2004
vor 13 Jahren

[...]damit hast du es dir ein wenig zu einfach gemacht 😃. So kannst du nicht verhindern, dass beispielsweise 80 und 90 gewählt werden — in der Summe bist du da schon bei 170.

Da hast du den Algorithmus falsch verstanden: Für 80 und 90 würde da (0,80,90,100) rauskommen, die Abstände wären 80,10 und 10 - macht zusammen 100.

Gruß,
dN!3L

G
45 Beiträge seit 2010
vor 13 Jahren

Nein, das passt schon:

a+b+c=z_1-0+z_2-z_1+100-z_2= z_1-z_1 + z_2-z_2 +100 =100

Mein Werte sind wahrscheinlich gleichverteilt über [0,100]. Dies muss jedoch erst noch bewiesen werden.

2.891 Beiträge seit 2004
vor 13 Jahren

Mein Werte sind auch gleichverteilt über [0,100].

Sind die 3 Summanden wirklich gleichverteilt? Sind nicht zwei der Summanden Durchschnitt 50 und der dritte Summand 0?

G
45 Beiträge seit 2010
vor 13 Jahren

[EDIT]Sind zwei Zufallsvariablen gleichverteilt, so ist auch deren Differenz wahrscheinlich nicht gleichverteilt.[/EDIT] Man könnte eventuell über den zentralen Grenzwertsatz argumentieren, was noch zu prüfen ist.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo gaussmath,

Sind zwei Zufallsvariablen gleichverteilt, so ist auch deren Differenz gleichverteilt.

das stimmt so wie es da steht schon mal nicht. Wenn man zwei Zufallszahlen aus [0-100] hat, gibt es nur einen Fall, in dem die Differenz 100 ist, aber 100 Fälle, in denen die Differenz 0 ist.

Das heißt allerdings nicht automatisch, dass die Kombinationen, die du erzeugst, nicht gleichverteilt sind. Das müsste ich erst noch überlegen. EDIT: Das Ergebnis der Überlegung im folgenden Beitrag zeigt, dass die Kombinationen, die du erzeugst, nicht gleichverteilt sind.

In jedem Fall muss das Array vor der Differenzbildung noch aufsteigend sortiert werden, damit der Algorithmus keine negativen Werte liefert.

herbivore

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo gaussmath,

ich gehe im folgenden von einer Gleichverteilung unter Berücksichtigung der Reihenfolge aus, so wie sie mein letzter Algorithmus liefert. In diesem Sinne kann dein Algorithmus nicht gleichverterteilt sein. Wenn man die Zahl 100 in drei Zahlen zwischen 0-100 aufteilt, gibt es 5151 Kombinationsmöglichkeiten (Summe der ersten 101 natürlichen Zahlen). Wenn man zwei Zufallszahlen zwischen 0-100 wählt, wie du das tust, gibt es 101*101 = 10201 Möglichkeiten. Diese müssen nun auf die 5151 gewünschten Kombinationen abgebildet werden. Da sich aber 10201 nicht ohne Rest durch 5151 teilen lässt, müssen bei der Abbildung manche Kombinationen öfter getroffen werden als andere. Eine Gleichverteilung ist bei deinem Algorithmus also sicher nicht gegeben. Zumindest dürfte aber die Verteilung deutlich gleichmäßiger sein als bei meinem ersten Algorithmus. Bis zum Beweis des Gegenteils gehe ich also davon aus, dass man es so "kompliziert" machen muss, wie ich es gemacht habe, um eine Gleichverteilung sicherzustellen (zumindest wenn man mit nur einem Versuch zu einem Ergebnis kommen will).

herbivore

G
45 Beiträge seit 2010
vor 13 Jahren

Hallo herbivore,

ich habe in der Tat Zweifel an meiner Aussage und werde da nochmal drüber nachdenken. Bis dahin werde ich meine bisherigen Beiträge editieren, so dass die Unsicherheit zum Ausdruck kommt.

Grüße, gm

1.361 Beiträge seit 2007
vor 13 Jahren

Hi,

die Nicht-Gleichverteilung ergibt sich aus herbivores Ergänzung:

In jedem Fall muss das Array vor der Differenzbildung noch aufsteigend sortiert werden, damit der Algorithmus keine negativen Werte liefert.

Natürlich will man negative Ergebnisse vermeiden, doch das "Hinsortieren" sorgt dafür, dass es nicht mehr gleichverteilt ist. Stattdessen sollte man die negativen Varianten einfach verwerfen und erneut würfeln. Dann haben wir die Gleichverteilung sichergestellt.

Wie herbivore korrekt schreibt, gibt es ja 101*102/2 = 5151 Möglichkeiten.

Bei der rein zufälligen Wahl von gaussmaths zwei Zahlen (im Folgenden x und y), ergeben sich 101*101 = 10201 Möglichkeiten.
Wenn wir nun aber einfach alle ungültigen verwerfen (anstatt sie einzusortieren), kommen wir wieder bei 5151 raus:

Ungültig ist ein Versuch, wenn x>y (dann ist die Differenz nämlich negativ).
Wie viele solcher ungültigen Paare gibt es nun?
Nun ja, es gibt 101*100 Möglichkeiten zwei [I]unterschiedliche [/I]Zahlen aus [0,100] zu wählen. Jedes Zahlenpaar kommt dabei in beiden Reihenfolgen vor. Beispielsweise (25, 36) und (36, 25).
Die hälfte von diesen Paaren hat eine positive und die andere hälfte eine negative Differenz. 
Also sind 101*100/2 die ungültigen Paare, bei denen etwas negatives rauskommt.

Verwerfen wir nun von den 101*101 theoretischen Kombinationen nun diese 101*100/2 ungültigen (da negativen), kommen wir auf
[FRAME](101*101) - (101*100/2) = (2*101*101 - 101*100)/2 = (101*202 - 101*100)/2  = (101*102)/2 =5151

Und das sind genau alle möglichen. Und jede ist gleichwahrscheinlich.[/frame]

Eine mögliche Implementierung wäre demnach:

static class App
{
   public static Random rand = new Random ();

   public static void SplitNumber (int n, out int a, out int b, out int c)
   {
		int x,y;
		do{
			x = ran.Next(n+1);
			y = ran.Next(n+1);
		}while(x>y);
		
		a = x;
		b = y-x;
		c = n-y;
   }

Allerdings ist diese do-while-Schleife zum Verwerfen etwas unschön.

beste Grüße
zommi

G
45 Beiträge seit 2010
vor 13 Jahren

Moin zommi,

hast du die Gleichverteilung mal überprüft mit dem Algorithmus? Hast du ein Diagramm?

Grüße, Marc

1.361 Beiträge seit 2007
vor 13 Jahren

Hi gaussmath,

nein überprüft habe ich es nicht, aber ich gehe davon aus.
Mit ran.Next(n+1) bekomm ich ja ne Gleichverteilung aus [0,100].
Zieh ich nun zweimal per Random.Next, bekomm ich wegen der Unabhängigkeit dieser Experimente dann ne Gleichverteilung der 10201 Werte aus [0,100]² raus. Da ich die "negativen" Paare einfach verwerfe sind die übrigen 5151 Paare doch ebenfalls noch gleichverteilt !?
Wenn ich bei nem Würfel sage: bei ner 6 nochmal würfeln, kommt doch insgesamt auch ne Gleichverteilung der Werte aus [1,5] raus !?

Und diese 5151 bilden sich 1:1 auf alle möglichen Zerlegung der 100 in drei Zahlen (mit Berücksichtigung der Reihenfolge) ab. Demnach sind diese ebenfalls gleichverteilt.

So meine Überlegung.

4.931 Beiträge seit 2008
vor 13 Jahren

Zommi, ich sehe es genau so wie du.

Und die while-Schleife könnte man einfach rauswerfen und im Falle von x > y diese Werte einfach vertauschen (oder aber allgemein jeweils min und max beider Werte bestimmen).

S
211 Beiträge seit 2010
vor 13 Jahren

Wenn ich das lese bedeutet "Gleichverteilung" hier, das jede Kombination aus 3 Zahlen, die zusammen addiert 100 ergeben, gleich oft möglich sind, ohne bestimmte Kombinationen zu bevorzugen.
Also quasi eine Gleichverteilung der Kombinationen.

Mein erster Gedanke war allerdings der, das eine Gleichverteilung unter den gewählten Zahlen herrschen soll, unabhängig der Kombination.
Also quasi eine Gleichverteilung der Zahlen, nicht der Kombinationen.
Und in diesem Fall wäre eine Gleichverteilung nicht möglich.

Konnte aber nicht so ganz unterscheiden um welche Gleichverteilung es nun geht. Die Diagramme am Anfang des Threads von gfoidl zeigen noch Verteilungen der Zahlen, jetzt gegen Ende geht es um die Gleichverteilungen der Kombinationen.

G
45 Beiträge seit 2010
vor 13 Jahren

Wenn das wirklich klappt, wäre das eine enorme Optimierung. Ich werde das in den nächsten Tagen mal vollständig implementieren.

G
45 Beiträge seit 2010
vor 13 Jahren

Die Diagramme am Anfang des Threads von gfoidl zeigen noch Verteilungen der Zahlen, jetzt gegen Ende geht es um die Gleichverteilungen der Kombinationen.

Hi,

das ist doch dasselbe. Jede Kombination ist gleichwahrscheinlich, somit kommt jeder Eintrag des Tripels (Zahl) gleich oft vor.

Grüße, gm

1.361 Beiträge seit 2007
vor 13 Jahren

Hi,

[...] um welche Gleichverteilung es nun geht.

Tja gute Frage ... 😃
Bei meinem Post hab ich mich auf die Gleichverteilung aller Kombinationen eingestellt.

Und die while-Schleife könnte man einfach rauswerfen und im Falle von x > y diese Werte einfach vertauschen (oder aber allgemein jeweils min und max beider Werte bestimmen).

Nein leider nicht. Denn dann gibt es eine Häufung bei diesen Kombinationen ! (da sowohl die Variante (18, 32) als auch (32, 18) dann bei dir auf (18, 32) abgebildet werden.
Allerdings gibt es diesen Fall bei der Kombination (20, 20) nicht.
Manche kommen dann also häufiger vor als andere => keine Gleichverteilung.

Um nochmal beim Würfelbeispiel zu bleiben:

"Bei einer 6 nochmal würfeln" => Gleichverteilung über [1,5]
"Zähl doch ne 6 wie ne 5" => keine Gleichverteilung über [1,5]

Und der Vorschlag mit dem Sortieren/Min-Max-Berechnen ist analog zur zweiten Vorgehensweise.

Daher bis dato die hässliche Schleife.

beste Grüße
zommi

S
211 Beiträge seit 2010
vor 13 Jahren

das ist doch dasselbe. Jede Kombination ist gleichwahrscheinlich, somit kommt jeder Eintrag des Tripels (Zahl) gleich oft vor.

Nein, weil innerhalb der Kombinationen nicht alle Zahlen gleichwahrscheinlich sind.
Da werden kleinere Zahlen immer öfter vorkommen als größere.

Und wenn innerhalb einer Kombination keine Gleichverteilung der Zahlen herrscht, dann herscht auch insgesamt keine Gleichverteilung der Zahlen.

EDIT: Aber nicht das ich falsch verstanden werden, die Gleichverteilung der Kombinationen ist natürlich möglich und (ohne es geprüft zu haben) so wie es oben steht auch richtig.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Th69,

Und die while-Schleife könnte man einfach rauswerfen und im Falle von x > y diese Werte einfach vertauschen (oder aber allgemein jeweils min und max beider Werte bestimmen).

das stimmt nicht. Ich habe ja schon weiter oben begründet warum.

herbivore