Problema Java

di
sc1512
il
4 risposte
S
sc1512
Pochi posts
Iscritto da
feb, 2016
Messaggi:
3

Problema Java

Ciao a tutti,
sono nuovo nella programmazione e sto affrontando questo problema, che consiste, dato in input un numero intero n ed un array completamente casuale di interi (quindi: lunghezza variabile, interi casuali), nel verificare che esista un sottoinsieme in questo array contenente elementi la cui somma sia uguale ad n.

Vi ringrazio in anticipo per l'aiuto.

4 Risposte

  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6284

    Re: Problema Java

    sc1512 ha scritto:

    dato in input un numero intero n ed un array completamente casuale di interi (quindi: lunghezza variabile, interi casuali), nel verificare che esista un sottoinsieme in questo array contenente elementi la cui somma sia uguale ad n.
    Innanzitutto, se ti aspetti che qualcuno ti scriva il codice ... no, è contro il regolamento, tra l'altro. Se invece vuoi qualche indizio/suggerimento, allora sì, ben volentieri perlomeno da parte mia.

    Parli di "sottoinsieme", questo vuol dire una sequenza contigua di un tot elementi. Quindi vuol dire che devi "provare" con tutti i possibili sottoinsiemi.

    Se hai la sequenza: 10 8 3 7

    Dovrai provare a sommare i sottoinsiemi:

    10
    10 8
    10 8 3
    10 8 3 7
    8
    8 3
    8 3 7
    3
    3 7
    7

    Cosa puoi osservare in questa progressione?
  • S
    sc1512
    Pochi posts
    Iscritto da
    feb, 2016
    Messaggi:
    3

    Re: Problema Java

    andbin ha scritto:

    sc1512 ha scritto:

    dato in input un numero intero n ed un array completamente casuale di interi (quindi: lunghezza variabile, interi casuali), nel verificare che esista un sottoinsieme in questo array contenente elementi la cui somma sia uguale ad n.
    Innanzitutto, se ti aspetti che qualcuno ti scriva il codice ... no, è contro il regolamento, tra l'altro. Se invece vuoi qualche indizio/suggerimento, allora sì, ben volentieri perlomeno da parte mia.

    Parli di "sottoinsieme", questo vuol dire una sequenza contigua di un tot elementi. Quindi vuol dire che devi "provare" con tutti i possibili sottoinsiemi.

    Se hai la sequenza: 10 8 3 7

    Dovrai provare a sommare i sottoinsiemi:

    10
    10 8
    10 8 3
    10 8 3 7
    8
    8 3
    8 3 7
    3
    3 7
    7

    Cosa puoi osservare in questa progressione?
    Il problema sta nel fatto che la sequenza non deve obbligatoriamente essere contigua, gli elementi possono in posizione i, i+4 ed i+7 per esempio.
  • S
    sc1512
    Pochi posts
    Iscritto da
    feb, 2016
    Messaggi:
    3

    Re: Problema Java

    Porto un esempio:
    dato [1, 2, 4, 5, 10] come vettore e n = 20, in maniera sequenziale non trovo una somma == 20, sebbene se sommassi gli elementi in posizione 0, 2, 3, 4 (quindi: 1+4+5+10) otterrei 20.
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6284

    Re: Problema Java

    sc1512 ha scritto:

    Il problema sta nel fatto che la sequenza non deve obbligatoriamente essere contigua
    Ok, allora è un requisito ben preciso che cambia le cose (e che avresti dovuto precisare prima). Quando si parla di array/vettori, per "sottoinsieme" generalmente si intende un range contiguo di elementi.

    Quindi se tu intendi "una qualunque combinazione degli elementi" allora è da vedere proprio così: tutte le combinazioni possibili degli N elementi prendendoli a gruppi che possono andare da 1 a N elementi. Alla fin fine è lo stesso insieme di combinazioni fattibili in binario:

    0 0 0 0
    0 0 0 1
    0 0 1 0
    0 0 1 1
    ......
    1 1 1 1

    dove 1 vuol dire "prendo l'elemento" e 0 "scarto l'elemento" in quella posizione. Quindi se hai N elementi dovrai fare 2^N combinazioni.
    Questo si può realizzare in diversi modi: con un metodo ricorsivo o con un algoritmo iterativo che ad esempio genera la stessa sequenza di combinazioni "prendi"/"scarta" che ho descritto sopra.

    Consiglio: prova la strada dell'algoritmo ricorsivo.
Devi accedere o registrarti per scrivere nel forum
4 risposte