Question

Scrieti un program in C++ care descompune pe n ca suma de k numere astfel incat produsul lor sa fie maxim.
EX: n=11
11=3+3+3+2 iar 3*3*3*2=54

Va rog muuuult!!!

Answer 1

Deci algoritmul va functiona astfel:
1. vom stoca intr-o variabila f, numarul n/k aproximat prin adaos
(in cazul nostru: n/k = 2,75 => f este 3)
2. Intr-un vector numere[] de k spatii scriem f-ul pe fiecare pozitie
(in cazul nostru: numere={3, 3, 3, 3})
3. Stocam in sum, suma numerelor din vectorul nou creat cu forumula: sum=f*k;
(sum=f*k=3*4=12)
Acum noi avem un vector facut doar din 3, 3, 3, 3 - iar suma nr este 12. Si din asta trebuie sa facem cumva, sa ramana suma egala cu n, deci cu 11:

4. Setam un c cu valoarea ultima pozitie in vectorul nostru(vom stoca de la 0 la 3, deci c va fi 3 (k-1)), apoi initializam un while, cu conditia: sum>n, apoi pentru fiecare repetitie, scadem valoarea numerelor din vector cu 1, si in acelasi timp si sum cu 1, si c cu 1...
si va rula astfel:
   a->  sum=12    n=11    c=3  numere={3, 3, 3, 3}
   b-> intrand in while -> conditia (sum>n) - adevarata(12>11)
         *numere[c]--; (stiind ca c=3[ultima poz din vector]) => numere={3, 3, 3, 2}
         *c--;  c-ul devine 2, adica trecem la pozitia anterioara din vector
         *sum--; (sum devine 11) (scadem sum cu 1, pentru ca am scazut si din vector un element cu 1)
   c-> se verifica conditia (11>11) fals-> se iese din while
   ==> numere{3, 3, 3, 2}

5. Cu un for, afisam toate cifrele, si daca nu suntem la ultima afisam si un +
3+3+3+2(aici suntem la ultima si nu mai afisam +)
6. Afisam un =, apoi afisam sum

******************************************************************
Algoritmul in C++

#include <iostream>
using namespace std;
int main(){
    int n, k, f, sum, i, c;
    cout<<"n=";cin>>n;
    cout<<"k=";cin>>k;
    int numere[k];

    if(n%k>0) f=n/k+1;
    else f=n/k;

    for(i=0;i<k;i++)
        numere[i]=f;
    sum=f*k;
    c=k-1;
    while(sum>n){
        numere[c]--;
        c--;
        sum--;
    }
    for(i=0;i<k;i++){
        cout<<numere[i];
        if(i!=k-1)cout<<"+";
    }
    cout<<"="<<n;
    return 0;
}