Извлечение подпоследовательности из массива

Question

Я пытаюсь решить алгоритм для извлечения подпоследовательности из массива. Он должен отображать самую длинную подпоследовательность простых чисел. Я написал весь алгоритм, но у меня все еще есть бесконечный цикл, и я не могу понять, где и почему. Я увеличиваю оба индекса и изменяю первый индекс в конце, но он все еще не работает. Большое спасибо !!!

P.S: citire считывает массив, prim определяет, является ли число простым или скомпонованным, afisare отображает подпоследовательность, а detSecv определяет самую длинную подпоследовательность.

#include <iostream> 
#include <math.h> 

using namespace std; 

void citireSecv(int &n,int x[50]) 
{ 
    cout<<"Da n: "; 
    cin>>n; 
    for(int i=1;i<=n;i++) 
    { 
     cout<<"Da un nr: "; 
     cin>>x[i]; 
    } 
} 

int prim(int n) 
{ 
    int d=2; 
    while(d<=sqrt(n) && n%d!=0) 
    { 
     if(d==2) 
      d=3; 
     else 
      d=d+2; 
    } 
    if(d>sqrt(n)) return 1; 
    else   return 0; 
} 

void afisare(int n,int x[50],int st,int f) 
{ 
    for(int i=st;i<=f;i++) 
     cout<<x[i]<<" "; 
} 

void detSecv(int n,int x[100],int &st,int &f) 
{ 
    st=1; f=0; 
    int i=1,j; 
    while(i<=n-1) 
    { 
     while(i<=n-1) 
     { 
      if(prim(x[i])==0 && prim(x[i+1])==0) i++; 
     } 
     j=i+1; 
     while(j<=n-1) 
      if(prim(x[j])==0 && prim(x[j+1])==0) j++; 
     if((j-i) > (f-st)) 
     { 
      st=i; 
      f=j; 
     } 
     i=j+1; 
    } 

} 



int main() 
{ 
    int n,x[100],st,f; 
    citireSecv(n,x); 
    detSecv(n,x,st,f); 
    afisare(n,x,st,f); 
    return 0; 
} 

Входные данные:

n=2 
First number is: 5 
Second number is: 7 

Answer 1

С небольшим изменением кода вы заставляете его работать, и, с одной стороны, вам не нужно запускать массив с индексом 1. вы всегда можете начинать с нуля индекса.

for(int i=1;i<=n;i++) 
{ 
    cout<<"Da un nr: "; 
    cin>>x[i]; 
} 

попытайтесь проверить случай, когда не существует простой подпоследовательности при печати.

void detSecv(int n, int *x, int &start, int &end) 
{ 
    start = -1; 
    end = -1; 
    int i=0,j; 
    while(i < n) { 
     if(prim(x[i])) { 
      j = i + 1; 
      while(j < n) 
       if(prim(x[j])) j++; 
       else break; 
     } else { 
      i++; 
      continue; 
     } 
     if((j-i) > (end - start)) { 
      start = i; 
      end = j-1; 
     } 
     i=j+1; 
    } 
} 

Answer 2

Вероятно, только один из многих проблем с этим кодом:

while(i<=n-1) 
    { 
     if(prim(x[i])==0 && prim(x[i+1])==0) i++; 
    } 
    j=i+1; 
    while(j<=n-1) 
     if(prim(x[j])==0 && prim(x[j+1])==0) j++; 

Есть два возможных бесконечных циклов здесь. Если условия в while не возвращают true на первой итерации, i (или j) никогда не будут увеличиваться, и у вас будет бесконечный цикл. Вы почти всегда должны увеличивать такие переменные вне любых условий.

Answer 3

Это лучший способ проверить, является ли число простым или не

bool IsPrime(int number) { 
int primeStep = 2; 
double stepLimit = sqrt(number); 
while(primeStep <= stepLimit) 
{ 
    if(number % primeStep == 0) 
     return false; 
    primeStep += 1; 
} 
return true; 
} 

И Nou вы можете применять эту функцию для каждого числа в массиве, и если это простое число, вы добавляете его в новом массиве:

void detSecv(int numberOfItems,int *arrayOfNumbers) 
{ 
    int arrayOfPrimeNumbers[50] = {}; 
    int index = 0; 

for(int i = 0; i < numberOfItems; i++) 
{ 
    if(IsPrime(arrayOfNumbers[i])){ 
     arrayOfPrimeNumbers[index] = arrayOfNumbers[i]; 
      index += 1; 
    } 
} 

int secondIndex = 0; 
while(arrayOfPrimeNumbers[secondIndex] != 0) 
{ 
    cout << arrayOfPrimeNumbers[secondIndex] << " "; 
    secondIndex += 1; 
} 
}