Question

Fişierul text NUMERE.IN conţine pe prima linie un număr natural nenul n (1≤n≤100) şi pe
următoarea linie n numere reale pozitive ordonate crescător, separate prin câte un spaţiu.
a) Scrieţi un program C/C++ care citeşte din fişierul NUMERE.IN numărul natural n, şi
determină, utilizând un algoritm eficient din punct de vedere al timpului de executare şi al memoriei utilizate, numărul minim de intervale închise de forma [x;x+1], cu x număr
natural, a căror reuniune include toate numerele reale din fişier.
Exemplu: Dacă fişierul NUMERE.IN are conţinutul:
6
2.3___2.3___2.8___5.7___5.7___6.3 // ( liniile sunt pentru a delimita cifrele )
atunci se afişează 3 (intervalele [2;3],[5;6],[6;7] sunt cele 3 intervale de forma
cerută care conţin numere din şir).
b) Descrieţi în limbaj natural metoda utilizată şi explicaţi în ce constă eficienţa ei.

Answer 1

Stiind ca sunt numere reale pozitive ordonate crescator, atunci nu avem nevoie de vreun vector, pur si simplu luam fiecare element in parte.
Stiind ca intervalele sunt de forma [x;x+1] trebuie sa verificam doar daca numarul respectiv este mai mic decat x+1 si sa stabilim xul initial
Asadar punem conditia: daca numarul real>nr intreg+1, atunci iti trebuie un nou interval, incrementeaza numarul de intervale cu 1 si stabileste urmatorul nr intreg ca partea intreaga a numarului real curent+1
Este un algoritm eficient pentru ca citeste sirul o singura data si foloseste doar 2 variabile intermediare: nr_intreg si nr_intervale

#include <iostream>
#include <fstream>
using namespace std;

int main(){
int n,nr_intervale=0,nr_intreg=-1;
double x;
ifstream fin("numere.in");
fin>>n;
while(n>0){
fin>>x;
if(x>nr_intreg){
nr_intervale++;
nr_intreg=(int)x+1;
}
n--;
}
cout<<nr_intervale;
}