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
- On commence avec le premier élève(i=0), définir visited[i] = Y.
- Initialiser NBCercles=1
- Passer à l'élève suivant j pour lequel friends[i][j] = Y, définir visited [j] = Y.
- 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.
- 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.
- Répétez les étapes ci-dessus jusqu'à ce que tous les élèves soient visités.
- 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
ESSADDOUKI
Mostafa