a) Scrieţi un program C/C++ care citeşte de la tastatură un număr natural n (0<n≤1000000) şi apoi n numere naturale nenule (cu cel mult 7 cifre fiecare) ordonate  crescător şi, utilizând un algoritm eficient din punct de vedere al memoriei utilizate şi al timpului de executare, determină pentru fiecare număr citit cea mai mică valoare  mai mare sau egală cu acesta ce reprezintă o putere a lui 2. Un număr natural x este putere a lui 2 dacă există un număr natural k astfel încât x=2 la puterea k.

Numerele astfel determinate vor fi scrise în fişierul BAC.TXT, separate prin câte un spaţiu.

Exemplu: dacă n=5 şi cele 5 numere citite au valorile 3 5 8 9 12 fişierul BAC.TXT va avea conţinutul: 4 8 8 16 16 (6p.)

b) Descrieţi succint, în limbaj natural, algoritmul pe baza căruia a fost scris programul de la punctul a), explicând în ce constă eficienţa metodei folosite. (4p.)

REZOLVARE

#include <fstream.h>

#include <conio.h>

unsigned long i,n,p,x; ofstream

f("BAC.txt");

void main()

{do{cout<<"Dati n[1-1000000]:";

cin>>n;} while(n<1 ||

n>1000000);

p=1; cout<<"Dati numerele:";

for(i=1;i<=n;i++)

{cin>>x; while(p<x) p*=2;

f<<p<<' ';}

f.close();}

Memorăm în p puterea lui 2 căutată. Iniţial, p=1. Pentru fiecare număr citit îl dublăm pe p (dacă e mai mic decât numărul) până devine cel puţin egal cu numărul citit şi  scriem pe p. Astfel, nu reluăm cu p=1 pentru fiecare număr, ci continuăm de la pasul precedent, dacă e cazul. Fie p=2k, deci 2k-1<x≤2k (unde x e ultimul număr din  şir), căci k e minim. Logaritmăm în baza 2 şi obţinem k-1<log2x≤k, deci k (numărul de înmulţiri cu 2 efectuate) este log2x dacă x e putere a lui 2 sau 1+[log2x], dacă x  nu e putere a lui 2.