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/

do góry

M.M. <m...@N...gazeta.pl> napisał(a):

> 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;
> }
>
>

bedzie to raczej po prostu jakis < wzorek ( N , M ) >
tak ze wydaje mi sie ze program jest tu nie bardzo na
miejscu
(ps mozesz mi przypomiec czy slowo static przed nazwa
funkcji znaczy ze jest ona prywatna dla modulu czy cos
innego? - nigdy tego nie uzywalem),

sam nie zajmuje sie raczej tego typu bardziej matematycznym
programowaniem na codzien (jak rowniez i biznesowym, www-owym
itd itd) blizsze mi tematy malych gierek video (ew ogolna teoria
programowania lub ostatnio nawet bardziej tzw temety humanistyczne)
totez nie bardzo mam sile i chec sie 'przelaczac' na obce mi zagadnienia
i wyprowadzac wzorka choc wydaje sie raczej b prosty





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

do góry

jest to mw tak skomplikowane jak licznie desek w plocie
i np dla przedzialu 10 i trzech kresek siega od ok 11*11*11
do 9*8*7 w zaleznosci czy brac zera srodkowe i tez te
z brzega [mam wieksze (i glupsze) problemy]





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

do góry

On pon, 16 sty 2012 12:02:34 in article news:<jf1049$7pn$1@inews.gazeta.pl>
M.M. wrote:
> 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 :/

Theorem two: http://en.wikipedia.org/wiki/Stars_and_bars_(combina
torics)

do góry

Mirek <p...@d...zind.ikem.pwr.wroc.pl> napisał(a):

> On pon, 16 sty 2012 12:02:34 in article news:<jf1049$7pn$1@inews.gazeta.pl>
> M.M. wrote:
> > 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 :/
>
> Theorem two: http://en.wikipedia.org/wiki/Stars_and_bars_(combina
torics)
Dobre, dzieki :)

Lezy u mnie na polce ksiazeczka "kombinatoryka dla programistow", lezy i
rdzewieje, nie mam czasu na czytanie :(

Pozdrawiam


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

do góry

On 2012-01-17, M.M. <m...@g...pl> wrote:
> Mirek <p...@d...zind.ikem.pwr.wroc.pl> napisał(a):
>
>> On pon, 16 sty 2012 12:02:34 in article news:<jf1049$7pn$1@inews.gazeta.pl>
>> M.M. wrote:
>> > 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 :/
>>
>> Theorem two: http://en.wikipedia.org/wiki/Stars_and_bars_(combina
torics)
> Dobre, dzieki :)
>
> Lezy u mnie na polce ksiazeczka "kombinatoryka dla programistow", lezy i
> rdzewieje, nie mam czasu na czytanie :(

Modelowy przykład, jak to formalne wykształcenie, które przez wiele osób
jest uważane za doskonale zbędne, jest jednak potrzebne w pracy
programisty. I jak się samodzielne zdobywanie odpowiednika tego
formalnego wykształcenia w pracy odbywa ("nie mam czasu na czytanie").

--
Secunia non olet.
Stanislaw Klekot

do góry

On Monday, January 16, 2012 12:58:43 PM UTC, Mirek wrote:
> Theorem two: http://en.wikipedia.org/wiki/Stars_and_bars_(combina
torics)

Zadanie robi sie ciekawsze, kiedy dodawane liczby maja inne ograniczenie niz docelowa
suma.

RW

do góry

Stachu 'Dozzie' K. <d...@g...eat.some.screws.spammer.invalid> napisał(a):

