Question

Fişierul text NUMERE.IN conţine pe prima linie un număr natural nenul n (2≤n≤100) şi pe
următoarea linie n numere reale pozitive, în ordine strict crescătoare, separate prin câte un spaţiu.

a) Scrieţi un program C/C++ care, utilizând un algoritm eficient din punct de vedere al
memoriei utilizate, determină şi afişează pe ecran cel mai mare număr natural x cu
proprietatea că în orice interval deschis având drept capete oricare două dintre cele n numere aflate pe linia a doua în fişierul NUMERE.IN se găsesc cel puţin x numere întregi.

Exemplu: dacă fişierul NUMERE.IN are conţinutul:
6
3.5 5.1 9.2 16 20.33 100
atunci se afişează 2 pentru că în oricare dintre intervalele
(3.5;5.1),(3.5;9.2),(3.5;16),(3.5;20.33),(3.5;100),(5.1;9.2),(5.1;16),(5.1;20.33)
(5.1;100),(9.2;16),(9.2;20.33),(9.2;100),(16;20.33),(16;100),(20.33;100)
există cel puţin două numere întregi.

b) Descrieţi în limbaj natural metoda utilizată şi explicaţi în ce constă eficienţa ei.

Answer 1

Numerele reale sunt ordonate strict crescator. Atunci, orice interval care cuprinde numere in ordine neconsecutiva(de exemplu elementul 1 si elementul 3) va fi un interval mai mare decat cele doua numere in ordine consecutiva(elementul 1 si elementul 2). Atunci, numarul minim de numere intregi ce se gaseste in toate intervalele este dat de numarul minim de numere din intervalele diferenta dintre numerele consecutive. 
Numarul de numere intregi dintr-un interval este dat de diferenta dintre partile intregi ale celor doua numere reale, adaugand 1 daca primul nr real este de fapt intreg
Ex: [5.1]-[3.5]=5-3=2 2 numere intregi intr-adevar: 4 si 5
Dar daca am avea 3 in loc de 3.5
[5.1]-[3.0]+1=5-3+1=3 ceaa ce este corect: acum avem 3,4,5 numere intregi
#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;

int main(){
//int max este inclus in limits.h
int n,min=INT_MAX,diferenta;
double nr_trecut,nr_actual;
ifstream fin("numere.in");
fin>>n>>nr_trecut;
//scadem nr_trecut deja luat in considerare
n--;
while(n>0){
fin>>nr_actual;
if(nr_trecut-(int)nr_trecut==0){
diferenta=(int)nr_actual-(int)nr_trecut+1;
}
else{
diferenta=(int)nr_actual-(int)nr_trecut;
}

if(diferenta<min){
min=diferenta;
}
nr_trecut=nr_actual;
n--;
}
cout<<min;
return 0;
}