Si un ordinateur ne peut contenir qu'un million de chiffres, comment découvrir le nombre médian de 100 millions de numéros?
4 Réponses :
Espérons que le vrai problème était "Comment puis-je faire un type externe"? (Si c'est des devoirs ... Je veux aider de la bonne manière.: -)
C'est ce que je pensais. :) Mais je ne suis pas sûr que ce soit la bonne réponse, alors j'ai demandé ici.
Il doit y avoir un moyen de le faire avec la contrainte littérale que l'appareil ne peut stocker que 1 million de chiffres. L'utilisation du genre externe semble être une triche. Maintenant, je vais être debout toute la nuit en pensant à cela.
Heh, je me demandais que moi-même. C'est une très bonne question.
Réduisez le problème à un plus difficile: Trier les 100 millions de chiffres Utilisation de Fusionner le tri Ensuite, prenez le 50 millionième élément.
Mais l'ordinateur peut contenir 1 million de chiffres, comment puis-je trouver le 50 millionième?
Sur la bande (Oh, à droite, ce n'est plus les années 80. Je voulais dire "sur le disque"), à la 50 millionième position. Vous avez des stockages pour vos éléments de 100 m, non? Parce que si vous ne le faites pas (éléments lus à partir d'un courant), l'exercice peut être prouvé impossible par un argument de comptage.
Il n'est pas correct pour 100 millions de chiffres de prendre 50 millions d'éléments, car 100 millions sont encore un nombre, il faut donc prendre la moyenne de 50 millions de euros et 50 millions d'éléments + 1.
Utiliser 101 ordinateurs et une sorte de fusionne comme une base de données.
MDR. Cette réponse devrait figurer comme la meilleure blague de programmeur!
Je vais le prendre comme une de mes réponses. :)
Trouvez les chiffres du Miltrege, puis signalez la médiane d'entre eux. (Hmmm, maintenant comment trouver ces chiffres de million de milieu ...)
Au mieux, cela devrait probablement être un wiki communautaire.
Il s'agit d'une question de programmation valide, comment calculer la médiane de manière efficace de la mémoire. Cela vient juste d'un casse-tête.
Utilisez l'approche «médiane des médianes».