Kombinatorika

Zanima me kako napisati program u c++ koji bi pronalazio koliko ima mogučih kombinacija i ispisivao ih?

Da pojasnim:

imamo niz u koji unesemo 4 broja i cilj programa je pronaći koliko je mogučih četveroznamenkstih brojeva koji su načinjeni od tih brojeva

ili

u niz unesemo nekoliko brojeva čiji zbroj je 100 i zanima nas na koliko  sve načina možemo dobiti zbroj 51 ili više

glavnina onog što me zanima je kako kombinirati prvo polje niza sa ostalima u nizu, pa onda drugo polje sa svima pa i sa prvim, i tako dalje

ako je moguće molio ih i pojašnjenje budući da tek počinjem sa programiranjem ovakvih zadataka

:) hvala unaprijed

hvala na pomoći....

link,stranica 24 za prvi zadatak.

A ovo drugo nema neku matematičku formulaciju (iako bi se dalo nešto napravit, sjećam se sličnih zadataka iz diskrete matematike), tu mislim da ćeš imat više koristi od neke tehnike dinamičkog programiranja.

Možda čak spremat u matrice neke sume pa kasnije čitat. Nemam neku pametnu ideju odmah na prvu, siguran sam da tu ima natjecatelja iz programiraja, oni su dosta takvih zadataka riješili :D

Međutim, ako ćeš kombinacije ispisati onda moraš uzeti i dovoljan broj petlji i uvjete za ispis shodno vrsti kombinatorike.

međutim, možda netko zna drugi način

Zvuči mi ko neka rekurzija...

int brojac=0;

void fja(int*niz, int duljina, int suma,int iduci)

{

       if (suma%10==0) ++brojac;

       fja(niz,duljina, suma+niz[iduci],iduci+1);

       fja(niz, duljina,suma,iduci+1);

}

nešto takvo (sa još provjerom dal idući ispada iz niza). Dakle u svakom koraku rekurzije pogledat kaj se desi sa sumom kad joj dodamo idući element i kad ne dodamo. I tako vrtit

p.s. ovo je samo ideja :D

varijabla k je suvišna (da je sad ne brišem)!

pogledaj možeš li ga preraditi, uglavnom, ovo je način sa iteracijom

ako ne ide, onda rekurzija

