/*****************************************************************************/ // travail : TP1 Q1, Q2 // auteur : Marc Blouin // description : permettre de trouver des alignements globaux de deux sequences. // date : 28 jan 2003 // cours : ift3290 /*****************************************************************************/ // Utilisation java tp1 asdf sdfg public class tp1 { private int tab[][]; String mySeq1, mySeq2; int nbSolPos =0; //le main valide les paramètres public static void main(String[] args) { if (args.length != 2){ System.out.println("il faut 2 parm vous avez : " + args.length); return; } tp1 unTp = new tp1(args[0],args[1]); } //constructeur avec tous les actions principals public tp1(String seq1, String seq2){ tab = new int[seq2.length() + 1][seq1.length() + 1]; mySeq1 = seq1; mySeq2 = seq2; remplirTout();//remplir le tableau de PD imprimer(); //imprimer le tableau remonter(); //remonter le tableau pour trouver les solutions optimals } //imprime le tableau de PD public void imprimer(){ System.out.println(" " + mySeq1); for (int i = 0 ; i <= mySeq2.length();i++){ if (i != 0){ System.out.print("\n" + mySeq2.charAt(i-1) + " "); } else { System.out.print("\n "); } for (int j = 0 ; j <= mySeq1.length();j++){ System.out.print(" " + tab[i][j]); } } } //remonte le tableau pour trouver les solutions optimals public void remonter(){ nbSolPos = 0; remonte(mySeq2.length(), mySeq1.length(),"",""); System.out.println("le nb sol opt : " + nbSolPos); } //fct recursive qui remonte par le ou les meilleurs chemins vers une //solution optimal. public void remonte(int pos1, int pos2, String aStr1, String aStr2){ if (pos1 == 0 && pos2 == 0){ System.out.println("\nune solution possible : "); System.out.println(" chaine 1 : " + aStr1); System.out.println(" chaine 2 : " + aStr2); nbSolPos++; } else { if (pos1 != 0 && tab[pos1][pos2] == tab[pos1-1][pos2]+1){ remonte(pos1-1, pos2, (" ").concat(aStr1), (mySeq2.substring(pos1-1, pos1)).concat(aStr2)); } if (pos1 != 0 && pos2 != 0 && (tab[pos1][pos2] == tab[pos1-1][pos2-1]+1 || (tab[pos1][pos2] == tab[pos1-1][pos2-1] && mySeq1.charAt(pos2-1) == mySeq2.charAt(pos1-1)) ) ){ remonte(pos1-1, pos2-1, (mySeq1.substring(pos2-1, pos2)).concat(aStr1), mySeq2.substring(pos1-1, pos1).concat(aStr2)); } if (pos2 != 0 && tab[pos1][pos2] == tab[pos1][pos2-1]+1){ remonte(pos1, pos2-1, (mySeq1.substring(pos2-1, pos2)).concat(aStr1), (" ").concat(aStr2)); } } } //remplit les côtés du tableau public void remplirCote(){ tab[0][0] = 0; for (int i = 1 ; i <= mySeq1.length(); i++){ tab[0][i] = tab[0][i-1] + 1; } for (int i = 1 ; i <= mySeq2.length(); i++){ tab[i][0] = tab[i-1][0] + 1; } } //remplit une case de la valeur optimal à la position pos1 en y et pos2 en x public void remplir(int pos1, int pos2){ int valmin = valmin = tab[pos1-1][pos2] + 1; if (tab[pos1][pos2-1] + 1 < valmin){ valmin = tab[pos1][pos2-1] + 1; } int isMatch = 1; if (mySeq1.charAt(pos2-1) == mySeq2.charAt(pos1-1)){ isMatch = 0; } if (tab[pos1-1][pos2-1] + isMatch < valmin){ valmin = tab[pos1-1][pos2-1] + isMatch; } tab[pos1][pos2] = valmin; } //remplit chacune des cases du tableau de PD public void remplirTout(){ remplirCote(); for (int i = 1 ; i <= mySeq2.length();i++){ for (int j = 1 ; j <= mySeq1.length();j++){ remplir(i,j); } } } }