1
votes

Trouvez l'élément dans une liste pratiquement infinie

J'essaye de résoudre ce problème:

Une liste est initialisée à ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"] , puis subit une série d'opérations. Dans chaque opération, le premier élément de la liste est déplacé à la fin de la liste et dupliqué. Par exemple, dans la première opération, la liste devient ["Leonard", "Penny", "Rajesh", "Howard", "Sheldon", "Sheldon"] (avec "Sheldon " étant déplacé et dupliqué); dans la deuxième opération, il devient ["Penny", "Rajesh", "Howard", "Sheldon", "Sheldon", "Leonard", "Leonard"] (avec "Leonard" étant déplacé et dupliqué); etc. Etant donné un entier positif n , trouvez la chaîne qui est déplacée et dupliquée dans l'opération n ème. [paraphrasé de https://codeforces.com/problemset/problem/82/A ]

J'ai écrit une solution qui fonctionne, mais c'est trop lent quand n est énorme:

l = ['Sheldon','Leonard','Penny','Rajesh','Howard']
n = int(input()) # taking input from user to print the name of the person
                 # standing at that position

 for i in range(n):
    t = l.pop(0)
    l.append(t)
    l.append(t)

    #debug
    # print(l)

print(t)

Comment puis-je faire c'est plus rapide?

python algorithm math implementation

5 commentaires

Vous pouvez trouver la réponse sans générer réellement la liste. Doubler chaque nom une fois doublera la longueur de la liste. Vous pouvez déterminer combien de fois vous auriez besoin de doubler la liste, puis en déduire quelle serait la structure de la liste à ce stade.

@khelwood pourriez-vous s'il vous plaît élaborer là-dessus.

@Aman Cherchez-vous quelqu'un pour résoudre ce problème à votre place? khelwood vous a donné un énorme indice qui devrait vous aider si vous voulez le résoudre vous-même.

@ Code-Apprentice Je suis l'indice de khelwoods depuis et j'essaie de résoudre .. Je ne suis qu'un débutant c'est pourquoi il faut du temps pour moi

@Aman Même en tant que non-débutant, résoudre des problèmes prend du temps

3 Réponses :

-1
votes

Vous ne pourrez pas éviter de calculer la liste, mais peut-être pouvez-vous le rendre un peu plus facile:

À chaque cycle (quand sheldon est à nouveau le premier), la longueur de la liste a doublé, donc cela ressemble à ceci:

Après 1 cycle: SSLLPPRRHH

Après 2 cycles: SSSSLLLLPPPPRRRRHHHH

...

alors que le nombre de cola qu'ils ont bu est de 5 * ((2 ** n) -1) où le n est le nombre de cycles.

Vous pouvez donc calculer l'état de la liste au cycle terminé le plus proche. Par exemple. Numéro de cola 50:

5 * ((2 ** 3)) = 40 signifie qu'après 40 cokes, Sheldon est le suivant sur la ligne.

Ensuite, vous pouvez utiliser l'algorithme décrit dans la tâche et obtenir le dernier de la ligne.

J'espère que cela vous aidera.

3 commentaires

Je vous recommande de lire, comment répondre aux questions. Cela aiderait certainement

Notez que votre suggestion évite de calculer la liste entière. Vous utilisez des mathématiques pour avancer autant de cycles que possible.

Je vous recommande d'apprécier une solution beaucoup plus efficace que la vôtre. Je sais que ce n'est pas vraiment écrit, mais pour être honnête, la lecture de votre question m'a presque donné un coup, alors ne parlez pas d'écriture

2
votes

Voici une solution qui s'exécute dans O (log (input / len (l))) sans faire de calcul réel (pas d'opérations de liste):

l = ['Sheldon','Leonard','Penny','Rajesh','Howard']
n = int(input()) # taking input from user to print the name of the person
                 # standing at that position

i = 0
while n>(len(l)*2**i):
    n = n - len(l)* (2**i)
    i = i + 1

index = int((n-1)/(2**i ))

print(l[index])

Explication: chaque fois que vous repoussez la liste entière, la longueur de la liste augmentera exactement de len (l) x 2 ^ i . Mais vous devez d'abord savoir combien de fois cela se produit. C'est ce que fait le while (c'est ce que fait n = n - len (l) * (2 ** i) ). Le while s'arrête lorsqu'il s'est rendu compte que i fois l'ajout de la double liste se produira. Enfin, après avoir compris i , vous devez calculer l'index. Mais dans la i -th liste ajoutée, chaque élément est copié 2 ^ i fois, vous devez donc diviser le nombre par 2 ** i code >. Un détail mineur est que pour l'index, vous devez soustraire de 1 car les listes en Python sont indexées à 0 tandis que votre entrée est indexée à 1.

0 commentaires

0
votes

Comme l'a dit @khelwood, vous pouvez déduire combien de fois vous devez doubler la liste.

Pour comprendre cela, notez que si vous commencez avec une liste de 5 personnes et effectuez 5 étapes de votre itération, vous allez même ordre qu'avant, avec tout le monde deux fois dedans.

Je ne suis pas sûr à 100% de ce que vous entendez par la nième position car elle change tout le temps, mais si vous parlez de la personne en tête après n itérations, résolvez le plus grand entier i qui remplit

5*2^i<n

pour obtenir le nombre de fois où votre liste a doublé. Ensuite, regardez la liste restante (chaque nom est mentionné i fois) pour obtenir le nom à la position n-5 * 2 ^ i.

0 commentaires