[c++]combinatoriek

[Verwijderd]

het gaat om de volgende probleem http://www.net-force.nl/challenge/level603/index.php
de logica is als volgt om te weten hoeveel mogelijkheden er zijn met 1 kistje moet je 1+0+0+0+0+0 doen
voor 2 kistjes geldt 1+1+1+1+1+1
voor 3 kistjes geldt 1+2+3+4+5+6
voor 4 kistjes geldt 1+3+6+9+12+15
voor 5 kistjes geldt 1+4+10+16+22+28
voor 6 kistjes geldt 1+5+15+25+35+45
enz enz
dit helemaal uit te gaan schtijven tot de 500 is gekkenwerk dus ik d8 ik maak een simpel progje.

C++:

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
int main()
{
  int a=1, b=2, c=3, d=4, e=5, f=6, n, v1=28, v=0, con;
    cout << v1 <<" bij 1 kistjes\n";
    cin >> n;
  for (; n>0; n--)
   {
    v=1+((b=1+b))+((c=b+c))+v;
    con=c-b;
    v=v+(d=c+con)+(e=d+con)+(f=e+con);
   }
   cout << v+v1 <<"\n";
   system ("pause");
  return 0;
}

voor 1 of 2 of 5 of 6 kistjes werkt het, k moet alleen wel 3 minder invullen dan ik wil, dus als ik met 4 kistjes wil weten moet ik 1 invullen bij n. Als ik 497 invul moet ik dan weten hoeveel mogelijkheden er zijn om die 5 ballen over alle kistjes te verdelen. Daar komt dan uit 207709250. Als ik dit invul bij net force krijg ik dat het verkeerd is, wat doe ik nu fout
btw ik ben een n00b in proggen dus misshien dat ik sommige dingen omsachtig heb gedaan, maar dat maakt nu niet uit;)

[Tim]

Ik snap de vraag eigenlijk al niet?

Bij 2 kopjes heb je toch veel meer mogelijkheden? (5 boven 2=20)
En wat is die 0? Een leeg kopje? En waarom staat de mogelijkheid 1 4 er 2x tussen?

[edit] ...

[ Voor 24% gewijzigd door Tim op 25-04-2003 19:47 ]

[Verwijderd]

neej ik heb alles uitgeschreven, kijk maar op de site je hebt niet meer dan 6 mogelijkheden voor de 2

[PiepPiep]

De tweede uitgeschreven is
0 5
1 4
2 3
3 2
4 1
5 0

Als je de derde zou uitschrijven zou dit het begin zijn
0 0 5
0 1 4
0 2 3
0 3 2
0 4 1
0 5 0
1 0 4
1 1 3
1 2 2
1 3 1
1 4 0
2 0 3
2 1 2
2 2 1
en nog een zooi mogelijkheden

[Verwijderd]

ik heb ze tot de 6 uitgeschreven. voor de eerste heb je
1+0+0+0+0+0
voor de tweede
1+1+1+1+1+1
voor de derde
1+2+3+4+5+6
de eerste van de reeks is altijd1 en de2de is 1 groter dan de vorige 2de.
Om de derde te vinden moet je bij de 2de de vorige 3de optellen hier zo dat zijn 3(de tweede)+3(de derde van de vorige). Je hebt dan de eerste 3 getallen die je moet optellen. Omdat de optelsom een rekenkundige rij is kun je de verschil nemen van de 3 en de 2de dan heb je de groeiconstante. En daarmee kun je dus de overige 3 bereken.
1+3+6+9+12+15
1+4+10+16+22+28
1+5+15+25+35+45
1+6+21+36+51+66
enz tot je er 500 hebt

[Tim]

ah, ik snap het

#1 je algoritme is verkeerd, ga maar eens verder met schrijven en dan zie je het vanzelf
#2 Je hebt last van een overflow, een int kan maximaal tot ergens in de 2 miljard, gebruik een double of een float

C:

#include <iostream.h>

void main()
{
    float  A=1, B=1, C=1, D=1, E=1, F=1;
    float pA=1,pB=1,pC=1,pD=1,pE=1,pF=1;
    float totaal=5;
    for( int i = 0; i < 499; i++ )
    {
        A = 1;
        B = A + pB;
        C = B + pC;
        D = C + pD;
        E = D + pE;
        F = E + pF;
        totaal += A+B+C+D+E+F;
        pA=A; pB=B; pC=C; pD=D; pE=E; pF=F;
        cout << A << "+" << B << "+" << C << "+" << D << "+" << E << "+" << F << endl;
    }
    cout << totaal << endl << "---"  << endl;
}

Probleem is echter dat ik dan een niet zo nauwkeurig antwoord krijg, geen idee hoe ik dat moet aanpassen

[Verwijderd]

en een long int dan??

[PiepPiep]

long int redt het ook niet
ik heb het geprobeert met een long long int in djgpp, maar die werkt niet goed of ik doe iets fout, zal die 2e wel zijn :-)
als ik sizeof(long) vraag is die 4 dus 32 bits, sizeof(long long) geeft 8 en zou dus wel 64 bits moeten zijn.
Mja, daar ga ik nu ff verder op klooien

[Verwijderd]

k snap je algoritme niet

[ Voor 4% gewijzigd door Verwijderd op 25-04-2003 21:28 ]

[Tim]

overflow kan je oplossen met __int64 (visual C++) of long long (djgpp blijkbaar)

