[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]

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]

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]

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.... :mbe:

[andbin]

Mi sembra che questo codice stabilisca se un vettore e' ordinato semplicemente confrontando i primi 2 elementi dello stesso.... :mbe: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]

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]

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 :doh:
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ì: :sperem:
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.

[sottovento]

Sei sicuramente sulla strada giusta, anche se non mi ritrovo con le parentesi ed il return "orfano" di un valore.

Alcuni particolari (concettualmente e' tutto OK, ma vorrai poi vedere il programma funzionare correttamente):

- Il numero 0 ed il carattere '0' sono ben distinti. Siccome C permette di sommare numeri/caratteri/... e' facile far confusione. Stai sommando il carattere '0', che significa che stai utilizzando il suo codice ascii (che dovrebbe essere 48).
Un modo per passare dal carattere rappresentante il numero al numero stesso e' quello di sottrarre '0'. Infatti '0' - '0' = 0. Siccome nel codice ascii i caratteri rappresentanti i numeri sono ordinati, sei sicuro che funziona....

[xbubbax]

Ma parli della versione iterativa o ricorsiva?

Quella iterativa sembra giusta, non capisco dove sbaglio

Quella ricorsiva è incompleta come hai detto tu...non so proprio cosa mettere al return. Avevo pensato a una variabile somma dove sommare tutti gli interi ma poi ogni volta che richiamo la funzione si ricrea anche la variabile e si azzera se all'inizio pongo int somma=0

[sottovento]

Ma parli della versione iterativa o ricorsiva?

Quella iterativa sembra giusta, non capisco dove sbaglio

Quella ricorsiva è incompleta come hai detto tu...non so proprio cosa mettere al return. Avevo pensato a una variabile somma dove sommare tutti gli interi ma poi ogni volta che richiamo la funzione si ricrea anche la variabile e si azzera se all'inizio pongo int somma=0

Stavo guardando quella ricorsiva. Cmq ho visto che il problema dei caratteri ce l'hai anche nella iterativa.
Al return metti 0: fa senso! In effetti, significa "se non ci sono caratteri da sommare, allora la somma e' 0". Corretto, no?

Ultima cosa: gli indici vanno da 0 a n-1, pertanto accedere all'n-esimo elemento del vettore non e' corretto. Fortunatamente, sistemare e' cosa da poco.

Non l'ho verificata, ma con queste piccole modifiche il tuo codice dovrebbe essere cosi':

int somma_interi_nel_testo(char stringa[], int n)
{
if(n == 0)
return 0; // Non ci sono elementi, quindi la somma e' zero

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

[xbubbax]

Perfetto. ho capito.

Questo per esempio era abbastanza facile come esercizio

[sottovento]

Azz :doh:
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ì: :sperem:
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.


Sehr gut!!
Direi che va bene

[xbubbax]

mica hai qualche sito dove ci sono esercizi di questo tipo per potermi esercitare?

io sto cercando tra i siti delle altre università, ma se ne hai qualcuno pronto è meglio, visto che sia quali esercizi cerco

[sottovento]

mica hai qualche sito dove ci sono esercizi di questo tipo per potermi esercitare?

io sto cercando tra i siti delle altre università, ma se ne hai qualcuno pronto è meglio, visto che sia quali esercizi cerco

Controllero', per ora non mi viene niente.
Comunque per esercizio potresti prendere un qualsiasi algoritmo iterativo e cercare di riscriverlo in forma ricorsiva.
Parti dai classici: successione di Fibonacci, Fattoriale, moltiplicazione eseguita con somme successive, somme eseguite con incrementi successivi, verifica se una stringa e' palindroma...

Se conosci delle strutture dati (es. alberi) puoi esercitarti su quelli.

Tempo addietro avevo fatto la proposta di creare una sezione con giochi di programmazione/quiz/esercizi. Sarebbe stato, oltre che utile, divertente....


Beh, visto che ci sono, ti lascio un quiz in C++:

Supponiamo che il tuo cliente abbia scritto un software, per esempio:


int main (void)
{
cout << "Hello, world";
}


Ed ora ti chieda: caro xbubbax, questo software mi scrive

Hello, world

sullo schermo, ma io volevo

************
* Hello, world *
************

Me lo puoi modificare? Pero'.... non voglio che tu modifichi ASSOLUTAMENTE NULLA di quanto c'e' fra le parentesi graffe, perche' e' il risultato del mio preziosissimo generatore di codice, che ho acquistato a caro prezzo e non ho i sorgenti. E' fattibile?

[xbubbax]

heehehe è impossibile per me quest'indovinello, nel senso che non ci riesco, non che non è fattibile.

ma int main(void) cosè?

una funzione o il corpo principale del programma cioè int main() ? se è così secondo me non si può fare, cioè come fai a scrivere fuori dal main principale?


comq ho ancora molti altri esercizi del mio prof sui quali esercitarmi quindi non è urgente trovarne altri. Seguiro il consiglio di fare con la ricorsione i programmi iterativi...

[xbubbax]

Non è che puoi darmi un occhiata a questo esercizio? E' l'ultimo, sennò poi davvero mi mandi a quel paese:D

intanto posto l'esercizio, tra 2 secondi scrivo anche la traccia

#include <stdio.h>
int Kfinestre(int v[], int size, int k, int w);
int main(){

int size;
int risultato;

printf("Inserisci la lunghezza del vettore:\n");
scanf("%d", &size);

int v[size];
int i,x;



for(i=0;i<size;i++){
scanf("%d", &x);
v[i]=x;
}

risultato=Kfinestre(v,size,13,3);
printf("%d\n", risultato);}

int Kfinestre(int v[], int size, int k, int w){
int i;
int somma=0;
int contatore=0;

for(i=0;i<size-2;i++){

for(i=0;i<w;i++){
somma += v[i];}
if(somma==k){
somma=0;
contatore += 1;} else somma=0;}
return contatore;}

[xbubbax]

allora la funzione prende un vettore, la sua grandezza e una coppia di numeri, ad esempio 13 e 3.

nel vettore devo trovare quante volte ci sono 3 numeri consecutivi che sommati danno 13

se i numeri erano 8 e 2 dovevo trovare nel vettore quante volte c'erano 2 numeri consecutivi che sommati danno 8

ad esempio se i due numeri sono 13 e 3 e il vettore è

v={1,4,5,4,2,7,8,5,5,3,9,2}

il risultato è 2, perchè la prima volta che ci sono 3 numeri consecutivi che sommati danno 13 è quella 4,5,4 e la seconda è 5,5,3 quindi il risultato è 2. spero di essere stato chiaro


comq sempre il mio programma mi sembra perfetto ma non funziona

[sottovento]

Mi sembra buono: l'unica cosa che vedo e' che hai scritto:

for(i=0;i<size-2;i++)

probabilmente intendevi

for(i=0;i<size-w;i++)

in piu' (e' una questione di stile, ma ti puo' salvare da tanti errori), inizializza somma subito prima del secondo ciclo for:

somma = 0
for(j=0;j<w;j++)
{
somma += v[i + j];
}


Come puoi vedere, hai usato 2 cicli for innestati uno nell'altro, e che usano la stessa variabile "i"! Il risultato e' difficile da prevedere. Cambia il ciclo piu' interno, usando per esempio "j". Inoltre la somma deve essere sugli elementi di posizione v[i+j]....

Altro non vedo. Prova e fai sapere....

PS.

int main(void) era proprio
int main()

L'ho scritto cosi' perche' sono vecchio

[sottovento]

PS l'indovinello: e' possibile! E non e' nemmeno difficile, basta pensarci su un attimo

[xbubbax]

Funziona.

Faccio sempre sti errori stupidi, di distrazione, come il fatto della i e j.


per l'indovinello:

comq fai a scrivere gli asterischi sopra e sotto quella scritta se dentro il main non puoi scrivere il programma?

oppure anche al di fuori del main si può scrivere?

non saprei proprio

[sottovento]

comq fai a scrivere gli asterischi sopra e sotto quella scritta se dentro il main non puoi scrivere il programma?
oppure anche al di fuori del main si può scrivere?
non saprei proprio

E' piuttosto facile. Suggerimento importante: stiamo parlando di C++

[xbubbax]

Il C++ non l'ho studiato ancora.

In C non si può risolvere?

[sottovento]

Il C++ non l'ho studiato ancora.

In C non si può risolvere?

Non ne vedo la soluzione. No, non penso proprio...