algorithme pour trier les éléments de trois tableaux

Question

Voici le stumper:

Commencez avec trois tableaux A, B et C avec un total de 2n+1 entrées. Ecrire un algorithme pour trier toutes les entrées de tous les tableaux en utilisant uniquement les deux méthodes suivantes:

1. X = sort(X) remplace le tableau X avec la version triée.

2. (X , Y) = doubleUp(X , Y) ne fait rien si X a plus d'éléments que Y, sinon il supprime les premières entrées de length(X)Y et les ajoute à la fin de X.

Voici ce que j'ai essayé jusqu'à présent. Si deux des tableaux sont vides, utilisez simplement sort sur le tableau non vide. Si l'un des tableaux est vide, alors je pense que je peux utiliser doubleUp pour obtenir un tableau pour avoir juste une chose et l'autre tableau pour avoir tout le reste, et si ce tableau singleton a le plus petit (ou le plus grand) élément , alors ça marche. Donc je peux utiliser sort après avoir utilisé doubleUp à chaque fois pour m'assurer que cela arrive. J'ai codé cela dans Maple et cela a fonctionné pour tous les cas que j'ai vérifiés.

Je n'ai aucune idée de comment le faire avec 3 tableaux. Quelqu'un a des idées?

Answer 1

Cela ressemble à un non-sens. Le nombre total d'entrées est impair. La seule façon d'augmenter la longueur d'un tableau est d'en faire le plus petit premier argument de doubleUp, auquel cas il se retrouve avec un nombre pair d'éléments. Donc, à moins que tous les éléments soient dans un tableau pour commencer, il n'y a aucun moyen de faire en sorte qu'un tableau contienne tous les éléments, triés ou non. Ainsi, le résultat final souhaité n'est pas un seul tableau contenant tous les éléments dans l'ordre. Ou si c'est le cas, alors la réponse à la question est "cela ne peut pas être fait".