Problema esercizio

[gabon83]

Salve seguo un corso di java ho un esercizio che sembra un vero e proprio rompicapo... spero qualcuno mi dia una mano, spero anche in qualche riga di codice :

Scivere un programma che determi il minimo intero n (dispari per forza), tale che i numeri da 0 a n inclusi possano essere divisi in due insiemi che
abbiano:
- lo stesso numero di elementi;
- la stessa somma degli elementi;
- la stessa somma del quadrato degli elementi;
- la stessa somma del cubo degli elementi.
Preferibilmente scrivere gli insiemi, per controllo.

Un paio di esempi, per chiarire:
- se il requisito fosse solo il primo, la risposta sarebbe 1 e gli insiemi { 0 } e { 1 } (un elemento ciascuno).
- se i requisiti fossero solo i primi due, la risposta sarebbe 3 e gli insiemi { 0, 3 } e { 1, 2 } (due elementi ciascuno, somma 3).
Il secondo insieme, però non soddisfa il terzo requisito (somme dei quadrati 9 e 5) e men che meno il quarto.
Esistono insiemi con più elementi che soddisfano i requisiti. Per esempio, { 0, 1, 6, 7 }, { 2, 3, 4, 5 }.
Il programma deve provare ad aumentare n fino a trovare la soluzione minima

Spero possiate aiutarmi
Grazie

[desa]

Interessante problema di ricerca...!

Una soluzione - decisamente non ottimizzata, visto che esegue numerosi ripetizioni di calcoli - è avere un ciclo che ti genera ad ogni loop un nuovo array contenente tutti gli elementi da 0 a n (con n che inizia da 1 e viene incrementato di 2, come dicevi tu).
Quindi testare tutte le permutazioni possibili per questo array (da cui la non ottimizzazione), confrontandone i valori presenti nella prima metà con la seconda.

Scusami se sono un po' generico, ma sono di corsa... prova a pensarci un po', nel caso nessuno ti risponda nel frattempo ne possiamo riparlare domani...!

[gabon83]

anche io vado..ne riparliamo più tardi ! La tua , mi sembra una risposta interessante ...

[gabon83]

salve torno a scrivere per avere qualche altro consiglio per risolvere l'esercizio... sarei eternametne grato se qualcuno mi desse qualche input con righe di codice .

Grazie

[desa]

Provo a formalizzare meglio la soluzione che ti avevo già proposto.
Non ho tempo di scriverti del codice ora, quindi ti indico qualcosa in PSEUDOCODICE... e poichè è un esercizio, così provi a pensarci un po'

main()
{
  lung = 2;
  do
  {
    crea_array(lung)
    permuta_array()
    lung = lung + 2

  } while (soluzione_non_trovata)
}

permuta_array(array, pos)
{
  if pos == array.length - 2
  {
    controlla_condizioni()
    scambia_ultime_2_posizioni
    controlla_condizioni()
  }
  else
  {
    for (index = pos; index < array.length - 2; index++)
    {
      scambia_pos_con_index
      permuta_array(array, pos - 1)
      riscambia_pos_con_index
    }
  }
}

In pratica il cuore dell'algoritmo è il metodo permuta_array: calcola tutte le permutazioni possibili per l'array ricevuto (spero sia tutto corretto, ovviamente non ho modo di fare test); è una procedura ricorsiva.
Come ti avevo detto, l'algoritmo non è ottimizzato... ma prova a vedere se ti viene qualche idea. In caso, posta di nuovo!

[LeleFT]

Come espressamente richiesto dal Regolamento, qui non si fornisce alcuna soluzione a esercizi per casa.
Il codice non lo puoi chiedere, lo devi fornire tu. E su quello di discute.

Per ricerca di codice già pronto, esiste il forum "Offro Lavoro / Collaborazione".

Senza contare, che il titolo della discussione non è affatto conforme a quanto richiesto dal Regolamento interno.

Chiudo.


Ciao.