Cerința
Numim secvență neuniformă a unui șir de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, cu proprietatea că oricare trei termeni aflați pe poziții consecutive sunt diferiți. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Se dă un șir de cel mult 106 numere naturale din intervalul [0,9], în care există cel puțin trei termeni diferiți pe poziții consecutive. Se cere să se afișeze lungimea maximă a unei secvențe neuniforme a șirului dat.
Date de intrare
Fișierul de intrare secventeneuniforme.in conține un șir de cel mult 106 numere naturale din intervalul [0,9] separate prin spații.
Date de ieșire
Fișierul de ieșire secventeneuniforme.out va conține pe prima linie lungimea maximă a unei secvențe neuniforme a șirului aflat în fișierul de intrare.
Restricții și precizări
proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate;
se recomandă o soluție care să nu folosească tablouri sau alte structuri de date similare.
MA POATE AJUTA CINEVA CU O REZOLVARE? SAU POATE SA MODIFICE CODUL MEU? IAU DOAR 80P
#include
#include
using namespace std;
ifstream f("secventeneuniforme.in");
ofstream g("secventeneuniforme.out");
int main()
{
int a, b = -1, c = -1, nr = 0, lungMax = 0;
while (f >> a) {
if (a != b && a != c) {
nr++;
b = c;
c = a;
} else {
if (nr > lungMax)
lungMax = nr;
if (a == c) {
c = a;
b = -1;
nr = 1;
} else {
b = c;
c = a;
nr = 2;
}
}
}
g<< lungMax << '\n';
return 0;
}
Răspunsuri la întrebare
Nu consideri cazul in care sirul se termina cu o secventa neuniforma.Acest algoritm trebuie sa mearga:
int main()
{
int a, b = -1, c = -1, nr = 0, lungMax = 0;
while (f >> a) {
if (a != b && a != c) {
nr++;
b = c;
c = a;
} else {
if (a == c) {
c = a;
b = -1;
nr = 1;
} else {
b = c;
c = a;
nr = 2;
}
}
if (nr > lungMax)
lungMax = nr;
}
g<< lungMax << '\n';
return 0;
}
Răspuns:
Explicație:
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("secventeneuniforme.in");
ofstream g("secventeneuniforme.out");
int secv, secvmax, cif, a,b,c;
bool diferite(int x, int y, int z)
{
return (x!=y && x!=z && y!=z);
}
int main()
{
f >> a >> b >> c;
if (diferite(a,b,c)) {secv=3; secvmax=3;}
while (f >> cif)
{
a=b; b=c; c=cif;
if (diferite(a,b,c))
{
if (secv==0) secv=3;
else ++secv;
}
else
{if (secv>secvmax) {secvmax=secv;}
secv=0;}
}
if (secv>secvmax) secvmax=secv;
g << secvmax;
}