[c++/logica]combinatoriek

[Dr HenDre]

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.

PHP-code:

#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

[dafelix]

over het maximum heen missgien?

simpel progje?

Ik weet het niet hoor, maar hier snap ik niks van:

v=v+(d=c+con)+(e=d+con)+(f=e+con);

1: Gebruik volledige variabelenamen, zodat je weet waar elk voor is
2: Schrijf het over meedere regels uit (eventueel met commentaar)
3: Doe bovenstaande en het is makkelijker debuggen.

[Dr HenDre]

eddie schreef op 25-04-2003 @ 20:25:
Ik weet het niet hoor, maar hier snap ik niks van:

v=v+(d=c+con)+(e=d+con)+(f=e+con);

con is de groeiconstante die kun je vinden door van het 3de getal c het tweede getal af te trekken (b) je krijgt dan met welke constante hij de hele tijd groeit. Als je dat hebt kun je de volgende uitrekenen door de vorige plus de constante. dus d=c+con en e=d+con enz

Klopt het derde antwoord van hun site wel?

Bij 3 kopjes heb je 21 mogelijkheden volgens hun. Ik kom aan 15:

014
023
032
041
401
302
203
104
410
320
230
140
005
050
500

15.
Welke mis ik?

[edit]
Oeps...

De 423, 432 etc verdeling vergeten
[/edit]

[Dr HenDre]

ok ik heb het, mn algoritme klopte niet en k had last van overflow. Een int gaat maar tot iets in de 2 miljard
http://gathering.tweakers.net/forum/...26214#17626214

[Dr HenDre]

Dr HenDre schreef op 25-04-2003 @ 21:14:
ok ik heb het, mn algoritme klopte niet en k had last van overflow. Een int gaat maar tot iets in de 2 miljard
http://gathering.tweakers.net/forum/...26214#17626214

maar met een double/float krijg je tog kommagetallen

Ik heb het in Perl geprobeerd (en een andere methode gebruikt), maar toch het verkeerde antwoord..

PHP-code:

#!/usr/bin/perl

use integer;
use Math::BigInt;

# Faculteit uitrekenen (4 * 3 * 2 * 1)
sub fac
{
    my $val = shift @_;

    if( $val > 1 )
    {
        return $val *    &fac( $val - 1 ) ;
    }
    else
    {
        return 1;
    }
}

my $cups = 500, $options = new Math::BigInt 0, $currentcups = 0, $balls = 5;

for( ; 1 < $cups; $cups--)
{
    $currentcups = $balls * &fac($cups) - $cups**2;
    $options += $currentcups;
    
}
# Niet vergeten de eerste mogelijkheid erbij op te tellen
print 'Aantal mogelijkheden: ' . ++$options . "\n"; 


Uitkomst:

Aantal mogelijkheden: +3623367028

[edit]
Fuck... overflow...
[/edit]

[Dr HenDre]

dat zuigt dus zwar, overflow

Jah, de faculteit van 500 vindt hij niet zo leuk

Dit lijkt er al meer op

'Aantal mogelijkheden: +611290999905393086744191131946743060868392324922630244293527831063706 8158489571045497708629947233338068508121356894156053109192088904058830 0123666847143530009751850610095261690511849764233302518402298624765714 3474298445246479522569352233237598027541152045607212167577822006951979 1784118029865750795551477893914216741264629416317787927782394938613729 6923260572386489158031093278419622794414335617718963639277105366238749 8596218461994537327773182606449350937899729117233395689160110570179452 8608277377516831521475056727181979344215397731890268043619809622525807 8796091265459932472564410015615452994025450613768567959227647208338051 8535575192086922583351995165318252811379151774516799360387586171568729 5042746806486018762157029887799750412001382197785980601450852758303036 5678251440539687372659257259151829381963394797404527386679127531166897 9247318018994833217104833344390364788319138758809160198116126753034303 5482396601315662613020273709625193203753309248450541818505951017742382 8641171138716359885939090013477910232369558829142558365609101309439757 8310028428251670046123739739342369310553997402161796552519526278221168 2644602062909812

Output completed (4 min 1 sec consumed) - Normal Termination'

Maar hij klopt nog steeds niet

[Dr HenDre]

#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); 


}

via GoT