Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
O smecherie pe care nu o inteleg

Balcon parter fara acte

unde gasesc un speed bag in bucur...

Programe TV cu altfel de sporturi
 Laptop "bun la toate" max...

ctfmon.exe - System Error (in Saf...

Ați prins vremurile cand 120 Volț...

Whatsapp nu afișeaza numele ...
 Medii admitere Politehnica Bucure...

Se extinde Baza de la Kogalniceanu

Politist mutilat de caine in curt...

Trotineta- cat rezista?
 Windows 11 si inregistrare de pe ...

Cont Facebook spart

Accesare Plex prin webstation

Reziliere contract Digi Mobil?
 

[TEMA] Celui mai lung subșir comun

- - - - -
  • Please log in to reply
22 replies to this topic

#1
dana10101010

dana10101010

    New Member

  • Grup: Members
  • Posts: 19
  • Înscris: 28.05.2014
Fișierul titu.in conține numere naturale din intervalul [1,10^2]: pe prima linie două numere,
m și n, pe a doua linie un șir de m numere, iar pe a treia linie un șir de n numere. Numerele aflate pe
aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul de termeni ai celui mai lung subșir comun celor două șiruri
aflate în fișier. Utilizați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul are conținutul alăturat, se afișează pe ecran
valoarea 3.
5 8
4 7 9 8 3
1 4 2 9 7 6 8 2

#2
maccip

maccip

    45 ani

  • Grup: Senior Members
  • Posts: 33,007
  • Înscris: 06.01.2007
Ok.
Pana citesc si eu problema, pune si tu ce-ai facut pana acum sa vedem ce-i de facut in continuare.

#3
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,360
  • Înscris: 10.08.2005
pai ce algoritmi stii?
ii implementezi pe toti, si testezi care sunt eficienti

#4
maccip

maccip

    45 ani

  • Grup: Senior Members
  • Posts: 33,007
  • Înscris: 06.01.2007
E faina problema. Hai s-o facem.

#5
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,360
  • Înscris: 10.08.2005
bine, dar ne trebuie alt exemplu

#6
maccip

maccip

    45 ani

  • Grup: Senior Members
  • Posts: 33,007
  • Înscris: 06.01.2007
Pai sa vedem ce zice Dana.

#7
dana10101010

dana10101010

    New Member

  • Grup: Members
  • Posts: 19
  • Înscris: 28.05.2014
using namespace std;
ifstream  f('titlu.in');
int n, m, i, j, L[101] [101], a[101], b[101];
int main ()
{
f>>m>>n<
for(i=1; i<=m; i++)
  f>>a[i];
for(i=1; i<=n; i++)
  f>>b[i];
for(i=1; i<=m; i++)
  for(j=1; j<=n; j++)
  if(a[i]==b[j])
  L[i] [j]=1+L[i-1] [j-1];
  else
  L[i] [j]=max(L[i-1] [j], L[i] [j-1]);
cout<<”numărul de termeni ai celui mai lung subșir comun celor două șiruri: ”;
cout<<L[m] [n]<<endl;
f.close();
return 0;
}

#8
maccip

maccip

    45 ani

  • Grup: Senior Members
  • Posts: 33,007
  • Înscris: 06.01.2007
Pai ideea e foarte buna.
Cum ai gandit?
Ce nu-ti merge?
De ce incepi indexarea de la 1?

Edited by maccip, 14 August 2018 - 16:53.


#9
maccip

maccip

    45 ani

  • Grup: Senior Members
  • Posts: 33,007
  • Înscris: 06.01.2007
Aight!

Solutia cu care ai venit mi se pare foarte buna.
Nu stiu ce nu-ti merge, dar, daca tu ai venit cu solutia, atunci n-ar trebui sa ai probleme sa corectezi erorile.
Din pct meu de vedere problema e rezolvata. Bravo celui care a facut-o.

#10
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,183
  • Înscris: 24.02.2007
[ https://www.youtube-nocookie.com/embed/BysNXJHzCEs?feature=oembed - Pentru incarcare in pagina (embed) Click aici ]

#11
salcudean99

salcudean99

    Junior Member

  • Grup: Members
  • Posts: 89
  • Înscris: 09.03.2016

View Postdana10101010, on 14 august 2018 - 15:55, said:

Fișierul titu.in conține numere naturale din intervalul [1,10^2]: pe prima linie două numere,
m și n, pe a doua linie un șir de m numere, iar pe a treia linie un șir de n numere. Numerele aflate pe
aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul de termeni ai celui mai lung subșir comun celor două șiruri
aflate în fișier. Utilizați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul are conținutul alăturat, se afișează pe ecran
valoarea 3.
5 8
4 7 9 8 3
1 4 2 9 7 6 8 2
pe exemplul ala nu vad niciun subsir comun de 3 elemente...imi scapa mie ceva?

#12
WinstonMontana

WinstonMontana

    Active Member

  • Grup: Members
  • Posts: 1,913
  • Înscris: 20.02.2018

View Postdana10101010, on 14 august 2018 - 15:55, said:

Fișierul titu.in conține numere naturale din intervalul [1,10^2]: pe prima linie două numere,
m și n, pe a doua linie un șir de m numere, iar pe a treia linie un șir de n numere. Numerele aflate pe
aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul de termeni ai celui mai lung subșir comun celor două șiruri
aflate în fișier. Utilizați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul are conținutul alăturat, se afișează pe ecran
valoarea 3.
5 8
4 7 9 8 3
1 4 2 9 7 6 8 2
reformulam problema:
pe prima linie avem:
<numarul de elemente al sirului m> , <numarul de elemente al sirului n>
pe a doua linie avem : elementele sirului m
pe a treia linie avem : elementele sirului n

Intrebare: de ce imi trebuie prima linie din moment ce stiu cele doua siruri ?

#13
WinstonMontana

WinstonMontana

    Active Member

  • Grup: Members
  • Posts: 1,913
  • Înscris: 20.02.2018
Sigur nu sunt 4 termeni la rezultatul final (click pe poza) ?
Attached File  distributie.png   9.05K   15 downloads

Edited by WinstonMontana, 15 August 2018 - 15:34.


#14
WinstonMontana

WinstonMontana

    Active Member

  • Grup: Members
  • Posts: 1,913
  • Înscris: 20.02.2018

View Postdani.user, on 14 august 2018 - 17:31, said:

[ https://www.youtube-nocookie.com/embed/BysNXJHzCEs?feature=oembed - Pentru incarcare in pagina (embed) Click aici ]
Intersant, procesare dupa diagonala secundara( sau principala depinde cum asezi termeni de cautat) a acelei matrici.

#15
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,183
  • Înscris: 24.02.2007
Poate fi orice diagonala. S-a nimerit sa fie cea principala in acel exemplu ca incepea LCS de la acelasi index in ambele siruri.

#16
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,360
  • Înscris: 10.08.2005

View PostWinstonMontana, on 15 august 2018 - 14:07, said:

reformulam problema:
pe prima linie avem:
<numarul de elemente al sirului m> , <numarul de elemente al sirului n>
pe a doua linie avem : elementele sirului m
pe a treia linie avem : elementele sirului n

Intrebare: de ce imi trebuie prima linie din moment ce stiu cele doua siruri ?
pentru ca nu stii cele doua siruri,
primesti o informatie cu privire la cele doua siruri, aloci memorie, operezi date

#17
WinstonMontana

WinstonMontana

    Active Member

  • Grup: Members
  • Posts: 1,913
  • Înscris: 20.02.2018

View PostMarianG, on 15 august 2018 - 20:24, said:

pentru ca nu stii cele doua siruri,
primesti o informatie cu privire la cele doua siruri, aloci memorie, operezi date
puteau sa folosesca vectorii din C++ .

#18
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,360
  • Înscris: 10.08.2005
si daca ai mai multe numere pe una din linii, nu cate specifica fisierul la inceput ?

Anunturi

Chirurgia spinală minim invazivă Chirurgia spinală minim invazivă

Chirurgia spinală minim invazivă oferă pacienților oportunitatea unui tratament eficient, permițându-le o recuperare ultra rapidă și nu în ultimul rând minimizând leziunile induse chirurgical.

Echipa noastră utilizează un spectru larg de tehnici minim invazive, din care enumerăm câteva: endoscopia cu variantele ei (transnazală, transtoracică, transmusculară, etc), microscopul operator, abordurile trans tubulare și nu în ultimul rând infiltrațiile la toate nivelurile coloanei vertebrale.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate