Newsgroup: it.comp.lang.c
Titolo: Problema ricerca massimo in array

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;
}

 {0,1,.., n}."
Devi prendere il resto della divisione tra interi, non il risultato della
divisione.
Sotto poi usi % quindi va bene.

I numeri sono n.
Gli indici del vettore vanno da 0 a n-1.
Numero casuale può assumere valori da 0 a n.
Facciamo un esempio.
- n = 6
- numero_casuale = 2
Si hanno le chiamate:
      Primo for
            max_elem1 = max(a[], 2);    (i=0)
            max_elem1 = max(a[], 2);    (i=1)
            max_elem1 = max(a[], 2);    (i=2)
      Secondo for
            max_elem1 = max(a[], 4);    (i=2)
            max_elem1 = max(a[], 4);    (i=3)
            max_elem1 = max(a[], 4);    (i=4)
            max_elem1 = max(a[], 4);    (i=5)
Osservazioni:
- non servono a niente i for, basta fare solo una chiamata alla funzione max
per il primo sottovettore e una per il secondo sottovettore
- nella chiamata di max presente nel secondo for viene passato erroneamente
a[], così si parte dalla posizione 0 del vettore
- se numero_casuale vale n (è random), il secondo for non viene eseguito e
max_elem2 risulta non definito (ha un valore a caso)
- se numero_casuale vale 0 (è random), il secondo for chiama "max(a[], n)",
non si riduce la dimensione del vettore, potenzialmente potresti non finire
mai
Non ha senso usare numero_casuale pari a 0 o a n (in questo caso i 2
sottovettori sono uno di 0 elementi e l'altro di n elementi).

Scusate la mia ignoranza. Ma per trovare il max di un array, non vedo 
come si possa trovare un algoritmo migliore allo "scorri tutto l'array e 
ricordati il massimo valore trovato". Ogni algoritmo infatti deve 
verificare tutti gli elementi per avere la sicurezza che il valore 
trovato sia il max assoluto.
E.


 ...
In effetti se l'array non e` ordinato questo e` 
l'agoritmo migliore.
Se pero` l'array e` ordinato esiste un algoritmo 
molto migliore di questo, addirittura O(1): 
il massimo ed il minimo sono il primo e l'ultimo 
elemento dell'array.
PS ordinare l'array con quicksort ed applicare 
l'algoritmo O(1) (come credo volesse l'esercizio)
non funziona.

 trovato sia il max assoluto.
...bhe', in questo caso, se a[0] e' gia' uguale a CHAR_MAX non hai 
bisogno di scorrerlo tutto :)
Ciao
-- 
Cybertoldo
Per rispondermi via email, sostituisci moc.liamg con 
gmail.com