Newsgroup: it.comp.lang.c++
Titolo: Programma ricorsivo MinMax

Ciao ragazzi!
Avevo bisogno di un parere!
Devo implementare una funzione ricorsiva con questa interfaccia:
void MinMax(int v[], int i, int j, int& min, int& max)
La funzione è una funzione ricorsiva che, prendendo in input un
vettore di interi non ordinato (es. di 10 elementi), il primo indice e
l'ultimo da considerare (es. i=0, j=9 se voglio cercare min e max su
tutto il vettore) e le variabili min e max in cui inserire i risultati,
calcola il minimo e il massimo valore presenti nel vettore. La funzione
è void, quindi i risultati non vengono restituiti ma salvati
direttamente nelle due variabili.
Inoltre la funzione può sfruttare le funzioni
int Min (int m, int n); e int Max (int m, int n);
Avete idea su come implementare la funzione ricorsiva, considerando ad
esempio una chiamata nel main del tipo:
MinMax({4,24,1,54,23,78,65,6,33,10},0,9,min,max) ?
Vi ringrazio se mi saprete dare qualche consiglio implementativo!
Ciao! 
Gabriele

vettore di interi non ordinato (es. di 10 elementi), il primo indice e
A occhio solo uno stupido o un esercizio universitario userebbero una 
funzione ricorsiva in un esercizio del genere.
Quindi immagino il problema faccia parte della 2° categoria. Quindi, data la 
tua probabile pigrizia, ti risolvo il problema e ti auguro di non passarlo. 
Ti do la risposta solo perchè per lo meno ci hai messo tempo a scrivere il 
messaggio in forma compiuta e io ci ho messo meno a risponderti di quanto tu 
ce ne abbia messo a scriverlo.
if (i <= j) {
    min = Min(v[i], min);
    max = Max(v[i], max);
    if (i != j)
        MinMax(v, i + 1, j, min, max)
} else {
    // Errore!
}
Occhio che all'inizio devi inizializzare accortamente min e max.
min = INT_MAX;
max = INT_MIN;
Quindi la cosa migliore sarebbe fare:
void MinMax(int v[], int i, int j, int& min, int& max)
{
    min = INT_MAX;
    max = INT_MIN;
    _MinMax(v, i, j, min, max);
}
void _MinMax(int v[], int i, int j, int& min, int& max)
{
    /// La funzione ricorsiva vera e propria
} 

 }
Dimenticavo. Ovviamente la funzione ricorsiva usa al suo interno se stessa!! 
Quindi _MinMax.
--- bye 

Ti ringrazio per l'aiuto.
L'esercizio è sì un esercizio universitario, ma se ho chiesto una
mano non è perché non avevo voglia di farlo, ma perché avevo qualche
difficoltà. Il fatto di rispondere e dare una mano non credo arroghi
nessun diritto di giudicare o umiliare chi la mano la chiede...
Il bello della rete e dei newsgroup è quello di poter chiedere cose
anche banali... Ognuno è poi libero di rispondere o di non rispondere,
se non ne ha voglia.
Ti ringrazio quindi per la risposta, ma sinceramente mi lascia un po'
sorpreso il tuo tono...
Vabbè, buon pomeriggio!
Ciao,
Gabriele

 funzione ricorsiva in un esercizio del genere.
