salut am o problema in C++

[st3or]

am o problema in C++ si nu stiu deloc sa o fac as aprecia tare mult daca mar ajuta cineva am mare nevoie sa fac aceasta problema

multumesc anticipat

Fi?ierul BAC.TXT are pe prima linie dou? numere naturale n ?i m (0<n<1000, 0<m<1000) separate prin câte un spa?iu, pe linia a doua n numere întregi ordonate strict cresc?tor, iar

pe linia a treia m numere naturale distincte. S? se scrie un program care cite?te toate

numerele din fi?ier ?i afi?eaz? pe ecran, desp?r?ite prin câte un spa?iu, toate numerele din a

doua linie a fi?ierului care apar cel pu?in o dat? ?i în linia a treia a acestuia

Exemplu: dac? fi?ierul are urm?torul con?inut:

6 5

2 3 4 5 8 9

4 5 2 11 8

atunci se va afi?a: 5 2 8, nu neap?rat în aceast? ordine.

a) Descrie?i în limbaj natural o metod? eficient? de rezolvare ca timp de executare. (4p.)

Scrie?i programul C/C++ corespunz?tor metodei descrise la punctul a).

[Starker]

//Starker
using namespace std;
#include<iostream>
#include<fstream>
int main()
{int n,m,v[1001],w[1001],i,j;
ifstream f("bac.txt");
f>>n>>m;
for(i=0;i<n;i++)
f>>v[i];
cout<<endl;
for(i=0;i<m;i++)
f>>w[i];
for(i=0;i<n;i++)
    for(j=0;j<m;j++)
         if(v[i]==w[j])
               cout<<v[i];
f.close();
return 0;
}

L-am facut acum la repezeala in pauza dintre orele de info. Nu l-am compilat dar ar trebui sa fie bun. Revin cu corecturi daca nu merge. Bafta si data viitoare fa-ti singur temele !

Edited March 6, 2012 by Starker

[Zamolxis666]

@Starker: Programul tau nu respecta intru totul cerinta de la punctul a) care zice sa fie optimizat pentru timpul de executie. Tu citesti ambele siruri de numere, il parcurgi pe al doilea, element cu element, si le cauti in primul sir, ceea ce duce la un timp de executie de ordinul O(n^2). Indiciul de care trebuia sa te legi era chiar in enunt si spunea ca primul sir este ordonat crescator

O medoa eficienta era:

Citesti primul sir de numere din fisier (pe care-l memorezi sub forma de vector), care este totodata sortat crescator, apoi citesti pe rand cate un numar din al doilea sir si faci o cautare binara in vector (daca numarul cautat este mai mare decat elementul din mijlocul vectorului, cauti recursiv in jumatatea din dreapta, altfel cauti recursiv in jumatatea din stanga, s.a.m.d)

[Starker]

E facut in pauza, si plus de asta nu a scris restrictie la timpul de compilare.

Se mai poate optimiza daca nu mai fac un al doilea vector, dar asta a fost prima idee care mi-a venit in cap.

[skull]

Exemplu: dac? fi?ierul are urm?torul con?inut:

6 5

2 3 4 5 8 9

4 5 2 11 8

atunci se va afi?a: 5 2 8, nu neap?rat în aceast? ordine.

Nu ma prind de ce nu se afiseaza si 4.

Asta e codul solutiei descrisa de Zamolxis666. Ma mir ca exista problema ce necesita cautare binara in variantele de bac.

#include <iostream>
using namespace std;
#define nMax 1001
#define pt(i) (1 << (i))

int N, M;

bool search(int x, int V[]) {
	int k = -1;
	for (int i = 9; i >= 0; i--) {
		if ( k + pt(i) < N && V[k+pt(i)] < x) k = k + pt(i);
	}
	if (k+1 < N && V[k+1] == x) return true;
		else return false;
}

int main() {
	int x;
	cin >> N >> M;
	int V[nMax];
	for (int i = 0; i < N; i++) cin >> V[i];
	for (int i = 0; i < M; i++) {
		cin >> x;
		if (search(x, V) ) cout << x << " ";
	}
}

Edited March 6, 2012 by skull

[cmiN]

Nici eu nu inteleg de ce nu afiseaza si 4, poate ai/e gresit exemplul.

toate numerele din a doua linie a fi?ierului care apar cel pu?in o dat? ?i în linia a treia a acestuia

Deci un numar din a doua linie poate aparea o data sau de mai multe ori in linia a treia, dar:

pe linia a treia m numere naturale distincte

Cum plm ?

Daca pe linia a doua avem doua numere la fel nu inseamna ca trebuie sa afisam unul singur, vezi linia de mai sus boldata.

Totusi mai 1337 ar merge :

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


vector<int> sorted;


int main()
{
    freopen("BAC.TXT", "r", stdin);
    int len1, len2;
    cin >> len1 >> len2;
    sorted.resize(len1);
    for (int i = 0; i < len1; ++i) cin >> sorted[i];
    for (int i = 0; i < len2; ++i) {
        int nr;
        cin >> nr;
        if (binary_search(sorted.begin(), sorted.end(), nr)) cout << nr << " ";
    }
    cout << endl;
    fclose(stdin);
    return 0;
}

P.S.: Codul lui Zamolxis da doar 4 pe testul:

3 4
2 2 4
4 3 1 2

Nu are nicio logica comparatia intre V[i-1] si V atat timp cat tu umbli in numerele de pe a treia linie care nu-s sortate si gandeste-te ce se intampla cand ai M mai mare decat N si faci V accesand o valoare cu continut random, ramas de la alocarea statica, neinitializata.

Bat la pariu ca cerinta de fapt trebuia sa specifice ca numerele distincte sunt pe a doua linie (cele sortate) mai ales ca au precizat ca sortarea este strict crescatoare, iar numerele de pe a treia linie era logic sa se repete fiindca tocmai de aia au precizat sa se afiseze numere din a doua linie ce apar cel putin o data pe a treia linie. Asta mergea la fel cu o cautare binara dar la fiecare afisare sa se adauge intr-un set/heap numarul respectiv pentru ca urmatoarele ce urmeaza a fi cautate/afisate sa fie mai intai cautate in cele deja afisate pentru a nu fi repetate. Sau mai simplu, numerele de pe a treia linie sa fie si ele sortate, iar apoi cautate liniar mereu plecand de la ultima pozitie cautata, pana cand se gaseste numarul sau se da de un numar mai mare decat cel cautat, iar complexitatea totala tot este sub MN.

Edited March 6, 2012 by cmiN

[skull]

Asa este, nu stiu de ce am facut comparatia aia pe V[i-1], V. Din cate stiu eu nu ai voie sa folosesti STL la bac, trebuie sa arati ca stii sa implementezi, nu sa apelezi ceea ce au implementat altii inaintea ta.

[cmiN]

Teoretic ai voie orice compileaza , la olimpiada specifica ca nu ai voie ASM sau biblioteci de retea, la bac nu am vazut sa specifice ceva si oricum nu cred ca apreciaza si promoveaza reinventarea rotii, dar ai dreptate nu merita riscul.