Articles of algorithme

Combinaisons de codes de hachage simples et rapides

Les gens peuvent-ils recommander des moyens simples et rapides pour combiner les codes de hachage de deux objects. Je ne suis pas trop préoccupé par les collisions car j’ai une table de hachage qui va gérer cela efficacement Je veux juste quelque chose qui génère un code rapidement possible. En lisant autour de SO et […]

Algorithme pour trouver la plus petite puissance de deux supérieure ou égale à une valeur donnée

J’ai besoin de trouver la plus petite puissance de deux supérieure ou égale à une valeur donnée. Jusqu’à présent, j’ai ceci: int value = 3221; // 3221 is just an example, could be any number int result = 1; while (result < value) result <<= 1; Cela fonctionne bien, mais se sent un peu naïf. […]

Pile avec find-min / find-max plus efficace que O (n)?

Je suis intéressé par la création d’une structure de données Java similaire à une stack qui prend en charge les opérations suivantes aussi efficacement que possible: Push, qui ajoute un nouvel élément au sumt de la stack, Pop, qui supprime l’élément supérieur de la stack, Find-Max, qui renvoie (mais ne supprime pas) le plus grand […]

Trouver 2 nombres dans un tableau non sortingé égal à une sum donnée

Nous devons trouver une paire de nombres dans un tableau dont la sum est égale à une valeur donnée. A = {6,4,5,7,9,1,2} Sum = 10 Alors les paires sont – {6,4}, {9,1} J’ai deux solutions pour cela. une solution O (nlogn) – sort + check sum avec 2 iterators (début et fin). une solution O […]

Comment compter les entiers entre les grands A et B avec une certaine propriété?

Lors de la programmation de concours, le modèle suivant se produit dans de nombreuses tâches: Etant donné les nombres A et B qui sont énormes (peut-être 20 chiffres décimaux ou plus), déterminez le nombre d’entiers X avec A ≤ X ≤ B qui ont une certaine propriété P SPOJ a beaucoup de tâches comme celles-ci […]

Vous cherchez des moyens pour un robot de se localiser dans la maison

Je pirate un robot aspirateur pour le contrôler avec un microcontrôleur (Arduino). Je veux le rendre plus efficace lors du nettoyage d’une pièce . Pour l’instant, il suffit d’aller tout droit et de tourner quand il frappe quelque chose. Mais j’ai du mal à trouver le meilleur algorithme ou la meilleure méthode à utiliser pour […]

Pourquoi dois-je toujours spécifier explicitement la plage dans les fonctions de l’algorithme de STL, même si je veux travailler sur l’ensemble du conteneur?

Lors de l’utilisation des fonctions STL comme sort() ou min_element() je dois toujours spécifier la plage de façon explicite et initiale: void range_example() { std::vector list = {7, 3, 9, 1, 5, 2}; auto found_element = std::min_element(list.begin(), list.end()); std::cout << *found_element << std::endl; } Cela a du sens si je n’ai l’intention de travailler que […]

Comment trouver le point d’intersection entre une ligne et un rectangle?

J’ai une ligne qui va des points A à B; J’ai (x, y) des deux points. J’ai aussi un rectangle centré sur B et la largeur et la hauteur du rectangle. J’ai besoin de trouver le point dans la ligne qui coupe le rectangle. Y a-t-il une formule qui me donne le (x, y) de […]

Points aléatoires à l’intérieur d’un parallélogramme

J’ai un polygone convexe à 4 côtés défini par 4 points en 2D et je veux pouvoir générer des points aléatoires à l’intérieur. Si cela simplifie vraiment le problème, je peux limiter le polygone à un parallélogramme, mais une réponse plus générale est préférable. Générer des points aléatoires jusqu’à ce que l’un soit à l’intérieur […]

Trouver le numéro de fibonacci nth pour très grand ‘n’

Je me demandais comment on pouvait trouver le nième terme de la séquence de fibonacci pour une valeur très grande de n disons, 1000000. En utilisant l’équation de récurrence de l’école primaire fib(n)=fib(n-1)+fib(n-2) , il faut 2-3 min pour trouver le 50ème terme! Après avoir googlé, j’ai appris la formule de Binet, mais elle n’est […]