Data una situazione e alcune condizioni, verifica che la situazione sia possibile

Question

Data una situazione e alcune condizioni, verifica che la situazione sia possibile

#1 da (1 voti)

2

Beh, è un problema che io e il mio amico avevamo pensato e, beh, non ho trovato nulla per risolvere il seguente problema (cercherò di esprimerlo nel modo migliore possibile):

Given that there are n number of teams, and the number of matches each team has played, and that no team can play more than 2 matches with any other team, predict if the distribution of matches played by each team is possible.

P.S. : Sono un programmatore Python, quindi (se possibile) post solo il codice python per spiegare ..

algorithms logic-programming

posta pradyunsg 04.05.2013 - 16:31

fonte

1 risposta

Leggi altre domande sui tag algorithms logic-programming

Sperimentare con "big data" e ridurre la mappa esiste un modo per copiare il diagramma "Tipo oggetto di lavoro" in TFS?

score 1 · Answer 1

Questo è un buon esercizio di propagazione dei vincoli e combinatoria. Ecco alcune idee:

Chiaramente ci sono distribuzioni di risultati che sono impossibili. Ad esempio, il numero totale di vincite deve essere uguale al numero totale di perdite e il numero totale di estrazioni deve essere un numero pari.
Se compili alcune distribuzioni di esempio sommando i risultati effettivi, inizierai a notare più regolarità. Ciascuno di questi è un altro criterio per dimostrare che una data distribuzione è impossibile.
Dimostrare che una distribuzione è possibile è un po 'più difficile. La prova più diretta è dare un esempio concreto di risultati che porterebbe alla distribuzione che ti viene data ..
Se non riesci a costruirne uno, l'algoritmo più semplice per decidere se ce n'è uno è enumerare tutti i possibili accoppiamenti e vedere se si adattano. Ad esempio, iniziando con la squadra di livello più alto, puoi condurre una ricerca completa: hanno vinto, perso, legato o non ancora giocato contro la squadra seconda classificata? (Hai detto che ci sono giochi di ritorno, quindi questa decisione deve essere presa due volte, ma ciò non cambia l'idea di base di una ricerca completa.) O trovi una configurazione di risultati corrispondente, o hai dimostrato che non c'è t uno.
Una ricerca completa è costosa, ma esistono diversi vincoli che è possibile utilizzare per potare lo spazio di ricerca. Ad esempio, non puoi assumere più vittorie per una squadra rispetto all'input dichiarato che hanno, e l'assunzione di come A giocata contro B deve confermare ciò che assumi su B contro A.