Varianta 2 din testele de antrenament Subiectul III punctul 3

AICI -->Propuneti un subiect de BAC si aveti rezolvarea 

Problema de mai jos apare in setul 1-> folder var-> varianta 2 

III.3.Fişierul bac.in conţine un şir de numere naturale distincte, din intervalul [1,10⁹]. Numerele din şir sunt separate prin câte un spaţiu şi cel puţin trei dintre ele au penultima cifră 2 și ultima cifră 0.

Se cere să se afișeze pe ecran cele mai mari trei numere din şir cu proprietatea că au penultima cifră 2 și ultima cifră 0. Numerele determinate sunt afişate în ordine crescătoare, separate prin câte un spaţiu. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.

Exemplu: dacă fişierul conţine numerele 9731 50 112 20 8 16 8520 3 2520 1520

pe ecran se vor afişa, în această ordine, numerele: 1520 2520 8520

a. Scrieți programul C/C++ corespunzător algoritmului proiectat. (8p.)

b. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)

Rezolvarea SUBIECTULUI III , punctul 3

Observati mai intai ca sunt minim 3 elemente din sir care se termina cu 20

Se cer cele mai mari numere ce se termina in 20 in ordine crescatoare.

Acest lucru presupune o sortare . Putem sorta toate elementele din Bac.in ceea ce nu e eficient sau doar cele care se termina in 20

Cerinta a se refera la proiectarea unui algoritm :

pas1 Citeste elementele sirului in vectorul A

pas2 Preia numai elementele ce se termina in 20 in vectorul B

pas3 Sorteaza B descrescator

pas4 Afiseaza B[2],B[1],B[0]

Programul C++

#include<iostream>

#include<fstream>

using namespace std;

fstream f(“Bac.in”);

int m,n,i,j,k,A[100],B[100];

int main()

{

n=0;i=0;j=0;m=0;//n si m indicii cei mai mari ai vectorilor A si B

//i,j SUNT variabile ce pot fi utile in citirea sau stabilirea indicelui pt vectorii A,B

while(!f.eof()) { f>>A[i];n=i;i++;

if(A[i]%100==20) {B[j]=A[i];

m=j;

j++;

}

}

//sortarea prin interschimbare cu variabila auxiliara k este cea mai eficienta metoda pentru

//tablouri mici cum este B

for(i=0;i<m;i++)

for(j=i+1;j<=m;j++) {if(B[i]<B[j] ) {k=B[i];

B[i]=B[j];

B[j]=k;

}

}

cout<<B[2]<<” “<<B[1]<<” “<<B[0];

f.close();//desi s.o. inchide fisiere automat este bine sa avem aceasta instructiune

//lipsa sa in cazuri rare poate genera erori de functionare

return 0;

}

REZOLVAREA cerintei b

Am pornit cu un algoritm care la modul general este :

pas1 Citeste elementele sirului in vectorul A

pas2 Preia numai elementele ce se termina in 20 in vectorul B

pas3 Sorteaza B descrescator

pas4 Afiseaza B[2],B[1],B[0]

Sa il detaliem (algoritmul de mai sus ) .

pas1 se declara n,m,i,j,k,A[100],B[100] si variabila fisier f asociata fisierului fizic Bac.in

   1.1se initializeaza n,m,i,j cu 0

pas2 se citesc elementele fisierului bac.in cat timp nu am ajuns la sfarsitul fisierului

    2.1. Se scrie in A[n] elementul citit din fisier n , i devine n si i++

……………………………………………………………………………………..

Am pus puncte  dar trebuie continuat.

pasii initiali au fost detaliati , aparand niste sub-pasi.

Eficienta se justifica la acest algoritm prin faptul ca nu sorteaza toate elementele din BAC.in .

El preia elementele ce se termina cu 20 si le sorteaza doar pe acestea .

In plus metoda de sortare necesita extrem de putin cod , este o interschimbare foarte eficienta la tablouri mici .

In prezent tablou mic inseamna ca poate avea chiar si milioane de elemente

Sa nu uitam ca un ecran clasic poate sa afiseze zeci de cadre pe secunda , fiecare cadru avand o matrice de cateva milioane de pixeli.