Hello, I am trying to code in C++ for a school project even though I am not used to it. The error is very likely the use of an incorrect index but I couldn't find it after an entire day of research..
From all the tests I have done, I am pretty sure that every function is correct except algC ; when I try to use algC (when the recursion is used by calculating C1 and/or C2), I get the error : Unhandled exception at 0x00007FF99357AFEC (ucrtbased.dll) in Hirschberg.exe: An invalid parameter was passed to a function that considers invalid parameters fatal.
Please someone help me.
Here's my annoted code :
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int min(int a, int b, int c) { //to find the minimum between 3 elements
if (a <= b && a <= c) {
return a;
}
if (b <= a && b <= c) {
return b;
}
if (c <= a && c <= b) {
return c;
}
else {
return 0;
}
}
bool existence(vector<char> A, vector<char> B, size_t n) { //existence of an index j such as A[0]==B[j]
for (size_t j = 0; j < n; j++) {
if (A[0] == B[j]) {
return true;
}
}
return false;
}
vector<char> partiel(vector<char> A, size_t i, size_t j) { //return the characters between i and j, in reverse order if j<i
vector<char> B;
if (i <= j) {
for (size_t e = i; e <= j; e++) {
B.push_back(A[e-1]);
}
return B;
}
if (i > j) {
for (size_t e = i; e >= j; e--) {
B.push_back(A[e - 1]);
}
return B;
}
}
int Mrecherche(size_t n, vector<int> D1, vector<int> D2) { //calculate minimum M
int M = 1000;
for (int j = 0; j < n; j++) {
int Mj = D1[j] + D2[n-1 - j];
if (Mj <= M) {
M = Mj;
}
}
return M;
}
size_t krecherche(size_t n, vector<int> D1, vector<int> D2, int M) { //Calculate maximum k
size_t k = 0;
for (size_t j = 0; j < n; j++) {
if (D1[j] + D2[n - 1 - j] == M) {
if (j >= k) {
k = j;
}
}
else {
continue;
}
}
return k;
}
int delta(size_t i, size_t j,vector<char> A, vector<char> B) { //distance between A[i] and B[j]
if (A[i] == B[j]) {
return 0;
}
else {
return 1;
}
}
vector<int> algB(size_t m, size_t n, vector<char> A, vector<char> B) { //calculate the maximum distance between two strings, represented by vectors
// 1.Initialisation
vector<vector<int>> K(2, vector<int>(n + 1, 0));
// 2. Calcul des coefficients
for (size_t i = 1; i <= m; i++) {
for (size_t j = 1; j <= n; j++) {
K[0][j] = K[1][j];
}
for (size_t j = 1; j <= n; j++) {
K[1][j] = min(K[0][j] + 1, K[1][j - 1] + 1, K[0][j - 1] + delta(i-1,j-1,A,B));
}
}
vector<int> D(n, 0);
for (size_t j = 0; j < n;j++){
D[j] = K[1][j + 1];
}
return D;
}
vector<char> algC(size_t m, size_t n, vector<char> A, vector<char> B) { //propose an optimal alignment, recursive function
vector<char> C;
// 1. Si problème trivial, on le résout
if (n == 0) {
C.push_back('-');
return C;
}
else if (m == 1) {
if (existence(A, B, n)) {
C.push_back(A[0]);
return C;
}
else {
C.push_back('-');
return C;
}
}
// 2. Sinon, on scinde le problème
else {
float mfloat = static_cast<float>(m);
float ifloat = mfloat/2;
size_t mil = floor(ifloat);
// 3. On évalue D(i,j) et D*(i,j) pour j from 0 to b
vector<int> D1;
vector<char> Q1 = partiel(A, 1, mil);
D1 = algB(Q1.size(), B.size(), Q1, B);
vector<int> D2;
vector<char> Q2 = partiel(A, m, mil + 1);
vector<char> Q3 = partiel(B, n, 1);
D2 = algB(Q2.size(), Q3.size(), Q2, Q3);
// 4. On cherche l'endroit où recoller les sous-solutions
int M;
M = Mrecherche(n, D1, D2);
size_t k;
k = krecherche(n, D1, D2, M);
// 5. On calcule les sous-solutions
vector<char> C1;
vector<char> P1 = partiel(A, 1, mil);
vector<char> P2 = partiel(B, 1, k);
C1 = algC(P1.size(), P2.size(), P1, P2);
vector<char> C2;
vector<char> P3 = partiel(A, mil + 1, m);
vector<char> P4 = partiel(B, k + 1, n);
C2 = algC(P3.size(),P4.size(),P3,P4);
// On fusionne les deux sous-solutions et on retourne le résulat.
for (int i = 0; i < C2.size(); i++) {
C1.push_back(C2[i]);
}
return C1;
}
}
int main() {
vector<char> A = {'A','C','T','G','A','T','T'};
vector<char> B = {'G','C','T','A','A','T','C','G'};
vector<char> C = algC(A.size(), B.size(), A, B);
for (int j = 0; j < C.size(); j++) {
cout << C[j] << endl;
}
return 0;
}
Salut, merci pour ta réponse ! C'est en effet pour aligner des séquences d'ADN, en utilisant l'algorithme d'Hirschberg (l'algorithme d'Hirschberg étant le sujet de mon projet).
J'ai d'abord utilisé des string mais j'ai eu une erreur "Exception thrown: read access violation. *this was 0x45." (a priori dans un fichier xstring) que je n'ai pas su résoudre donc j'ai opté pour des vector<char> à la place.
Donc je pense que si je reprends des strings, j'aurais à nouveau la même erreur.
En utilisant les références, tu suggères d'utiliser des pointeurs à la place des vecteurs ? Je ne suis pas du tout familier avec la notion de pointeurs, si je comprends bien : on initialise vector<char> vect; et &vect, ou vec.begin() renvoie à l'adresse mémoire du premier élément du vecteur, mais vect[0] m'y renverrait directement donc quel est l'intéret ?
EDIT : J'ai tenté de repasser en string et de ne plus utiliser de variables longueurs et le problème que j'avais sur les string est résolu, mais j'ai le même problème qu'en vector : "string subscript out of range"
Je ne connais pas tout à fait l'algorithme d'Hirschberg mais je me doute comment il fonctionne. Remarques que tu as un problème avec les string et également les vector<char>. Tu as un bug fondamental quelque part qui ne dépend ni de l'un ni de l'autre. Je préfère les string car il y a plus de fonctions et/ou méthodes pour nous aider. Plus ton code sera simple, plus il sera facile à debugger. Autre exemple en regard de ta fonction min(): #include <iostream> #include <algorithm> int main(void) { int a=11, b=4, c=5; std::cout << std::min({a, b, c}) << std::endl; } Essaies de ne pas utiliser le namespace std La méthode .size() existe autant pour les vector que pour les string. C'est donc inutile de passer les longueurs en paramètre. Le passage par référence utilise des pointeurs, mais dans ce cas, tu n'en verras pas la différence dans le codage. Le compilateur s'occupe de tout ... Essaies de simplifier ton code et tu pourrait le poster à nouveau. De mon côté, je regarde l'algo. Il y a peut-être du code qui existe en C++
Le Tout est souvent plus grand que la somme de ses parties.
Je ne sais pas ce qui dysfonctionne en effet.. En mettant des cout un peu partout pour voir, je pensais que c'était la valeur de k qui était trop grande ou trop petite, mais même en la bornant, ça ne fonctionne pas.
J'ai essayé de simplifier et annoter mon code le plus possible :
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int a, int b, int c) {
//élement minimal d'une liste de trois éléments
int m = a;
if (b < m) m = b;
if (c < m) m = c;
return m;
}
string partiel(string A, int i, int j) {
//string contenant les caractères i à j de A, dans le sens inverse si i>j.
// 0 <= i <= A.size() - 1
// 0 <= j <= A.size() - 1
string B = "";
if (i <= j) {
for (int e = i; e <= j; e++) {
B = B + A[e];
}
return B;
}
if (i > j) {
for (int e = i; e >= j; e--) {
B = B + A[e];
}
return B;
}
}
int recherche(vector<int> D1, vector<int> D2) {
// Détermine le k maximal tel que
// D1[j]+D2[D1.size()-j) = M
//où M = min ( D1[j] + D2[D1.size() - j)
// D1 et D2 de même taille par construction
int M = D1[0] + D2[D1.size()-1];
int k = 0;
for (int j = 1; j < D1.size(); j++) {
int Mj = D1[j] + D2[(D1.size()-1) - j];
if (Mj <= M){
M = Mj;
}
}
for (int j = 0; j < D1.size(); j++) {
if (D1[j] + D2[(D1.size() - 1) - j] == M) {
if (j > k) {
k = j;
}
}
}
return k; //Donc 0<= k <= D1.size() -1
}
int delta(int i, int j, string A, string B) {
//Distance entre les char A[i] et B[j]
if (A[i] == B[j]) {
return 0;
}
else {
return 1;
}
}
vector<int> algB(string A, string B) {
// 1.Initialisation
vector<vector<int>> K(2,vector<int>(B.size()+1, 0));
// 2. Calcul des coefficients de K : distance minimale entre A1i et B1j
for (int i = 1; i <= A.size(); i++) {
for (int j = 1; j <= B.size(); j++) {
K[0][j] = K[1][j];
}
for (int j = 1; j <= B.size(); j++) {
K[1][j] = min(K[0][j] + 1, K[1][j - 1] + 1, K[0][j - 1] + delta(i - 1, j - 1, A, B));
}
}
//on veut récupérer le vecteur K[1], sans le premier élément qui est toujours 0.
vector<int> D(B.size(), 0);
for (int j = 0; j < D.size(); j++) {
D[j] = K[1][j+1];
}
return D; //Donc tous les vecteurs D1, D2 sont de taille B.size()
}
string algC(string A, string B) {
// 1. Si problème trivial, on le résout
if (B.size() == 0 || A.size()==0) {
return "-";
}
else if (A.size() == 1) {
for (size_t j = 0; j < B.size(); j++) {
if (A[0] == B[j]) {
return { A[0] };
}
}
return "-";
}
// 2. Sinon, on scinde le problème
else {
int mil = floor(static_cast<float>(A.size())); //élément milieu de A
// 3. On évalue D(i,j) et D*(i,j) pour j de 0 à B.size()-1
vector<int> D1 = algB(partiel(A,0,mil-1),B);
vector<int> D2 = algB(partiel(A,A.size()-1,mil),partiel(B,B.size()-1,0));
// 4. On cherche l'endroit où recoller les sous-solutions
int k = recherche(D1, D2);
// 5. On calcule les sous-solutions
string C1 = algC(partiel(A,0,mil-1),partiel(B,0,k-1));
string C2 = algC(partiel(A,mil,A.size()-1),partiel(B,k,B.size()-1));
// On fusionne les deux sous-solutions et on retourne le résulat.
return C1 + C2;
}
}
int main() {
string A = "ACTGATT";
string B = "GCTAATCG";
string C = algC(A, B);
for (int j = 0; j < C.size(); j++) {
cout << C[j] << endl;
}
return 0;
}
J'ai toujours l'erreur "string subscript out of range" bien que j'ai vérifié pleins de fois chaque boucle for, est-ce que ça pourrait venir d'une initialisation du string ?
Ta fonction delta dit ceci: int delta(int i, int j, string A, string B) { Tu retournes soit 0, soit 1 Pourquoi appeler cela une distance? Ne devrais-tu pas retourner i - j ?
edit:
Je ne comprend pas cette ligne: int mil = floor(static_cast<float>(A.size())); //élément milieu de A et ceci ne marcherait pas? int mil = A.size() / 2;
- Edité par PierrotLeFou 9 octobre 2022 à 18:10:28
Le Tout est souvent plus grand que la somme de ses parties.
C'est simplement une hypothèse, on considère que deux caractères différents ont une distance de 0 et des caractères différents une distance élémentaire de 1. (C'est un choix, c'est aussi possible d'utiliser une matrice de similarité, qui attribue une distance à chaque couple de caractère)
J'ai tenté de faire le même code en python, avec lequel je suis plus à l'aise, pour essayer de comprendre ce qui ne va pas mais j'ai la même erreur de dépassement d'indice..
Combien de lignes fait ton code en Python? Je connais également le Python. Si tu as le même problème en Python, c'est l'algorithme qui est le problème, pas vraiment le code (même si le code reflète l'algorithme ...)
Le Tout est souvent plus grand que la somme de ses parties.
Je pense que c'est l'algorithme en soi en effet, je vais essayer de revoir cette partie, et si il y a encore un problème de code, je te tiendrais au courant.
Merci beaucoup pour ton temps !
EDIT :
Problème résolu ! C'était bien une erreur dans l'algorithme et non dans le code. (Du fait d'avoir adapté l'algorithme de base d'Hirschberg prévu pour le calcul de la plus longue sous chaîne commune à un problème d'alignement, il ne fallait pas découper mes sous problèmes en deux parties distinctes mais avec un point de jointure commun aux deux solutions. C'est ce qui causait le décalage de un élément de string qui posait problème.)
Tout fonctionne parfaitement maintenant !
Merci encore pour tes conseils !
- Edité par Noah3010 9 octobre 2022 à 20:19:58
An invalid parameter was passed to a function that
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.