PDA

Visualizza la versione completa : [C] Restituire la sequenza ordinata più lunga contenuta nell'array


asteroid
24-02-2011, 19:13
Sviluppare una function C che, dati come parametri di input un array di int e il suo size,
determina e restituisce come parametri di output l'indice di inizio e la lunghezza della piu
lunga sequenza ordinata (senso crescente) contenuta nell'array.


Devo applicare un algoritmo di ordinamento del genere?


#include <stdio.h>
#include <stdlib.h>
void seq_ord_array(int [],int );
int main(int argc, char *argv[])
{int a[100],i,n;
printf("inserisci il size dell array:");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("inserisci l'%d-esimo elemento dell'array: \n",i);
scanf("%d",&a[i]);
}
seq_ord_array(a,n);
for(i=0;i<n;i++)
printf("la lunghezza della sequenza ordinata e':%d,\t e il suo indice e':%d\n",n,a);
system("PAUSE");
return 0;
}
void seq_ord_array(int a[],int n)
{
int i,j;
int sequenza;
for(i=1;i<n;i++){
sequenza=a[i];
j=i-1;
while(j>0 && a[j]>sequenza){
a[j+1]=a[j];
j--;
}
a[j+1]=sequenza;
}
}

VincenzoTheBest
24-02-2011, 20:03
Originariamente inviato da asteroid
Devo applicare un algoritmo di ordinamento del genere?

No, l'obiettivo dell'esercizio non è ordinare l'array..

lolide
24-02-2011, 21:27
Lo scopo dell'esercizio è restituire un altro array con la sequenza di numeri ordinati più lunga trovata nell'array di partenza.
Quindi avendo:

10,2,4,5,7,1,0,4,1,7,5,5,7,7,8,9

devi ritornare

5,5,7,7,8,9

TI consiglio di ciclare tutti i numeri, in una variabile tieni l'ultimo indice di partenza della sequenza ordinata ed in un'altra ti tieni la lunghezza della sequenza, ed in altre due ti tieni quelle della sequenza + lunga.
Se l'ultima sequenza che incontri ha lunghezza maggiore dell'ultima che hai memorizzato, allora sostituisci le due variabili.

Alla fine del ciclo ti ritrovi con due variabili.
Ovviamente devi anche comprendere il caso in cui non ci siano risultati, che risolvi semplicemente settando le variabili del risultato a -1 invece di 0 (quindi se non sono settate, l'indice sarà -1, visto che gl'indici degli array partono da 0).

MrX87
25-02-2011, 02:13
ciao, ho dato una occhiata al tuo problema...pensavo di risolvero così...vedi un pò se t va bene...magari prova a vedere se si può fare qualche modifica per ottimizzarlo un pò!
ciao


#include <stdio.h>
#include <stdlib.h>
int seq_ord_array(int [],int , int*);
int main(int argc, char *argv[])
{
int a[5]={9,5,4,3,1};
int i,n=5;
int index_start;
int dim_seq;

dim_seq = seq_ord_array(a,n, &index_start);

printf ("%d %d\n", index_start, dim_seq);

for (i=index_start; i<index_start+dim_seq; i++ ) {
printf ("%d ", a[i]);
}

return 0;
}
int seq_ord_array(int v[],int n, int* index_start)
{
int i,j=0,k=1,x;
int max=0;
int cont;

i=0;
while ( i<n-1 ){
cont=1;
if ( v[i] < v[i+1] ) {
cont++;
k = i+1;
x=i;
while ( k < n-1 ) {
if ( v[k] < v[k+1] ) cont++;
k++;
}
if ( cont > max ) {
max = cont;
j=x;
}
}
i=i+k;
}
*index_start = j;
return max;

}

Loading