Formel für Verteilung?

Re(10): Formel für Verteilung?

Penguin — Fri, 12 Jul 2002 09:48:32 GMT

vielen dank!

hat mit beiden (für vba abgewandelten) methoden funktioniert.

im übrigen dauert das im excel schon ca. 1 min (abgesehen davon dass nach 65536 möglichkeiten ein zwangsstop ein gelegt wird ) - auf einem amd tbird 700, naja wie auch immer.

Vielen Dank auf jeden Fall allen die so nett und schnell geholfen haben!!

Re(10): Formel für Verteilung?

thewanderer — Fri, 12 Jul 2002 08:20:13 GMT

... nicht resourcenschonend programmieren wollen ... oder können .

Re(9): Formel für Verteilung?

cltom — Fri, 12 Jul 2002 07:45:16 GMT

Nun, wie gesagt: meiner ist bestimmt der ineffizienteste. Das macht sich natürlich bei hohen Werten für max besonders drastisch bemerkbar, da die allermeisten getesteten Möglichkeiten falsch sind.

Schön, das es besser geht.

Aber ein Bekannter (Informatiker) hat mal gesagt, schnellere PCs werden nur deshalb gebraucht, weil die Leute nicht resourcenschonend programmieren wollen.

Re(9): Formel für Verteilung?

cltom — Fri, 12 Jul 2002 07:42:46 GMT

ist unterwegs (war schon weg gestern)

Re(8): Formel für Verteilung?

Penguin — Thu, 11 Jul 2002 19:58:48 GMT

bitte zeig es mir:

mailto:stewin@gmx.at

Re(7): Formel für Verteilung?

le — Thu, 11 Jul 2002 15:19:24 GMT

Hehe, ich habs mal mit 1000 probiert, meiner war nach 2 sec fertig, deinen hab ich nach 5 min. abgebrochen

Re(9): Formel für Verteilung?

le — Thu, 11 Jul 2002 15:14:02 GMT

Noch ein Anmerkung: ich habe bei beiden Programmen die Ausgabe der einzelnen Zwischenergebnisse weggelassen und gebe nur das Endergebnis aus.

Re(8): Formel für Verteilung?

le — Thu, 11 Jul 2002 15:12:23 GMT

Aber trotzdem sieht man ganz klar, _wie_ ineffizient dein Algorithmus ist, ich hab mal meinen mit deinem verglichen:

deiner:
----------

$ time ./verteilung_slow
Anzahl: 176851

real    0m0.766s
user    0m0.758s
sys     0m0.000s

meiner:
-----------

$ time ./verteilung
Anzahl: 176851

real    0m0.004s
user    0m0.001s
sys     0m0.003s

Erstaunlich, oder?

Re(6): Formel für Verteilung?

cltom — Thu, 11 Jul 2002 15:09:27 GMT

werde morgen deinen algorithmus nehmen, dann kann man's auch für n=1000 verwenden jetzt muss ich aber weg.

Re(5): Formel für Verteilung?

cltom — Thu, 11 Jul 2002 15:08:38 GMT

yep, ich weiss, siehe oben

Re(4): Formel für Verteilung?

le — Thu, 11 Jul 2002 15:07:22 GMT

Das ist nicht sehr effizient, da du ja Ergenisse, die du nicht brauchst wegschmeißt (und zwar sehr viele!).

Re(7): Formel für Verteilung?

cltom — Thu, 11 Jul 2002 15:06:58 GMT

Nun, meiner ist bestimmt der ineffizienteste, da alle Möglichkeiten (auch 100 100 100 100 oder 0 0 0 0 durchprobiert werden), aber selbst auf dem ollen Duron 900 hier, geht das für n=100 in ein paar Sekunden

Re(6): Formel für Verteilung?

le — Thu, 11 Jul 2002 14:56:10 GMT

Deine Zahl stimmt.

Hier der C-Code, wie ich draufgekommen bin (ich hoffe, der Browser vermurkst die Formatierung nicht):

#define MAX 100

