Défi
Écrivez une fonction qui, à partir d'un tableau d'entrée arbitraire, sélectionnera toutes les combinaisons de nombres dont la somme est 10.À première vue, la tâche est simple, il vous suffit d'écrire une récursivité et de trier toutes les valeurs.
Ou vous pouvez utiliser un incrément binaire, mais pour parcourir toutes les valeurs d'un vecteur de nombres de longueur N, il faut 2 ^ n itérations.
Tout d'abord, nous choisissons un cas spécial, supposons que le tableau se compose de nombres> 0. Plus tard, sur la base de cet exemple, nous implémenterons tous les cas.ÉTAPE 1
a) Considérons l'un des cas particuliers - la somme de tous les éléments du tableau <10.
La logique est simple, somme (V) <10, puis somme (V) -V [i] <somme, c'est-à-dire si la somme des combinaisons sera toujours inférieure à 10.
b) Si somme (V) = 10, alors la somme somme (V) -V [i] <somme. Le résultat sera un seul
v .
ÉTAPE 2
Nous supprimons tous les inutiles du vecteur
Par exemple, prenez le tableau [13, 10, 20, 13, 13, 18, 2, 9, 5, 8, 8, 9, 2, 1, 8, 16, 4, 15, 2, 2, 2, 1, 5 , 5, 5].
Cela montre immédiatement qu'il n'est pas logique de rechercher des combinaisons si la valeur est> 10, mais tout deviendra immédiatement clair. si on le trie:
[1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10, 13, 13, 13, 15, 16, 18, 20 ]
À ce stade, nous pouvons déjà savoir avec certitude que nous devons supprimer tous les éléments supérieurs à 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10]
Mais en fait, tout est un peu plus intéressant. nous devons limiter le vecteur à la valeur de sorte que V [0] + V [i] <= 10; où j'ai tendance à N; Mais si V [i] = 10, alors on ajoute 10 au résultat
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9]
ÉTAPE 3
Il y a des éléments en double dans un tableau déjà filtré. Si nous décomposons le vecteur en sous-vecteurs et calculons leur somme, nous obtenons quelque chose comme ça
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[5, 5, 5, 5] => 20
[8, 8, 8] => 24
[9.9] => 18
L'essence de mes pensées est telle qu'il n'est pas logique d'envisager des combinaisons de nombres répétés si leur nombre * valeur> 10. Autrement dit, nous coupons les vecteurs jusqu'à ce que leur somme soit inférieure à 10 et ajoutons ceux qui sont 10 au résultat:
[1,1] => [1,1]
[2, 2, 2, 2, 2] => [2, 2, 2, 2]
[4] => [4]
[5, 5, 5, 5] => [5]
[8, 8, 8] => [8]
[9.9] => [9]
À la suite de la 3ème étape, notre vecteur sera le suivant
[1, 1, 2, 2, 2, 4, 5, 8, 9]
Comme vous pouvez le voir, la taille du vecteur est passée de 25 à 9, elle est beaucoup plus petite (rappelez-vous le nombre d'itérations);
Avec des nombres négatifs
C'est un peu plus compliqué. nous supposerons que nous avons mis en œuvre la fonction de recherche de combinaisons pour un vecteur trié positif sur la base des restrictions précédentes.
peigne (arr, sum), où sum est le montant requis, arr est un vecteur trié à partir de nombres positifs
Par exemple, prenez le vecteur:
[19, 15, -9, 3, -13, -8, -12, 11, -2, -10, 0, 7, 17, -17, -14, -15, -11, -6, -12 , -10, 9]
1. Briser le vecteurA = uniquement des valeurs positives
B = uniquement des valeurs négatives
Et voyez aussi si nous avons des valeurs = 0
2. TrierTrier les vecteurs (positif croissant, négatif décroissant)
Vérifiez le cas spécial pour les nombres positifs (ÉTAPE 1)
3. Vérification du positifVérifiez les valeurs positives
peigne (B, 10)3. Vérifiez le négatifcréer des combinaisons de tous les nombres négatifs, mais avec la restriction:
(somme des éléments modulo) <(somme de tous les positifs) + 10
on trouve des combinaisons pour les NOUVELLES sommes de référence (la somme des éléments modulo + 10)
4. Égalité 0Si le vecteur source a une valeur de 0, alors nous ajoutons toutes les combinaisons + 0 au résultat;
En raison de ces limitations, en moyenne, lors du test de valeurs avec un tableau de 28 et 1000 tests de long, le gain de temps est de près de 42%
Attention à ne pas avoir l'air nerveux. L'auteur n'est pas responsable des souffrances morales.function combine(arr, etalon = 10) {