API tools faq
paste
Advertisement
reza0310

NSI 4

reza0310
May 10th, 2021
1,196
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 10.42 KB | None | 0 0
raw download clone embed print report
  1. 1) matrix = [[0, 1, 1, 0, 1],
  2.           [1, 0, 0, 0, 0],
  3.           [1, 0, 0, 1, 1],
  4.           [0, 0, 1, 0, 1],
  5.           [1, 0, 1, 1, 0]]
  6.  
  7. 2)
  8. a) Ce programme permet de détecter la présence de cycles dans un graphe.
  9. b)
  10. File: File contenant les prochains points a visiter.
  11. Visites: Liste donnant pour chaque noeud l'information de si il a déjà été visité ou non.
  12. Parent: Donne le prédécesseur direct de chaque noeud pour éviter de compter un demi-tour comme un cycle.
  13. Courant: Noeud actuellement en cours de visite.
  14.  
  15. c)
  16.  
  17. n      | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  | 5                                  |
  18. -------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
  19. u      | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 0                                  |
  20. -------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
  21. file   | [0] -> []                          | []                                 | [1]                                | [1, 2]                             | [1, 2]                             | [2, 4]                             | [2, 4]                             | [2, 4]                             | [2, 4]                             | [2, 4]                             | [4]                                | [4]                                | [4]                                | [4]                                | [4]                                | []                                 |
  22. -------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
  23. visites| [True, False, False, False, False] | [True, False, False, False, False] | [True, True, False, False, False]  | [True, True, True, False, False]   | [True, True, True, False, False]   | [True, True, True, False, True]    | [True, True, True, False, True]    | [True, True, True, False, True]    | [True, True, True, False, True]    | [True, True, True, False, True]    | [True, True, True, False, True]    | [True, True, True, False, True]    | [True, True, True, False, True]    | [True, True, True, False, True]    | [True, True, True, True, True]     | [True, True, True, False, True]    |
  24. -------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
  25. parent | [-1, -1, -1, -1, -1]               | [-1, -1, -1, -1, -1]               | [-1, 0, -1, -1, -1]                | [-1, 0, 0, -1, -1]                 | [-1, 0, 0, -1, -1]                 | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, -1, 0]                  | [-1, 0, 0, 2, 0]                   | [-1, 0, 0, 2, 0]                   |
  26. -------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
  27. courant| 0                                  | 0                                  | 0                                  | 0                                  | 0                                  | 1                                  | 1                                  | 1                                  | 1                                  | 1                                  | 2                                  | 2                                  | 2                                  | 2                                  | 2                                  | 4                                  |
  28. -------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
  29. i      | 0                                  | 1                                  | 2                                  | 3                                  | 4                                  | 0                                  | 1                                  | 2                                  | 3                                  | 4                                  | 0                                  | 1                                  | 2                                  | 3                                  | 4                                  | 0                                  |
  30. -------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40. matrix = [[0, 1, 1, 0, 1],
  41.          [1, 0, 0, 0, 0],
  42.          [1, 0, 0, 1, 1],
  43.          [0, 0, 1, 0, 1],
  44.          [1, 0, 1, 1, 0]]
  45.  
  46. voies_du_jedi = [[1]]
  47. culs_de_sac = []
  48. boucles = []
  49. boucles_taillees = []
  50.  
  51. def tailler(boucle):
  52.    indexs = []
  53.    for i, x in enumerate(boucle):
  54.        if boucle.count(x) > 1:
  55.            indexs.append(i)
  56.            if len(indexs) == 2:
  57.                return boucle[indexs[0]:indexs[1]]
  58.  
  59. def chercher(liste, element):
  60.    i = -2
  61.    for k, y in enumerate(liste):
  62.        if y == element:
  63.            return k
  64.    return i
  65.  
  66. def PARKOUR(voix):
  67.    populi = []
  68.    plus = -1
  69.    for i, x in enumerate(matrix[voix[-1]]):
  70.        if x == 1 and chercher(voix, i) < len(voix)-2:
  71.            v = voix.copy()
  72.            v.append(i)
  73.            populi.append(v)
  74.            plus += 1
  75.    return populi, plus
  76.  
  77. while len(voies_du_jedi) != 0:
  78.    vox, avenir = PARKOUR(voies_du_jedi[0])
  79.    #print(voies_du_jedi)
  80.    boucle = False
  81.    if avenir == -1:
  82.        culs_de_sac.append(voies_du_jedi.pop(0))
  83.        boucle = True
  84.    else:
  85.        for x in voies_du_jedi[0]:
  86.            if voies_du_jedi[0].count(x) > 1:
  87.                boucle = True
  88.        if boucle == True:
  89.            boucles.append(voies_du_jedi.pop(0))
  90.    if not boucle:
  91.        voies_du_jedi.pop(0)
  92.        voies_du_jedi.extend(vox)
  93. #print(culs_de_sac, boucles)
  94. for boucle in boucles:
  95.    b = tailler(boucle)
  96.    b.sort()
  97.    if not b in boucles_taillees:
  98.        boucles_taillees.append(b)
  99. print("Nous avons détecté "+str(len(boucles_taillees))+" boucles dans ce graphe:")
  100. for b in boucles_taillees:
  101.    print("-"+str(b))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!