Informatică, întrebare adresată de camalex2007, 8 ani în urmă

Fișierul cheltuieli.in are cel mult 10⁶ linii, fiecare linie conţinând câte trei numere naturale din intervalul [1,10²], reprezentând, în această ordine, date despre câte o achiziţie: tipul produsului cumpărat, numărul de produse de acest tip cumpărate, respectiv prețul unui astfel de produs la acel moment. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.
Se cere să se afişeze pe ecran cea mai mare sumă cheltuită pentru toate produsele de același tip, precum și numărul de tipuri de produse pentru care s-a obținut această sumă.
Proiectati un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul cheltuieli. in are conținutul alăturat, se afişează pe ecran: 26 2 (s-a cheltuit suma maximă 26 pentru produsele de tipul 1 și 4: 26 = 16 • 1 + 5 • 2 = 1 • 10 + 2 • 8)

cheltuieli.in:
4 1 10
1 16 1
4 2 8
2 1 5
1 5 2

a. Descrieți în limbaj natural algoritmul proiectat, justificând eficienta acestuia.

b. Scrieți programul C/C++ corespunzător algoritmului proiectat.​

Răspunsuri la întrebare

Răspuns de lucaciucandrei
7

a) Programul citeste din fisier triplete de numere

     si calculeaza suma fiecarui tip de produs in vectorul s,

     in acelasi timp afland si suma maxima din vectorul s.

     Vectorul s se va parcurge apoi pentru a se contoriza numarul de aparitii

     al sumei maxime in variabila k.

     Algoritmul este eficient din punct de vedere al timpului de executare

     deoarece numerele din fisier sunt citite o singura data

     iar vectorul s este reparcurs o singura data

     doar pentru contorizarea aparitiilor sumei maxime

     rezultand o complexitate liniara O(n) unde n este numarul de triplete din fisier.

   b) #include <iostream>

     #include <fstream>

     using namespace std;

     int main() {

         int x, y, z, a[100]={0}, k=0, smax=-1;

         ifstream f("cheltuieli.in");

         while (f>>x>>y>>z) {

             s[x]=s[x]+y*z;

             if (s[x]>smax) {

                 smax=s[x];

             }

         }

         f.close():

         for (int i=1; i<=100; i++) {

             if (s[x]==smax) {

                 k++;

             }

         }

         cout<<smax<<' '<<k;

         return 0;

     }

Alte întrebări interesante