+ Rispondi al Thread
Visualizzazione dei risultati da 1 a 10 su 10

Discussione: [Div et impera] ricerca indici i,j per cui A[i]*A[j]=N

  1. #1
    tvd_40 non è in linea Novello
    Post
    9

    [Div et impera] ricerca indici i,j per cui A[i]*A[j]=N

    Help me! per favore!
    Non riesco a risolvere questo esercizio :

    Dato un vettore ordinato di interi A[1 . . . n] ed un intero N, si progetti e si analizzi
    un algoritmo basato sulla tecnica Divide et Impera che, preso in input il vettore A ed il numero
    N determini se esistono o meno due indici i e j per cui A[i] × A[j] = N.

    L'idea potrebbe essere questa :
    codice:
    Alg(A,i,j,x,N)
    if (j=i) return false    
    m = (i+j)/2
    if ((A[m]*x) = N) return true
    if ((A[m]*x)> N) return Alg(A,i, m-1,x,N)
    else return Alg(A,m+1,j,x,N)
    Ultima modifica di AntonioG; 26-10-2013 12:51 

  2. #2
    tvd_40 non è in linea Novello
    Post
    9
    Così è più accettabile?

    codice:
    Algo (A[i..j],N)
    if (i>j) return false   //array vuoto
    m = (i+j)/2
    if (A[m]=N)
        for l=1 to m
           for r=l+1 to m
              if ((A[l]*A[r]) = N) return true
              else return false
    if (A[m]>N)
    Algo(A[i...m-1],N)
    else
    Algo(A[m+1...j,N])
    Help me!
    Vi prego!!
    Ultima modifica di tvd_40; 30-09-2013 17:39 

  3. #3
    Luogo
    marte
    Post
    635
    Blogs
    2
    codice:
    int DivetImperia(int A[],int szA,int N,int* i,int* j)
    {
        for (*i=0; *i < szA - 1 ; (*i)++)
        {
            for (*j = *i; *j < szA ;(*j)++)
            {
                if (A[*i] * A[*j] == N)
                    return 1;
            }
        }
    
        return 0;
    }
    
    
    int main()
    {
        int A[10] = {3,5,21,34,115,550,1024,2480,9999,12000};
    
        int i,j;
    
        int N = 63;
    
        if (DivetImperia(A,10,N,&i,&j))
        {
            printf("A[i] * A[j] = N \n");
            printf("A[%d] * A[%d] = %d \n",i,j,N);
            printf("%d * %d = %d\n",A[i],A[j],N);
        }
        else
        {
            printf("Nessun A[i] * A[j] = N\n");
        }
    
        return 0;
    }
    Potrebbe andare?
    Ultima modifica di AntonioG; 01-10-2013 12:41 
    Easy framework per il linguaggio C.
    vbextreme hack your life

  4. #4
    tvd_40 non è in linea Novello
    Post
    9
    Prima di tutto grazie mille per la risposta

    ..solo che non ho capito la tecnica divide et impera come l'hai applicata..

    scusami probabilmente sono un po' dura di comprendonio

  5. #5
    Luogo
    marte
    Post
    635
    Blogs
    2
    no scusa a te che ho perso il thread...
    semplicemente scorro tutto il primo array e lo moltiplico passo passo per il secondo,se uguale ad N restituisco:

    [Pseudo code]
    codice:
    array a[?]=valori casuali
    array b[?]=valori casuali
    
    per ogni elemento di a
        per ogni elemento di b
            moltiplico a*b se = N restituisco i valori
        end b
    end a
    piu che altro è una tecnica di "brute force" ovvero cerco ogni possibile soluzione e se trovo il risultato restituisco il tutto.
    Easy framework per il linguaggio C.
    vbextreme hack your life

  6. #6
    Paolodocet non è in linea Novello
    Post
    39

    Vediamo...

    Ciao,
    Per prima cosa attenzione, un algoritmo divide et impera, utilizza la RICORSIONE. Quindi non si deve scorrere l'array, anzi, per quanto mi riguarda, non ho mai visto un algoritmo divide et impera che usi un for per scorrere l'array.
    Il divide et impera, si fonda su tre parti:
    1. Individuare i casi base, in altri termini, tutte le volte che riesco a trovare la soluzione ad un problema, immediatamente senza fare nulla. Nel tuo caso, se ci sono, due elementi, vado semplicemente a verificare se la moltiplicazione mi restituisce un valore uguale ad N.

    2. Divido l'array in due parti, e risolvo RICORSIVAMENTE, i sotto problemi. Cioè in parole povere, cerco di avvicinarmi al caso base: se ho cinque elementi, divido l'array in parti più piccole! fino a quando non posso utilizzare i casi base per risolvere il sotto problema.

    3. Unisco il tutto.

    A mio parere l'algoritmo, ti chiede semplicemente, di rispondere TRUE o FALSE, ma non ti chiede di trovare pure gli indici. Quindi sostanzialmente si tratta di una metodo che deve restituire un booleano. Bene, io lo risolverei così, credo che funzioni:

    codice:
    Boolean calcola(A[], int N, int i, int j) {
    
    Boolean a = false
    
    If(j-i+1 = 2 AND A[i] * A[j] = N) //se nel l'array ci sono 2 elementi e il loro prodotto è N, ritorniamo TRUE 
    Return TRUE;
    
    If(j-i+1 = 2 AND A[i] * A[j] != N) // in caso contrario, ritorniamo false
    Return false
    
    If(j-i+1 < 2) // ritorniamo false pure se ci sono meno di due elementi
    Return false
    
    m=(i+j)/2
    
    If(A[m] <= N AND m+1 < j AND A[m] * A[m+1] =N) // questa serve perché quando dividiamo l'array potrebbe essere
    a = TRUE.                                           // che l'elemento alla metà del l'array moltiplicato per quello successivo        
                                                    // rispetti la nostra condizione. Se A[m] è più grande di N, non ha senso fare   
                                                    // il controllo dato che i numeri sono ordinati e che c'è una moltiplicazione
    
    
    Boolean b = calcola(A,N,i,m)
    Boolean c = calcola (A,N,m+1, j)
    
    If (a or b or c) // non ci resta che unire il tutto. Se almeno una tra a, b, c è TRUE, allora significa che il nostro metodo  
                               // deve ritornare TRUE.
    Return TRUE
    
    Else 
    Return false

    Non ho controllato attentamente, quindi magari ho fatto qualche svista, ma credo che debba funzionare.
    Ciao, se hai bisogno di qualcosa, non esitare a chiedere.
    Ultima modifica di Paolodocet; 23-10-2013 19:20 

  7. #7
    tvd_40 non è in linea Novello
    Post
    9
    siiii..grazie!
    E' perfetto!!
    non riuscivo ad imbroccare il ragionamento giusto!
    Grazie mille!

  8. #8
    tvd_40 non è in linea Novello
    Post
    9
    Devo aggiungere [risolto] al titolo?

  9. #9
    L'avatar di AntonioG
    AntonioG non è in linea Moderatore Globale Ultimo blog: Commodore 64 e Codemotion
    Luogo
    Roma
    Post
    16,225
    Blogs
    5
    Fatto ... Ciao
    Avvisi generali e importanti, a pena CHIUSURA thread e/o BAN
    Il crossposting è vietato.
    Le richieste di "pappa pronta" sono vietate.
    Utilizzate i tag CODE per il codice.
    Leggere il Regolamento per chiarimenti PRIMA di creare nuovi thread.
    Utilizzare sempre i PM per comunicare con i moderatori.
    Non mi contattate in PM per problemi di software, usate il forum

  10. #10
    Paolodocet non è in linea Novello
    Post
    39
    Figurati, buono studio!

+ Rispondi al Thread

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi