Devoir 1

CSI2572 Automne 2004-09-21

Soumission par webCT

Date de soumission: 2004-10-07 23:59

Q1 (4pts):

Un test par ADN compare des échantillons de code génétique entre un
enfant, sa mère et un père potentiel. Tous les échantillons sont
représentés par des chaines de charactères majuscules entre 'E' et 'H'
inclus. Si exactement 50% des charactères dans l'échantillon de
l'enfant sont les mêmes que celui de l'homme, et à la même position,
et que le reste des charactères sont les mêmes que celui de la mêre,
et à la meme position, l'homme est possiblement le père de l'enfant.
Par contre, s'il est impossible de partitionner le code génétique de
l'enfant de telle manière à ce qu'il corresponde à 50% à celui de
l'homme, et à 50 % à celui de la mère, l'homme n'est probablement pas
le père.

Par example, à supposer que le code génétique de l'enfant est :
"EFGGHI" et que celui de la mère est : "EGGEEI", la partie "E*G**I"
dans le code de l'enfant doit être venue de la mère. Si le code du
père est "GFFGHG", l'homme est possiblement le père de l'enfant. Par
contre, si le code du père est "EIGGEI" il ne peut pas être le père.

Remarquez que dans cet example, l'homme a 4 gènes à la bonne position
par rapport au code de l'enfant, mais que comme 3 de ces gènes
appartiennent déja à la mère, il ne peut quand même pas être le père
de l'enfant.

Vous allez coder une méthode qui prendra comme argument des
échantillons de l'enfant, de la mère et de plusieurs pères potentiels.
votre méthode retournera les indices des hommes qui ne peuvent pas
être le père, en ordre croissant.

class: Papatest
Méthode: PapaImpossible
Paramètres: char*, char*, char**, int
Retour: vector<int>
Signature de la méthode:

vector<int>  PapaImpossible (char* CodeEnfant,

char* CodeMaman,

char** CodeHommes,

int NombreHommes)

La méthode est publique.

Les chaines charactères qui encodent les codes gènetiques de l'enfant,
des hommes et de la mère sont toutes de la mème longueur et se
terminent toutes par le caractère '\0'. Elles sont toutes de longueur
impaires (paires si on ne compte pas le dernier charactère).

Le code génétique  de la mère contiendra toujours au moin 50% de gènes
correspondant à ceux de l'enfant.

examples:

"EFGGHI\0"
"EGGEEI\0"
{"EIGGEI\0", "GFFGHG\0", "EFGGEI\0", "IFEEEI\0"}
4

è Retour: {0, 2, 3}

Ø Plus d'examples vous seront fournis plus tard.

Ø Un driver pour votre classe/méthode vous sera aussi fournit plus tard.

Ø Vous devez vous servir de la base de code suivante:

§ Papatest.h

Q2 (4pts):

Les patrons qui se retrouvent sur certain mollusques tel que le Conus et le Symbolia (voir ci-dessous) sont générés par des automates cellulaires organiques simples. Les pigments des mollusques produisent des sécretions qui produisent à leur tour des pigments en suivant des régles triviales.

Pour cette question, vous allez devoir implémenter un automate
cellulaire simple. Un automate cellulaire est un système qui évolue de
manière discrète à partir d'un état initial et d'un ensemble de
règles. Par exemple http://www.bitstorm.org/gameoflife/ présente un
automate basé sur des règles fixes qui permet à l'utilisateur de
spécifier des états initiaux différents.

À l'inverse de celui la, votre automate sera basé sur un état initial
fixe, mais permettra à son utilisateur de spécifier les règles qui
dictent son évolution. Il sera aussi plus simple parce qu'il
n'évoluera que dans un sens précis (uni dimension). Chacune des règles
choisis par l'utilisateur pourra être représentées par une série de
diagrammes dans la forme:

* * *

*

Où les * peuvent être l'un de 3 charactère possibles: '#','O' ou '.' , reprèsentant chacun un des trois états possibles de chaque cellule.

Par example, la règle suivante, indique que la cellule qui vient après la première ligne devrait être le charactère 'O' si la cellule qui la précède directement est aussi le charactère 'O' et que celles à droite et à gauche sont les charactères '#'

# O #

O

Comme l'état suivant de la cellule sera déterminé par les trois cellules qui la précèdent, il y a 27 (3*3*3) états initials possibles. Pour le devoir, par convention, ces états seront toujours placés dans l'ordre suivant:

0- # # #	1- # # O	2- # # .	3- # O #	4- # O O	5- # O .	6- # . #
7- # . O	8- # . .	9- O # #	10- O # O	11- O # .	12- O O #	13- O O O
14- O O .	15- O . #	16- O . O	17- O . .	18- . # #	19- . # O	20- . # .
21- . O #	22- . O O	23- . O .	24- . . #	25- . . O	26- . . .

Dans votre programme, les régles seront représentés par un tableau de 27 charactères ('#','O' ou '.'). La position d'un charactère dans le tableau indique l'état initial auquel il est fait référence.

Par example, étant donné l'ensemble de règles suivant :

#

#

.

#

O

O

O

O

#

#

#

#

.

#

O

#

.

.

.

.

.

#

#

.

O

#

.

Le charactère situé dans la case 5 fait référence à la règle suivante:

# O .

O

Tandis que le charactère à la case 26 fait référence à la régle:

. . .

.

Example:

Étant donné l'état initial :

#

#

#

#

#

#

#

#

#

.

.

.

.

O

O

.

#

et la régle:

0	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
#	.	O	O	O	.	#	#	O	O	.	.	.	.	#	#	#	.	O	O	O	O	#	#	.	.	.

Voici l'automate sur trois étape:

#

#

#

#

#

#

#

#

#

.

.

.

.

O

O

.

#

#

#

#

#

#

#

#

#

O

O

.

.

.

#

#

#

O

O

#

#

#

#

#

#

.

O

#

.

.

.

O

#

.

O

.

O

#

#

#

#

O

#

O

.

O

.

.

O

.

#

#

class: CellAuto
Méthode: fillGrid
Paramètres: char**, char [27], int

Retour: void

Signature de la méthode:

void  fillGrid (char** Grid, char rule[27], int numRangees)

La méthode est publique.

Vous devez aussi implémenter la méthode valide, qui vérifie qu'une règle est valide, à la fois par les charactères dont elle est composée et dans sa longueur (la déclaration se trouve dans le fichier lié plus bas).

Ø Lorsque une cellule est sur la bordure de l'automate, la case à l'extrème gauche (si la cellule est sur la bordure droite) ou à l'extrème droite (si la bordure est à l'extrème gauche) est considérée pour compléter la règle (wraparound).

Ø Plus d'examples vous seront fournis plus tard.

Ø Un driver pour votre classe/méthode vous sera aussi fournit.

Ø Vous devez utiliser la base de code suivante:

§ ellAuto.h

Q3 (2pts):

Expliquer les différences et les similarités entre le passage de paramétre à une fonction par valeur et par addresse. Dans quelle situations utiliserions nous l'un plutôt que l'autre?