[C] Ricorsione ordinamento vettore

[xbubbax]

Allora, devo scrivere una funzione che restituisca 1 se il vettore è ordinato in modo crescente, -1 se è ordinato im modo decrescente e 0 se gli elementi stanno a caso.

con la RICORSIONE

buttate giu qualche idea, intanto ci penso anc'ìhio

[xbubbax]

ho abbozzato questo ma non sembra avere molto senso

int ordinato(int vett[], int n){
                                
                                
                                if(n=1){return 0;}
                                
                                if(a[n-1]>a[n-2){return 1;}
                                
                                else return ordinato(int vett[], n-1);}

[sottovento]

Devi espandere un pochino il tema.
Per esempio, la tua funzione restituisce:
1 - se il vettore e' ordinato in modo crescente;
-1 - se il vettore e' ordinato in modo decrescente;
0 - se il vettore non e' ordinato;
-2 - se il vettore e' formato da elementi finora uguali.

il senso del risultato -2 e' che altrimenti non puoi stabilire l'ordine di vettori i cui primi elementi sono tutti uguali, ma dovrai rimandare la decisione fino a quando troverai un elemento diverso.

Usando questa considerazione, scriverai una funzione

int getOrder (int *vect, int n)

dove vect e' il tuo vettore ed n e' il numero di elementi ivi contenuti.
Potrai "giocare" con n al fine di ridurre la dimensione del vettore fino al/ai casi base.

BASE:
- se n <= 1 (quindi 0 o 1 elemento), ritornerai -2 (tutti elementi uguali, finora);
- se n == 2, ritornerai i corrispondenti confronti

PASSO RICORSIVO
- se n > 2, allora
- chiami ricorsivamente getOrder (vect, n-1).
Otterrai un risultato compreso fra {-1, 1, 0, -2};
- confronti gli elementi vect[n-2] e vect[n-1], ed il risultato lo confronti
con quanto riportato dalla chiamata ricorsiva.

C'est tout

[xbubbax]

ci provo

[sottovento]

Originariamente inviato da xbubbax

ci provo

Bene. Ho realizzato un piccolo codice per provare che funzionasse, se ti serve lo posto

[xbubbax]

ho provato a scrivere questo ma non so cosa ci va al posto di if(n==2)

int ordinamento(int vett[], int n){
                                   if(n<=1){
                                            return -2;}
                                   if(n==2){
                                            
                                            
                                   if(n>2){
                                           ordinamento(int vett[], int n-1);}

Non è per me la ricorsione, sono piu per le cose meccaniche

[sottovento]

Ciao,
anche il caso n > 2 deve essere controllato.

Comunque parliamo ora del caso n == 2. Io farei i confronti (tutti) fra gli unici due elementi che compongono il vettore:

- se vect[0] > vect[1] ritorna -1 (ordinato in modo decrescente)
- se vect[0] < vect[1] ritorna 1 (ordinato in modo crescente)
- se vect[0] == vect[1] ritorna -2 (vettore con tutti elementi uguali)

Ovviamente non hai il caso di vettore non ordinato, visto che contiene solo due elementi, i quali possono essere solo uguali o diversi fra loro e, se diversi, uno e' maggiore dell'altro

[xbubbax]

int ordinamento(int vett[], int n){
                                   if(n<=1){
                                            return -2;}
                                   if(n==2){
                                            if(vett[0]>vett[1]){return -1;}
                                            if(vett[0]<vett[1]){return 1;}
                                            if(vett[0]==vett[1]){return -2;}}
                                            
                                            
                                   if(n>2){
                                           ordinamento(int vett[], int n-1);}

Tipo così?

per se il vettore ha piu di 2 elementi devo richiamare direttamente la funzione con n-1 o cosa?

[yorkeiser]

http://it.wikipedia.org/wiki/Quicksort

[xbubbax]

ma io non devo ordinare il vettore, devo controllare in che modo è ordinato

[sottovento]

Originariamente inviato da xbubbax

int ordinamento(int vett[], int n){
                                   if(n<=1){
                                            return -2;}
                                   if(n==2){
                                            if(vett[0]>vett[1]){return -1;}
                                            if(vett[0]<vett[1]){return 1;}
                                            if(vett[0]==vett[1]){return -2;}}
                                            
                                            
                                   if(n>2){
                                           ordinamento(int vett[], int n-1);}

Tipo così?

per se il vettore ha piu di 2 elementi devo richiamare direttamente la funzione con n-1 o cosa?

Si, tipo cosi'. Pero' potresti evitare quanto meno il confronto (vett[0] == vett[1]) mettendo un else o un return -2 secco.

Per quanto riguarda la parte n > 2, devi fare qualcosa di piu' articolato:

1 - ret = ordinamento (vett, n-1); // Controlli se il vettore con n-1 elementi e' in qualche modo ordinato
2 - se ((ret == 1 oppure ret == -2) AND // quindi il vettore precedente e' crescente o quasi
vett[n-2] <= vett[n-1]) // Anche l'ultimo elemento e' maggiore o uguale del precedente
allora
puoi ritornare 1, cioe' il vettore al passo n e' ordinato in maniera crescente.


Analogamente dovrai affrontare il caso in cui il vettore e' ordinato in maniera decrescente.

Piu' semplice e' il caso che il vettore al passo n-1 sia formato da elementi tutti uguali e che anche l'ultimo elemento sia uguale

Infine, il caso che il vettore al passo n-1 sia non ordinato e' banale: in tal caso e' non ordinato anche al passo n.

[xbubbax]

piu o meno ho capito, ora faccio un altro esercizio e ci voglio riuscire da solo

grazie

[andbin]

Una soluzione può essere questa:

int ordinato (int *arr, int len)
{
    int r = 0;

    if (len > 1)
        r = arr[0] <= arr[1] ? +1 : -1;

    if (len > 2 && ordinato (&arr[1], len-1) != r)
        r = 0;

    return r;
}

L'unico caso particolare è quello di un array con 1 elemento, in tal caso ritorna 0 (che in effetti non è nemmeno sbagliato ... non c'è ordine).

[xbubbax]

Potete dare un occhiata a questo esercizio. E' una funzione iterativa che somma i numeri presenti in un testo. Mi da dei numeri enormi però il programma sembra giusto

#include <stdio.h>
#define SIZE 20
int somma_interi_nel_testo(char *stringa);

int main(){
           
           int somma=0;
           char stringa[SIZE];
           
           printf("Inserisci una stringa:\n");
           scanf("%s", &stringa);
           
           somma=somma_interi_nel_testo(stringa);
           
           printf("%d", somma);
           while(getchar() != '\n');
printf("Premere INVIO per continuare...");
getchar();
           }
           



int somma_interi_nel_testo(char *stringa){
                                          int somma=0;
                                          
                                          for(;*stringa='\0';*stringa++){
                                                               
                                          if(((*stringa)>=0)&&((*stringa)<=9)){
                                                                               somma += *stringa;}
                                                                               }}

[sottovento]

Originariamente inviato da andbin

Una soluzione può essere questa:

int ordinato (int *arr, int len)
{
    int r = 0;

    if (len > 1)
        r = arr[0] <= arr[1] ? +1 : -1;

    if (len > 2 && ordinato (&arr[1], len-1) != r)
        r = 0;

    return r;
}

L'unico caso particolare è quello di un array con 1 elemento, in tal caso ritorna 0 (che in effetti non è nemmeno sbagliato ... non c'è ordine).

Mi sembra che questo codice stabilisca se un vettore e' ordinato semplicemente confrontando i primi 2 elementi dello stesso....

[andbin]

Originariamente inviato da sottovento

Mi sembra che questo codice stabilisca se un vettore e' ordinato semplicemente confrontando i primi 2 elementi dello stesso....

Analizzalo meglio. Noterai che l'algoritmo che ho usato parte dal fondo dell'array e appena trova discordanza nell'ordine di 3 valori (A vs B e B vs C), ritorna 0 da lì in avanti (tornando indietro dalla ricorsione).

[sottovento]

Originariamente inviato da andbin

Analizzalo meglio. Noterai che l'algoritmo che ho usato parte dal fondo dell'array e appena trova discordanza nell'ordine di 3 valori (A vs B e B vs C), ritorna 0 da lì in avanti (tornando indietro dalla ricorsione).

Hai ragione.
Cmq ho provato a passare
{ 15, 10, 8, 7, 6, 5, 2, 2, 2, 2} e
{ 15, 10, 8, 7, 3, 3, 3, 3, 2, 1}
Mi ha detto, in entrambi i casi, che il vettore non e' ordinato... salvo errori miei, ovviamente
(cmq non penso sia un mio errore ma sia l'operatore ternario...)

[xbubbax]

potete darmi un occhiata all'ultimo programma che ho postato?

[xbubbax]

questa dovrebbe essere la versione ricorsiva(incompleta), ditemi almeno se sono sulla giusta strada

int somma_interi_nel_testo(char stringa[], int n){
                                                  
                                                  if(n==0){
                                                           return 
                                                  if((stringa[n]>=0)&&(stringa[n]<=9)){
                                                                                       return stringa[n]+somma_interi_nel_testo(stringa[n], n-1);} else return somma_interi_nel_testo(stringa[], n-1);}

[andbin]

Originariamente inviato da sottovento

Cmq ho provato a passare
{ 15, 10, 8, 7, 6, 5, 2, 2, 2, 2} e
{ 15, 10, 8, 7, 3, 3, 3, 3, 2, 1}
Mi ha detto, in entrambi i casi, che il vettore non e' ordinato...

Azz
Vero ... ma è un problema di concetto a cui non ho pensato subito. Avendo due valori adiacenti uguali, non si può stabilire alcunché sull'ordinamento, nel senso che dovrà essere il resto a determinarlo. In pratica, due valori uguali devono essere "bypassati".

Si dovrebbe aggiungere un quarto valore che indica appunto un "non so nulla dell'ordine".

Dovrebbe essere ok così:

int ordinato (int *arr, int len)
{
    int r = -2, rr;

    if (len > 1)
        r = arr[0] < arr[1] ? +1 : arr[0] > arr[1] ? -1 : -2;

    if (len > 2)
    {
       rr = ordinato (&arr[1], len-1);

       if (r == -2)
           r = rr;
       else if (rr != -2 && r != rr)
           r = 0;
    }

    return r;
}

Se tutti i valori nell'array fossero uguali o se ci fosse 1 solo elemento, si otterrebbe alla fine -2.
È praticamente la ipotesi dei valori che facevi tu all'inizio.