👤
ANDRIESBOSS92EZ
a fost răspuns

Se consideră două tablouri unidimensionale A şi B cu elemente numere naturale din
intervalul [1;10000]. Spunem că tabloul A “se poate reduce” la tabloul B dacă există o
împărţire pe secvenţe de elemente aflate pe poziţii consecutive în tabloul A astfel încât prin înlocuirea secvenţelor cu suma elementelor acestora să se obţină, în ordine, elementele tabloului B.
De exemplu tabloul se poate reduce la tabloul

http://imgur.com/a/U7tlt

Fişierul text NUMERE.IN conţine pe prima linie două numere naturale nenule n şi m
(1≤m≤n≤100), pe linia a doua n numere naturale din intervalul [1;10000] şi pe linia a
treia alte m numere naturale din intervalul [1;10000]. Pe fiecare linie numerele sunt
separate prin câte un spaţiu.
a) Scrieţi un program C/C++ care citeşte toate numerele din fişierul NUMERE.IN şi verifică, utilizând un algoritm eficient din punctul de vedere al timpului de executare, dacă tabloul construit cu cele n numere aflate pe linia a doua în fişier se poate reduce la tabloul construit cu cele m numere aflate pe linia a treia în fişier. Programul afişează pe ecran mesajul DA în caz afirmativ şi mesajul NU în caz negativ.

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

Răspuns :

Elementele din B sunt sume de elemente consecutive din vectorul A. Atunci, daca scazi succesiv elemente din B pana obtinem 0.

Prin citirea elementelor o data din B si A obtinem verificarea in mod direct

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

int main(){
int n,m,i=0,j,ok;
ifstream fin("numere.in");
fin>>n>>m;
int a[n],b[m];
for(j=0;j<n;j++){
fin>>a[j];
}
for(j=0;j<m;j++){

fin>>b[j];
}

for(j=0;j<m;j++){
while(b[j]>0&&i<n){
b[j]=b[j]-a[i];
i++;
}
if(b[j]<0||(b[j]>0&&i==n)){
ok=0;
break;
}
ok=1;
}
if(ok==1){
cout<<"DA";
}
else{
cout<<"NU";
}
return 0;
}
Vă mulțumim că ați vizitat platforma noastră dedicată Informatică. Sperăm că informațiile oferite v-au fost utile. Dacă aveți întrebări sau aveți nevoie de asistență suplimentară, nu ezitați să ne contactați. Așteptăm cu nerăbdare să vă revedem și nu uitați să ne salvați în lista de favorite!


Ez Askings: Alte intrebari