Cercles d'amis

Do you want to read our courses in English? please visit our new website cs-teachers.com Click here

Cercles d'amis

Problème : 

Il y a N étudiants dans une classe, chaque étudiant peut avoir 0 ou plusieurs amis si A est un ami de B et B est un ami de C, le A et le C sont également des amis.

Nous définissons un cercle comme un groupe d’élèves amis, tel que défini par la définition ci-dessus.

étant donnée une matrice friends de taille NxN constitués des caractères Y ou N. Si les friends[i][j]=Y alors les ième et jième étudiants sont des amis, sinon N.

Trouvez le nombre total de ces cercles d'amis en classe


  1. On commence avec le premier élève(i=0), définir visited[i] = Y.
  2. Initialiser NBCercles=1
  3. Passer à l'élève suivant j pour lequel friends[i][j] = Y, définir visited [j] = Y.
  4. Trouvez récursivement les amis de j et marquez-les comme étant visités jusqu'à ce que tous les étudiants pouvant être atteints à partir de i = 0 soient couverts, ils formeront un cercle d'amis.
  5. une fois que tous les amis de l'étudiant 1 sont parcourus, nous passons au prochain étudiant non visité et augmentons le NBCercles de 1.
  6. Répétez les étapes ci-dessus jusqu'à ce que tous les élèves soient visités.
  7. retourne NBCercles.
        friends = [['Y', 'Y', 'N', 'N'], ['Y', 'Y', 'Y', 'N'],
                    ['N', 'Y', 'Y', 'N'], ['N', 'N', 'N', 'Y']]
         
         
         def Cercle(friends):
             NB = len(friends)
             # Nombre de cercles
             NC = 0
             visited = [False for j in range(NB)]
             # parcourir les étudiants
             for i in range(NB):
                 # si l'élément n'est pas encore visité
                 if visited[i] == False:
                     # définir comme visité
                     visited[i] = True
         
                     # visiter ces voisins
                     # i indice de l'étudiant en cours
                     PARCOURSPROFONDEUR(i, visited)
         
                     # incrémenter le compteur
                     NC += 1
             return NC
         
         
         def PARCOURSPROFONDEUR(indice, visited):
             global friends
             for j in range(len(visited)):
                 # si etudiant j est ami(e) avec indice et n'est pas encore visité
                 if friends[indice][j] == 'Y' and indice != j and visited[j] == False:
                     # définir comme visité
                     visited[j] = True
         
                     # visiter ces voisins
                     PARCOURSPROFONDEUR(j, visited)
         
         
         print(Cercle(friends))         
                  
                

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Commentaire(s)

Pour laisser un commentaire vous devez avoir un compte Inscription, ou Se connecter