Le moyen le plus optimal pour trouver la somme de 2 nombres représentés comme des listes chaînées

J'essayais d'écrire un programme pour le problème que j'ai mentionné ci-dessus, les nombres (ie les listes) peuvent être de longueur inégale, je n'ai pas pu figurer une façon de faire autre que le plus souvent la pensée de l'approche à savoirLe moyen le plus optimal pour trouver la somme de 2 nombres représentés comme des listes chaînées

liste-1 inverse
liste-2 inverse
trouver la somme et le stocker dans une nouvelle liste représentée par la liste-3
inversez la liste.

La complexité de ceci devrait être de O (n + m). Y a-t-il moyen de le réduire ou de le faire mieux?

Source

2009-10-18 Shiv

Oui, pouvez-vous expliquer ce qui se trouve réellement dans ces listes chaînées? Aussi, probablement la réponse est: non, vous ne pouvez pas faire mieux que O (n); mais cela dépend de la façon dont vous représentez ces choses. – BobbyShaftoe

Qu'entendez-vous par "numéros représentés sous forme de listes chaînées"? Voulez-vous dire que vous avez une liste liée, avec un chiffre enregistré dans chaque élément? De plus, si vous avez besoin de faire quelque chose qui implique chaque élément de deux listes liées, le meilleur temps que vous obtiendrez peut-être est O (n + m), parce qu'il faut autant d'opérations pour regarder toutes les listes. éléments. –

ouais Brian c'est ce que je veux dire. – Shiv

Idéalement, la première chose que je voudrais faire est de stocker les numéros dans l'ordre inverse chiffres, donc 43712 est stocké comme:

2 -> 1 -> 7 -> 3 -> 4

Il fait des opérations arithmétiques beaucoup plus facile.

L'affichage d'un nombre peut se faire de manière itérative ou plus simplement avec un algorithme récursif. Note: tout cela suppose des listes à liaison unique.

Editer: Mais vous avez déclaré depuis que vous n'avez pas le choix dans le format de stockage. En tant que tel, votre meilleur pari est d'inverser les deux listes, faire l'addition, puis inverser le résultat.

Source

2009-10-18 04:16:23 cletus

Je suppose qu'il ne soit pas à choisir comment ils sont stockés, c'est pourquoi il commence par inverser la liste, sinon le vôtre est l'approche la plus simple. –

yup c'est à droite James – Shiv

Mais qu'en est-il du temps qu'il faut pour les inverser, puisque vous ne connaissez pas la longueur à l'avance, de sorte que vous ne pouvez pas le faire en place.Vous finissez par enlever la tête de la source, et les repoussant dans l'autre ordre, mais cela signifie que vous traversez complètement la liste deux fois, en faisant une opération mineure. –

Si vous pouvez utiliser une liste doublement chaînée, vous pouvez rapidement passer à la fin de chaque liste, puis revenir en arrière en ajoutant les numéros à chaque point et les ajouter à une nouvelle liste.

Vous devrez déterminer quelle liste est la plus longue et l'additionner en fonction de la longueur de la liste la plus courte, puis terminer la sommation et ajouter la liste la plus longue. Mais, vous aurez quelques problèmes avec le fait que la somme peut aller au-dessus d'un chiffre, donc si cela arrive, vous devrez suivre le dépassement et l'ajouter au nœud suivant.

Source

2009-10-18 04:19:21

Im en utilisant seulement une liste de liens simples. – Shiv

Ensuite, déterminez la longueur, trouvez le plus long, ajoutez les nœuds qui sont en excès à la nouvelle liste, puis ajoutez-les, mais, vous devez garder une trace du nœud précédent en cas de débordement, et si ce débordement déborde, alors vous avez un problème. –

Cela impliquera de parcourir la liste plusieurs fois, d'abord pour trouver les longueurs, et ensuite pour faire des ajouts, j'essaie cependant de minimiser le nombre de fois que je traverse la liste. Merci pour votre suggestion cependant, j'avais d'abord pensé à cela. – Shiv

Je ne pense pas à une meilleure solution au problème comme indiqué. Le problème de base est que vous devez traiter les éléments de la liste dans l'ordre inverse. En théorie, vous pouvez implémenter l'algorithme de manière récursive, évitant ainsi le recours à des étapes d'inversion explicites. Mais cela nécessite O(max(m,n)) l'espace de pile, et serait probablement plus lent.