> > Lezy u mnie na polce ksiazeczka "kombinatoryka dla programistow", lezy i
> > rdzewieje, nie mam czasu na czytanie :(
>
> Modelowy przykład, jak to formalne wykształcenie, które przez wiele osób
> jest uważane za doskonale zbędne, jest jednak potrzebne w pracy
> programisty.

Coz moge rzec. Przez okolo 15 lat zawodowej praktyki programisty
zdarzylo mi raptem jeden raz, ze musialem policzyc calke. Calka nie
byla trywialna, ale bylem swiezo po studiach, troche pamietalem, troche
sciaglalem z internetu i zdaje sie ze po 30 minutach mialem wzor
analityczny. Korzysci byly fajne, bo calka dawala polozenie animowanych
obiektow w funkcji czasu - czyli bez wzgledu na szybkosci i obciazenie
komputera animacja wylgadala zawsze tak samo. Za to z pracy prawie
mnie zwolnili "bo animacje robi sie korzystajac z czegos gotowego", a
to cos gotowe na starszym komputerze mulilo sie i mulilo... uzytkownik
nie mogl przez flasha zwyczajnie skorzystac z interfejsu na stronie.

Pochodne jakby czesciej... jesli dobrze pamietam to musialem ich
jeden raz uzyc w pracy zawodowej - nie bylo wyjscia, naprawde trzeba bylo.

Generalnie lubie sie uczyc, a swego czasu musialem znac teorie
przynajmniej na poziomie umozliwiajacym zdanie egzaminow. Tyle ze
nie mam prawie zadnej motywacji do podtrzymywania tej wiedzy. Problem
poruszony w tym watku i wiele innych problemow o ktorych na grupach
pisze, z reguly nie maja nic wspolnego z moja praca zawodowa. Z reguly w
pracy zawodowej uzywam matematyki na poziomie szkoly podstawowej, z rzadka
ze szkoly sredniej. Tematy na grupach z reguly poruszam po to zeby
cos sobie przypomniec, zeby calkowicie z glowy nie wylecialo, z reguly
sa to zadania wymyslone przeze mnie dla zwyklego treningu.

To co spotykam w pracy zawodowej to z reguly koszmarek. Przede wszystkim
spotykam ludzi ktorzy maja o sobie niezwykle wysokie zdanie i bardzo sie
chwala a w praktyce sa wg mojej oceny przecietni albo ponizej przecietnej.
W pracy dzialaja zwierzece instynkty...

Pamietam swoj pierwszy wiekszy projekt. Kumpel napisal jakies algorytm,
zadanie trudne, kod niezrozumialy i dlugi, testow brak. Mialem 100% pewnosci
ze zostal w jego kodzie chociaz jeden blad. Wzialem ten jego kod, dopisalem
na szybko tyle testow ile zdolalem, a na koniec if( ! test() ) abort();.
Kumpel to zobaczyl i do szefa, ze robie niepotrzebna dwa razy i wstawiam
abort, a przez to program moze sie wywalic, no i ja na dywaniku. Tak
oslupialem ze szczeka opadla mi do parkietu. No ale nic, jakos ten
moj abort przetrwal w kodzie do chwili testow w realu. Oczywiscie mialem
racje i oczywiscie byl blad i oczywiscie program sie wywali. Wiec co zrobil
moj kumpel z pracy? Poszedl do szefa i powiedzial ze to przeze mnie bo ja
wstawilem aborta i ja znowu na dywaniku. Na nastepny dzien juz do
pracy nie poszedlem - z wlasnej woli.

Niestety w drugiej bylo tak samo i w trzeciej tez... a teraz to olewam.
Jak chca zebym zrobil badziewnej jakosci kod to tak robie. I tak
sprytny marketingowiec wcisnie go klientom. Na pozadku dziennym mam
zakazy uzywania klas bo kod jest za trudny dla innych programistow.
Dwa razy w zyciu mialem do wykonania calkiem spory projekt w ktorym byl
zakz uzywania zmiennych loklanych!!! Co to byla za masakra.... Zakaz
abortow i wyjatkow to prawie norma - to nie jest statystyka z jednej
firmy.

Po co mam wykuc na blache podrecznik z kombinatoryki czy analizy
matematycznej jesli w praktyce programistycznej nie moge swobodnie
korzystac z takich podstawowych rzeczy jak klasy, kroswalidacja czy
niezmienniki? Z rzadka do nich siegam, ale tylko dlatego ze lubie,
praca programistyczna nie daje mi takiej motywacji.

Pozdrawiam!


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

do góry

Dnia Tue, 17 Jan 2012 09:30:17 +0000 (UTC), Stachu 'Dozzie' K. napisał(a):

> On 2012-01-17, M.M. <m...@g...pl> wrote:
>> Mirek <p...@d...zind.ikem.pwr.wroc.pl> napisał(a):
>>
>>> On pon, 16 sty 2012 12:02:34 in article news:<jf1049$7pn$1@inews.gazeta.pl>
>>> M.M. wrote:
>>> > 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 :/
>>>
>>> Theorem two: http://en.wikipedia.org/wiki/Stars_and_bars_(combina
torics)
>> Dobre, dzieki :)
>>
>> Lezy u mnie na polce ksiazeczka "kombinatoryka dla programistow", lezy i
>> rdzewieje, nie mam czasu na czytanie :(
>
> Modelowy przykład, jak to formalne wykształcenie, które przez wiele osób
> jest uważane za doskonale zbędne, jest jednak potrzebne w pracy
> programisty. I jak się samodzielne zdobywanie odpowiednika tego
> formalnego wykształcenia w pracy odbywa ("nie mam czasu na czytanie").

To jest pół prawdy. Cała jest taka, że czytać należy zawsze.

do góry

M.M. <m...@g...pl> napisał(a):

> Stachu 'Dozzie' K. <d...@g...eat.some.screws.spammer.invalid> napisał(a):
>
> > > Lezy u mnie na polce ksiazeczka "kombinatoryka dla programistow", lezy i
> > > rdzewieje, nie mam czasu na czytanie :(
> >
> > Modelowy przykład, jak to formalne wykształcenie, które przez wiele osób
> > jest uważane za doskonale zbędne, jest jednak potrzebne w pracy
> > programisty.
>
> Coz moge rzec. Przez okolo 15 lat zawodowej praktyki programisty
> zdarzylo mi raptem jeden raz, ze musialem policzyc calke. Calka nie
> byla trywialna, ale bylem swiezo po studiach, troche pamietalem, troche
> sciaglalem z internetu i zdaje sie ze po 30 minutach mialem wzor
> analityczny. Korzysci byly fajne, bo calka dawala polozenie animowanych
> obiektow w funkcji czasu - czyli bez wzgledu na szybkosci i obciazenie
> komputera animacja wylgadala zawsze tak samo. Za to z pracy prawie
> mnie zwolnili "bo animacje robi sie korzystajac z czegos gotowego", a
> to cos gotowe na starszym komputerze mulilo sie i mulilo... uzytkownik
> nie mogl przez flasha zwyczajnie skorzystac z interfejsu na stronie.
>
> Pochodne jakby czesciej... jesli dobrze pamietam to musialem ich
> jeden raz uzyc w pracy zawodowej - nie bylo wyjscia, naprawde trzeba bylo.
>
> Generalnie lubie sie uczyc, a swego czasu musialem znac teorie
> przynajmniej na poziomie umozliwiajacym zdanie egzaminow. Tyle ze
> nie mam prawie zadnej motywacji do podtrzymywania tej wiedzy. Problem
> poruszony w tym watku i wiele innych problemow o ktorych na grupach
> pisze, z reguly nie maja nic wspolnego z moja praca zawodowa. Z reguly w
> pracy zawodowej uzywam matematyki na poziomie szkoly podstawowej, z rzadka
> ze szkoly sredniej. Tematy na grupach z reguly poruszam po to zeby
> cos sobie przypomniec, zeby calkowicie z glowy nie wylecialo, z reguly
> sa to zadania wymyslone przeze mnie dla zwyklego treningu.
>
> To co spotykam w pracy zawodowej to z reguly koszmarek. Przede wszystkim
> spotykam ludzi ktorzy maja o sobie niezwykle wysokie zdanie i bardzo sie
> chwala a w praktyce sa wg mojej oceny przecietni albo ponizej przecietnej.
> W pracy dzialaja zwierzece instynkty...
>
> Pamietam swoj pierwszy wiekszy projekt. Kumpel napisal jakies algorytm,
> zadanie trudne, kod niezrozumialy i dlugi, testow brak. Mialem 100% pewnosci
> ze zostal w jego kodzie chociaz jeden blad. Wzialem ten jego kod, dopisalem
> na szybko tyle testow ile zdolalem, a na koniec if( ! test() ) abort();.
> Kumpel to zobaczyl i do szefa, ze robie niepotrzebna dwa razy i wstawiam
> abort, a przez to program moze sie wywalic, no i ja na dywaniku. Tak
> oslupialem ze szczeka opadla mi do parkietu. No ale nic, jakos ten
> moj abort przetrwal w kodzie do chwili testow w realu. Oczywiscie mialem
> racje i oczywiscie byl blad i oczywiscie program sie wywali. Wiec co zrobil
> moj kumpel z pracy? Poszedl do szefa i powiedzial ze to przeze mnie bo ja
> wstawilem aborta i ja znowu na dywaniku. Na nastepny dzien juz do
> pracy nie poszedlem - z wlasnej woli.
>
> Niestety w drugiej bylo tak samo i w trzeciej tez... a teraz to olewam.
> Jak chca zebym zrobil badziewnej jakosci kod to tak robie. I tak
> sprytny marketingowiec wcisnie go klientom. Na pozadku dziennym mam
> zakazy uzywania klas bo kod jest za trudny dla innych programistow.
> Dwa razy w zyciu mialem do wykonania calkiem spory projekt w ktorym byl
> zakz uzywania zmiennych loklanych!!! Co to byla za masakra.... Zakaz
> abortow i wyjatkow to prawie norma - to nie jest statystyka z jednej
> firmy.
>
> Po co mam wykuc na blache podrecznik z kombinatoryki czy analizy
> matematycznej jesli w praktyce programistycznej nie moge swobodnie
> korzystac z takich podstawowych rzeczy jak klasy, kroswalidacja czy
> niezmienniki? Z rzadka do nich siegam, ale tylko dlatego ze lubie,
> praca programistyczna nie daje mi takiej motywacji.
>
>

to zalezy co sie robi, bo praca programisty spaja wiele
rozmaitych terytoriow - jak lubisz kombinatoryke w programowaniu
czy metody numeryczne to musialbys poszukac
1. takiej roboty,
mi jest to np obecnie obce, tak samo nie dotyczy mnie wogole
2. programowanie baz danych (kiedys przez pol roku uzywalem sqla
to sie troche nauczylem ale to dawne czasy),
3. stronek www, czy wogole
4.jakichs systemow rozproszonych (po kilku lub wiecej kompach)

5. 6. 7. itd itd












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

do góry