Hey

Jestem prawie pewny ze jest na to analityczny wzor. Przypomni
ktos? Problem: na ile sposobow mozna zsumowac N liczb,
tak aby kazdy skladnik byl z przedzialu domknietego <0,M> i
suma zeby wynosila M. Oczywiscie chodzi o liczby calkowite.

Przykladowe sumy dla N=3 i M=5
5 + 0 + 0 = 5 // poprawna
3 + 2 + 0 = 5 // poprawna
2 + 2 + 1 = 5 // poprawna
2 + 2 + 2 = 6 // niepoprawna
2 + 2 + 0 = 4 // niepoprawna
-1 + 6 + 0 = 5 // niepoprawna

Dla liczb z przedzialu od 1 do M mozna to zadanie rozwiazac zamieniajac
kodowanie binarne na kodowanie unarne. Np. na ile sposobow mozna zsumowac
3 liczby aby uzyskac 10? Kreski to liczby kodowane unarnie, a dwukropki
to separatory pomiedzy liczbami:
||:|||||:||| -> 2 + 5 + 3 = 10

Teraz widac ze zadanie mozna przedefinowac:
Na ile sposobow mozna rozstawic dwukropki pomiedzy kreskami?
Mamy (9 nad 2) = 36

A jak to rozwiazac jesli zera tez sa dozwolone? Ponizszy programik niby
rozwiazuje, ale ma zlozonosc wykladnicza wzgledem (M+1) ^ N :/

Pozdrawiam
----------------------------------------------------
-------------------

#include <cstdlib>
#include <cstdio>

#define MAX (8) // M
#define DEPTH (10) // N

typedef int ityp;
typedef const int cityp;
typedef unsigned int utyp;
typedef const unsigned int cutyp;

static utyp find( cutyp sum=0 , cutyp depth=0 ) {
if( depth == DEPTH )
return sum == MAX; // if( sum == MAX ) return 1; else return 0;
utyp res = 0;
for( ityp i=0 ; i<=MAX ; i++ )
res += find( sum+i , depth+1 );
return res;
}

int main( int argc, char *argv[] ) {
utyp sum = find();
printf("sum = %u\n",sum);
return 0;
}




--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/