Ne treba ti rekurzija (jako rijetko optimalno rjesenje trazi rekurziju. Najbolje je opet koristiti dinamicko programiranje, a koristit cemo i jedan mali trik koji ce nam drasticno smanjiti slozenost i poterbu za memorijom (to mozemo jer nas ne zanimaju sami zbrojevi nego samo koliko ih je djeljivih sa 10).

imat cemo polje a, od 10 intova. a[n] ce predstavljati broj zbrojeva koji pri djeljenju s 10 daju ostatak n, pa ce a[0] predstavljati broj zbrojeva koji su djeljivi s 10 (ostatak 0).

Na pocetku imamo zbroj od nula clanova, njegov zbroj je 0, pa je a[0] = 1, a ostali su 0 (ako ne zelis brojati taj zbroj, onda na sammom kraju smanjis a[0] za 1). Sad gledamo za prvi broj - mozemo ga pribrojiti svakom dosadasnjem zbroju i tako dobiti nove zbrojeve (ako ti nije jasno o cemuse radi, reci pa cu detaljnije objasniti), i tako za svaki broj. Na kraju je rjesenje a[0]:

for(int i = 0; i < n; i++)

{

    for(int j = 0; j < 10; j++)

         tmp[j] = a[j] //moramo privremeno spremiti dosadasnje zbrojeve da ne zbrojimo dvaput, sto nam se lako moze dogoditi ako nismo oprezni

      for(int j = 0; j < 10; j++)   {

         a[j + broj[i] % 10] = tmp[[j + broj[i] % 10] + tmp[j];

    }

}

Za onaj zadatak u kojem zbroj mora biti 51 imamo slijedece(varijable i, j, n nisu konzistente s petlhjom koju sam bio napisao):

Zadatak rjesavamo dinamicki, to znaci da cemo prvo rjesavati jednostavniji problem, pa cemo polako nadogradivati rjesenje za jednostavniji problem, dok ne dodemo do rjesenja za zadani. U nasem slucaju to znaci da cemo gledati koliko kombinacija zbrojeva postoji za prvih n brojeva, gdje ce n krenuti od 0, i ici do ukupnog broja zadanih brojeva. Vazno je napomenuti da nas ovjde zanima broj kombinacija, a ne koje su to konkretno kombinacije, pa nam je za svaki slijedeci broj bitno samo na koliko se nacina od prethodnih brojeva mogu dobiti svaki zbroj. Takoder je bitno da imamo gornju granicu zbrojeva koji nas zanimaju (moze se i bez, ali se malo komplicira).

Polje a[i] ce nam u svakom koraku oznacavati broj kombinacija (zbrojeva) koje daju zbroj i za prvih n brojeva. Najjednostavniji je slucaj kad nemamo niti jedan broj, tada na jedan nacin mozemo dobiti zbroj 0 (ne uzmemo niti jedan broj, ili uzmemo sve, kako hoces ), a niti jedan drugi zbroj naravno ne mozemo dobiti. Povecamo n na 1, i sad promatramo isti problem za samo jedan broj: svakom prethodnom zbroju mozemo ili pribrojiti taj broj ili ne pribrojiti. Unutarnju petlju radimo silazno da bismo izbjegli pribrojavanje istog broja vise puta:

Primjer:

Recimo da je prvi broj jednak 3. Tada vidimo da je jedini zbroj koji smo dosad mogli dobiti 0 (jer a[i] = 0 za i != 0), sto znaci da zelimo postaviti a[3] = 1 (nulu smo mogli dobiti na jedan nacin, a 3 niti na jedan - znaci da cemo sada 3 moci dobiti tako da svakom zbroju koji je davao 0 pribrojimo 3 (a[0] nacina), ili da svakom zbroju koji je davao 3 ne pribrojimo 3 (a[3] nacina)). No, u kasnijim koracima mi necemo unaprijed znati koje zbrojeve mozemo postici iz prethodnih zbrojeva, pa cemo na neki nacin morati pregledati polje. Ako bismo krenuli ispocetka dogodilo bi nam se slijedece - vidimo da a[0] = 1, pa postavimo a[3] = 1, no sad kad dodemo do a[3], vidimo da je a[3] = 1 pa postavimo a[6] = 1! Ako krenemo pregledavati poslje od pocetka, dogodit ce nam se da cemo svaki broj pribrojavati vise puta, i dobit cemo broj kombinacija u kojem se svaki broj moze proizvoljan broj puta pojaviti u zbroju. To nije ono sto zelimo - nama se svaki broj moze pojaviti najvise jednom, pa moramo na neki nacin izbjeci to visestruko pribrojavanje. U ovom slucaju je to jednostavno bilo izvesti silaznom petljom, jer se uvijek updateaju a[i] sa vecim indeksom i, pa znamo da nam se nece dogoditi da koristimo vec updateanu verziju zbroja.

Ovo je prilicno slicno matematickoj indukciji zapravo - baza su nam vrjiednosti polja a za n = 0, jer je to rjesenje problema sa 0 zadanih brojeva. Ako imamo rjesenje za prvih k brojeva (n = k), tada promotrimo k+1-vi broj:

Svakom prethodnom zbroju mozemo ili pribrojiti nas novi broj (broj[k + 1]) ili ne pribrojiti. To znaci da cemo zbroj jednak i + broj[k + 1] moci dobiti na a[i] nacina jer smo na toliko nacina mogli od prethodnih k brojeva dobiti i, i sad svakom od tih zbrojeva dodamo broj[k + 1] plusa[j + broj[k + 1]] jer smo na toliko nacina od prethodnih k brojeva mogli dobiti zbroj i + broj[k + 1], i sad niti jednom od njih ne dodamo broj[k + 1]. Novo dobiveno polje a nam upravo opisuje na koliko nacina mozemo dobiti svaki od zbrojeva izmedu 0 i 51 od prvih k+1 brojeva.

Kada navedeni postupak prodemo za sve zadane brojeve, dobit cemo broj kombinacija za svaki od zbrojeva izmedu 0 i 51, a ono sto nas zanima u zadatku je upravo a[51], pa je to i rjesenje.

Razlika u ovom drugom zadatku je u tome da nam silazna petlja ne bi pomogla u izbjegavanju redundancije, tj svejedno bismo neke brojeve vise puta pribrojili zato sto ostaci pri dijeljenju s 10 idu u krug (nakon 9 slijedi 0) za razliku od zbrojeva koji stalno rastu. Zato koristimo pomocno privremeno polje tmp u koje pospremimo vrijednosti od a da budemo sigurni da pravilno updateamo svaki a u petlji.

Takoder, ovdje nas samo zanima broj kombinacija kojima dobivamo zbrojeve djeljive s 10, a kako zbrajanje "cuva ostatak", nisu nam ni bitni konkretni zbrojevi nego samo broj nacina na koji mozemo dobiti pojedine ostatke.

Opet krecemo s a[0] = 1, ako ne uzmemo niti jedan broj, njihov zbroj je 0 sto je djeljivo s 10, i slicno kao u proslom gledamo:

Ostatak (i + broj[k+1]) % 10 mozemo dobiti na toliko nacina na koliko smo mogli dobiti iz prvih k brojeva (tmp[(i + broj[k+1]) % 10]) kojima ne dodamo broj[k+1] plus broj nacina na koji mozemo dobiti zbroj ciji je ostatak i kojima dodamo broj[k+1].

Ako ti nije sasvim jasno jos uvijek, probaj slijediti algoritam rucno s nekim brojevima pa ces valjda skuziti   Ako imas jos kakvih pitanja samo naprijed, bas mi ubijas monotoniju na poslu

Evo ti neki kod recimo za ovaj prvi u c++, konzistentan s varijablama u opisu gore:

#include<iostream>

using namespace std;

void main() {

   int uk; //broj elemenata

   int a[52] = 0; //broj kombinacija za pojedini ostatak

   a[0] = 1;

   cin >> uk;

   int broj[uk]; //zadani brojevi, valjda ovo radi (nisam se neko vrijeme sluzio c++ pa sam zaboravio jel se moze ovo, ako ne radi, uvijek mozes koristiti vector ili malloc)

   for(int i = 0; i < uk; i++) cin >> broj[i];

   for(n = 0; n < uk, n++){ //rjesavamo problem broj po broj

      for(i = 51; i >= 0; i--){ //provjeravamo za svaki broj sve prethodne zbrojeve

         if (broj[n] + i < 52) //zanimaju nas samo zbrojevi manji od 52

            a[broj[n] + i] += a[i]; //svakom zbroju koji daje i mozemo dodati novi broj, a svakom koji daje broj[n] + i mozemo ne dodati novi broj, pa je ovo ukupan broj kombinacija

      }

   }

   cout << a[51]; //ispisujemo broj kombinacija kojima dobivamo zbroj 51

   return 0;

}

Vanjska petlja ti mora ici za n < k, unutarnja petlja mora ici unazad, osim ako zelis da se svaki broj moze vise puta pribrojiti, ostalo izgleda ok na prvi pogled (osim sto ne radi za uk > 100000)

Ma nije ni Pascal za bacit, ja sam cijelu srednju radio u Pascalu i nis mi nije falilo. Doduse, prelazak na C++ definitivno ima svojih prednosti, pa podrzavam

Ovi zadaci su super, i predlazem ti da ih sve pokusas rijesiti, ako ces imati problema prilikom rjesavanja, slobodno pitaj ovdje