Ho questo problema: "Algoritmo del massimo di un array 1D (di size
qualunque, non necessariamente potenza intera di 2) di char, approccio
divide et impera, implementato con tecnica ricorsiva e variante
casuale. L'idea è quella dell'algoritmo implementato in max_radd, ma
l'implementazione deve essere fatto con tecnica ricorsiva. La variante
casuale prevede che, a ogni passo, una porzione di array (per esempio
quella individuata dal primo indice =8 e dal secondo indice = 20) non
venga divisa esattamente a metà, ma venga suddivisa in due parti per
esempio (da 8 a k) e (da k+1 a 20) dove k è un numero casuale in
(9,10,11,...,19). Quindi, per es., la prima suddivisione di array (1..n)
avverrà scegliendoa caso un intero tra 2 e n-1 e non necessariamente
scegliendo l'indice (n+1)/2.
Usare la function rand(), il cui prototipo è in <stdlib.h>, per
generare a caso un numero intero: si ricorda che, se numero_casuale è
dichiarata di tipo int, allora l'istruzione numero_casuale=rand()/(n
+1);
genera un numero casuale di tipo int (distribuzione uniforme) in
{0,1,.., n}."
Finora ho scritto il seguente codice, ma non riesco a procedere con le
operazioni nella chiamata ricorsiva (oltre ad altri errori che non
riesco a individuare):
#include <stdio.h>
#include <stdlib.h>
char max(char [],int );
int main()
{
int n,i,j;
printf("Inserisci il numero degli elementi:\n");
scanf("%d",&n);
char a[n], massimo;
for (i=0; i<n; i++)
{
a[i]=rand();
printf("a(%d)=%c \n",i,a[i]);
}
massimo= max(a, n);
printf("Il massimo dell'array e' %c\n", massimo);
system ("PAUSE");
return 0;
}
char max(char a [], int n)
{
int numero_casuale,n1,n2;
char max_elem, max_elem1, max_elem2;
numero_casuale=rand()%(n+1);
if n==1 max_elem=a[0];
else if n==2 {
if a[0]>a[1]
max_elem= a[0];
else
max_elem=a[1];
}
else
{
for (i=0; i<=numero_casuale; i++) /
*chiamata ricorsiva
{
n1=numero_casuale;
max_elem1=max(a[],n1);
}
for (i=numero_casuale; i<n; i++)
{
n2=n-numero_casuale;
max_elem2=max(a[],n2);
}
if max_elem1>=max_elem2 /*confronto
elementi massimi ottenuti nelle divisioni delle due parti di array
iniziale*/
max_elem=max_elem1;
else
max_elem=max_elem2;
}
return max_elem;
}
Rispondi quotando