forse (è una speranza) con ricorsivo non intende rigorosamente 
ricorsivo, ma dicotomico (ciò che può essere facilmente 
implementato in modo ricorsivo, al prezzo di una maggiore 
inefficenza e molto più probabili crash se i dati sono molti o 
sfortunatamente gli entry-point di ricerca mal scelti).
In effetti anche io personalmente odio le implementazioni 
dicotomiche ricorsive quando non proprio necessarie (raro).
Quele che sia l'accezione con cui si intendeva, leggo poi 
l'esempio voluto di chiamata
QUOTE
MinMax({4,24,1,54,23,78,65,6,33,10},0,9,min,max) ?
/QUOTE
e allora qui suona l'allarme : attento che per poter sfoderare 
l'efficienza (e anche solo non mancare i dati cercati), gli 
algoritmi ricorsivi (o solo dicotomici) richiedono espressamente 
di ricevere dati ordinati in input.
Dati random in teoria devono prima essere ordinati. Certo, ci 
sono anche ordinamenti ricorsivi, tipo Quick sort, ma a quel 
punto il guadagno di tempo si manifesta solo per array grandi.
In ogni caso se DEVI assolutamente operare in questo modo, 
garantisciti la chiamata ad una funzione di ordinamento.
Secondariamente ti consiglio anche di semplificarti la vita 
facendo due sotto-chiamate diverse una per la ricerca del minimo 
e l'altra del massimo.
Questo perché se con una ricerca lineare è triviale aggiornare 
entrambe le reference nello stesso loop (aggiungi un confronto 
in più e stop), con la ricorsione non penso sia facile tracciare 
due ambiti di ricerca potenzialmente distinti, disgiunti o 
parzialmente sovrapposti, contemporaneamente.
Quindi separa le due ricerche.
Cmq una ricerca tale su array non ordinati, comincia a giovarsi 
della maggiore efficienza delle routine non lineari solo per 
array piuttosto grossi (almeno un 10000-100000 elementi a 
seconda del peso temporale dei contronti (ad es. se sono double 
sono più time consuming dei long, e limitare il N° di confronti 
è più importante).
ciao
Soviet_Mario


se non ne ha voglia.
Se tu credi di avere il diritto di fare domande banali, io credi di avere il 
diritto di insultare chi fa domande banali :-)
Il mio karma resta in pareggio: ti ho aiutato e ti ho insultato... +1/-1.
Il problema di fondo è che questa domanda NON ti ha reso un programmatore 
migliore (perchè NON hai chiesto un algoritmo generico... Hai chiesto la 
risoluzione di un problema molto specifico), NON ha aiutato altre persone 
che leggono il ng (perchè è improbabile che devano fare un esercizio del 
genere, e anche se dovessero è meglio se se lo fanno da soli). Quindi 
l'unico risultato è che ora hai un esercizio in meno da fare. La vedo un po' 
come barare. E' come se avessi chiesto "chi mi aiuta a barare un pochino 
sugli esercizi universitari"? Dopotutto se ne hai chiesto uno di esercizio e 
io te l'ho risolto, perchè non chiedere anche gli altri? Se NON riuscivi a 
fare l'esercizio perchè troppo difficile evidentemente (scegline una):
A) Non sei pronto per l'esame (perchè troppo difficile/perchè non hai 
studiato abbastanza/perchè non sei abbastanza sveglio/perchè non sei adatto 
alla materia)
B) Non hai capito la materia (vedi le motivazioni di prima)
C) Il tuo prof spiega da cani (sempre possibile)
D) Sei pigro e dopo 5 min hai deciso che era più semplice chiedere al tuo 
compagno di banco (che in questo caso è il ng)
Osserva inoltre che questo problema, con pochi semplici passaggi, è 
assimilabile al problema "base" della ricorsione (il famoso fattoriale 
ricorsivo). Se prendi solo il min o solo il max ti puoi facilmente rendere 
conto che la regola del "prendi un elemento e fa fare la ricorsione a me 
stesso di tutti gli altri elementi (se ce ne sono)" è sempre la stessa. 
Quindi procedendo con il "Dividi et Impera" (regola sempre valida nella 
programmazione) ci saresti riuscito a risolverlo.
Esempio:
int FattorialeRicorsivo(int a)
{
    int curr = a;
    int prod = curr;
    if (curr > 1) {
        int FattRestanti = FattorialeRicorsivo(curr - 1);
        prod *= FattRestanti;
    }
    return prod;
}
int MinRicorsivo(int v[], int numel)
{
    int curr = v[0];
    int min = curr;
    if (numel > 1) {
        int minRestanti = MinRicorsivo(&v[1], numel - 1);
        min = Min(min, minRestanti);
    }
    return min;
}
Se non ho fatto errori di scrittura ecco un perfetto esempio di Minimo 
Ricorsivo praticamente identico a un Fattoriale Ricorsivo in cui ogni 
singolo passaggio è stato esplicitato. Noti la somiglianza? Certo che c'è...
Sul fatto poi che magari ci avresti messo 2 giorni a farlo invece che 10 
minuti... Beh... Cosa avresti fatto se avessi dovuto fare un disegno 
artistico carta & penna? Ci avresti messo 2 giorni e non ti saresti 
lamentato :-) Sì, ogni persona ha i suoi tempi E SE LI TIENE.


Non voglio sindacare sulla tua buona volonta', ma e' un fatto che la
rete pullula di pigroni che cercano di farsi fare i compiti e si puo'
quindi capire l'origine dei sentimenti espressi da MaxMax.
Sono pero' convinto che avrebbe fatto meglio a darti una dritta senza
aggiungere commenti piuttosto che risolvere l'esercizio, a maggior
ragione se aveva il dubbio che tu fossi uno dei pigroni sopra
menzionati.
Ciao,
Nicola

 lamentato :-) Sì, ogni persona ha i suoi tempi E SE LI TIENE.
