J'ai un petit problème avec la tête de cette tâche de travail. La tâche dit:
"Écrivez une fonction appelée MOVESMALLEST B> qui déplace tous les éléments entiers minimaux au début de la matrice. Tous les articles restants doivent rester à leur place. (Le tableau et sa taille sont des paramètres) p>
Exemple: i> Le tableau: 2, 3, 5, 1, 2, 3, 6, 4, 2, 1, 1 changements dans 1, 1, 1 , 2, 3, 5, 2, 3, 6, 4, 2 P> void MoveSmallest(int A[],int n)
{
int Min;
for(int i=0;i<n;i++)
{
if(i==0)
{
Min=A[i];
}
else if(A[i]<=Min)
{
Min=A[i];
}
}
3 Réponses :
À partir de la fin de la matrice, gardez une trace du nombre d'éléments minimaux que vous avez rencontrés. Ensuite, chaque fois que vous rencontrez un élément non minimum, déplacez-le à droite le nombre d'éléments minimes que vous avez rencontrés jusqu'à présent:
void MoveSmallest(int A[], int n)
{
int min;
//Find min logic
//shift non-min elements and count min elements
int cnt = 0;
for (int i = n-1; i >=0; --i)
{
if (A[i] == min)
cnt++;
else
A[i+cnt] = A[i];
}
//Add min elements
for (int i = 0; i < cnt; ++i)
A[i] = min;
}
Une fois que vous avez trouvé la valeur minimale, tout ce qu'il reste à faire, c'est bouger les choses autour afin d'avoir les valeurs minimales au début de la matrice.
Vous pouvez le faire en permutant les valeurs jusqu'à ce que vous soyez arrivé. à la "gauche" de la matrice (c.-à-d. Index 0). Vous pouvez également utiliser std :: échange pour faire la permutation, à la place de la variable temporaire TMP .
Merci. Je pense que c'est la solution dans mon cas car je ne peux utiliser que les bases de C ++.
Cette solution peut fonctionner, mais est inefficace, car elle est quadratique en runrime. 100 éléments signifie 10000 itérations de boucle. Il existe des moyens plus efficaces d'établir des éléments de partition, tels que l'utilisation de la division et de la conquérir, semblable à une sorte de fusion.
Oui, je sais ces considérations. Mais étant donné qu'il s'agit d'un exercice de devoirs, j'ai deviné qu'une solution simple à écrire était la mieux adaptée à cette question.
Ouais. Tout comme @ n0m1s dit. Je ne peux utiliser que les bases de la langue. Il n'est pas nécessaire d'être optimal ou efficace.
@ Them1Ke25 Le tri de la fusion peut être mis en œuvre à l'aide de "bases de la langue". La question est que vous n'avez pas pensé à une meilleure façon de le faire en utilisant des bases de la langue.
@ N0M1S - Oui, mais le but du débutant devrait, le plus tôt possible, essayez de penser à de meilleurs moyens de faire des choses. Je ne serais pas surpris si cette solution reçoit un B ou B - note et non A par l'enseignant (où l'enseignant cherche Pour de meilleurs moyens, remarquez à quel point la solution est inefficace).
@Paulmckenzie Je comprends votre point. Mais je crois que la méthode entièrement comprise (aussi naïfe et inefficace qu'elle est) est préférable d'apprendre une langue qu'un code collé copieux mal compris.
Étant donné que vos messages mentionnent "Basic C ++" mais non mentionner ce qui est "Basic", voici une autre solution. Ceci est sous l'hypothèse que la création de tableaux pour des fins "de travail" est considérée comme "Basic C ++".
void MoveSmallest(int A[], int n)
{
// get the minimum value
int Min = A[0];
for (int i = 1; i < n; ++i)
{
if (A[i] < Min)
Min = A[i];
}
// get the count of the number of minimum values
int minCount = 0;
for (int i = 0; i < n; ++i)
{
if (A[i] == Min)
++minCount;
}
if (minCount > 0)
{
// create a work array and fill in the first
// minCount values with the minimum value
int *B = new int[n];
for (int i = 0; i < minCount; ++i)
B[i] = Min;
// now fill in the rest of the work array with the values
// in the A[] array that are not equal to Min
int current_pos = minCount;
for (int i = 0; i < n; ++i)
{
if (A[i] != Min)
B[current_pos++] = A[i];
}
// Now copy work array back to A array
for (int i = 0; i < n; ++i)
A[i] = B[i];
// get rid of work array
delete[] B;
}
}
Vous pouvez utiliser STD :: Swap () à ... hein .. Échangez deux éléments de votre tableau. Tout ce dont vous avez besoin est de déterminer lesquels vous avez besoin. Vous pouvez écrire un autre cycle, qui compare chaque élément avec min et la saute avec l'un des éléments les plus à gauche.
Vous avez la première étape à droite. Vous devez maintenant déterminer comment déplacer tous les éléments correspondant à un
min au début de la matrice. Un bon moyen de commencer est de penser à déplacer un seul élément au début et à la façon dont vous allez changer tous les éléments ultérieurs une place. @grungegurunge Swap ne fonctionnerait pas ici depuis que PO mentionne que l'ordre des éléments restants doit être préservé@Glc Et comment vous allez changer tous les éléments ultérieurs une place vers le bas Vous voulez dire "up"?
"Tous les articles restants doivent rester à leurs endroits." Je suppose que cela signifie "doit rester dans leur ordre d'origine", n'est-ce pas? Parce que le premier
2 dans l'exemple ne reste certainement pas au même endroit dans le tableau.Cela semblerait être une solution à deux lignes utilisant
std :: min_element etstd :: stable_partition .Oui, cela signifie que l'ordre des éléments "non les plus petits" de la matrice doit rester identique. Désolé de ne pas préciser. Le "exemple" résume quelle fonction la fonction doit faire assez bien.
En outre, je ne suis pas autorisé à utiliser des fonctions prédéfinies.
@ Them1ke25 Eh bien, implémenter ce que fait Stable_Partition. C'est votre réponse, ou du moins la pointe de la procédure à suivre.
Je crois que la mission a été donnée pour voir si vous pouvez concevoir une solution autre que la réponse que vous avez acceptée.
@Paulmckenzie N ° de vue pour cette mission, je ne peux que les bases mêmes de la langue. Boucles, siest, fonctions propres, tableaux. C'est tout c'est pourquoi j'ai choisi cette réponse.
@MCHOLEWINSKI - Vous semblez mal comprendre. Vous pouvez utiliser C ++ sans aucune bibliothèque et vous trouverez toujours une réponse plus efficace. Pensez-vous que ces fonctions utilisent la magie pour faire leur travail? Non, c'est juste que vous n'avez pas pensé à résoudre le problème plus efficacement. En réalité, ce n'est pas un problème C ++ - c'est un problème avec une meilleure façon (pas en termes de code) de partitionnement des éléments. Consultez ma réponse sur une façon de le faire plus efficacement en utilisant un espace supplémentaire.
@Paulmckenzie Je comprends ça. Je sais aussi qu'il y a beaucoup de solutions meilleures que celles que je propose, mais comme débutant, en C ++, je suppose que la solution que j'ai choisie est assez bonne. L'apprentissage de quelque chose consiste à devenir meilleur audit sujet, alors je pense que ce n'est pas un problème énorme de commencer avec des idées moins efficaces et de les rendre progressivement mieux. Néanmoins, merci pour votre contribution.