int main(void)
{

    int a,b,c,d;
    int counter = 0;

    for (a = MAX; a >= 0; a--)
    {
        for (b = MAX - a; b >= 0; b--)
        {
            for (c = MAX - a - b; c >= 0; c--)
            {
                d = MAX - a - b - c;
                printf("%3d %3d %3d %3d\n", a, b, c, d);
                counter++;
            }
        }
        printf("-----------------\n");
    }

    printf("Anzahl: %d\n", counter);

    return 0;
}

Ich bin mir nicht sicher, ob es effizientere Algorithmen für dieses Problem gibt (was natürlich nicht heißen soll, daß dieser Algorithmus effizient ist ).

Re(7): Formel für Verteilung?

cltom — Thu, 11 Jul 2002 14:54:03 GMT

hmm, dein System habe ich nicht ganz gecheckt. Ich kann dir aber umgekehrt mein kleines Programm anbieten, das dir die möglichkeiten ausgibt.

Re(4): Formel für Verteilung?

indic — Thu, 11 Jul 2002 14:53:44 GMT

Neue Idee:

Für jede Summe x der ersten beiden Felder gibt es abhängig von dieser Summe (x+1) Möglichkeiten, sie auf die Felder 1 und 2 zu verteilen (Siehe z.B. vorheriges Posting).
Die Summe der anderen beiden Zahlen ist dann (100-x) und es gibt analog (100-x+1) Möglichkeiten sie zu verteilen auf die Felder 3 und 4.
Also ist das End-Ergebnis = Summe (über x=0 bis 100) von (x+1)*(100-x+1)

= Summe (über x=0 bis 100) von (-x^2 +100x +101)
= Summe (über x=1 bis 100) von (-x^2 +100x +101) + 101

= -338350 + 505000 + 10100 +101 (nach Tafelwerkformeln für die ersten 100 Zahlen bzw. Quadratzahlen)

= 176851 Möglichkeiten

Würd mich ja ma interessieren ob dein Programm das gleiche rauskriegt.

Grüße
indic

Re(6): Formel für Verteilung?

Penguin — Thu, 11 Jul 2002 14:52:34 GMT

Das von mir angewendete System:

Die Zahl der Möglichkeiten steigt in folgender Form an:

Zahl der Möglichkeiten der vorigen Variable (bei 100 ist dieser Wert null - ich hab von 100 runtergezählt) + die Differenz zwischen 100 und dem jetztigen Wert +1.

Dann kommst in Summe auf ca. 100000 (genaue Zahl hab ich wieder gelöscht.)

ABer du kannst gerne mein Makro in einer Excel -Tabelle ausprobieren.

Re(5): Formel für Verteilung?

cltom — Thu, 11 Jul 2002 14:47:30 GMT

so, also hier, was ich gefunden habe:

Die Anzahl an Möglichkeiten steigt in folgender Weise mit der Zahl, die auf die Variablen verteilt werden soll.

Für 4 Variablen:

Zahl    Möglichkeiten
  1           4
  2         10
  3         20
  4         35
  5         56
  6         84
  7        120
  8        165
  9        220
10       286

20     1771
30     5456
40    12341

100 176851
usw.

Ich habe leider noch nicht heraussen, wonach die Formel geht.

Re(4): Formel für Verteilung?

Penguin — Thu, 11 Jul 2002 14:28:40 GMT

für 3 felder kann ichs auch locker berechnen im excel, aber mir fehlt irgendwie die logik für die vierte variable...

Re(4): Formel für Verteilung?

Penguin — Thu, 11 Jul 2002 14:27:28 GMT

