[es] - prikazati u obliku zbira brojeva

strimad
Vrsac

Član broj: 190687
Poruke: 10
*.static.sbb.rs.

Profil

^{26.02.2009. u 11:35 - pre 196 meseci}

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

Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*

+1 Profil

Re: prikazati u obliku zbira brojeva

^{26.02.2009. u 12:04 - pre 196 meseci}

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

Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com

+125 Profil

Re: prikazati u obliku zbira brojeva

^{26.02.2009. u 12:33 - pre 196 meseci}

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

. Sada preostaje da za svako moguće rešenje petljom konstruišeš permutacije svih dvojki i trojki. Nikakava rekurzija nije potrebna.

http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja

Odgovor na temu

mmix
Miljan Mitrović
Chief Software Architect
Financial Intelligence Software Ltd.
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6050

+4631 Profil

Re: prikazati u obliku zbira brojeva

^{26.02.2009. u 14:13 - pre 196 meseci}

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)?

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog
naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji
je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan,
sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv - Z.Đinđić

Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com

+125 Profil

Re: prikazati u obliku zbira brojeva

^{26.02.2009. u 14:46 - pre 196 meseci}

Da, podrazumevao sam samo celobrojna nenegativna rešenja ;)

http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja

Odgovor na temu

strimad
Vrsac

Član broj: 190687
Poruke: 10
93.86.197.*

Profil

Re: prikazati u obliku zbira brojeva

^{26.02.2009. u 22:29 - pre 196 meseci}

Hvala puno

Pozz

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.dynamic.sbb.rs.

+2801 Profil

Re: prikazati u obliku zbira brojeva

^{05.03.2009. u 19:48 - pre 196 meseci}

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

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu