[C#] Algoritmo gioco della scopa

[MonsterMash]

Non è un porblema strettamente legato al C#, ma dato che è questo il linguaggio che sto usando e che il tag sul linguaggio è obligatorio...

La mia domanda è: voi come realizzereste un algoritmo per stabilire quali carte tra quella a terra possono essere prese con una specifica carta nel gioco della scopa?
Praticamente il problema è di stabilire se e quali carte, tra quelle a terra, sommate danno il numero della carta che sto giocando. L'unico modo che mi viene in mente per tentare tutte le possibili combinazioni è di usare un numero di cicli for annidati pari al numero delle carte che sono a terra (prima provo la somma tra tutte le carte, poi tra tutte meno la prima, poi tra tutte meno la seconda, ... , poi tra tutte meno le prime due, poi tra tutte meno la prima e la terza, ...). Ma se non so a priori quante sono le carte a terra...

Grazie a tutti.

Ciao.

[morocarlo]

se salvi in un vettore le carte che hai a terra fai presto a fare questa cosa... basta un semplice for annidato che confronti le varie carte...

[gibra]

Originariamente inviato da MonsterMash
Ma se non so a priori quante sono le carte a terra...

Perchè, chi è che mette le carte a terra?

Scusa, ma se non lo sai tu che hai sviluppato il programma, significa solo che non ne tieni conto. Basta farlo.

[MonsterMash]

Originariamente inviato da morocarlo
se salvi in un vettore le carte che hai a terra fai presto a fare questa cosa... basta un semplice for annidato che confronti le varie carte...

Puo' darsi che non ho capito bene cosa intendi, ma per come la vedo io usando un for annidato posso stabilire solo se due carte tra quelle a terra hanno per somma la carta che sto giocando, non posso fare lo stesso controllo per tre o piu' carte. Se per esempio a terra ci sono asso, due, tre, cinque e nove e io gioco un dieci, con il singolo for annidato prenderei il nove e l'asso, mentre non verrebbe rilevata la possibilita' di prendere asso, due, tre e cinque, la cui somma fa pure dieci.

Mi sfugge qualcosa?

[MonsterMash]

Nessuna idea?
Credo che sia un problema più matematico che ti programmazione, anche cercando online non ho trovato niente.

[morocarlo]

ho capito...
devi fare la prima con la seconda, se poi è ancora minore vai con la terza, o con la quarta e via dicendo....
Una soluzione un po mal fatta potrebbe essere quella di fare una procedura diversa in base al numero di carte che hai in mano, tanto al massimo sono 10... ma si deve trovare anche un altro metodo...
hai mai pensato a una funzione ricorsiva... in questo caso dovrebbe andare...prova a pensarci.

[MonsterMash]

Originariamente inviato da morocarlo
ho capito...
devi fare la prima con la seconda, se poi è ancora minore vai con la terza, o con la quarta e via dicendo....

Una soluzione un po mal fatta potrebbe essere quella di fare una procedura diversa in base al numero di carte che hai in mano, tanto al massimo sono 10... ma si deve trovare anche un altro metodo...

Si ma non implementerei mai una soluzione simile... anche perchè si tratterebbe di fare 10 (DIECI!) for annidati, cosa che rischierebbe di rendere terribilmente pesante l'algoritmo. E la complessità computazionale è una cosa di cui devo tenere conto, dato che l'applicazione dovrà girare su dispositivi mobile (cellulari e palmari).

hai mai pensato a una funzione ricorsiva... in questo caso dovrebbe andare...prova a pensarci.

Penso anche io che l'unica soluzione sarebbe usare un algoritmo ricorsivo, ma prima di mettermi a scervellarmici speravo di trovare una soluzione facile e pronta qui sul forum .

[morocarlo]

pronti ce ne saranno anche in rete, ma molto meglio se te lo fai... alla fine non è complicatissimo, ci saranno 2-3 if al massimo e poi richiami la funzione... non è difficile se hai già le carte salvate in un vettore...

[Pirelli72]

Purtroppo sembra una cosa facile....ma non è difficile.
Ti rimando a questo progetto che funziona in questo modo:

-dati x numeri (che potrebbero essere le carte), ad esempio {2,5,6,3} avrò che le combinazioni possibili saranno

2
5
6
3
2,5
2,6
2,3
5,6
5,3
6,3
2,5,6
2,5,3
5,6,3
1,4,3
1,5,4,3

Ora posso sapere la somma di tutte le combinazioni e confrontarle con un valore e sapere quindi la combinazione che mi porta a quella somma.

[MonsterMash]

Originariamente inviato da Pirelli72
Purtroppo sembra una cosa facile....ma non è difficile.
Ti rimando a questo progetto che funziona in questo modo:

-dati x numeri (che potrebbero essere le carte), ad esempio {2,5,6,3} avrò che le combinazioni possibili saranno

2
5
6
3
2,5
2,6
2,3
5,6
5,3
6,3
2,5,6
2,5,3
5,6,3
1,4,3
1,5,4,3

Ora posso sapere la somma di tutte le combinazioni e confrontarle con un valore e sapere quindi la combinazione che mi porta a quella somma.

In effetti ieri ho risolto la cosa con un algoritmo ricorsivo, ma darò un'occhiata al link che mi hai segnalato, magari è una soluzione più efficente della mia (anche se ho fatto delle prove, e almeno sul mio cellulare, l'algoritmo, anche nei casi più complicati, viene eseguito in pochi centesimi di secondo).

L'algoritmo che ho realizzato io a grandi linee funziona così: gli passo il vettore delle carte a terra e la carta che sto giocando io. Lui ad ogni giro di ricorsione effettua la somma tra una delle carte a terra e un parametro (che nel primo ciclo di ricorsione gli viene passato pari a zero), e quindi verifica se questa somma è minore o uguale alla carta che sto giocando. Se la somma è minore, continua con la ricorsione passando la somma come parametro (che verrà sommato a sua volta con un'altra carta a terra nel ciclo successivo), considerando le carte già sommate come potenzialmente da prendere in abbinamento ad altre carte che potrebbero completare la somma. Se la somma è uguale ho trovato una delle mie soluzioni.

Grazie a tutti per l'aiuto .

P.S. Chi se la sente di testare il mio gioco di scopa una volta che sarà completato?