[ strimad @ 26.02.2009. 11:35 ] @
Ako neko ima ideju za sledeci problem...

Treba neki zadati broj prikazati u obliku zbira brojeva 2 i 3 i to u svim mogucim kombinacijama.

Npr.
7 = 2 + 2 + 3
7 = 2 + 3 + 2
7 = 3 + 2 + 2

8 = 2 + 2 + 2 + 2
8 = 2 + 3 + 3
8 = 3 + 2 + 3...

Pozz
[ vlaiv @ 26.02.2009. 12:04 ] @
Resenje nije preterano komplikovano.

Na primer : Rekurzivna funkcija koja ce redom da oduzima vrednosti iz skupa sabiraka, dodaje ih u listu i salje dalje preostali iznos i listu sabiraka u rekurziju

evo nekog pseudo koda

Code:


// ulaz
int N;
int sabirci[k];

array resenja;
int najmanji_sabirak;

void nadji_najmanji
{
    najmanji_sabirak = sabirci[0];
    for(int i=1;i<k;i++)
        if(najmanji_sabirak<sabirci[i])
            najmanji_sabirak = sabirci[i];
}


void rekurzija(preostalo, trenutna_lista_sabiraka)
{
    if(preostalo==0){
        resenja.add(trenutna_lista_sabiraka);
        return;
    }else if(preostalo<najmanji_sabirak)
        return;
    }else{
        for(int i=0;i<k;i++){
            if(sabirci[i]>=preostalo){
                trenutna_lista_sabiraka.push_end(sabirci[i]);
                rekurzija(preostalo-sabirci[i],trenutna_lista_sabiraka);
                trenutna_lista_sabiraka.pop_end();
            }
        }
    }
}

nadji_najmanji;

rekurzija(N,array());

[ Goran Rakić @ 26.02.2009. 12:33 ] @
Prvo odredi broj dvojki i trojki. Kako je broj dvojki dobijaš kao celobrojna rešenja jednačine što je pak trivijalno. Tako za dobijaš rešenja i . Sada preostaje da za svako moguće rešenje petljom konstruišeš permutacije svih dvojki i trojki. Nikakava rekurzija nije potrebna.
[ mmix @ 26.02.2009. 14:13 ] @
Zaboravio si uslov m,n >= 0 bez toga resenje nije trivijalno i u opstem slucaju ih ima beskonacno. U svakom slucaju ti treba jos jedna iteracija za resavanje jednacine. Malo sam zardjao, koji bi O() bio za ovo resenje (resavanje jednacine + permutori)?
[ Goran Rakić @ 26.02.2009. 14:46 ] @
Da, podrazumevao sam samo celobrojna nenegativna rešenja ;)
[ strimad @ 26.02.2009. 22:29 ] @
Hvala puno

Pozz
[ Nedeljko @ 05.03.2009. 19:48 ] @
Ako je paran, prvo resenje je sa svim dvojkama, a ako je neparan, sa jednom trojkom i svim ostalim dvojkama.

Ostala resenja se dobijaju petljom u kojoj se u svakom koraku broj dvojki smanji za 3, a broj trojki poveca za 2.

Code:
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
    int n, d, t;
    
    cout << "Unesi broj : " << endl;
    
    while (true) {
    cin >> n;
    
    if (n < 2)
        cout << "Greska! Broj ne sme biti manji od 2" << endl;
    else
        break;
    }
    
    if (n % 2 == 0) {
    d = n/2;
    t = 0;
    } else {
    d = (n-3)/2;
    t = 1;
    }
    
    while (d >= 0) {
    cout << n << " = " << d << "*2 + " << t << "*3" << endl;
    d -= 3;
    t += 2;
    }
    
    return EXIT_SUCCESS;
}