Dans une matrice étendue, renvoie l'élément précédent en C++

Discutez d'un problème basé sur la matrice étendue. Une matrice étendue est une matrice dont la taille augmente d'un certain facteur.

Nous avons ici une matrice de caractères dont la taille est agrandie par des multiples de 2, c'est-à-dire que si la taille de la matrice d'origine est N * N, alors la taille de la matrice développée devient 2N * 2N. On nous donne une séquence de caractères située en (i, j) et nous devons renvoyer la séquence de caractères située en (i, (j - N - 1)%N).

Comprenons en visualisant quelques matrices d'expansion initiales.

Given Matrix -> [ a, b ] [ c, d ], 2 X 2 matrix
Multiplying with { a, b, c, d }
A X [ a, b ]
B X [ a, b ]
C X [ a, b ]
D X [ a, b ]
[ c, d ] [ c, d ] [ c, d ] [ c, d ]

Expanded Matrix -> [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ], 4X4 matrix
To expand again, multiply it by { a, b, c, d } and a matrix of size 8X8 will be formed.

Expanded Matrix - > [ aaa, aab, aba, abb, baa, bab, bba, bbb ]
[ aac, aad, abc, abd, bac, bad, bbc, bbd ]
[ aca, acb, ada, adb, bca, bcb, bda, bdb ]
[ acc, acd, adc, add, bcc, bcd, bdc, bdd ]
[ caa, cab, cba, cbb, daa, dab, dba, dbb ]
[ cac, cad, cbc, cbd, dac, dad, dbc, dbd ]
[ cca, ccb, cda, cdb, dca, dcb, dda, ddb ]
[ ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd ]

Ce sont deux matrices d'expansion initiales ; en supposant que nous obtenions une séquence de caractères "bcc", alors nous devons renvoyer la séquence qui vient de rester, qui est "ajouter". De plus, en supposant que la matrice est cyclique, c'est-à-dire si la séquence donnée est à (i, 0), alors renvoie la séquence à (i, N-1)

Input: abb
Output: aba
Explanation: The sequence just left to abb is aba in the 8X8 matrix.

Input: aadc
Output: aacd

Input: abbcd
Output: abbcc

Façons de trouver la solution

Pensez d'abord au problème , la seule solution qui me vient à l'esprit. La solution est de trouver une matrice étendue contenant la séquence donnée mais qui n'a pas l'air très complexe. Nous devons d’abord former la matrice, puis rechercher la séquence.

Approche efficace

Après avoir examiné quelques matrices initialement développées, nous avons découvert un modèle à travers lequel nous pouvions voir l'élément précédent. Autrement dit,

• parcourt la séquence de caractères à partir du dernier index.

• Si l'élément d'index est 'b' ou 'd', remplacez-le par 'a' ou 'c' et arrêtez de parcourir le tableau.

• Si l'élément d'index est « a » ou « c », remplacez-le par « b » ou « d » et passez à l'index suivant et vérifiez-le.

Exemple

Code C++ de la méthode ci-dessus

#include <bits/stdc++.h>
using namespace std;
int main (){
   string seq = "abbcd";
   int n = seq.length ();
   // traverse through the string from last.
   for (int i = n; i >= 0; i--){
      // if the element is b or d, change them and stop traversing.
      if (seq[i] == &#39;b&#39;){
      seq[i] = &#39;a&#39;;
      break;
   }
   if (seq[i] == &#39;d&#39;){
      seq[i] = &#39;c&#39;;
      break;
   }
   // if an element is b or d, change them and move to the next element.
   if (seq[i] == &#39;a&#39;)
      seq[i] = &#39;b&#39;;
   else if (seq[i] == &#39;c&#39;)
      seq[i] = &#39;d&#39;;
   }
   cout << "The Previous sequence is: " << seq;
   return 0;
}

Sortie

The previous sequence is: abbcc

Conclusion

Dans cet article, nous avons discuté de la matrice de caractères étendue et de la façon dont elle est formée. Nous avons également discuté de la recherche de l’élément précédent dans une matrice étendue. Nous avons résolu ce problème en comprenant les modèles créés par la matrice de caractères étendue.

Nous avons également discuté du code C++ pour résoudre ce problème, que nous pouvons écrire dans n'importe quel langage de programmation comme C, Java, Python, etc. Nous espérons que ce tutoriel vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!