Le code suivant prend dans un entier t puis prend en 3 autres entiers t temps et retourne le nombre maximum de fois que vous pouvez soustraire 1 de deux entiers différents à au même moment, alors que le programme s'arrête quand il n'y a qu'un seul entiers supérieur à 0 restant. J'ai résolu le problème, mais je veux réduire la complexité de temps du code et je ne sais pas comment. Comment puis-je obtenir la même sortie sans utiliser toutes ces boucles qui augmentent la complexité de temps? EDIT: Je ne veux pas que mon code réécrit pour moi, c'est des devoirs et tout ce que je veux, ce sont des conseils et une aide afin que je puisse réduire la complexité de temps, que je ne fais pas Savoir comment faire. Editer 2: Dans mon algorithme, je trie les 3 numéros dans l'ordre croissant, j'utilise une boucle tandis que pour vérifier si le plus petit nombre (S / Arr [0]) est> 0. Après cela, j'utilise deux autres boucles lorsque vous alternez entre les nombres de taille les plus importants et moyens (L / Arr [2] et M / ARR [1] [1]) et décrément des variables S et L ou M (alternatif) . Quand S devient 0, cela signifiera que je peux simplement décrémenter l et m jusqu'à ce que l'un d'entre eux équivaut à 0, puis j'imprimer la variable de comptage (je compte d'incrémenter chaque fois que je décède deux des variables).
3 Réponses :
Je ne suis pas sûr que je comprenne le problème correctement, mais si vous souhaitez connaître le nombre maximum de fois que vous pouvez soustraire Le montant maximum fois que je peux soustraire 1 est 20, si j'ai toujours choisi de soustraire du sous-ensemble J'espère que cela vous aidera! (En supposant que je n'ai pas totalement mal compris la question ^ _ ^ ")
Après le commentaire de clarification, je pense que tout ce que vous avez à faire est de trouver le minimum entre la somme des éléments non maximaux et l'élément maximum. Considérez les exemples suivants:
Si vous recevez l'ensemble D'autre part, le compte de l'ensemble Dernier exemple: Considérez l'ensemble Si vous continuez à effectuer des exemples dans cette veine, vous devriez être capable de vous convaincre que la solution va toujours être 1 jusqu'à ce que zéro de deux éléments dans un ensemble de trois éléments, je crois que le La réponse devrait être la même que la recherche de l'élément médian de l'ensemble. Par exemple, si j'ai l'ensemble
10 20 30
{20, 30} , tandis que le minimum serait 10 , si je choisis toujours de soustraire du sous-ensemble {10, 20} . .
edit:
{80, 10, 210} Par exemple, la réponse à votre problème est de 90, car nous pouvons soustraire 10 du sous-ensemble {80, 10 < / code>}, nous laissant avec {70, 0, 210} où nous pouvons renforcer davantage 70 du sous-ensemble {70, 210} , nous laissant avec {0,0,140} , où nous ne pouvons plus effectuer plus d'opérations. nous avons effectué 80 + 10 = 90 soustractions par 1 dans ce cas, max = 210 et min + med = 90
{2,2,2} . Nous pouvons soustraire 2 du sous-ensemble {2,2} , nous laissant avec {0,0,2} , où nous ne pouvons plus exécuter d'opérations. Dans ce cas, nous avons effectué 2 soustractions de 1 max = 2 et min + med = 4
{2,3,5} . Nous pouvons soustraire 2 du sous-ensemble {2,3} , nous laissant avec {0,1,5} , où nous pouvons soustraire 1 du sous-ensemble {1,5} , entraînant {0,0,4} , où nous ne pouvons plus exécuter d'opérations. Dans ce cas, nous avons effectué 2 + 3 = 5 soustractions de 1 max = 5 et min + med = 5
Vous voyez que c'est ce que je pensais d'abord aussi, mais s'avère que le maximum pour 10 20 30 est 30 parce que vous pouvez soustraire du sous-ensemble {10, 30} 10 fois que le tableau sera {0, 20, 20} et U Peut soustraire du sous-ensemble {20, 20} 20 fois, ajoutez 20 à 10 et la réponse est de 30.
@AlHuthaliHumaid - Regardez votre commentaire. Faut-il des boucles pour comprendre la valeur est de 30? Ou juste une pensée intuitive?
@AlHuthalihumaid j'ai édité ma réponse en réponse à votre commentaire
@Luissosa Testez votre solution ici
En supposant que votre code est correct, vous pouvez examiner exactement ce que vos boucles font et les regarde plus mathématiquement. En supposant que votre programme a été correct, il produit les mêmes résultats pour toutes les entrées que j'ai essayées.
Je ne sais pas si j'ai bien compris le problème correctement. Mais si vous aviez, vous pouvez optimiser l'algorithème de la manière suivante:
int count = 0;
int a = 20, b = 10, c = 21;
sort(a, b, c); // Function that sorts the numbers, so that a is the smallest and c is the largest
count += a; // count = 10
c -= a; // a = 10, b = 20, c = 11
if(c < b) {
float diff = b - c; // diff = 9
float distribute = diff / 2; // distribute = 4.5
count += b - ceil(distribute); // count = 25
}
else count += b;
Cela ressemble à des devoirs?
Au lieu de me montrer du code et de nous demander de vous réécrire pour vous - car il s'agit d'une question sur les algorithmes et la complexité - vous pouvez peut-être décrire votre algorithme pour nous et demander des conseils sur la façon de le rendre plus optimal? Comme il se trouve cela ressemble à un "écrire mon code pour moi" Question des devoirs.
Je ne veux pas que mon code soit réécrit pour moi, je veux des conseils sur la manière de réduire la complexité de temps.
Pensez à cela: Comment pouvez-vous supprimer complètement les boucles les plus profondes, où vous venez d'incrémenter / des compteurs de décréments dans chaque itération?
Vous pouvez réduire la complexité en utilisant un algorithme différent. Le même algorithme a une complexité fixe (en supposant que la mise en œuvre n'est pas gâchée)
Utilisez un meilleur algorithme. Tournez sur votre optimiseur de compilateurs. Peut-être que vous voulez en.cppreference.com/w/cpp/algorithm/nth_element
Trier dans décroissant commande à la place. En supposant
R ≥ g ≥ b , réfléchissez aux différents cas éventuels,B + g> r ,B + g = r etB + g. (Je crois que cela peut être résolu sans aucune boucle du tout.) Je suis d'accord avec @Molbdnilo - la façon dont la question est libellée, cela devrait être résoluble sans aucune boucle. Quelle est la raison pour compter "manuellement" dans un
pendant en boucle, lorsque vous savez à quelle distance vous êtes de 0? C'est juste un réarrangement et des mathématiques simples sont tout ce qu'il faut.