Beh, c'e' anche chi impara e migliora, soprattutto quando le cose gli
vengono spiegate. ;-)
Ciao,
Nicola

 
Io suggerirei qualcosa di simile... visto che mi sto impratichendo di 
C++ (diciamo che lo sto imparando :-( .. gradirei suggerimenti e 
confronti sulla mia implementazione).
void MinMax(int v[], int i, int j, int& min, int& max)
{
  if (i>j)
	{
	int min_blocco,max_blocco;
	if (i!=j) {
			MinMax(v, i+1, j, min_blocco, max_blocco);
			min=Min(min_blocco,v[i]);
			max=Min(max_blocco,v[i]);
		  } else
		{
		min=v[i];
		max=v[i];
		}
	} else
	{
	//Gestione errore i>j
	}
}
Per MAXMAX:
Mi pare che sia "gemello" del tuo , una sfumatura diversa.... cioe' come 
spiegare il mio ragionamento..mi pare che tu butti il min, max dalla 
chiamante che sta sopra mentre nella mia versione questo va giu' 
giu'subito  fino in fondo e il lavoro parte da li a risalire... oddio 
..odio le ricorsioni.
Magari abbiamo scritto la stessa cosa in modo diverso e mi si e' 
semplicemente aggrovigliato il cervello?
Mi sa che tra un pochetto compilo questo codice e lo provo..
Mi sembra giusto ma potrei aver pure scritto una $%&/ata pazzesca
SAluti a tutti

AHHHHHHHHHHHHHHHHHHHHH
10 righe di codice piene di BUGSSSS
ecco il codice corretto e pronto alla compilazione/esecuzione.... una 
piattaforma di test completa...
Consigli di stilo/forma/errori/pericoli/vizi da correggere sono sempre 
graditi e ->motivo<- per cui posto..saluti
#include <iostream>
int Min(int i, int j)
{
	if (i < j) return i;
	else return j;
}
int Max(int i, int j)
{
	if (i > j) return i;
	else return j;
}
void MinMax (int const v[], int i, int j, int &min, int &max)
{
	if (i <= j)
	{
		int min_blocco, max_blocco;
		if (i != j)
		{
			MinMax (v, i + 1, j, min_blocco, max_blocco);
			min = Min (min_blocco, v[i]);
			max = Min (max_blocco, v[i]);
		}
		else
		{
			min = v[i];
			max = v[i];
		}
	}
	else
	{
		//Gestione errore i>j
	}
}
int main()
{	int max,min;
	int v[] = {4, 24, 1, 54, 23, 78, 65, 6, 33, 10};
	MinMax(v, 0, 9, min, max);
	std::cout<<"min "<< min << std::endl <<"max "<< max;
	return 0;
}
Non riesco a capire perche' non mi permette in nessun caso di fare
MinMax({4, 24, 1, 54, 23, 78, 65, 6, 33, 10}, 0, 9, min, max);
al posto della variabile v creata per aggirare il problema, qualcuno me 
lo spiega?
Saluti

Oops mi e' scappato un BUG la minmax correttà e':
void MinMax (int const v[], int i, int j, int &min, int &max)
{
	if (i <= j)
	{
		int min_blocco, max_blocco;
		if (i != j)
		{
			MinMax (v, i + 1, j, min_blocco, max_blocco);
			min = Min (min_blocco, v[i]);
			max = Max (max_blocco, v[i]);
		}
		else
		{
			min = v[i];
			max = v[i];
		}
	}
	else
	{
		//Gestione errore i>j
	}
}
TESTATO E FUNZIOANNTE!!!!

Probabilemnte non avevo espresso bene, qualcuno ha dei suggerimenti per 
migliorare questa mia implementazione?(soprattuto di stile e per 
eliminare probabili soluzioni poco "professionali"&acerbe)
Saluti

Fabiano wrote:

non mi viene in mente molto, a parte che le tue Min e Max non servono: 
esistono già nella libreria standard del c++ e si chiamano std::min ed 
std::max (si trovano in <algorithm>).
-- 
MSN: sirpsycho_78 -at- hotmail dot com
"Miss, simme juti a fernì int' 'o cess, e mo' ca rimango 'i sulo, te 
mann 'a fanculo."
"Chì la zent la pasa a far banzeina e quel l'an an'va'! Non si può 
andare avanti così!"

 
Primo passo avanti =).. grazie