Heim > Backend-Entwicklung > C++ > Hauptteil

Peterson-Diagrammproblem im C-Programm

PHPz
Freigeben: 2023-08-26 11:01:10
nach vorne
883 Leute haben es durchsucht

Angenommen, wir haben eine Grafik wie unten gezeigt. Bei diesem Diagramm handelt es sich um ein Peterson-Diagramm. Die Eckpunkte sind von 0 bis 9 nummeriert. Jeder Scheitelpunkt hat einige Buchstaben. Betrachten Sie einen Spaziergang W auf diesem Diagramm mit L-Eckpunkten. Wenn die Buchstabenfolge beim Gehen von W mit der von S übereinstimmt, wird die Zeichenfolge S durch Gehen von W realisiert. Wir können einen Scheitelpunkt mehrmals besuchen.

Peterson-Diagrammproblem im C-Programm

Zum Beispiel ähnelt eine Zeichenfolge S „ABBECCD“, die durch Gehen (0, 1, 6, 9, 7, 2, 3) implementiert wird. Unsere Aufgabe besteht darin, einen solchen Spaziergang zu finden und, falls es einen solchen Spaziergang gibt, den lexikographisch kleinsten Spaziergang zu finden. Wenn es keinen solchen Spaziergang gibt, wird -1 zurückgegeben.

Algorithmus

petersonGraphWalk(S, v) – Die chinesische Übersetzung von

begin
   res := starting vertex
   for each character c in S except the first one, do
      if there is an edge between v and c in outer graph, then      
         v := c
      else if there is an edge between v and c+5 in inner graph, then
         v := c + 5
      else
         return false
      end if
         put v into res
      done
   return true
end
Nach dem Login kopieren

Example

ist:

Example

#include<iostream>
using namespace std;
bool adj_mat[10][10] = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0},
   {1, 0, 1, 0, 0, 0, 1, 0, 0, 0},
   {0, 1, 0, 1, 0, 0, 0, 1, 0, 0},
   {0, 0, 1, 0, 1, 0, 0, 0, 1, 0},
   {1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
   {1, 0, 0, 0, 0, 0, 0, 1, 1, 0},
   {0, 1, 0, 0, 0, 0, 0, 0, 1, 1},
   {0, 0, 1, 0, 0, 1, 0, 0, 0, 1},
   {0, 0, 0, 1, 0, 1, 1, 0, 0, 0},
   {0, 0, 0, 0, 1, 0, 1, 1, 0, 0}
};
char S[100005];
char res[100005];
bool petersonGraphWalk(char* S, int v){
   res[0] = v + &#39;0&#39;;
   for(int i = 1; S[i]; i++){
      //traverse the outer graph
      if(adj_mat[v][S[i] - &#39;A&#39;] || adj_mat[S[i] - &#39;A&#39;][v]){
         v = S[i] - &#39;A&#39;;
      }
      //then check the inner graph
      else if(adj_mat[v][S[i] - &#39;A&#39; + 5] || adj_mat[S[i] - &#39;A&#39; + 5][v]){
         v = S[i] - &#39;A&#39; + 5;
      }else{
         return false;
      }
      res[i] = v + &#39;0&#39;;
   }
   return true;
}
main() {
   char* str = "ABBECCD";
   if(petersonGraphWalk(str, str[0] - &#39;A&#39;) || petersonGraphWalk(str, str[0] - &#39;A&#39; + 5)){
      cout << res;
   }else{
      cout << -1;
   }
}
Nach dem Login kopieren

Output

0169723
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonPeterson-Diagrammproblem im C-Programm. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage