Question

IN C++ , Element Lipsa 1
Transmiterea datelor de la un calculator la altul în cadrul unei rețele se face "ca prin magie" în cazul conexiunilor de mare viteză. Totuși, când locuiești pe o stradă unde nimeni nu și-a tras fibră optică și ești singurul care vrea să se uite la TED Talks pe YouTube, transmisia începe să pară mai puțin magică.

Fiecare informație se transmite pe internet sub forma unui grup de pachete. În cazul în care vrei să faci video streaming de pe YouTube, faptul că se mai pierde din când în când câte un pachet pe drum poate să treacă neobservat și să poți viziona videoclipul dorit cu succes.

Să presupunem că ai putea observa pachetele care ajung la calculatorul tău într-o perioadă de 1 minut. Putem să reprezentăm aceste pachete ca un șir de numere întregi. De asemenea, de cealaltă parte a rețelei se pot observa pachetele care au fost trimise.

Cerință
Ți se dă un șir de n numere întregi, reprezentând pachetele trimise și un alt șir cu n - 1 numere întregi, reprezentând pachetele care au ajuns cu succes până la tine. Elementele din cel de-al doilea șir vor fi în aceeași ordine ca și cele din primul, cu excepția unui element din primul șir care va lipsi din al doilea. Identifică elementul lipsă.

Challenge: Poți să rezolvi problema parcurgând elementele din fiecare șir o singură dată?

Date de intrare
Pe prima linie se va găsi numărul n, iar pe următoarele două linii elementele celor două șiruri.

Date de ieșire
Programul va afișa pe ecran numărul X, care reprezintă elementul lipsă din cel de al doilea șir.

Precizări și restricții
1 ≤ n ≤ 1 000
elementele din șir nu vor avea valori mai mari de 100 000, respectiv mai mici de -100 000
Există o soluție a problemei care folosește un singur for (excluzând citirea). Poți să o găsești?
Exemple
Date de intrare .................... Date de ieșire
10
34 32 45 -67 89 21 34 5 7 9
34 32 45 89 21 34 5 7 9 ................................... -67
VA ROG SA EXPLICATI !!!! MULTUMESC !

Answer 1

PROGRAM C++ :

#include <iostream>

using namespace std;

int main(){

   //Declarare date

   unsigned n,i;

   int p[1000];    //Pachete trimise

   int s[1000];    //Pachete sosite

   //Citire date

   cin >> n;

   for(i=0;i<n;i++) cin >> p[i];

   for(i=0;i<n-1;i++)cin >> s[i];

   //Determinare pachet lipsa

   bool gasit=0;

   for(i=0;i<n-1 && gasit==0;i++){

       if(p[i]!=s[i]){

           gasit=1;

           cout << p[i];

       }

   }

   if(!gasit)cout<<p[n-1];

}

Explicatie :

Pachetul lipsa este primul pachet care apare in p si nu apare in s. Altfel spus, pana la pachetul lipsa cei doi vectori sunt egali.

Astfel e nevoie doar sa comparam p[i] cu s[i] pana cand i ajunge la valoarea n-1 SAU pachetul lipsa a fost gasit pe o pozitie anterioara.

In momentul in care gasim pachetul lipsa in afisam si schimbam valoarea variabilei gasit la 1.

Daca la finalul acestui bloc de cod pachetul nu a fost inca gasit inseamna ca pachetul lipsa este chiar ultimul pachet din p (elementul p[n-1] mai exact).

Completari ale informatiilor date in cerinta

Informatiile de retelistica oferite in cerinta nu sunt complete.

1. "faptul că se mai pierde din când în când câte un pachet pe drum poate să treacă neobservat și să poți viziona videoclipul dorit cu succes"

Afirmatia e adevarata in cazul protocolului UDP (protocol folosit in special pentru streaming).

In cazul protocolului TCP (protocol folosit mai ales pentru transmiterea de documente/informatii) pachetele pierdute sunt retrimise, nu poate sa treaca neobservat.

2. "Elementele din cel de-al doilea șir vor fi în aceeași ordine ca și cele din primul"

In realitate pachetele nu vin neaparat in ordinea in care au fost trimise. Sunt reordonate in ordinea corecta la destinatie (mai ales in cazul TCP).