tries = 100 # nombre d'essais / de repetitions n = 128 # nombre de personnes dans le village ############################ci-dessous: tache 3 ################################# def computeHonestPerson_MEDIUM_RECURSIVE(A, isHonest): '''vous pouvez utiliser la fonction isHonest(A[i],A[j]) pour avoir l'avis sur person A[j] donne par person A[i].''' n = len(A) #ECRIVEZ VOTRE CODE ICI return random.choice(A) #<--- il faut changer, pour le moment c'est aleatoire. ############################ci-dessus: tache 3 ################################## ############################ci-dessous: tache 4 ################################# def computeHonestPerson_FAST_CHAIN(A, isHonest): '''vous pouvez utiliser la fonction isHonest(A[i],A[j]) pour avoir l'avis sur person A[j] donne par person A[i].''' n = len(A) #ECRIVEZ VOTRE CODE ICI return random.choice(A) #<--- il faut changer, pour le moment c'est aleatoire. ############################ci-dessus: tache 4 ################################## ############################ci-dessous: tache 5 ################################# def computeHonestPerson_FAST_RECURSIVE(A, isHonest): '''vous pouvez utiliser la fonction isHonest(A[i],A[j]) pour avoir l'avis sur person A[j] donne par person A[i].''' B = list(A) #ECRIVEZ VOTRE CODE ICI return random.choice(A) #<--- il faut changer, pour le moment c'est aleatoire. ############################ci-dessus: tache 5 ################################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## ########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.################## import random def generateProblem(n): arrangement = random.choice( ["random","honest_first","honest_last","honest_middle","alternating","two_blocks","checkerboard"] ) S = [0]*n honest_count = n//2 + 1 if arrangement == "random": for i in range(honest_count): S[i] = 1 random.shuffle(S) elif arrangement == "honest_first": for i in range(honest_count): S[i] = 1 elif arrangement == "honest_last": for i in range(n - honest_count, n): S[i] = 1 elif arrangement == "honest_middle": start = (n - honest_count) // 2 for i in range(start, start + honest_count): S[i] = 1 elif arrangement == "alternating": for i in range(n): if i % 2 == 0 and honest_count > 0: S[i] = 1 honest_count -= 1 for i in range(n): if honest_count > 0 and S[i] == 0: S[i] = 1 honest_count -= 1 elif arrangement == "two_blocks": block_size = honest_count // 2 for i in range(block_size): S[i] = 1 for i in range(n - (honest_count - block_size), n): S[i] = 1 elif arrangement == "checkerboard": pattern = [1, 0, 0] for i in range(n): if honest_count > 0 and pattern[i % 3] == 1: S[i] = 1 honest_count -= 1 for i in range(n): if honest_count > 0 and S[i] == 0: S[i] = 1 honest_count -= 1 if (sum(S) != n//2 + 1): print(f"ERROR in generateProblem with {arrangement}.") count = 0 def isHonest(i, j): nonlocal S, count count += 1 if S[i] == 1: return bool(S[j]) else: return random.choice([True, False]) def giveAnswer(i): nonlocal S return bool(S[i]) def numQuestions(): nonlocal count return count def reset(): nonlocal count count = 0 return isHonest, giveAnswer, numQuestions, reset print("=" * 93) print(f"{'Algorithm':<20} {'Personne Computed':<26} {'Really Honest?':<26} {'# Questions asked':<20}") print("-" * 93) for _ in range(tries): isHonest, giveAnswer, numQuestions, reset = generateProblem(n) reset() sol = computeHonestPerson_MEDIUM_RECURSIVE([i for i in range(0, n)], isHonest) print(f"{'MEDIUM_RECURSIVE':<20} {sol:<26} {str(giveAnswer(sol)):<26} {numQuestions():<20}") reset() sol = computeHonestPerson_FAST_CHAIN([i for i in range(0, n)], isHonest) print(f"{'FAST_CHAIN':<20} {sol:<26} {str(giveAnswer(sol)):<26} {numQuestions():<20}") reset() sol = computeHonestPerson_FAST_RECURSIVE([i for i in range(0, n)], isHonest) print(f"{'FAST_RECURSIVE':<20} {sol:<26} {str(giveAnswer(sol)):<26} {numQuestions():<20}") print() print("=" * 93)