Idee e consigli su un algoritmo per un'applicazione

[miky2184]

Ciao,
è da poco che mi sono avvicinato al mondo della programmazione android, però ho un problema su come realizzare un algoritmo di calcolo delle spese per un'applicazione che sto creando.

Sto creando un'applicazione, che date diverse spese, deve effettuare il calcolo di quanto ognuno deve dare ad un altro utente.

Ad esempio c'è l'utente x, y, z e k
x ha avuto spese di 5 euro
y ha avuto spese di 10 euro
z ha avuto spese di 25 euro
k ha avuto spese di 0 euro
ogni spesa è una variabile di input, che ovviamente possono variare, quelle riportate sono a titolo di esempio.

l'applicazione dovrà quindi mostrare come risultato che
x deve dare 5 euro a z
y non deve dare nulla a nessuno
e k deve dare 10 euro a z

avete idee di come posso calcolare ed ottenere questo risultato finale?

grazie mille anticipatamente
ogni idea è ben accetta

[frank17next]

Ciao,
è da poco che mi sono avvicinato al mondo della programmazione android, però ho un problema su come realizzare un algoritmo di calcolo delle spese per un'applicazione che sto creando.

Sto creando un'applicazione, che date diverse spese, deve effettuare il calcolo di quanto ognuno deve dare ad un altro utente.

Ad esempio c'è l'utente x, y, z e k
x ha avuto spese di 5 euro
y ha avuto spese di 10 euro
z ha avuto spese di 25 euro
k ha avuto spese di 0 euro
ogni spesa è una variabile di input, che ovviamente possono variare, quelle riportate sono a titolo di esempio.

l'applicazione dovrà quindi mostrare come risultato che
x deve dare 5 euro a z
y non deve dare nulla a nessuno
e k deve dare 10 euro a z

avete idee di come posso calcolare ed ottenere questo risultato finale?

grazie mille anticipatamente
ogni idea è ben accetta

Ma se invece la offri tu la cena? Non risolvi direttamente?

scherzi a parte ... non è poi così banale
Ancor prima di iniziare a pensarci, leggevo i dati forniti dall'esempio, che effettivamente si incastrano molto bene, essendo divisibili per 5. Ma che succede ad esempio se un componente del gruppo, k, può contemporaneamente ridare i soldi sia a z che a x? Quale si sceglie? Vabbè, questo magari è un problema successivo.
In ogni caso,
Hai già iniziato a scrivere del codice a riguardo?

Così, su due piedi, oltre a rastrellare i dati in input (calcolo del numero dei componenti, calcolo della quota personale, ecc...), organizzerei i componenti in due gruppi distinti (forse array ma meglio liste concatenate - dinamiche) denominati tipo 'Creditori' e 'Debitori' (separati in base ai calcoli di valore assoluto della quota versata a fronte della quota della spesa, nel tuo esempio se x ha versato 5 a fronte di quota 10 è un debitore, ecc...
Separati i due gruppi, bisogna trovare un buon modo per fare i match tra i valori di entrambi, in modo da incastrare adeguatamente le persone dell'uno e dell'altro in base agli importi e conservarne il legame.
Il legame è proprio la parte più ostica, perchè tu non ti limiti a fare i calcoli delle quote del conto, ma vuoi adeguatamente fornire anche eventualmente il dato di chi deve dare a chi e quanto.
Magari per conservare i legami dei match degli importi sarebbe opportuno memorizzarli un un terzo gruppo, di comodo, (sempre una lista), che storicizzi il success match tra importo positivo e negativo dei creditori e debitori.
Certo, con l'esempio che hai fatto il tutto sembra semplice, ma immagina una cena di 37 persone con quota 19,89, dove c'è chi paga 16,00 eur, chi paga 26,34 eur ecc...
L'ho buttata qui, se riesco a ritagliare un pò di tempo, ci penso

[miky2184]

Ciao, grazie della risp. Inizialmente mi sembrava un'appl banale da realizzare, poi però la realizzazione del quanto una persona deve dare ad un'altra ha iniziato a crearmi diversi problemi.

L'idea che mi è venuta ora, che devo provare a sviluppare è di creare un ciclo fin quando la propria parte da dare non diventa zero, e poi fare delle valutazioni, in base alla quotaparte che è comunque uguale ad ognuno. appena butto giù una bozza di codice, la pubblico, magari qualcuno ha qualche idea o suggerimento

grazie

[miky2184]

Io finora ho scritto questo codice.
mTOm, tTOt, sTOs, fTOf è quanto ognuno deve dare a se stesso, ovvero qnt ognuno deve dare o ricevere, quindi nell'esempio di prima:

x = mTOm = -5
y = tTOt = 0
z = sTOs = +15
k = fTOf = -10

questo è il codice che ho scritto:

if (mTOm < 0) {
if (tTOt > 0) {
if (tTOt > mTOm) {
mTOt = mTOm;
tTOt = tTOt + mTOt;
mTOm = mTOm - mTOm;
} else {
mTOt = tTOt;
tTOt = tTOt - mTOt;
mTOm = mTOm - tTOt;
}
}
if (sTOs > 0) {
if (sTOs > mTOm) {
mTOs = mTOm;
sTOs = sTOs + mTOs;
mTOm = mTOm - mTOm;
} else {
mTOs = sTOs;
sTOs = sTOs - mTOs;
mTOm = mTOm - sTOs;
}
}
if (fTOf > 0) {
if (fTOf > mTOm) {
mTOf = mTOm;
fTOf = fTOf + mTOf;
mTOm = mTOm - mTOm;
} else {
mTOf = fTOf;
fTOf = fTOf - mTOf;
mTOm = mTOm - fTOf;
}
}
}

per il calcolo del primo funziona tutto, però poi se ripeto il codice, ovviamente cambiando in maniera opportuna il codice per gli altri, i calcoli vengono fatti male...ora non riesco a capire bene dove sto sbagliando.
Controllerò meglio nei prox giorni, se qualcuno ha qualche idea, o qualche suggerimento mi faccia sapere

grazie a tutti in anticipo

[pourquoipas]

Ciao, io farei così:
Fai la media spesa a persona ovvero
Somma tutte le spese (nel tuo caso 5 + 10 + 25 + 0) = 40
Dividi per il numero di partecipanti (4) = 40/4 = 10
il risultato (spesaMedia) è quanto deve spendere ogni partecipante.
A questo punto facendo spesaMedia - spesa partecipante ottiene un valore che rappresenta se il singolo partecipante deve dare (valore positivo) o ricevere soldi (chiamiamolo bilancio).
es :
bilancio di x = 10 - 5 = +5
bilancio di y = 10 - 10 = 0
bilancio di z = 10 - 25 = -15
bilancio di k = 10 - 0 = 10
(in pratica chi ha bilancio positivo, deve dare dei soldi per tornare a zero, chi ha bilancio negativo li deve avere per tornare a zero)
E fin qui hai trovato chi deve dei soldi e chi ne deve avere, ora ti manca solo distribuirli.
Per distribuirli ci potrebbero essere vari modi, ad esempio
- scorri la tua lista di partecipanti e prendili uno alla volta
- finchè il partecipante in esame ha bilancio maggiore di zero
--- scorri la lista di partecipanti e prendili uno alla volta
--- se il partecipante di questo secondo giro ha bilancio negativo deve ricevere soldi
----- se i soldi che deve ricevere sono maggiori del bilancio del primo giro
------- quest'ultimo da tutti i soldi al partecipante del secondo giro ed è a posto
----- altrimenti
------- dai al partecipante del secondo giro i soldi che gli spettano e cerca altri partecipanti cui dare la rimanenza

E' forse più semplice spiegarlo con un esempio (ho messo qualche commento per spiegare meglio il tutto):

    public static class People {
    	// La media. Per ora la metto statica ipotizzando una sola elaborazione per volta
    	// Se devo mantenere attive due o più diverse liste di persone allora va trovata
    	// una soluzione alternativa
    	public static BigDecimal media = BigDecimal.ZERO;
    	// Nome
    	public String nome;
    	// Spesa
    	public BigDecimal spesa = BigDecimal.ZERO;
    	
    	public People(String nome, BigDecimal spesa) {
    		this.nome = nome;
    		this.spesa = spesa;
    	}

    	/** il bilancio attuale (che dovrà andare a zero) è dato da:<br>
    	* spesa iniziale + (tutti i soldi dati ad altri) - (tutti i soldi ricevuti da altri)
    	*/
    	public BigDecimal bilancio() {
    		BigDecimal spesaAttuale = spesa;
    		for (Give g : daDare) {
    			spesaAttuale = spesaAttuale.add(g.importo);
    		}
    		for (Give g : daRicevere) {
    			spesaAttuale = spesaAttuale.subtract(g.importo);
    		}
    		return media.subtract(spesaAttuale);
    	}
    	
    	public List<Give> daDare = new ArrayList<Give>();
    	public List<Give> daRicevere = new ArrayList<Give>();
    }
    public class Give {
    	// Chi darà soldi
    	public People debitore;
    	// A chi li darà
    	public People creditore;
    	// quanto darà
    	public BigDecimal importo;
    	public Give(People debitore, People creditore, BigDecimal importo) {
    		this.creditore = creditore;
    		this.debitore = debitore;
    		this.importo = importo;
    	}
    }


    /** calcola la media (spesa a testa) dalla lista di partecipanti
    *
    */
    public void media(List<People> partecipanti) {
    	BigDecimal media = BigDecimal.ZERO;
    	for (People p : partecipanti) {
    		media = media.add(p.spesa);
    	}
    	media = media.divide(new BigDecimal(partecipanti.size()), 20, RoundingMode.HALF_UP);
    	People.media = media;
    }

    /** distribuisce i soldi fra chi deve dare e chi deve ricevere
    *
    */
    public void distribuisci(List<People> partecipanti) {
    	for (People p1 : partecipanti) {
    		BigDecimal resto = p1.bilancio();
    		// Se il bilancio è positivo, p1 deve dare dei soldi ad altri
    		Iterator<People>it = partecipanti.iterator();
    		while (it.hasNext() && (BigDecimal.ZERO.compareTo(resto) < 0)) {
    			People p2 = it.next();
    			BigDecimal bilancioP2 = p2.bilancio();
    			if (bilancioP2.compareTo(BigDecimal.ZERO) < 0) {
    				// se il bilancio di p2 è negativo, allora p2 deve ricevere dei soldi
    				BigDecimal ricevereP2 = BigDecimal.ZERO.subtract(bilancioP2);
    				if (ricevereP2.compareTo(resto) > 0) {
    					// p2 deve ricevere più del resto di p1, p1 da tutto a p2
    					Give g = new Give(p1, p2, resto);
    					p1.daDare.add(g);
    					p2.daRicevere.add(g);
    					resto = BigDecimal.ZERO;
    				} else {
    					// p2 deve ricevere meno del resto di p1, 
    					// p1 darà a p2 soldi per pareggiare e il resto ad altri
    					Give g = new Give(p1, p2, ricevereP2);
    					p1.daDare.add(g);
    					p2.daRicevere.add(g);
    					resto = resto.subtract(ricevereP2);
    					
    				}
    			}
    		}
    	}
    }

    public void logDistribuzione(String tag, List<People> partecipanti) {
    	for (People p1 : partecipanti) {
    		for (Give g : p1.daDare) {
    			Log.i(tag, g.debitore.nome + " deve dare " + NumberFormat.getCurrencyInstance().format(g.importo) + " a " + g.creditore.nome);
    		}
    	}
    }

    
    public void test() {
    	List<People> partecipanti = new ArrayList<People>();

    	// Riempi partecipanti
    	partecipanti.add(new People("x", new BigDecimal(5)));
    	partecipanti.add(new People("y", new BigDecimal(10)));
    	partecipanti.add(new People("z", new BigDecimal(25)));
    	partecipanti.add(new People("k", BigDecimal.ZERO));

    	media(partecipanti);

    	distribuisci(partecipanti);

    	logDistribuzione("TEST", partecipanti);
   	
    }

Se prendi il pezzo di codice sopra e lo incolli in una activity (tutto classi comprese)
e dentro all'onCreate richiami la funzione test(); ti troverai nei log l'output seguente:

06-24 11:09:21.599: I/TEST(25180): x deve dare $5.00 a z
06-24 11:09:21.599: I/TEST(25180): k deve dare $10.00 a z

(Non badare al $ è che sul mio cellulare ho il locale en_US e comunque la funzione di log è solo per vederlo sul logCat, dopo dovrai tu gestirti i dati come preferisci).
Le cose importanti sono:
la sotto classe People (che raccoglie i dati di una persona, i soldi che ha messo e dopo i calcoli quanto deve dare e/o ricevere e a chi/da chi).
la sotto classe Give (che indica un trasferimento di soldi da uno dei partecipanti ad un'altro)
la funzione media che calcola la spesa media di ogni partecipante
la funzione distribuisci che calcola chi deve dare soldi a chi.

la distribuisci per ora è proprio di base e molto poco ottimizzata, in teoria si potrebbe cercare prima dei match esatti di importo dare/avere, e poi aggiungere altre logiche per cercare di minimizzare il frazionamento dei soldi. Però dovrebbe fare i conti giusti (magari fai altre prove con altri dati)
le due sottoclassi People e Give potresti anche decidere di crearle come classi vere e proprie (a me erano comode così per un test veloce)

In bocca al lupo !

[miky2184]

Grazie mille davvero, sembra proprio quello che mi serve oggi lo provo e dico i risultati grazie mille


Inviato dal mio HTC Incredible S usando Androidiani App