Progetto Eulero # 163 comprensione

Question

Ho trascorso molto tempo alla ricerca di una soluzione per this problem. Ho disegnato tonnellate di triangoli tratteggiati, ho contato i triangoli in casi semplici e ho cercato una sorta di schema. Sfortunatamente, ho colpito il muro. Sono abbastanza sicuro che le mie capacità di programmazione/matematica non soddisfano il prereq per questo problema.

Quindi ho trovato una soluzione online per accedere ai forum. Non ho capito la maggior parte dei metodi e alcuni mi sembravano troppo complicati.

Qualcuno può darmi una comprensione di questo problema? Uno dei metodi, trovato qui: http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (Problema C) consentito per una singola funzione da utilizzare.

Come hanno trovato questa soluzione? A questo punto, mi piacerebbe davvero capire alcuni dei concetti alla base di questo interessante problema. So che cercare la soluzione non faceva parte dello spirito di Eulero, ma sono abbastanza sicuro che non avrei comunque risolto il problema.

Answer 1

Questo è essenzialmente un problema nella combinatoria enumerativa, che è l'arte di contare le combinazioni di cose. È un bel soggetto, ma probabilmente ci vuole un po 'di riscaldamento prima di poter apprezzare i trucchi del ninja nel riferimento che hai dato.

D'altra parte, i commenti nel thread delle soluzioni per il problema indicano che molti hanno risolto il problema utilizzando un approccio a forza bruta. Uno dei trucchi più comuni consiste nel prendere tutte le possibili combinazioni di tre linee nel diagramma e vedere se producono un triangolo che si trova all'interno del triangolo più grande.

È possibile ridurre considerevolmente lo spazio di ricerca osservando che le linee si trovano in una delle sei direzioni. Dal momento che una combinazione di linee che include due linee parallele non produrrà un triangolo, puoi scorrere le triple linee in modo che ogni linea nella tripla abbia una direzione diversa.

Dato tre righe, calcolare i loro punti di intersezione. Avrai tre possibilità 1) le linee sono coincidenti - si intersecano tutte in un punto comune 2) due delle linee si intersecano in un punto esterno al triangolo 3) tutti e tre i punti di intersezione sono distinti, e si trovano tutti all'interno il triangolo esterno

Basta contare le condizioni di soddisfazione delle combo (3) e il gioco è fatto. Il numero di combinazioni di linee da testare è O (n), che non è proibitivo.

EDIT1: rileggendo la tua domanda, ho l'impressione che tu possa essere più interessato a ottenere una spiegazione della soluzione/formula combinatoria che un profilo di un approccio di forza bruta. Se è così, dillo e cancellerò questa risposta.Ma direi anche che la domanda in quel caso non sarebbe adatta a questo sito.

EDIT2: vedere anche a combinatorics solution by Bill Daly and others. È matematicamente un po 'più gentile dell'altro.

Answer 2

Non ho risolto questo problema per project euler e sto uscendo dalla domanda e dalla soluzione che hai fornito. Nel caso della singola funzione, la metodologia presentata era in definitiva semplice individuazione del modello. Il risolutore ha suddiviso la domanda presentata in tre parti, in base ai tipi di triangoli presenti negli incroci. È un approccio abbastanza normale a questo tipo di problema, rompere il modello più grande in quelli più piccoli per rendere più facile la soluzione. Le funzioni utilizzate per esprimere le varie forme di triangoli che posso solo dedurre sono state generate con una mente di ricerca del modello molto acuta o con qualche teoria/geometria dei numeri. È anche oltre lo scopo di questa spiegazione e la mia conoscenza. Questo problema non ha nulla a che fare con la programmazione. È fondamentalmente interamente matematica. Se leggi il sito che ti è piaciuto, puoi vedere la logica che è stata raggiunta per raggiungere le domande.