Che cos'è un decente puzzle grafico per principianti? [chiuso]

Question

Sto cercando di conoscere meglio i problemi che richiedono la risoluzione dei grafici (sono meglio risolti dai grafici).

Se qualcuno ha un vecchio problema di ACM Programming Competition che utilizzava i grafici, o ha un altro problema che ha trovato particolarmente illuminante mentre lo ha elaborato, lo apprezzerei. Voglio familiarizzare con i grafici, identificare facilmente i problemi di tipo grafico ed essere in grado di utilizzare algoritmi di attraversamento dei grafici di base.

Qualcuno ha un dolce problema che può inviare a modo mio?

Answer 1

Ho trovato questo libro estremamente utile (Amazon Link): Sfide di programmazione

Non solo fornisce una spiegazione abbastanza approfondita di grafici, alberi, strutture di dati di base, ma offre una manciata di sfide di programmazione che coinvolgono ogni tipo! Questo documento mi è più utile del mio libro di testo!

Ecco alcuni dei problemi del grafico in esso:

Problemi relativi a Traversata grafico :

• Bicolore: pg 203
• Giocare con le ruote: pag. 204
• La guida turistica: pg 206
• Slash Maze: pg 208
• Modifica scalette: pg 210
• Torre dei cubi: pg 211
• Dal crepuscolo all'alba: pag 213
• Problemi alla Torre di Hanoi (di nuovo!): pag. 215

Problemi relativi a algoritmi grafici (Dijkstra, Min Spanning Tree, ecc.):

• Lentiggini: pag. 231
• La collana: pg 231
• Caserma dei pompieri: pag 234
• Ferrovie: pag. 235
• Guerra: pag 237
• La Gran Cena: pag. 241

Answer 2

Per avere una migliore comprensione delle operazioni sul grafico, potresti voler semplicemente implementare alcuni grafici algoritmi .

Prova a implementare un solutore o generatore Nurikabe . Avrebbe bisogno di un po 'di operazioni grafiche classiche.

Answer 3

Dovresti conoscere il Konigsberg Bridge Problem . Dovresti anche familiarizzare con i tipi di strutture dati che spesso emergono nei problemi di teoria dei grafi.

Answer 4

I grafici possono letteralmente essere utilizzati per modellare quasi qualsiasi problema. Topcoder.com Le partite di maratona spesso si prestano a soluzioni basate su grafici.

• Il problema ProcessorScheduling potrebbe essere risolto con grafici.
• Il problema GraphBuilder .
• Il problema Distance .
• Il problema MapMaker (problema di colorazione k ponderato, che è un classico problema di informatica).

Potresti verificare alcuni di questi problemi - e ce ne sono altri da cui provengono.

Answer 5

Non dici quale lingua stai usando (pensando di usare). Se posso, suggerirei Lisp o Python. Sono entrambi utili per una facile manipolazione dei grafici. Se vuoi essere davvero fantasioso, potresti voler creare un bel risultato usando PyGame.

Per quanto riguarda il problema, dai un'occhiata a un semplice programma e convertilo in un grafico. Suggerimento, ogni token è un nodo. Supponendo di avere alcuni loop ed equazioni, è possibile attraversare il grafico e identificare ciò che potrebbe essere spostato al di fuori del loop. Le equazioni potrebbero essere riorganizzate per essere più "efficienti".

La mia logica per questo problema è che ti aiuterà come programmatore vedendo il tipo di processi che potrebbero essere in corso all'interno delle fasi di ottimizzazione di un compilatore.

A proposito, se ci provi sopra, dai un'occhiata a Plex , ti farà risparmiare un sacco di tempo con i parser.

Answer 6

http://codekata.pragprog.com/2007/01/kata_nineteen_w.html

Suggerimento: un DAWG è un metodo abbastanza valido.