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) if n == 1: return A[0] p1 = computeHonestPerson_MEDIUM_RECURSIVE(A[:n//2], isHonest) p2 = computeHonestPerson_MEDIUM_RECURSIVE(A[n//2:], isHonest) count1 = 0 for i in range(0, len(A)): if A[i] != p1 and isHonest(A[i], p1): count1 += 1 if 2*count1 >= n-1: return p1 else: return p2 ############################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) B = [] for i in range(0, n): if len(B) == 0: B.append(A[i]) else: if isHonest(A[i], B[-1]): B.append(A[i]) else: B.pop() return B[ 0 ] ############################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].''' n = len(A) if n == 1: return A[0] C = [] for i in range(0, n//2): if isHonest(A[2*i], A[2*i+1]): C.append(A[2*i+1]) if n%2 == 0: return computeHonestPerson_FAST_RECURSIVE(C, isHonest) elif n%2 == 1: m = 2*len(C) #number of persons left after removing pairs which said D if m%4 == 0: return computeHonestPerson_FAST_RECURSIVE( C + [A[-1]], isHonest ) else: return computeHonestPerson_FAST_RECURSIVE( C, isHonest ) ############################ci-dessus: tache 5 ################################## ############################ci-dessous: version iterative de tache 5 ################################# def computeHonestPerson_FAST_ITERATIVE(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) while len(B) > 1: n = len(B) C = [] for i in range(0, n//2): if isHonest(B[2*i], B[2*i+1]): C.append(B[2*i+1]) if n%2 == 0: B = C elif n%2 == 1: m = 2*len(C) #number of persons left after removing pairs which said D if m%4 == 0: C.append( B[-1] ) B = C else: B = C return B[0] #############################ci-dessus: version iterative de 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.################## 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}") if giveAnswer(sol) == False: print("ERROR! wrong answer returned by MEDIUM_RECURSIVE.") quit() 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}") if giveAnswer(sol) == False: print("ERROR! wrong answer returned by FAST_RECURSIVE.") quit() reset() sol = computeHonestPerson_FAST_ITERATIVE([i for i in range(0, n)], isHonest) print(f"{'FAST_ITERATIVE':<20} {sol:<26} {str(giveAnswer(sol)):<26} {numQuestions():<20}") if giveAnswer(sol) == False: print("ERROR! wrong answer returned by FAST_ITERATIVE.") quit() 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}") if giveAnswer(sol) == False: print("ERROR! wrong answer returned by FAST_CHAIN.") quit() print() print("=" * 93)