[JAVA] La Bandiera Tricolore

[life_is_a_bitch]

Salve a tutti,
volevo proporvi un classico degli esercizi che si svolgono in un corso di programmazione java...

Dato un array di interi, si crei un metodo void bandiera(int [] a) che suddivida tale array in tre parti senza usare array di appoggio.
una parte con gli int che %3 danno resto 0, un'altra con quelli che danno resto 1 e la restante con quelli che danno resto 2.

Dovendo realizzare un metodo boolean testBandiera(int[] a) che verifichi la reale suddivisione dell'array nelle tre parti sopracitate, come lo fareste?
a me per ora non vengono in mente soluzioni brillanti...
a voi la parola ! e grazie preventivamente dell'aiuto

[andbin]

Dato un array di interi, si crei un metodo void bandiera(int [] a) che suddivida tale array in tre parti senza usare array di appoggio.
una parte con gli int che %3 danno resto 0, un'altra con quelli che danno resto 1 e la restante con quelli che danno resto 2.Chiaramente bisognerebbe fissare delle condizioni sulle caratteristiche dell'array in input. E cioè che l'array sia lungo un multiplo di 3 e che ci sia un numero corretto di valori per ognuna delle tre parti (per fare un esempio, se l'array è lungo 9 non ci possono essere 4 elementi per cui %3 = 0).
Dico bene? ;)

[Gica78R]

Chiaramente bisognerebbe fissare delle condizioni sulle caratteristiche dell'array in input. E cioè che l'array sia lungo un multiplo di 3 e che ci sia un numero corretto di valori per ognuna delle tre parti (per fare un esempio, se l'array è lungo 9 non ci possono essere 4 elementi per cui %3 = 0).
Dico bene? ;)

Non mi sembra che ci sia un vincolo che impone che le tre parti dell'array debbano essere della stessa dimensione, quindi l'array può essere di qualunque dimensione e, in teoria, contenere anche solo valori multipli di 3, che quindi occuperanno tutto l'array...

[morskott]

Io risolverei cosìpublic class Bandiera{
public static void bandiera(int[] a){
bandiera(a,0);
}

private static void bandiera(int[] a,int index){
if (index==a.length) return;
else{
if (a[index]%3==0) mettiSinistra(a,index);
if (a[index]%3==2) mettiDestra(a,index);
bandiera(a,index+1);
}
}

private static void mettiDestra(int[] a,int index){
int temp=a[a.length-1];
a[a.length-1]=a[index];
a[index]=temp;
}

private static void mettiSinistra(int[] a,int index){
int temp=a[0];
a[0]=a[index];
a[index]=temp;
}

public static boolean testBandiera(int[] a){
return testBandiera(a,0,0);
}

private static boolean testBandiera(int[] a,int index,int mode){
if (a.length==index) return true;
else
if (mode==3) return false;
else{
return a[index]%3==mode && (testBandiera(a,index+1,mode) || testBandiera(a,index+1,mode+1));
}
}
}

[andbin]

Non mi sembra che ci sia un vincolo che impone che le tre parti dell'array debbano essere della stessa dimensione, quindi l'array può essere di qualunque dimensione e, in teoria, contenere anche solo valori multipli di 3, che quindi occuperanno tutto l'array...E allora, scusa, che "bandiera" sarebbe?? :p

Comunque io ho solo fatto una domanda/precisazione e l'unico che può rispondere/confermare è life_is_a_bitch. Per me potrebbe andare bene tanto la "mia" specifica quanto la "tua".

[mad_hhatter]

Io risolverei cosìpublic class Bandiera{
public static void bandiera(int[] a){
bandiera(a,0);
}

private static void bandiera(int[] a,int index){
if (index==a.length) return;
else{
if (a[index]%3==0) mettiSinistra(a,index);
if (a[index]%3==2) mettiDestra(a,index);
bandiera(a,index+1);
}
}

private static void mettiDestra(int[] a,int index){
int temp=a[a.length-1];
a[a.length-1]=a[index];
a[index]=temp;
}

private static void mettiSinistra(int[] a,int index){
int temp=a[0];
a[0]=a[index];
a[index]=temp;
}

public static boolean testBandiera(int[] a){
return testBandiera(a,0,0);
}

private static boolean testBandiera(int[] a,int index,int mode){
if (a.length==index) return true;
else
if (mode==3) return false;
else{
return a[index]%3==mode && (testBandiera(a,index+1,mode) || testBandiera(a,index+1,mode+1));
}
}
}