bin mir ziemlich sicher dass es 100 über 4 ist, allerdings komm ich auf ca. 100000 möglichkeiten (hab eigene brutalovariante ausprobiert:

Sub y()

a = 28
reihe = 3
alt = 0
While a >= 0
differenz = 100 - a
Range(Cells(reihe, 26), Cells(reihe + alt + differenz + 1, 26)).Value = a
alt = alt + differenz + 1
reihe = reihe + alt
a = a - 1
Wend

End Sub

das gibt mir mal die erste Variable runter.

Im übrigen bezweifle ich, dass deine lösung funktioniert, die quersumme sollte immer 100 ergeben.

wenn du jetzt jede von anfang an runterschreibst, kommt was anderes raus.

Re(3): Formel für Verteilung?

indic — Thu, 11 Jul 2002 14:20:55 GMT

Stimmt, du hast natürlich recht,

meine Argumentation würde zutreffen wenn die 100 "Dinge" alle verschieden wären was hier aber nicht der Fall ist. Da es nur auf die Summe ankommt ist die Anzahl bedeutend kleiner.

100 über 4 glaube ich aber auch nicht, wie folgendes Gegenbeispiel zeigt:
statt 100 soll Summe nur 4 sein und
statt 4 nur 2 Felder zum Aufteilen

Möglichkeiten:
4 0
3 1
2 2
1 3
0 4
also 5 Möglichkeiten, 4 über 2 ist jedoch 6.

Bin noch am grübeln

indic

Re(2): Formel für Verteilung?

cltom — Thu, 11 Jul 2002 13:56:28 GMT

hä?
1.6 *10^60 ??? Wie kommst du auf das?

Es können theoretisch maximal 100*100*100*100 sein (also 10^8), davon fallen aber alle jene weg, die in Summe nicht 100 ergeben. Es sind also wesentlich weniger.

Re: Formel für Verteilung?

indic — Thu, 11 Jul 2002 13:49:10 GMT

Ich denke die Anzahl ist 4 hoch 100, weil du für jedes deiner 100 (gedachten) "Elemente" genau 4 Möglichkeiten hast, *TRÖT* es auf A oder B oder C oder D zu legen.

also nach Schultaschenrechner rund 1,6 * 10 hoch 60 Möglichkeiten = Zeilen.

Ich hoffe, du hast nen schnellen Rechner...

Grüße
indic.

Re(3): Formel für Verteilung?

cltom — Thu, 11 Jul 2002 13:30:41 GMT

Naja, die brutalo-Variante ist, alle 4 Variablen von 0 bis 100 durchlaufen zu lassen, in 4 verschachtelten schleifen und innerhalb der letzten zu prüfen, ob die Summe 100 ergibt. In diesem Fall ausgeben oder eben einen zähler erhöhen.

Das macht 101^4 Durchläufe, also etwas mehr als 10^8 if-Abfragen.

Aussehen würde das so:

for a:=0 to 100 do
begin
  for b:=0 to 100 do
  begin
    for c:=0 to 100 do
    begin
      for c:=0 to 100 do
        if (a+b+c+d=100) then inc(counter); {oder Ausgabe von a,b,c,d}
      end;
    end;
  end;
end;

Ich werde mal eben ausprobieren, wie lange das dauert.

Im übrigen ein interessantes Problem, weiss noch nicht, ob es nun 100 über 4 ist oder doch was anderes.

Re(2): Formel für Verteilung?

Penguin — Thu, 11 Jul 2002 10:39:47 GMT

kannst du die mal posten, vielleicht kanns ichs ja auf vba umlegen...

Re: Formel für Verteilung?

pong — Thu, 11 Jul 2002 10:32:54 GMT

von excel hab ich leida keine ahnung

in c wärens 4 for-schleifen

Formel für Verteilung?

Penguin — Thu, 11 Jul 2002 10:02:15 GMT

Hat zwar nur beinahe etwas mit Programmierung zu tun, aber die anderen Rubriken passen noch weniger:

Ich suche eine Formel, womit ich alle möglichen Verteilungen von 100 (nur ganze Zahlen) auf 4 Variable bekomme:

zB

A        B      C      D
100    0      0      0
99      1      0      0
99     0       1      0
99      0       0     1
98     2       0
.
.
.
.
.

usw.

Die Anzahl wäre schon toll, wirklich brauchen würd ich aber eine Möglichkeit wie ich die einzelnen Felder berechnen kann (in Excel) wie mit

A: =wenn(B =0 und C=0 und D=100-A dann A(vorige Zeile)-1);...

usw.

Weiß jemand Rat?