Mais je pense que c'est vraiment dire que vous avez choisi une mauvaise représentation. Si vous représentez les nombres comme des listes doublement chaînées de int ou des tableaux de int (avec une taille explicite), la complexité sera O(max(m,n)) avec une plus petite constante de proportionnalité.

Remarque: O(max(m,n)) et O(m+n) sont tous deux des abus de la notation O. Strictement parlant, O est définie en termes de limite car une seule variable va à l'infini. Considéré de cette façon, O(max(m,n)) et O(m+n) tous les deux réduire à O(m) ou O(n). Cependant, je comprends ce que vous essayez de dire :-).

Source

2009-10-18 04:20:52

Eh bien c'est une contrainte de conception, je ne suis pas libre de choisir la méthode de représentation, c'est quelque chose qui a été discuté avec un ami il y a quelques heures. :) – Shiv

La seule optimisation potentielle, qui se ferait au détriment de la clarté du code, consisterait à combiner les inversions initiales en une seule boucle. Vous passez ensuite de O (n + m + m) à O (m + m), bien que les étapes à l'intérieur de la boucle soient plus coûteuses.

Source

2009-10-18 05:05:06 jfawcett

@jfawcett - Je suis sûr que cela ne donnera aucune amélioration ... en supposant que vous faites une inversion de liste par retournement de pointeur. –

@jfawcett, pouvez-vous expliquer votre solution un peu plus, j'ai pensé à ce sujet mais j'étais à perte pour voir comment je pouvais combiner les étapes initiales d'inverser les deux listes en une seule boucle. Puisque je ne sais pas quel nombre est plus long, peut-être que certains pseudocodes aideraient. – Shiv

La méthode que vous avez proposée était reverse/count 1 (len = x), puis reverse/count 2 (len = y), puis additionne/stocke la nouvelle (len = max (x, y)). Si, au contraire, vous avez une seule boucle qui inverse à la fois 1 et 2 en même temps. En marche arrière une seule, vous faites quelque chose comme while (currentHead! = NULL) { } remplacer par while (currentHead1! = NULL || currentHead2! = NULL) { if (currentHead1) { inverse 1 } si (currentHead2) { inverse 2 }} Cela fonctionne uniquement avec inversion non récurrent, bien sûr. – jfawcett

Vous pouvez faire mieux sans inversion de liste. WLOG Je vais supposer que les deux listes ont une longueur égale (préfixer avec 0 si nécessaire).

Commencez l'addition de gauche à droite (du plus significatif au moins significatif). Vous avez trois cas, en fonction de la somme des deux chiffres:

= 9: garder neuf et augmenter une counter
< 9: écrire counter x neuf, écrire somme, réinitialiser counter
9: augmentation dernier chiffre, écrire counter x zéro, écrire somme (modulo 10), réinitialiser le compteur

Je travaille sur l'exemple suivant:

2 568 794 + 
1 438 204 
--------- = 
4 006 998

Ajouter 2 + 1 = 3: 3 cas.
- list = (3), counter = 0
Ajouter 5 + 4 = 9: 1 cas
- list = (3), counter = 1
Ajouter 6 + 4 = 9: cas 1
- list = (3), counter = 2
Ajouter 8 + 8 = 16: cas 3
- list = (4, 0, 0, 6), counter = 0
Ajouter 7 + 2 = 9: cas 1
- list = (4, 0, 0, 6), counter = 1
Ajouter 9 + 0 = 9: cas 1
- list = (4, 0, 0, 6), counter = 2
Ajouter 4 + 4 = 8: cas 2
- list = (4, 0, 0, 6, 9, 9, 8), counter = 0

Source

2009-11-01 17:27:06 Alexandru

C'est génial, mais comment cette méthode fonctionnera-t-elle pour des listes de longueurs inégales? – Shiv

Vous devez toujours connaître les tailles de la liste et les rendre égales en ajoutant 0 à la valeur la plus courte (ou, mettre les premiers éléments m - n (m> n) dans la liste finale). – Alexandru

Le moyen le plus optimal pour trouver la somme de 2 nombres représentés comme des listes chaînées

Répondre

Questions connexes