recherche séquentielle devoirs question

Considérons un fichier disque contenant 100 enregistrements a. Combien de comparaisons seraient nécessaires en moyenne pour trouver un enregistrement en utilisant la recherche séquentielle, si l'enregistrement est connu pour être dans le fichier?recherche séquentielle devoirs question

Je compris que c'est 100/2 = 50.

b. Si le dossier a une probabilité de 68% d'être dans le fichier, combien de comparaisons sont nécessaires en moyenne?

C'est la partie avec laquelle j'ai des problèmes. Au début, je pensais que c'était 68% * 50, mais j'ai alors réalisé que c'était faux après y avoir réfléchi. Alors j'ai pensé que c'était (100% - 68%) * 50, mais je sens toujours que c'est faux. Des indices?

Source

2010-03-09 neuromancer

Répartir dans deux cas: lorsque l'enregistrement est dans le fichier, et quand il est pas. Comptez les séparément. –

Je le décomposerais ainsi, en une moyenne pondérée.

A 68% de chance d'être dans le fichier; dans ces circonstances, une moyenne de 50 comparaisons sera nécessaire à partir de votre résultat dans la partie I.

32% de chances que l'enregistrement ne soit pas dans le fichier; Dans ces circonstances, vous devrez examiner chaque dossier, par exemple 100 comparaisons.

0,68 * 50 + 0,32 * 100 = 66 comparaisons en moyenne.

Mais il a été un moment que je pris un cours sur la probabilité ...

Source

2010-03-09 03:37:06 Peter

Ce ne serait pas 0.32 * 99, puisque pour 100 enregistrements 99 comparaisons sont faites, pas 100. – neuromancer

Comment faire seulement 99 comparaisons? S'il y a 100 enregistrements, et que vous ne savez pas avec certitude que celui que vous recherchez existe, n'auriez-vous pas besoin de regarder chaque enregistrement en utilisant une recherche séquentielle? – Peter

Je suppose que j'ai été troublé par le mot «comparaison», en pensant que vous étiez en train de comparer les nombres les uns aux autres. – neuromancer

recherche séquentielle devoirs question

Répondre

Questions connexes