Compte tenu d'un ensemble de villes et d'une distance entre chaque paire de villes, le problème est de trouver la tournée la plus courte possible qui visite chaque ville une fois exactement et revient au point de départ.
Compte tenu d'un ensemble de villes et d'une distance entre chaque paire de villes, le problème est de trouver la tournée la plus courte possible qui visite chaque ville une fois exactement et revient au point de départ.
Problème : étant donné 2 processus i et j, vous devez écrire un programme capable de garantir une exclusion mutuelle entre les deux sans aucun support matériel supplémentaire.
Génération de tableaux triés aléatoirement Nous stockons les éléments du tableau aléatoire dans un tableau, puis nous le trions et l'imprimons.
Étant donné un nombre « n » et un n nombres, triez les nombres à l’aide du tri par fusion simultanée. (Indice : essayez d'utiliser les appels système shmget, shmat).Partie 1 : L'algorithme (COMMENT ?) Créez de manière récursive deux processus enfants, un pour la moitié gauche, un pour la moitié droite. Si le nombre d'éléments dans le tableau d'un processus est inférieur à 5, effectuez un tri par insertion. Le parent des deux enfants fusionne ensuite le résultat et revient au parent et ainsi de suite. Mais comment le rendre concurrent ?Partie 2 : La logique (POURQUOI ?) La partie importante de la solution à ce problème n'est pas algorithmique, mais consiste à expliquer les concepts de système d'exploitation et de noyau. Pour réaliser un tri simultané, nous avons besoin d’un moyen de faire fonctionner deux processus sur le même tableau en même temps. Pour faciliter les choses, Linux fournit de nombreux appels système via de simples points de terminaison API. Deux d'entre eux sont shmget() (pour l'allocation de mémoire partagée) et shmat() (pour les opérations de mémoire partagée). Nous créons un espace mémoire partagé entre le processus enfant que nous bifurquons. Chaque segment est divisé en enfants gauche et droit qui sont triés, la partie intéressante étant qu'ils travaillent simultanément ! shmget() demande au noyau d'attribuer une page partagée pour les deux processus. Pourquoi le fork() traditionnel ne fonctionne pas ? La réponse réside dans ce que fait réellement fork(). D'après la documentation, « fork() crée un nouveau processus en dupliquant le processus appelant ». Le processus enfant et le processus parent s'exécutent dans des espaces mémoire distincts. Au moment de fork(), les deux espaces mémoire ont le même contenu. Les écritures en mémoire, les modifications du descripteur de fichier (fd), etc., effectuées par l'un des processus n'affectent pas l'autre. Nous avons donc besoin d'un segment de mémoire partagée.
Étant donné un tableau d'entiers positifs, remplacez chaque élément du tableau de telle sorte que la différence entre les éléments adjacents du tableau soit inférieure ou égale à une cible donnée. Nous devons minimiser le coût d’ajustement, c’est-à-dire la somme des différences entre les nouvelles et les anciennes valeurs. Nous devons essentiellement minimiser ?|A[i] - Anew[i]| où 0 ? je ? n-1, n est la taille de A[] et Anew[] est le tableau avec une différence adjacente inférieure ou égale à la cible. Supposons que tous les éléments du tableau soient inférieurs à la constante M = 100.
Étant donné un entier n représentant le nombre de chiffres. La tâche consiste à imprimer tous les nombres à n chiffres de telle sorte que la différence absolue entre la somme des chiffres aux positions paires et impaires soit exactement de 1. Remarque : le nombre ne doit pas commencer par 0 (les zéros non significatifs ne sont pas autorisés).
Étant donné un arbre d'expression simple, composé d'opérateurs binaires de base, c'est-à-dire + , - ,* et / et quelques entiers, évaluez l'arbre d'expression.
Étant donné le nombre de chiffres n, imprimez tous les nombres à n chiffres dont la somme des chiffres totalise la somme donnée. La solution ne doit pas considérer les 0 comme chiffres. Exemples :
Étant donné deux tableaux d'entiers, ajoutez leurs éléments dans un troisième tableau en satisfaisant les contraintes suivantes -
Étant donné un tableau d'entiers, déterminez s'il est possible de supprimer exactement un entier du tableau qui divise le tableau en deux sous-tableaux avec la même somme.
Étant donné un tableau contenant à la fois des entiers positifs et négatifs, recherchez le produit du sous-tableau de produits maximum. La complexité temporelle attendue est O(n) et seul l’espace supplémentaire O(1) peut être utilisé.
Étant donné un tableau arr[] et un entier k, recherchez le tableau après avoir inversé chaque sous-tableau de k éléments consécutifs en place. Si le dernier sous-tableau contient moins de k éléments, inversez-le tel quel. Modifiez le tableau en place, ne retournez rien.
Étant donné une liste d'entiers, réorganisez la liste de telle sorte qu'elle consiste en une alternance d'éléments minimum et maximum en utilisant uniquement des opérations de liste. Le premier élément de la liste doit être le minimum et le deuxième élément doit être le maximum de tous les éléments présents dans la liste. De même, le troisième élément sera le prochain élément minimum et le quatrième élément sera le prochain élément maximum et ainsi de suite. L'utilisation d'espace supplémentaire n'est pas autorisée. Exemples :
Étant donné une plage [n, m], trouvez le nombre d'éléments qui ont un nombre impair de facteurs dans la plage donnée (n et m inclus). Exemples :
Étant donné un tableau binaire de taille n où n > 3. Une valeur vraie (ou 1) dans le tableau signifie actif et faux (ou 0) signifie inactif. Étant donné un nombre k, la tâche consiste à trouver le nombre de cellules actives et inactives après k jours. Après chaque jour, le statut de la ième cellule devient actif si les cellules gauche et droite ne sont pas identiques et inactif si les cellules gauche et droite sont identiques (toutes deux 0 ou toutes deux 1).
Étant donné un tableau de n entiers uniques où chaque élément du tableau est compris dans la plage [1, n]. Le tableau contient tous les éléments distincts et la taille du tableau est (n-2). Par conséquent, deux nombres de la plage manquent dans ce tableau. Trouvez les deux nombres manquants.
Étant donné un tableau trié de n valeurs uniformément distribuées arr[], écrivez une fonction pour rechercher un élément particulier x dans le tableau. La recherche linéaire trouve l'élément en un temps O(n), la recherche sautée prend un temps O(n) et la recherche binaire prend un temps O(log n). La recherche par interpolation est une amélioration par rapport à la recherche binaire pour les instances, où les valeurs d'un tableau trié sont uniformément distribuées. L'interpolation construit de nouveaux points de données dans la plage d'un ensemble discret de points de données connus. La recherche binaire va toujours à l'élément du milieu pour vérifier. D'un autre côté, la recherche par interpolation peut aller vers différents emplacements en fonction de la valeur de la clé recherchée. Par exemple, si la valeur de la clé est plus proche du dernier élément, la recherche par interpolation commencera probablement vers la fin. Pour trouver la position à rechercher, elle utilise la formule suivante.
Étant donné un tableau de n éléments distincts. Trouvez le produit maximum du minimum de deux nombres dans le tableau et la différence absolue de leurs positions, c'est-à-dire trouvez la valeur maximale de abs(i - j) * min(arr[i], arr[j]) où i et j varient de 0 à n-1.
