tries = 10 # nombre d'essais / de rpetitions n = 128 # nombre de personnes dans le village #####################ci-dessous: tache 3.########################## def computeHonestPerson_SLOW_ITERATIVE(A, isHonest): n = len(A) if n == 1: return A[0] for j in range(0, len(A)): count = 0 for i in range(0, len(A)): if i != j and isHonest(A[i], A[j]): count += 1 if 2*count >= len(A)-1: #the -1 is needed when n is odd return j #####################ci-dessus: tache 3.########################### #####################ci-dessous: tache 4.########################## def computeHonestPerson_SLOW_RECURSIVE(A, isHonest): n = len(A) if n == 1: return A[0] count = 0 for i in range(0, n-1): if isHonest(A[i], A[n-1]): count += 1 if 2*count >= len(A)-1: #the -1 is needed when n is odd return A[n-1] else: return computeHonestPerson_SLOW_RECURSIVE(A[0:n-1], isHonest) #####################ci-dessus: tache 4.########################### ########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_SLOW_ITERATIVE([i for i in range(0, n)], isHonest) print(f"{'SLOW_ITERATIVE':<20} {sol:<26} {str(giveAnswer(sol)):<26} {numQuestions():<20}") reset() sol = computeHonestPerson_SLOW_RECURSIVE([i for i in range(0, n)], isHonest) print(f"{'SLOW_RECURSIVE':<20} {sol:<26} {str(giveAnswer(sol)):<26} {numQuestions():<20}") print() print("=" * 93)