View Full Version : [c] ricorsione
Come trovare il minimo di un array 1D con metodo ricorsivo? :mbe:
Ho provato varie strade ma credo di essere giunto a qualche cosa di troppo complesso! Deve esserci sicuramente un metodo MOLTO più facile!
Come trovare il minimo di un array 1D con metodo ricorsivo? :mbe:
Ho provato varie strade ma credo di essere giunto a qualche cosa di troppo complesso! Deve esserci sicuramente un metodo MOLTO più facile!Scusa... perché usare la ricorsione quando basta un semplice ciclo for??
Come trovare il minimo di un array 1D con metodo ricorsivo? :mbe:
Ho provato varie strade ma credo di essere giunto a qualche cosa di troppo complesso! Deve esserci sicuramente un metodo MOLTO più facile!
qualcosa del genere:
int array_min( int* data, int length )
{
return rec_min( data[0], data+1, length -1);
}
int rec_min( int x, int* data, int length )
{
if (length == 0 )
return x;
x = min(x,data[0])
return rec_min( x , data+1, length-1);
}
Che tra l'altro dovrebbe risultare tail-recursive.
Scusa... perché usare la ricorsione quando basta un semplice ciclo for??
perché purtroppo quando le persone incompetenti chiedono di realizzare qualche cosa per dei corsi non si rendono conto che così non insegnano a programmare ma confondono solo le idee....
Che tra l'altro dovrebbe risultare tail-recursive.
tail-recursive significa???
Pensa che in realtà si dovrebbe creare una ricerca di minimo con ricorsione e approccio divide et impera...
assurdo da un punto di vista della logica della programmazione :doh:
tail-recursive significa??? che si converte in un algoritmo iterativo con estrema naturalezza e semplicità :D
Pensa che in realtà si dovrebbe creare una ricerca di minimo con ricorsione e approccio divide et impera...
prova questa porcheria ma non ti fidare troppo, l'ho scritta in 2 secondi senza manco provare :D
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define F FunzioneTotalmenteImbecille
int FunzioneTotalmenteImbecille(int *Array, int Start, int End) {
if (End == Start) {
return Array[Start];
}
return MIN(F(Array, Start, Start + (End - Start) / 2),
F(Array, Start + (End - Start) / 2 + 1, End));
}
assurdo da un punto di vista della logica della programmazione :doh: concordo, e sono sinceramente contento per te che tu l'abbia capito: vuol dire che nonostante le assurde richieste dei professori, se gli studenti ci mettono del loro alla fine qualcosa in termini di preparazione la guadagnano lo stesso. intendiamoci, ovviamente sarebbe tutto più facile se i professori evitassero di andare controcorrente...
ma perché non chiedi al tuo prof di farvi fare algoritmi che meritino realmente un approccio divide et impera? come ad esempio uno dei tanti algoritmi di ordinamento... -_-'
perché purtroppo quando le persone incompetenti chiedono di realizzare qualche cosa per dei corsi non si rendono conto che così non insegnano a programmare ma confondono solo le idee....Purtroppo non posso fare altro che quotare quanto appena detto. :( Direi volentieri qualcos'altro sui professori ... ma è meglio se non lo faccio. :Perfido:
Ah, per il minimo di un array ci ho provato anche io. Ecco la "mia" soluzione:
int int_array_min (int *arr, int length)
{
int min = *arr;
if (length > 1)
min = int_array_min (arr+1, length-1);
return *arr < min ? *arr : min;
}
int main (void)
{
int a[4] = { 12, 5, 7, 20 };
int min;
min = int_array_min (a, 4);
return 0;
}Non l'ho provata al 100% ma credo che sia ok.
ma perché non chiedi al tuo prof di farvi fare algoritmi che meritino realmente un approccio divide et impera? come ad esempio uno dei tanti algoritmi di ordinamento... -_-'
e vero, ma è l'unico modo per forzare gli studenti a provare la programmazione ricorsiva.
anche se sarebbe meglio impararla su un linguaccio funzionale(io ho imparato su schema, e anche io all'epoca lo odiavo...)
che si converte in un algoritmo iterativo con estrema naturalezza e semplicità :D
prova questa porcheria ma non ti fidare troppo, l'ho scritta in 2 secondi senza manco provare :D
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define F FunzioneTotalmenteImbecille
int FunzioneTotalmenteImbecille(int *Array, int Start, int End) {
if (End == Start) {
return Array[Start];
}
return MIN(F(Array, Start, Start + (End - Start) / 2),
F(Array, Start + (End - Start) / 2 + 1, End));
}
concordo, e sono sinceramente contento per te che tu l'abbia capito: vuol dire che nonostante le assurde richieste dei professori, se gli studenti ci mettono del loro alla fine qualcosa in termini di preparazione la guadagnano lo stesso. intendiamoci, ovviamente sarebbe tutto più facile se i professori evitassero di andare controcorrente...
:mbe:
L'approccio divide et impera qua non ti serve, l'array non è ordinato e devi *comunque* passare in rassegna tutti gli elementi . Se fai un paio di conti vedrai che all'incirca fai lo stesso numero di confronti. A voler essere pignoli, in questo modo accedi "a saltoni" alla memoria, col probabile risultato di rallentare l'afflusso dei dati alla cpu (soprattutto se l'array è piu' grande della cache del processore).
e vero, ma è l'unico modo per forzare gli studenti a provare la programmazione ricorsiva.
anche se sarebbe meglio impararla su un linguaccio funzionale(io ho imparato su schema, e anche io all'epoca lo odiavo...)
Concordo, una volta assimilata la ricorsione diventa piu' naturale e pure semplice da capire.
In questo caso pero' l'esempio non è dei migliori ([i]grazie[(i] anche alla scelta del C come linguaggio).
:mbe:
L'approccio divide et impera qua non ti serve, [...] l'ha detto lui che serve, è una richiesta dell'esercizio
il_luridone
28-05-2006, 01:06
io risolverei così
int
minimo (int *input, int p, int r)
{
int q; /* mediano attorno il quale dividiamo l'array */
if ((r - p) > 0)
{
q = floor ((r - p) / 2);
return MIN (minimo (input, p, p + q), minimo (input, p + q + 1, r));
}
else
return input[p];
}
input è l'array di interi, p e r sono gli indici del primo e dell'ultimo elemento. Per esempio, se hai un array con tre interi, hai p = 0 e r = 2.
Se r - p > 0 allora hai più di un elemento nell'array e hai bisogno di spezzare il problema: q è il mediano inferiore dell'array e le due parti vengono passate a due chiamate ricorsive della funzione.
Se r - p == 0 allora l'array ha un solo elemento, che è banalmente il minimo dell'array.
Quando le ricorsioni spezzettano i sottoproblemi fino ad arrivare ad array di un elemento, la ricorsione finisce e i numeri ritornati vengono confrontati dalla macro MIN
#define MIN(x,y) ((x) < (y) ? (x) : (y))
che non è altro che un condizionale per selezionare il numero minore.
Questo è un semplice codice di test, se lo intitoli "min_ricorsivo.c" lo puoi compilare con "gcc -Wall -ansi -pedantic -lm -o min_ricorsivo min_ricorsivo.c"#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MIN(x,y) ((x) < (y) ? (x) : (y))
int
minimo (int *input, int p, int r)
{
int q;
if ((r - p) > 0)
{
q = floor ((r - p) / 2);
return MIN (minimo (input, p, p + q), minimo (input, p + q + 1, r));
}
else
return input[p];
}
int
main (int argc, char **argv)
{
int i;
int *input;
input = (int *) malloc ((argc - 1) * sizeof (int));
if (input == NULL)
{
perror ("errore malloc");
exit (1);
}
if (argc == 1)
{
printf ("uso: min_ricorsivo <numeri interi>\n");
printf ("i numeri interi devono essere separati da spazi.\n");
exit (1);
}
for (i = 1; i < argc; i++)
{
input [i-1] = strtol(argv[i], (char **)NULL, 10);
printf ("%d ", input [i - 1]);
}
printf ("\n");
printf ("min = %d\n", minimo(input, 0, argc - 2));
return 0;
}Metti qualche numero come argomento a linea di comando e dovrebbe sputare il minimo. Per capire bene cosa succede aiuta sicuramente disegnare l'array di input su un foglio ed eseguire il programma passo passo con un debugger, controllando tutti i valori delle variabili e aggiornando di conseguenza il disegno.
Spero vada bene, l'ora è quella che è :stordita:
perché purtroppo quando le persone incompetenti chiedono di realizzare qualche cosa per dei corsi non si rendono conto che così non insegnano a programmare ma confondono solo le idee....
tail-recursive significa???
Significa che l'ultima istruzione della funzione e` la chiamata ricorsiva. Molti compilatori di linguaggi funzionali possono usarla per ottimizzare l'uso dello stack (non credo che ci siano compilatori c che lo fanno)
Pensa che in realtà si dovrebbe creare una ricerca di minimo con ricorsione e approccio divide et impera...
assurdo da un punto di vista della logica della programmazione :doh:
Delirio puro. :muro:
(primo post: saluti a tutti!)
Concordo, una volta assimilata la ricorsione diventa piu' naturale e pure semplice da capire.
In questo caso pero' l'esempio non è dei migliori ([i]grazie[(i] anche alla scelta del C come linguaggio).
Comunque anche con un linguaggio funzionale nessuno userebbe mai la ricorsione per cercare il minimo in un vettore, in lisp:
(reduce #'min array)
l'ha detto lui che serve, è una richiesta dell'esercizio
Chiedo scusa, non l'avevo capito :p
Comunque anche con un linguaggio funzionale nessuno userebbe mai la ricorsione per cercare il minimo in un vettore, in lisp:
(reduce #'min array)
Sicuro, se non altro perchè abbiamo funzioni di piu' alto livello già pronte . Il mio discorso era che, volendo scriversela, di solito la versione ricorsiva riesce ad essere piu' elegante e chiara della corrispondente iterativa, ma in questo caso è il contrario.
Il mio discorso era che, volendo scriversela, di solito la versione ricorsiva riesce ad essere piu' elegante e chiara della corrispondente iterativa, ma in questo caso è il contrario.
Diciamo che dipende, certe cose sono piu` chiare con un loop, certe ricorsivamente.
il_luridone
28-05-2006, 16:16
A me non sembra tanto strano che la didattica insegni roba poco utile in pratica ma semplice concettualmente.
Capire un concetto nuovo come la ricorsione partendo da casi reali mi sembra controproducente. Una volta compreso il concetto grazie all'esempio banale e scolastico, si può procedere per gradi di difficoltà (come si fa sempre in ogni corso non solo informatico).
Poi sarà compito dello studente digerire il concetto elementare ed applicarlo ai casi veri.
A me non sembra tanto strano che la didattica insegni roba poco utile in pratica ma semplice concettualmente.
Capire un concetto nuovo come la ricorsione partendo da casi reali mi sembra controproducente. Una volta compreso il concetto grazie all'esempio banale e scolastico, si può procedere per gradi di difficoltà (come si fa sempre in ogni corso non solo informatico).
Poi sarà compito dello studente digerire il concetto elementare ed applicarlo ai casi veri.
E qual'e` lo scopo didattico di scrivere algoritmi inutilmente contorti?
E qual'e` lo scopo didattico di scrivere algoritmi inutilmente contorti? imparare la sofisticata tecnica della contorsione, anche detta yoga informatico; aiuta a ritrovare il benessere interiore del tuo software: diurifica, vivifica, slarga le vene, fa ca@are bene.
il_luridone
28-05-2006, 19:51
E qual'e` lo scopo didattico di scrivere algoritmi inutilmente contorti?
Lo scopo didattico di questo eserecizio è imparare la ricorsione. È inutilmente contorto al fine di trovare il minimo in un array in modo efficace ed elegante, ma il fine dell'esercizio non è tanto la ricerca in sè, ma appunto la ricorsione. È un pretesto, per intenderci.
Usare l'algoritmo giusto al momento giusto è sacrosanto, ma non è attuale. Adesso deve imparare la ricorsione. Non credo che il prof a lezione abbia detto "questo è il modo migliore per trovare il minimo". Piuttosto avrà detto "questa è la ricorsione, provate voi a cercare il minimo in un array di interi".
slarga le vene
Mi hai convinto, da ora in poi se devo scorrere un array usero` la ricorsione divide et impera e partiro` dall'elemento nel mezzo.
dottorkame
24-07-2006, 10:34
Lo scopo didattico di questo eserecizio è imparare la ricorsione. È inutilmente contorto al fine di trovare il minimo in un array in modo efficace ed elegante, ma il fine dell'esercizio non è tanto la ricerca in sè, ma appunto la ricorsione. È un pretesto, per intenderci.
Usare l'algoritmo giusto al momento giusto è sacrosanto, ma non è attuale. Adesso deve imparare la ricorsione. Non credo che il prof a lezione abbia detto "questo è il modo migliore per trovare il minimo". Piuttosto avrà detto "questa è la ricorsione, provate voi a cercare il minimo in un array di interi".
Hai ragione fino ad un certo punto, e' vero che per capire i concetti all inizio e' meglio fare qualche esercizio "inutile" e assurdo logicamente, ma a volte si esgera. Io sto diventando scemo per fare un sillabatore in prolog, e' un po come cercare di bere un pentolone d' acqua con una forchetta...
Vash1986
24-07-2006, 11:56
E come disse il mio professore all'università... la ricorsione è molto sofisticata, ma quando può essere evitata, evitatela!!
trallallero
24-07-2006, 12:16
imparare la sofisticata tecnica della contorsione, anche detta yoga informatico; aiuta a ritrovare il benessere interiore del tuo software: diurifica, vivifica, slarga le vene, fa ca@are bene.
:sbonk:
E come disse il mio professore all'università... la ricorsione è molto sofisticata, ma quando può essere evitata, evitatela!! il tuo professore è un co***one (come quasi tutti gli altri del resto :fagiano: )
Vash1986
24-07-2006, 12:50
il tuo professore è un co***one (come quasi tutti gli altri del resto :fagiano: )
intendi dire che preferisci una funzione ricorsiva a un ciclo for? :rolleyes:
intendi dire che preferisci una funzione ricorsiva a un ciclo for? :rolleyes:
Dipende.
Il problema della ricorsione è che viene spesso illustrata con esempi ridicoli, controproducenti e sbagliati.
Esempi tipici con i quali viene introdotta la ricorsione sono il calcolo del fattoriale e la serie di fibonacci, che sono probabilmente la scelta peggiore tra la rosa delle scelte peggiori.
D'altro canto, la ricorsione è una tecnica potente che merita di essere appresa in quanto fornisce le soluzioni più eleganti ed efficaci per tutta una serie di problematiche, penso ad esempio ad un parser top-down.
E poi si, i professori sono al 99% dei raccomandati, quindi è dura trovarne uno buono.
intendi dire che preferisci una funzione ricorsiva a un ciclo for? :rolleyes: intendo dire che troppa gente fa delle questioni informatiche questioni religiose: sono tutti strumenti, si usano quando servono.
Esempi tipici con i quali viene introdotta la ricorsione sono il calcolo del fattoriale e la serie di fibonacci, che sono probabilmente la scelta peggiore tra la rosa delle scelte peggiori. ma no, dimentichi la ricerca del minimo in un vettore :asd:
Vash1986
24-07-2006, 17:09
intendo dire che troppa gente fa delle questioni informatiche questioni religiose: sono tutti strumenti, si usano quando servono.
Non è una questione religiosa... sono consigli che si danno ad apprendisti programmatori. Non è che tutti arrivano a capire automaticamente che un ciclo for è più efficiente di una ricorsione ove è possibile implementarlo facilmente (come il calcolo fattoriale).
Che poi ci sono casi in cui questo, in cui si fa della ricorsione uno strumento, come dici tu, per fini didattici è un altro discorso.
Anche se personalmente ritengo più proficuo a livello didattico non dire allo studente: "risolvi questo problema con una ricorsione", bensì lasciare alla sua testolina il compito di decidere quando questa è veramente necessaria e proficua.
E poi si, i professori sono al 99% dei raccomandati, quindi è dura trovarne uno buono.
Esagerato... diciamo all'80% :p
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.