Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 09-07-2019 15:24:27

zizou47
Membre
Inscription : 05-07-2019
Messages : 20

doublon, arrangement

bonjour : )

def existe_doublon(liste):
res=False
n=len(liste)
for k in range(n-1):
  for j in range(k+1,n):
   if liste[k]==liste[j]:
    res=True
return res
-------------------
Q : Combien y a t'il de test d'égalités entre chaîne de caractères lors de l'appel avec un paramètre liste de longueur n ?
moi je connais le produit cartésien ' (n - 1) * (n - (k+1))  et a mon c un arrangement de A (n) et p = nombre de doublons ?

Hors ligne

#2 09-07-2019 17:15:28

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : doublon, arrangement

Salut,

Tu cherches quoi exactement ?
Le nombre de doublons ou le nombre de tests d'égalité ?
Remarques
1. Sers-toi de la balise code <> qui respectera l'indentation

2. Si ton script est censé te fournir le nombre de tests d'égalité, tu seras déçu : il ne te donnera pas ce nombre...
   Tes tests sont systématiques, donc il faut calculer ce nombre de tests immédiatement après la 2e boucle for...
   Déclarer une variable tests=0 en même temps que res=True
   Supposons une liste avec n=10 chaînes de caractères
   Test de liste[0]  avec list[1] à list[9]  --> 9 tests
   Test de liste[1]  avec list[2] à list[9]  --> 8 tests
   Test de liste[2]  avec list[3] à list[9]  --> 7 tests
   ..................................................................
   Test de liste[7]  avec list[8] à list[9]  --> 2 tests
   Test de liste[8]  avec list[9]              --> 1 test
   Total S=1+2+3+4+5+6+7+8+9 = 49

   J'ai fait l'essai avec une liste de 100 chaînes de caractère.
   Pour ça, j'ai tiré 100 fois au hasard une lettre de l'alphabet ente "A" et "Z" inclus).
   J'obtiens 4950 soit la somme des nombres de 1 à 99.

3. Si ton script est censé te fournir le nombre de tests d'égalité positifs (vrais, si tu veux), tu seras déçu aussi.
    Il ne te donnera pas non plus ce ce nombre...
    La faute en est à la variable res...
    Écris plutôt
    a) res = 0  au lieu de res = True
    b) puis ensuite après le if : res+=1  au lieu à nouveau de res=True
    Et là comme j'ai construit une liste aléatoire, la valeur de res sera aussi aléatoire...

Voilà, j'ai modifié ta fonction pour qu'elle fournisse tests et res.
J'ai d'abord importé le module randint qui fournit un entier entre a et b inclus si tu demandes randint(a,b)
Je lance ce script :

from random import randint

def existe_doublon(liste):
    n,tests,res=len(liste),0,0
    for k in range(n-1):
        for j in range(k+1,n):
            tests+=1
            if liste[k]==liste[j]:
                res+=1
    return tests,res

Ensuite, je fabrique ma liste :

>>> liste=[chr(65+randint(0,25)) for i in range(100)]

chr(65) est la lettre A, chr(90) la lettre Z :

>>> print(chr(65),chr(90))
A Z
>>>

Donc je tire 100 fois un nombre au hasard entre 0 et 25 inclus et je l'ajoute à 65, et je stocke le caractère correspondant à ce code dans liste....
Tu peux recommencer autant de fois que tu veux cette ligne

>>> liste=[chr(65+randint(0,25)) for i in range(100)]

et tu fais suivre chaque fois de :

print(existe_doublon(liste))

Si tu veux plus ou moins de 100 éléments dans liste tu modifies 100.
Si tu veux plus de caractères différents soit en commençant par A (alors tu gardes 65) ou se terminant après Z (alors tu augmentes 25)

Voilà plusieurs essais sans rien modifier :

>>> liste=[chr(65+randint(0,25)) for i in range(100)]
>>> print(existe_doublon(liste))
(4950, 182)
>>>
>>> liste=[chr(65+randint(0,25)) for i in range(100)]
>>> print(existe_doublon(liste))
(4950, 187)
>>>
>>> >>> print(existe_doublon(liste))
(4950, 167)
 

Tu vois que tests be change pas mais que res est aléatoire...
n=len(liste)
$tests=\dfrac{(n-1)\times n}{2}$
avec 100 :
$tests=\dfrac{99\times 100}{2}=4950$

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 10-07-2019 12:13:17

zizou47
Membre
Inscription : 05-07-2019
Messages : 20

Re : doublon, arrangement

merci bq mr yoshi, tu sais! je me suis dit je vais créer une variable (compteur) mais toujours il y a une une dans ma tète "le compteur va compter le nombre de doublons, mais pour le nombre de tests elle prend quelle ligne dans le code? donc l'idée  c d'avant la ligne IF
j'ai croisé un problème comme ca( change le placement) mais je sais pas... je pense que c manque d’expérience ^^.
une question : la on est d'accord n_tests = n(n-1) / 2; mais comment tu peux la prouver mathématiquement sans test sur IDE? j'insiste sur /2

Hors ligne

#4 10-07-2019 12:57:05

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : doublon, arrangement

Salut,

mais comment tu peux la prouver mathématiquement sans test sur IDE? j'insiste sur /2

C'est quelque chose ce très courant, il suffit de chercher "Somme des n premiers nombres entiers"
La démonstration la plus simple et la plus courante : on écrit deux fois la somme une fois dans l'ordre croissant, une fois dans l'ordre décroissant :


S = 1 +  2  +  3  + ... + n-2 + n-1 + n
S = n + n-1 + n-2 + ... +  3  +  2  + 1

Et on additionne...
Chaque "colonne" a pour somme n+1
$2S = \underbrace{(n+1) + (n+1) + (n+1) + ... +(n+1) + (n+1) + (n+1)}_{\text{n termes égaux à n+1}}$
D'où
$2S=n(n+1)$
Et donc
$S=\dfrac{n(n+1)}{2}$
C'est le mathématicien Gauss qui est à l'origine de cette formule.
Enfant, sont instituteur donna comme défi à des élèves de calculer la somme des nombres de 1 à 100.
Quelle ne fut pas sa surprise lorsque le petit Gauss, peu après, lui présenta le résultat...
Et à la demande de son Instit stupéfait, il expliqua qu'il avait remarqué que 100+1=101, 99+2 = 101, 98 + 3 = 101...
Et que donc sur son ardoise, il avait calculé (100 * 101)/2...

Dans ton cas avec ta liste à n éléments tu fais la somme des entiers de 1 à n-1, donc ta somme est :
$S=\dfrac{(n-1)\times n}{2}$

Ça te va ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 10-07-2019 13:49:58

zizou47
Membre
Inscription : 05-07-2019
Messages : 20

Re : doublon, arrangement

merci, j'ai compris l'idée, (je vais voir plus)
ton exercice :)
http://www.bibmath.net/forums/viewtopic.php?id=10097

Hors ligne

Pied de page des forums