Exercice 1 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <stdio.h>
#include <stdlib.h>
 
#define MAX(x,y) ((x>y)?(x):(y))
 
char nucleotide(int N, char* s)
{
        /* Tableau pour le nombre d'occurences de chaque nucléotide */
        int stat[4] = { 0,0,0,0 }, max;
        
        /* Remplissage du tableau */
        while(N--)
        {
                switch(s[N]) 
                {
                        case 'A' : stat[0]++; break;
                        case 'C' : stat[1]++; break;
                        case 'G' : stat[2]++; break;
                        case 'T' : stat[3]++; break;
                }
        }
        
        /* Recherche du maximum */
        max = MAX(MAX(stat[0],stat[1]),MAX(stat[2],stat[3]));
        if(max == stat[0]) return 'A';
        if(max == stat[1]) return 'C';
        if(max == stat[2]) return 'G';
        if(max == stat[3]) return 'T';
 
        return 'A';
}
 
int main(void)
{
  int N;
  char* s;
 
  scanf("%d\n", &N);
  s = calloc(N+1, sizeof(char));
  fgets(s, N+1, stdin);
 
 
  printf("%c\n", nucleotide(N, s));
 
  return 0;
}

Exercice 2 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <stdio.h>
#include <stdlib.h>
 
 
void traduction(int N, int M, char* table_traduction[64][2], char* s)
{
        int i,j;
        
        /* Pour chaque triplet de nucléotides */
        for(i=0; i<N; i+=3)
        {       
                /* Recher de l'acide aminé correspondant */
                for(j=0; j<M; j++)
                {
                        if(table_traduction[j][0][0] == s[i] && 
                         table_traduction[j][0][1] == s[i+1] && 
                         table_traduction[j][0][2] == s[i+2]) 
                        {
                                /* Affichage */
                                printf("%s ", table_traduction[j][1]);
                                break;
                        }
                }
        }
        printf("\n");
}
 
int main(void)
{
  int N;
  int M;
  char* table_traduction[64][2];
  char* s;
  int i;
  scanf("%d\n", &N);
  scanf("%d\n", &M);
 
  for (i = 0 ; i < M ; i++) {
    table_traduction[i][0] = malloc(100);
    table_traduction[i][1] = malloc(100);
    scanf("%s ", table_traduction[i][0]);
    scanf("%s ", table_traduction[i][1]);
  }
 
  s = calloc(N+1, sizeof(char));
  fgets(s, N+1, stdin);
 
  traduction(N, M, table_traduction, s);
 
  return 0;
}

Exercice 3 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* Taille de la table de hachage */
#define TABLE_TAILLE 1000000
 
/* Entités de la table */
typedef struct entree {
        char *seq;
        int stat;
} entree;
 
entree table[TABLE_TAILLE];
 
/* Fonction de hachage de Bernstein, trouvée sur wikipédia... */
unsigned int hash(char *str, int len)
{
        unsigned int hash = 5381;
        unsigned int i; 
 
        for(i=0; i<len && str[i]; i++)
                hash = ((hash << 5) + hash) + str[i];
 
        return hash;
}
 
/* Incrémente le compteur d'une séquence pointée par /seq/ de longeur /longeur/ */
void incremente_seq(char *seq, int longueur)
{
        unsigned int i;
 
        i = hash(seq, longueur) % TABLE_TAILLE;
        /* Gestion des collisions en open addressing */
        while(table[i].seq && strncmp(table[i].seq, seq, longueur) != 0)
        {
                i++;
                i %= TABLE_TAILLE;
        }
        /* Création éventuelle de l'entrée */
        table[i].seq = seq;
        /* Incrémentation */
        table[i].stat++;
}
 
char* sous_sequence(int N, int L, char* s)
{
        int max=0, i;
        char *max_seq;
 
        /* Initialization de la table de hachage */
        memset(table, 0, sizeof(entree)*TABLE_TAILLE);
        
        /* Remplissage de la table avec les séquences de /s/ */
        for(i=0; i<(N-L); i++)
                incremente_seq(s+i, L);
        
        /* Recherche du max dans la table */
        for(i=0; i<TABLE_TAILLE;i++)
        {
                if(table[i].stat > max
                 || (max != 0 && table[i].stat == max && strncmp(table[i].seq, max_seq, L) < 0))
                {
                        max = table[i].stat;
                        max_seq = table[i].seq;
                }
        }
        
        /* Remise sous forme de chaîne */
        max_seq[L]=0;
        return max_seq;
}
 
int main(void)
{
        int N;
        int L;
        char* s;
 
        scanf("%d\n", &N);
        scanf("%d\n", &L);
        s = calloc(N+1, sizeof(char));
        fgets(s, N+1, stdin);
 
        printf("%s\n", sous_sequence(N, L, s));
 
        return 0;
}

Exercice 4 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <stdio.h>
#include <stdlib.h>
 
#define ABS(x) ((x>0)?(x):(-x))
#define MIN(x,y) ((x<y)?(x):(y))
#define MAX(x,y) ((x>y)?(x):(y))
 
int edition(int N1, int N2, char* s1, char* s2)
{
        int *dp, *dc, *tmp, i, j;
        
        /* J'utilise l'algorithme de la distance de Levenshtein dynamique,
         * classique mais avec une optimisation de la mémoire : seules
         * deux lignes de la matrice des distances sont conservées.
         * /dc/ pour la ligne courante et /dp/ pour la ligne précédente. */
        dp = (int*)malloc(sizeof(int*)*(N1+1));
        dc = (int*)malloc(sizeof(int*)*(N1+1));
 
        dp[0] = 0;
        for(i = 1; i <= N2; ++i) dp[i] = i;
 
        for(i = 1; i <= N1; ++i)
        {
                dc[0] = i;
                /* Ici invervient une optimisation sur le nombre de transformations
                 * maximal : il suffit de calculer une tranche diagonale assez large
                 * de la matrice et l'on peut être sûr que la solution sera à
                 * l'intérieur */
                for(j = MAX(1,i-150); j <= MIN(i+150,N2); ++j)
                {
                          dc[j] = MIN(MIN(dp[j] + 1,dc[j - 1] + 1),
                 dp[j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1));
                }
                tmp = dp;
                dp = dc;
                dc = tmp;
        }
        
        return MIN(100,dp[N2]);
}
 
int main(void)
{
  int N1;
  int N2;
  char* s1;
  char* s2;
 
  scanf("%d\n", &N1);
  scanf("%d\n", &N2);
  s1 = calloc(N1+1, sizeof(char));
  fgets(s1, N1+1, stdin);
  getchar();
 
  s2 = calloc(N2+1, sizeof(char));
  fgets(s2, N2+1, stdin);
  getchar();
 
 
  printf("%d\n", edition(N1, N2, s1, s2));
  
  return 0;
}