Pagina 1 di 2 1 2 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 12
  1. #1
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    55

    [C] Partizione di un array, dubbio su un punto...

    Ciao a tutti!
    Devo creare un algoritmo che esegue il partizionamento di un array, però ho alcuni dubbi.

    Innanzitutto, il valore di partizionamento deve essere nnecessariamente contenuto nell'array? ad esempio, se io volessi partizionare l' array 1 2 4 8 3 6 9 5 utilizzando come valore d partizionamento il 7, posso farlo?

    Altro dubbio: se nell'array il valore di partizionamento è contenuto 2 o più volte, come è possibile partizionarlo?

  2. #2
    1. In che linguaggio?
    2. Il da farsi in questi "corner case" dipende dalle specifiche della tua funzione, non c'è necessariamente una cosa giusta... Anche se quello che io mi aspetterei sarebbe di restituire l'array intero se il separatore non c'è, e restituire più array nel caso di più presenze del separatore.
    Amaro C++, il gusto pieno dell'undefined behavior.

  3. #3
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    55
    in c, scusa se non ho specificato..

    comunque non ho capito il nesso del tuo punto 2 con la mia domanda xD

  4. #4
    Il punto 2 è la mia risposta alle tue domande... ovvero, sostanzialmente quello che devi fare nei "casi strani" che hai citato non ha necessariamente una risposta giusta, dipende da come definisci "partizionare".
    Amaro C++, il gusto pieno dell'undefined behavior.

  5. #5
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    55
    capisco...
    comunque sto cercando di creare l'algoritmo ma purtroppo non funge in alcuni casi....

    potresti postarne uno in c che funzioni almeno nei casi generali?... vorrei capire dove sto sbagliando...

  6. #6
    Posta quello che hai scritto finora e la consegna (nel caso sia un esercizio), che partiamo da quello.
    Amaro C++, il gusto pieno dell'undefined behavior.

  7. #7
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    55
    la consegna dice semplicemente "partizionamento di un array" riferendosi (come suggerimento) all'algoritmo 4.5 di dromey...

    ecco l'algoritmo:

    codice:
    //altro codice ....
    i=0;
    j=n-1;
    
    do
    {
     while(array[i]<=p && i<j) i++;  //dove p è il valore di partizione
     while(array[j]>p && i<j) j--;
     
    if(i<j)
     change(array,i,j);  //scambia gli elementi di posto i e j
    
    } while(i<j);
    
    //altro codice...
    questo codice funziona senza problemi, ma mi sto fissando sulle eventualià scritte sopra


    P.S l'if(i<j) prima della chiamata alla funzione change può anche essere omesso ma mi sembra rischioso, tu che consigli?

  8. #8
    Ah pardon, per qualche motivo avevo inteso partizionamento in un altro senso... comunque, mi pare che sia corretta; sui tuoi due casi:
    - p non presente: non è un problema, nel codice non cerchi mai l'eguaglianza con p, ma solo il > o il <=;
    - p è presente più volte: anche qui, proprio perché non cerchi l'uguaglianza ma le disuguaglianze di cui sopra, è possibile partizionare, semplicemente la zona dei >p inizierà solo dopo l'ultima occorrenza di p.
    P.S l'if(i<j) prima della chiamata alla funzione change può anche essere omesso ma mi sembra rischioso, tu che consigli?
    L'i<j è sempre verificato s all'inizio del do lo era (dato che i due while modificano i e j solo se i<j); l'unico caso in cui si può avere i<j quindi è se alla prima iterazione i>=j (ovvero, se n=0 o n=1); per n=1 non è un problema, per n=0 (e j=-1) può essere un problema per il secondo while (vai a guardare array[-1].
    Per questo motivo, toglierei l'if e cambierei il do...while in un semplice while, per evitare di entrare nel ciclo nel caso n=0.
    Ultima modifica di MItaly; 21-12-2014 a 20:39
    Amaro C++, il gusto pieno dell'undefined behavior.

  9. #9
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    55
    capisco,
    grazie mille anche per il do..while in while, non avevo considerato il caso n=0 xD

    Purtroppo quest'esercizio mi ha mandato in confuzione grazie alle mie solite paranoie :S

  10. #10
    Amaro C++, il gusto pieno dell'undefined behavior.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.