Algoritme is niet zo moeilijk, alhoewel ik betwijfel of het goed is, want volgens die site klopt het niet. Ik heb gewoon de eerste mogelijkheden (tot 4 doosjes), en dit kwam er uit.
Het zou moeten kloppen. Als je er 0 in het eerste bakje doet, heb je dezelfde oplossing als bij het vorige aantal bakjes.

[edit]Hebbes: verkeerd geteld

22359848185500

C:

#include <iostream>
#include <iostream.h>

void main()
{
    __int64 A=1, B=1, C=1, D=1, E=1, F=1;
    __int64 pA=1,pB=0,pC=0,pD=0,pE=0,pF=0;
    __int64 totaal=1;
    for( int i = 1; i < 500; i++ )
    {
        A = 1;
        B = i;
        C = B + pC;
        D = C + pD;
        E = D + pE;
        F = E + pF;
        totaal += A+B+C+D+E+F;
        pA=A; pB=B; pC=C; pD=D; pE=E; pF=F;
        printf("%I64d + %I64d + %I64d + %I64d + %I64d + %I64d \n", A, B, C, D, E, F);
    }
    printf("%I64d \n", totaal);


}

[ Voor 42% gewijzigd door Tim op 25-04-2003 22:02 ]

[djc]

Jezus, anders zet je dit topic op nog acht fora neer.

Software & Multimedia, Onzin, Programming & Webscripting.

[PiepPiep]

Volgens mij is het zo dat
Als je 1 knikker moet verdelen, dat je het aantal bakjes als het aantal oplossingen hebt.
Als je 1 bakje hebt is de oplossing 1
Als je meer hebt ligt het anders, dan is de oplossing het volgende opgetelt :
0 in het eerste bakje, aantal = zelfde als 1 bakje minder.
1 in het eerste bakje, aantal = zelfde als 1 bakje minder met 1 knikker minder.
....
alles-1 in het eerste bakje, aantal = zelfde als aantal bakjes nog over
Dus dit geeft
F(knikkers, bakjes) = F(knikkers, bakjes-1) + F(knikkers-1, bakjes-1) .... F(1, bakjes-1)
Als je F(knikkers-1, bakjes) zou gaan uitschrijven zou je simpel hetzelfde krijgen, behalve de F(knikkers, bakjes-1) dus krijg je

F(knikkers, bakjes) = F(knikkers, bakjes-1) + F(knikkers-1, bakjes)
Onthoud wel dat
F(1, bakjes) = bakjes (1 knikker kan in alle bakjes als mogelijkheid liggen)
F(knikkers, 1) = 1 (die knikkers kunnen maar in 1 bakje dus 1 mogelijkheid)

Volgens mij is het op die getallen manier zeg maar van de TS dan als volgt

1 1 1 1 1
2 3 4 5 6
3 6 10 15 21
4 10 20 35 56
5 15 35 70 126
enz....
500 *grootgetal* *grootgetal* *grootgetal* *grootgetal*

En tot slot moeten dan als ik die site goed begrijp van elke regel het 5 getal worden genomen en die bij elkaar opgetelt is dan de oplossing.
Dus 1+6+21+56+126+..........
Geloof dat ik met excel op iets van 1.2E11 kreeg ofzo, alleen heb ik die al gesloten dus kan ik het niet meer zien
In C lukt het me dus nog niet, long long is wel netjes 64 bits volgens sizeof maar toch komt er iets van 13000 uit ofzo.
Ja, ik deed printf("%lld", totaal); voor de mensen die denken dat ik %ld gebruikte

[edit]
Bah.. net te laat

[Verwijderd]

ok bedankt iedereen

[juanita]

You have 5 balls that you have to divide (put the balls in the cups) between a number of cups in all possible ways.

1 cup:
---
|5|
---
1 possibility
Total: 1 possibility

2 cups:
-----
|1|4|
-----
|2|3|
-----
|3|2|
-----
|4|1|
-----
|5|0|
-----
|0|5|
-----
6 possibilities
Total: 7 possibilities

3 cups:
21 possibilities
Total: 28 possibilities

Continue until you have 500 cups. The total of possibilities from 1 to 500 is the answer.

standaard combinatoriek probleem. Distribute m balls among n urns in which the urns are labeled and the balls are not. Empty urns allowed.

In wiskundige vorm:
hoeveel oplossingen heeft de volgende vergelijking
u₁ + u₂ + ... + u_n = m
u_i >= 0

De oplossing voor dit probleem is C(m + n - 1, m). Nu nog even sommeren.

Geen ingewikkelde C++ zooi voor nodig.
Met excel of Haskell even sommeren geeft 22359848185500

klopt dat?

[ Voor 3% gewijzigd door juanita op 11-08-2005 18:19 ]

[juanita]

Die C(m + n - 1, m) is de oplossing van de recurente vergelijking (die kan je ook gewoon gebruiken uiteraard maar dat is iets minder voor de complixiteit van het probleem)

f(m, n) = f(m, n - 1) + f(m - 1, n)

met randvoorwaarden

f(m, 1) = 1 en
f(1, n) = n.

[ Voor 25% gewijzigd door juanita op 11-08-2005 18:29 ]

[NMe]

Je bent er al vaker op gewezen dat oude topics schoppen onwenselijk is. Kijk liever even naar de datum van de laatste post voordat je repliet. De kans is behoorlijk klein dat een topicstarter na ruim 2 jaar nog steeds met dit probleem zit.

Om te voorkomen dat hier discussies door elkaar gaan lopen, en mensen gaan replyen op anderen die hier misschien allang niet meer rondlopen, zet ik een slotje op dit topic.