Scrieţi un program C/C++ care citeşte de la tastatură două numere naturale, m și n
(2
), și apoi două șiruri de m și respectiv n numere naturale din intervalul [1,103
],
elementele a două tablouri unidimensionale x și y. Programul decide dacă y este un subşir
al lui x, adică dacă există un număr k astfel încât xk=y1, xk+1=y2. Xk+n=yn-1 și xk+n+1=yn
(elementele celui de-al doilea tablou se regăsesc pe poziții consecutive în primul) și afişează
pe ecran mesajul DA în caz afirmativ și NU în caz contrar.
Exemplu: Dacă x = {2,7,3,9,10,4,5,8,6,1,9} atunci şirul y= {9,10,4} este subşir al lui x dar y=
{4,5,6,9} nu este subşir al lui x.
Răspunsuri la întrebare
Răspuns:
#include <stdio.h>
#include <stdlib.h>
void populezaTablourile(int *primulTablou, int dimensiuneaPrimuluiTablou, int *alDoileaTablou, int dimensiuneaCeluiDeAlDoileaTablou);
void afiseazaTablourile(int *primulTablou, int dimensiuneaPrimuluiTablou, int *alDoileaTablou, int dimensiuneaCeluiDeAlDoileaTablou);
void verificaConditieSubsir(int *primulTablou, int dimensiuneaPrimuluiTablou, int *alDoileaTablou, int dimensiuneaCeluiDeAlDoileaTablou);
void elibereazaMemoria(int *primulTablou, int *alDoileaTablou);
int main()
{
int dimensiuneaPrimuluiTablou, dimensiuneaCeluiDeAlDoileaTablou;
printf("Introdu dimensiunea primului tablou >> ");
scanf("%d", &dimensiuneaPrimuluiTablou);
printf("Introdu dimensiunea celui de al doilea tablou >> ");
scanf("%d", &dimensiuneaCeluiDeAlDoileaTablou);
int *primulTablou = (int *)calloc((unsigned long long)dimensiuneaPrimuluiTablou, sizeof(int));
int *alDoileaTablou = (int *)calloc((unsigned long long)dimensiuneaCeluiDeAlDoileaTablou, sizeof(int));
populezaTablourile(primulTablou, dimensiuneaPrimuluiTablou, alDoileaTablou, dimensiuneaCeluiDeAlDoileaTablou);
afiseazaTablourile(primulTablou, dimensiuneaPrimuluiTablou, alDoileaTablou, dimensiuneaCeluiDeAlDoileaTablou);
verificaConditieSubsir(primulTablou, dimensiuneaPrimuluiTablou, alDoileaTablou, dimensiuneaCeluiDeAlDoileaTablou);
elibereazaMemoria(primulTablou, alDoileaTablou);
return 0;
}
void populezaTablourile(int *primulTablou, int dimensiuneaPrimuluiTablou, int *alDoileaTablou, int dimensiuneaCeluiDeAlDoileaTablou)
{
for (int i = 0; i < dimensiuneaPrimuluiTablou; i++)
{
printf("Introdu numarul >> ");
scanf("%d", &primulTablou[i]);
if (primulTablou[i] < 1 || primulTablou[i] > 103)
{
elibereazaMemoria(primulTablou, alDoileaTablou);
exit(EXIT_FAILURE);
}
}
for (int i = 0; i < dimensiuneaCeluiDeAlDoileaTablou; i++)
{
printf("Introdu numarul >> ");
scanf("%d", &alDoileaTablou[i]);
if (alDoileaTablou[i] < 1 || alDoileaTablou[i] > 103)
{
elibereazaMemoria(primulTablou, alDoileaTablou);
exit(EXIT_FAILURE);
}
}
}
void afiseazaTablourile(int *primulTablou, int dimensiuneaPrimuluiTablou, int *alDoileaTablou, int dimensiuneaCeluiDeAlDoileaTablou)
{
printf("Primul tablou >> [ ");
for (int i = 0; i < dimensiuneaPrimuluiTablou; i++)
printf("%d ", primulTablou[i]);
printf("]\nAl doilea tablou tablou >> [ ");
for (int i = 0; i < dimensiuneaCeluiDeAlDoileaTablou; i++)
printf("%d ", alDoileaTablou[i]);
printf("]\n");
}
void verificaConditieSubsir(int *primulTablou, int dimensiuneaPrimuluiTablou, int *alDoileaTablou, int dimensiuneaCeluiDeAlDoileaTablou)
{
// 1 -> adevarat, 0 -> fals
int primulNumar = alDoileaTablou[0], esteSubSir = 1, existaSubSir = 0;
// esteSubSir = 1 ( plecăm cu ideea că există un subșir în interiorul șirului mare )
// parcurgem fiecare număr din interiorul primului tablou, salvăm în "primulNumar" primul număr din al doilea tablou
for (int i = 0; i < dimensiuneaPrimuluiTablou; i++)
{
if (primulTablou[i] == primulNumar)
// dacă numărul curent ( din primul tablou ) este egal cu primul număr din al doilea tablou
// practic există posibilitatea ca al doilea tablou să fie subșir primului și verificăm asta!
{
esteSubSir = 1; // aici resetăm în caz că s-a mai găsit o potrivire dar s-a demonstrat ulterior că nu este subșir
for (int j = 0; j < dimensiuneaCeluiDeAlDoileaTablou; j++)
{
// parcurgem fiecare element din al doilea tablou și verificăm dacă sunt egale, elementele din cele 2 tablouri
if (primulTablou[i + j] != alDoileaTablou[j])
{
// primulTablou[i + j] practic dacă am găsit o asemănare în primul tabel la indexul 2 și al doilea tabel are 2 elemente
// i o să fie la noi 2, j o să fie 0
// prima dată verificăm 2 + 0 ( 2 ) cu 0
// după verificăm 2 + 1 ( 3 ) cu 1 ... practic verifici unu după altul :)) succesiv
// dacă nu-s toate numerele egale
esteSubSir = 0; // setăm esteSubSir la 0 ( că la prima asemănare nu s-a găsit un subșir )
break;
// și ieșim din for-ul ăsta ( că dacă mai rămân 10 elemente de verificat nu mai are rost din moment ce am găsit că nu e subșir)
}
}
existaSubSir = (esteSubSir == 0) ? 0 : 1; // dacă nu s-a găsit subșir, existăSubșir rămâne 0 ( fals )
// și se mai caută în restul de numere rămase pentru o nouă egalitate
}
if (existaSubSir == 1)
break;
// dacă s-a mai găsit o egalitate și în if-ul din al doilea for toate elementele au fost egale atunci esteSubSir devine 1,
// există subȘir devine și el 1 ( și din moment ce am găsit un subșir nu mai are rost să căutăm dacă mai sunt deci ieșim și din primul FOR)
}
printf("%s\n", existaSubSir == 1 ? "DA" : "NU"); // dacă s-a găsit un subșir afișăm DA, altfel NU
}
void elibereazaMemoria(int *primulTablou, int *alDoileaTablou)
{
free(primulTablou);
free(alDoileaTablou);
}
Explicație:
Eu l-am testat pentru cele 2 exemple menționate de tine și funcționează, sper să nu fi omis ceva.