[Archives] Mathématiques pures, physique, chimie, etc. : problèmes d'entraînement cérébral sans rapport avec le commerce. - page 583

[Alexey Subbotin]

MikeM:

A propos de l'horloge :

4 minutes après le départ flip 4 minutes après le départ

après avoir été retourné en 4 minutes 4 minutes, en 7 minutes 3 minutes.

après 3 minutes supplémentaires

dans 4 minutes 1 min, dans 7 minutes 0

retourner 7 minutes

en 4 minutes 1 min, en 7 minutes 7

après une autre minute.

4 minutes 0, 7 minutes 6

retournez les 7 minutes.

en 4 minutes 0, en 7 minutes 1

dans une autre minute - le bon moment!

correctement)

[MikeM]

La première passe compte les uns, les deux et les trois, et la deuxième passe remplit le tableau "trié" avec le bon nombre de chiffres.

[TheXpert]

Première passe de comptage, deuxième passe d'écriture. O(n) bien sûr.

[sand]

GaryKa:

Voici une énigme.

Bien sûr, c'est ennuyeux, mais aux entretiens comme une apothéose de la connaissance sur les tableaux de tri)).

Donc, un problème de tri

Il existe un tableau de N cellules, dans lequel les unités, les deux et les trois sont placés dans un ordre aléatoire.

Construisez le meilleur algorithme de tri.

C'est-à-dire seulement 3 choix de données ?

Première passe : compter combien de uns, combien de deux et combien de trois.

Deuxième passage : on remplit.

Total 2 passes.

[GaryKa]

MikeM:
Premier passage - compter les uns, les deux et les trois, deuxième passage - remplir le tableau "trié" avec la bonne quantité de bons chiffres.

Oui ;) les pauvres candidats encombrés par les questions précédentes sur le tri à ne pas faire pour le plaisir du public, et la bulle, et les inserts, et toutes les combinaisons avec les exceptions.

[MikeM]

GaryKa:
Oui ;) les pauvres candidats, trop enchaînés par les questions de tri antérieures, font ce qu'ils font pour divertir le public, avec des bulles, des échantillons et toutes sortes de combinaisons avec des exceptions.

Ce dont vous avez besoin n'est pas compliqué. Tout ce qui est compliqué est inutile !

[MikeM]

Une question simple (pour les programmeurs) :

A+B=...

[TheXpert]

valeur attendue :)

[MikeM]

Il ne s'agit pas d'un opérateur d'une quelconque langue. C'est le côté gauche de l'égalité. Que faut-il écrire sur le côté droit ?

[Alexey Subbotin]

sand:

C'est-à-dire seulement 3 variantes de données ?

Première passe : compter combien de uns, combien de deux et combien de trois.

Deuxième passage : remplir.

Total 2 passes.

En un seul passage :

Créer une copie vide d'un tableau de la même taille, l'initialiser avec deux.

Nous partons du début du tableau. Si nous rencontrons 1, nous le copions depuis le début ; si nous rencontrons 3, nous le copions depuis la fin.