bisogno di aiuto per quanto riguarda le modalità di attuazione this..choosing una migliore struttura di dati

StackOverflow https://stackoverflow.com/questions/4530161

Domanda

Voglio analizzare un circuito digitale combinatoria. Un file ASCII contiene la descrizione del circuito, secondo il seguente formato:

<name> <logic gate> <inputs> <outputs> <input 1>…<last input> <output> <delay>

Dove: <name> è una stringa con non più di 20 caratteri con il nome della porta logica. <logic gate> è una stringa con non più di 20 caratteri che identifica il tipo di porta logica. Può essere INPUT, OUTPUT, AND, OR, NOT. <inputs> è un intero uguale a 0 per INPUT, 1 per NOT o OUTPUT, 2 per AND e OR. <outputs> è un intero uguale a 0 per OUTPUT, o greter di 0 altrimenti. <input 1>, <last input>, <output> sono stringhe con non più di 20 caratteri ciascuna, che identifica i nomi della rete di ingresso / uscita per le porte logiche. <delay> è un numero intero che identifica la visualizzazione della porta logica prende per calcolare la sua funzione.

Il programma, dopo aver letto il file contenente la descrizione del circuito, deve calcolare il percorso critico del circuito, che può essere definito come il percorso di collegamento di una porta di tipo INPUT con altri di OUTPUT per il quale la somma del ritardo delle porte nel percorso è il più alto tra tutti i possibili percorsi nel circuito.

Can anyone please tell me the data structures that are best suited for storing the information the program has to elaborate.
How could i load the the data structure into the memory?

Esempio

A INPUT 0 1 net1 1
B INPUT 0 1 net2 1
C INPUT 0 1 net3 1
G1 NOT 1 1 net1 net4 1
G2 OR 2 1 met3 net4 net5 1
G3 AND 2 1 net4 net2 net6 2
G4 AND 2 1 net6 net5 net7 2
D OUTPUT 1 0 net6 1
E OUTPUT 1 0 E 1 



In this example the critical path is A/G1/G2/G4/E with a delay of 7.

Come posso implent questo.?

È stato utile?

Soluzione

Se ho capito bene la tua domanda, sei davvero vogliono sapere quale algoritmo si dovrebbe usare per calcolare il percorso critico. Questo sembra simile ad un "qual è il percorso più breve?" - tipo di domanda. Mi consiglia Algoritmo di Dijkstra per questo problema.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top