può essere che mi sbagli, ma non è errato? se ho questo array {0, 1, 1, 0} arrivato all'ultimo elemento, scambia i due zeri e basta... invece di scambiare i 2 elementi, mettiDestra e mettiSinistra dovrebbero fare spazio e infilare l'elemento rispettivamento in a[length-1], a[0]... ripeto: sempre che non mi sia perso qualche passaggio :)

[morskott]

può essere che mi sbagli, ma non è errato? se ho questo array {0, 1, 1, 0} arrivato all'ultimo elemento, scambia i due zeri e basta... invece di scambiare i 2 elementi, mettiDestra e mettiSinistra dovrebbero fare spazio e infilare l'elemento rispettivamento in a[length-1], a[0]... ripeto: sempre che non mi sia perso qualche passaggio :)

Mo sull'array che dici tu devo ancora pensare, ma la mia idea è, se è %3=0 sta tutto a sinistra, %3=2 tutto a destra, cioè, se in qualsiasi pos dell'array trovo un elem che %3=0 lo metto nella prima posizione di sin, se %3=2 lo metto nell'ultima posizione a destra e implicitamente alla fine quelli %3=1 saranno in mezzo

EDIT:Hai ragione, dovrei fare uno scalamento progressivo su tutti gli elem dell'array

EDIT2:
Ecco la versione corretta (spero)public class Bandiera{
public static void bandiera(int[] a){
bandiera(a,0);
}

private static void bandiera(int[] a,int index){
if (index==a.length) return;
else{
if (a[index]%3==0) mettiSinistra(a,index);
if (a[index]%3==2) mettiDestra(a,index);
bandiera(a,index+1);
}
}

private static void mettiDestra(int[] a,int index){
int temp=a[index];
for (int i=a.length-1;i>index;i--)
a[i-1]=a[i];
a[a.length-1]=temp;
}

private static void mettiSinistra(int[] a,int index){
int temp=a[index];
for (int i=0;i<index;i++)
a[i+1]=a[i];
a[0]=temp;
}

public static boolean testBandiera(int[] a){
return testBandiera(a,0,0);
}

private static boolean testBandiera(int[] a,int index,int mode){
if (a.length==index) return true;
else
if (mode==3) return false;
else{
return a[index]%3==mode && (testBandiera(a,index+1,mode) || testBandiera(a,index+1,mode+1));
}
}
}

[wingman87]

Io farei una specie di bubble sort:
inizia la ricerca, se trovo un %3=0 lo porto su finchè non trovo la cima o un altro %3=0, se trovo un %3=1 lo porto su finchè non trovo un %3=1 o un %3=0 o la cima, se trovo un %3=2 lo lascio dov'è...
E per la verifica basta scorrere l'array, se trovo blocchi di numeri dello stesso tipo in posti differenti allora ritorno false

[andbin]

Innanzitutto premetto che come "specifiche" mi va anche bene quando detto da Gica78R, cioè che non ci siano vincoli sulla lunghezza dell'array o sulla ripartizione dei valori.

Detto questo mi permetto di postare la "mia" versione:
import java.util.*;

public class Prova
{
public static void main (String[] args)
{
int[] arr;

arr = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
System.out.println ("prima: " + Arrays.toString (arr));
bandiera (arr);
System.out.println ("dopo: " + Arrays.toString (arr));

arr = new int[] { 3, 2, 4, 6, 9, 8, 10 };
System.out.println ("prima: " + Arrays.toString (arr));
bandiera (arr);
System.out.println ("dopo: " + Arrays.toString (arr));
}

public static void bandiera (int[] a)
{
for (int i=0, k=0; i < 3; i++)
{
for (int j=k; j < a.length; j++)
{
if (a[j] % 3 == i)
{
int t = a[k];
a[k++] = a[j];
a[j] = t;
}
}
}
}
}L'output è:

prima: [0, 1, 2, 3, 4, 5, 6, 7, 8]
dopo: [0, 3, 6, 1, 4, 7, 2, 5, 8]
prima: [3, 2, 4, 6, 9, 8, 10]
dopo: [3, 6, 9, 4, 10, 8, 2]

Come potete vedere, l'algoritmo che ho usato è davvero molto semplice, lineare e pulito e, almeno per me, ricorda molto il bubble-sort.
L'unica cosa è che non è "stable" cioè non mantiene l'ordine relativo degli elementi (si noti che nel secondo test 2 e 8 vengono scambiati come ordine).

Se lo volete "stable", beh, ci debbo pensà.....

[mad_hhatter]

Innanzitutto premetto che come "specifiche" mi va anche bene quando detto da Gica78R, cioè che non ci siano vincoli sulla lunghezza dell'array o sulla ripartizione dei valori.

Detto questo mi permetto di postare la "mia" versione:
import java.util.*;

public class Prova
{
public static void main (String[] args)
{
int[] arr;

arr = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
System.out.println ("prima: " + Arrays.toString (arr));
bandiera (arr);
System.out.println ("dopo: " + Arrays.toString (arr));

arr = new int[] { 3, 2, 4, 6, 9, 8, 10 };
System.out.println ("prima: " + Arrays.toString (arr));
bandiera (arr);
System.out.println ("dopo: " + Arrays.toString (arr));
}

public static void bandiera (int[] a)
{
for (int i=0, k=0; i < 3; i++)
{
for (int j=k; j < a.length; j++)
{
if (a[j] % 3 == i)
{
int t = a[k];
a[k++] = a[j];
a[j] = t;
}
}
}
}
}L'output è:

prima: [0, 1, 2, 3, 4, 5, 6, 7, 8]
dopo: [0, 3, 6, 1, 4, 7, 2, 5, 8]
prima: [3, 2, 4, 6, 9, 8, 10]
dopo: [3, 6, 9, 4, 10, 8, 2]

Come potete vedere, l'algoritmo che ho usato è davvero molto semplice, lineare e pulito e, almeno per me, ricorda molto il bubble-sort.
L'unica cosa è che non è "stable" cioè non mantiene l'ordine relativo degli elementi (si noti che nel secondo test 2 e 8 vengono scambiati come ordine).

Se lo volete "stable", beh, ci debbo pensà.....

molto bello, bravo!
per renderlo stabile, la mia versione (verisone di moskott modificata) risulta stabile se l'inserimento a destra inserisce nell'ultima posizione, mentre l'inserimento a sinistra inserisce a destra dell'area A,
dove làarea A eà la parte sinistra dell'array e tale che i suoi elementi sono divisibili per 3

pero' a occhio la complessita' e' maggiore della tua soluzione

[71104]

E cioè che l'array sia lungo un multiplo di 3 e perché? anche un array da 4 locazioni può essere diviso in tre parti, per esempio le prime due locazioni, la successiva, e la successiva ancora. piuttosto dovrebbe verificare che la lunghezza sia maggiore o uguale a 3.

e che ci sia un numero corretto di valori per ognuna delle tre parti (per fare un esempio, se l'array è lungo 9 non ci possono essere 4 elementi per cui %3 = 0). perché? :wtf:

[andbin]

molto bello, bravo!Grazie. :)

Una implementazione "stable" si può fare in questo modo:
public static void bandiera (int[] a)
{
for (int i = 0; i < a.length-1; i++)
{
for (int j = i+1; j < a.length; j++)
{
int mi = a[i] % 3;
int mj = a[j] % 3;

if (mi > mj || (mi == mj && a[i] > a[j]))
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}Questo è un "vero" bubble-sort, solo con il test tra i due elementi un po' particolare.

Un esempio è questo:
prima: [9, 6, 10, 7, 4, 1, 14, 11, 5, 2]
dopo: [6, 9, 1, 4, 7, 10, 2, 5, 11, 14]

Tuttavia il bubble-sort ha una complessità decisamente maggiore rispetto alla implementazione che ho postato prima.


e perché? anche un array da 4 locazioni può essere diviso in tre parti, per esempio le prime due locazioni, la successiva, e la successiva ancora. piuttosto dovrebbe verificare che la lunghezza sia maggiore o uguale a 3.

perché? :wtf:Calma ... era solo un mio "dubbio".