aide pour exercice

Si je te suis tes étapes :
1/ "codage binaire" de chaque ligne
a b d e f devient 1 1 0 1 1 1 0

2/puis de comparer les lignes 2 a 2 (c'est pas 1 à 1 ?)

Code:

---

1 2 3 4 5

1 1 0 1 1 1 0 1 1 1 0 1 1 0 ------------- 1 1 0 0 1 1 0

---

3/suite ok

C'est bien ce que tu veux dire ?
Si c'est ça, on devra faire une comparaison de chaque codage binaire, non ?

Citation:

---

Envoyé par tania

Si je te suis tes étapes :
1/ "codage binaire" de chaque ligne
a b d e f devient 1 1 0 1 1 1 0

---

oui. tu peux faire un codage binaire "pur" si ca tient sur un int/long (32/64 bits = 32/64 symboles)

Citation:

---

2/puis de comparer les lignes 2 a 2 (c'est pas 1 à 1 ?)

Code:

---

1 2 3 4 5

1 1 0 1 1 1 0 1 1 1 0 1 1 0 ------------- 1 1 0 0 1 1 0

---

---

oui. ca fait C(2,nl) operations, avec "nl" le nombre de lignes. Cette partie de l'algo est parallelisable.

(on dit bien 2 a 2 dans ce cas... non ?)

Citation:

---

3/suite ok

C'est bien ce que tu veux dire ?
Si c'est ça, on devra faire une comparaison de chaque codage binaire, non ?

---

Dans un langage digne de ce nom, tu as des operateurs qui manimulent les champs de bits, et qui te diront combien de bits sont a 1 dans un int/long.

Après, il faut extraire les combinaisons possibles: C(4,nb) groupes de 4, avec "nb" le nombre de bit a 1.

Citation:

---

Envoyé par tania

@Trap, je ne comprend pas ton rapprochement entre la somme des combinaisons manquantes, le resultat d'un AND et le tableau (0 pour ce présent, 1 manquant).

Peut-tu faire un exemple avec un AND ?

---

Je reprends mon exemple

Code:

---

1 2 3 4 5 6 7

a b c d e f g 1: 0 0 0 0 0 1 1 => codage 32 + 64 = 96 en hexa 1 100 000 2: 0 0 1 0 1 0 0 => codage 4 + 16 = 20 en hexa 0 010 100 3: 1 0 0 0 0 0 1 => codage 1+ 64 = 65 en hexa 1 000 001 4: 0 1 0 1 0 0 0 => codage 2 + 8 = 9 en hexa 0 001 010 5: 1 0 1 0 0 0 0 => codage 1 + 4 = 5 en hexa 0 000 101 6: 0 0 1 0 1 0 0 => codage 4 + 16 = 20 en hexa 0 010 100

---

maintenat si tu fais un AND bit à bit des codage de 1 et 2 =
1: en hexa 1 100 000
2: en hexa 0 010 100
on obtient 0 000 000, donc un résultat nul et pas d'élément commun en effet abcde et abdfg n'ont pas quatre lettres communes

Si maintenant on fait la même chose pour 1 et 3
1: en hexa 1 100 000
3: en hexa 1 000 001
on obtient 1 000 000 donc un résultat non nul et au moins 4 lettres communes
abcde et bcdef on bien les 4 lettres bcde communes

Idem pour 2 et 5:
2: en hexa 0 010 100
5: en hexa 0 000 101
on obtient 0 000 100
Résultat non nul, abdfg et bdefg ont bien 4 lettres communes.

@Trap D: ca marche car tu es dans un cas particulier: un alphabet de 7 elements et toutes les lignes ont 4 valeurs (+ 2 trous).

A partir du moment ou 2 lignes ont 1 trou en commun, elles ont forcement soit 4, soit 5 valeurs communes.

En fait Trap, ta méthode est simple et bonne dans le contexte actuel.
Quoi qu'il y a n'a pas besoin de faire de somme et calcul en hexa, le 1er tableau suffit à trouver.

Il suffit de chercher le chiffre manquant sur les 2 chiffres qui manque sur 2 lignes différentes.
Ainsi le c ou 4 apparait à la fois en ligne 2, 5 et 6.


Par contre, que devient cette méthode si les lettres vont de A à H ?

Citation:

---

Envoyé par tania

Par contre, que devient cette méthode si les lettres vont de A à H ?

---

Elle marche s'il y a au maximum 2 vides par ligne:

ligne A = 6 symboles parmi 8 + 2 vides
ligne B = 6 symboles parmi 8 + 2 vides

si 1 vide en commun, ca revient a avoir un alphabet de 7 symboles (au lieu de 8) et un seul vide par ligne:

ligne A = 6 symboles parmi 7 + 1 vide
ligne B = 6 symboles parmi 7 + 1 vide

Intersection A/B possibles:
5 symboles ( si le vide restant est commun )
4 symboles ( si les 2 lignes n'ont pas le meme vide )

Comme l'a très bien dit pseudocode, ma méthode fonctionne dans les conditions de l'exemple, a savoir

Citation:

---

Envoyé par pseudocode

ca marche car tu es dans un cas particulier: un alphabet de 7 elements et toutes les lignes ont 4 valeurs (+ 2 trous).

---

C'est pour celà que j'ai écrit

Citation:

---

Envoyé par Trap D

si on s'en tient à l'exemple donné

---