8. Din fişierul vector.in se citeşte un vector de numere întregi, pozitive, cu cel puţin 2 cifre fiecare. Sa se determine cea mai lungă subsecvenţă de elemente prime, ale căror inverse sunt tot numere prime.
Exemplu: dacă fişierul vector.in are următorul conţinut:
9
11 971 44 19 181 751 347 33 929
atunci subsecvenţa cerută este: 181751347
Răspunsuri la întrebare
#include <iostream>
#include <fstream>
using namespace std;
// Funcție care verifică dacă un număr este prim
bool estePrim(int n)
{
// Numerele mai mici sau egale cu 1 nu sunt prime
if (n <= 1)
{
return false;
}
// Verificăm dacă n este divizibil cu orice număr între 2 și rădăcina pătrată din n
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
return false;
}
}
// Dacă nu am găsit niciun divizor în intervalul dat, atunci n este prim
return true;
}
int main()
{
// Deschide fișierul vector.in pentru citire
ifstream f("vector.in");
// Vectorul care conține elementele citite din fișier int v[100];
// Variabilă care ține evidența dimensiunii curente a vectorului
int n = 0;
// Citește elementele vectorului din fișier
int x;
while (f >> x)
{
v[n] = x;
n++;
}
// Vectorul care conține cea mai lungă subsecvență de elemente prime, ale căror inverse sunt tot numere prime
int subsecventaMaxima[100];
// Variabilă care ține evidența dimensiunii curente a subsecvenței
int dimensiuneSubsecventaMaxima = 0;
// Vectorul care conține subsecvența curentă de elemente prime, ale căror inverse sunt tot numere prime
int subsecventaCurenta[100];
// Variabilă care ține evidența dimensiunii curente a subsecvenței
int dimensiuneSubsecventaCurenta = 0;
// Parcurgem fiecare element din vectorul de intrare
for (int i = 0; i < n; i++)
{
// Verificăm dacă elementul curent este prim
if (estePrim(v[i]))
{
// Calculăm inversul elementului curent
int invers = 0;
int copie = v[i];
while (copie > 0)
{
int cifra = copie % 10;
invers = invers * 10 + cifra;
copie /= 10;
}
// Verificăm dacă și inversul elementului curent este prim
if (estePrim(invers))
{
// Dacă ambele numere sunt prime, adăugăm elementul curent la subsecvența curentă
subsecventaCurenta[dimensiuneSubsecventaCurenta] = v[i];
dimensiuneSubsecventaCurenta++;
}
else
{
// Dacă inversul elementului curent nu este prim, începem o nouă subsecvență
// Comparăm lungimea subsecvenței curente cu cea mai lungă subsecvență identificată până în acel moment
if (dimensiuneSubsecventaCurenta > dimensiuneSubsecventaMaxima)
{
// Dacă subsecvența curentă este mai lungă decât cea mai lungă subsecvență identificată până acum, o salvăm ca fiind cea mai lungă subsecvență
dimensiuneSubsecventaMaxima = dimensiuneSubsecventaCurenta;
for (int j = 0; j < dimensiuneSubsecventaMaxima; j++)
{
subsecventaMaxima[j] = subsecventaCurenta[j];
}
}
// Resetăm subsecvența curentă
dimensiuneSubsecventaCurenta = 0;
}
}
else
{
// Dacă elementul curent nu este prim, începem o nouă subsecvență
// Comparăm lungimea subsecvenței curente cu cea mai lungă subsecvență identificată până în acel moment
if (dimensiuneSubsecventaCurenta > dimensiuneSubsecventaMaxima)
{
// Dacă subsecvența curentă este mai lungă decât cea mai lungă subsecvență identificată până acum, o salvăm ca fiind cea mai lungă subsecvență
dimensiuneSubsecventaMaxima = dimensiuneSubsecventaCurenta;
for (int j = 0; j < dimensiuneSubsecventaMaxima; j++)
{
subsecventaMaxima[j] = subsecventaCurenta[j];
}
}
// Resetăm subsecvența curentă
dimensiuneSubsecventaCurenta = 0;
}
}
// După ce am parcurs toate elementele din vector, comparăm încă o dată lungimea subsecvenței curente cu cea mai lungă subsecvență identificată până în acel moment
if (dimensiuneSubsecventaCurenta > dimensiuneSubsecventaMaxima)
{
// Dacă subsecvența curentă este mai lungă decât cea mai lungă subsecvență identificată până acum, o salvăm ca fiind cea mai lungă subsecvență
dimensiuneSubsecventaMaxima = dimensiuneSubsecventaCurenta;
for (int j = 0; j < dimensiuneSubsecventaMaxima; j++)
{
subsecventaMaxima[j] = subsecventaCurenta[j];
}
}
// Afișăm cea mai lungă subsecvență identificată
for (int i = 0; i < dimensiuneSubsecventaMaxima; i++)
{
cout << subsecventaMaxima[i];
}
return 0;
}
Salut!
Ai rezolvarea in C++ mai jos
#include <fstream>
using namespace std;
ifstream in("vector.in");
ofstream out("vector.out");
bool prim(int n) {
if (n <= 1) {
return false;
}
else if (n != 2 && n % 2 == 0) {
return false;
}
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
int invers(int n) {
int ogl = 0;
while (n != 0) {
ogl = ogl * 10 + n % 10;
n /= 10;
}
return ogl;
}
int main() {
int n, a[1001], l = 1, lmax = 1, p = 1, u = 1, pmax = 1, umax = 1;
in >> n;
for (int i = 1; i <= n; ++i) {
in >> a[i];
if (i != 1) {
if (prim(a[i]) && prim(invers(a[i])) && prim(a[i - 1]) && prim(invers(a[i - 1]))) {
l++;
if (p == 1) {
p = i - 1;
}
else {
u = i;
}
}
else {
l = 1;
p = 1;
u = 1;
}
if (l > lmax) {
lmax = l;
pmax = p;
umax = u;
}
}
}
for (int i = pmax; i <= umax; ++i) {
out << a[i] << " ";
}
in.close();
out.close();
return 0;
}