Jump to content
GGEZ - Devoted to excellence
Guest Guest guest user
Existing user? Sign In  

Sign In



Sign Up
Search In
  • More options...
Find results that contain...
Find results in...
Sign in to follow this  
Mirel1337

Coding cu Mirel: Plata unei sume cu monede

Recommended Posts

Avem mai jos o reprezentare a unui progrămel cât se poate de simplu prin care dăm de la tastatură o sumă și niște monede cu care se va plăti suma dată folosind metoda greedy. Metoda Greedy (lacomului) este o metodă de programare care se foloseşte în probleme de optimizare şi care furnizează o singură soluţie, de preferat cea mai bună.

#include <iostream>
int m[50], n, i, j, S, nr[50], nrm;
bool solutie;
using namespace std;
int sortare_desc()
{
    int aux;
    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++)
            if (m[i] < m[j])
            {
                aux = m[i];
                m[i] = m[j];
                m[j] = aux;
            }
    return aux;
}
void init()
{
    for (i = 1; i < n; i++)
        nr[i] = 0;
}
void tipar()
{
    cout << endl;
    if (solutie == false)
        cout << "Nu exista solutii!";
    else
    {
        for (i = 0; i < n; i++)
            cout << nr[i] << " monede cu valoarea " << m[i];
        cout << "S-au folosit " << nrm << " de monede.";
    }
}
int main()
{
    cout << "Introduceti suma necesara calculului: ";
    cin >> S;
    cout << "Introduceti numarul de monede folosite: ";
    cin >> n;
    cout << endl;
    for (i = 0; i < n; i++)
    {
        cout << "Valoarea monedei de tipul " << i << " este: ";
        cin >> m[i];
    }
    cout << endl;
    sortare_desc();
    init();
    i = 0;
    while (S > 0 && i < n)
    {
        if (m[i] <= S)
        {
            nr[i] = S / m[i];
            S %= m[i];
            nrm += nr[i];
        }
        i++;
        if (i == n - 1 && S > 0) // nu mai sunt monede disponibile, insa mai este suma de plata
            solutie = false;
    }
    tipar();
    return 0;
}

 

  • Like 4

Share this post


Link to post
Share on other sites

As dori si versiunea care foloseste memoization cunoscuta si sub denumirea de programare dinamica,

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.