javascript - Algorithme : étant donné un nombre, de combien de façons la somme peut-elle être égale à ce nombre ?

Question

Par exemple, 8 peut être 4 plus 4, 2 plus 5 plus 1, etc. Combien y a-t-il de façons et énumérez toutes les façons ensemble

Answer 1

1. Les vrais chiffres n'ont pas de solution

2. Les nombres négatifs n'ont pas de solution

3. Si le nombre de nombres doit être très simple, s'il y en a deux, la moitié d'entre eux peut être énumérée. Pour plus d'un, vous pouvez vous référer à l'algorithme ci-dessous et le modifier à une longueur fixe

.

4. Si le nombre de nombres n'est pas certain, 0 ne peut pas exister merci de vous y référer

;

Traversez la récursion en fonction de la longueur de la formule, car elle peut être élaguée et l'efficacité est considérable

function count (num) {
  if (!(num > 1)) { return [] }

  var equations = []
  var eq = []
  for (let len = 2; len <= num; len += 1) {
    _countByLen(num, eq, 0, len, 0)
  }
  return equations

  function _countByLen (num, eq, i, len, sum) {
    if (i === len) {
      if (sum === num) {
        equations.push(eq.join('+'))
      }
      return
    }

    for (let n = eq[i - 1] || 1; n < num; n += 1) {
      let newSum = n + sum
      if (newSum > num) { break }
      eq[i] = n
      _countByLen(num, eq, i + 1, len, newSum)
    }
  }
}

count(5) // ['1+4', '2+3', '1+1+3', '1+2+2', '1+1+1+2', '1+1+1+1+1']

La façon dont j'y pensais au début était de mettre en cache 1~n résultats de formule à chaque fois de manière récursive. L'enregistrer est une perte d'espace, et les parcours répétés sont également très lents

.

function count (num) {
  if (!(num > 1)) { return [] }

  var equations = [,[[1]]]
  _count(num)
  return equations[num].slice(0, -1).map(eq => eq.join('+'))

  function _count (num) {
    if (equations[num]) { return equations[num] }

    let halfNum = Math.floor(num / 2)
    let eqNum = [] // 即 equations[num]
    for (let n = 1; n <= halfNum; n += 1) {
      _count(num - n).forEach(eq => {
        if (n <= eq[0]) {
          eqNum.push([n].concat(eq))
        }
      })
    }
    eqNum.push([num])
    equations[num] = eqNum
    return eqNum
  }
}

count(5) // ["1+1+1+1+1", "1+1+1+2", "1+1+3", "1+2+2", "1+4", "2+3"]

Answer 2

Si c'est un nombre réel... cette question n'a aucun sens

Écrivez un ajout deux par deux

Écrivez une récursivité ici... Je ne connais que peu la récursivité. .

R

var color = ''; 
var wow = (n, i = 0) => {
    if (i > n / 2) return ;
    else {
        console.log(`%c ${n} = ${i} + ${n - i} `, color); 
        wow(n, i + 1); 
    }
}

S

Answer 3

Il n’y a pas de solution simplement parce que vous n’avez pas donné suffisamment de conditions, cela peut être fait avec des entiers positifs. Avec la récursion la plus simple, la complexité temporelle est inacceptable. Le programme avec n=100 plantera immédiatement
La programmation dynamique que j'utilise utilise une matrice pour enregistrer s[i,j] pour enregistrer les résultats correspondants, de sorte qu'il n'est pas nécessaire de recalculer les résultats précédents à chaque fois.
Parmi eux, si, j, i=n, ​​​​le nombre de combinaisons commençant par j, car il n'y a pas de cas de 0, donc c'est s[i,0]. Ce que je mets c'est s[i,1]. +s[i,2]+. Le résultat de ..+s[i,j]
Par exemple, s[5,1] signifie n=5, 1+1+1+1+1, 1+1+. 1+2, 1+1+1+ 3, 1+1+1+4, 1+2+2, 5 cas,
En fait, selon cette méthode, on voit facilement que s[i,1] =s[i-1,0], donc
s [i,0]=s[i,1]+s[i,2]+...+s[i,j]
s[i,0] =s[i-1,0]+s[i ,2]+...+s[i,j]
Parmi eux, si on supprime les conditions répétées, il suffit de calculer s[i,i],
s[i,0]=s[i-1,0] +...+s[i,i]
Puisque s[i,i]=1, il suffit de calculer
s[i,2] +s[i,3]+...+s[i à la fin,i-1] résultat
Parce que les combinaisons de nombres suivantes peuvent être assemblées par les combinaisons précédentes,
identique à s[i, 1] = s[i-1,0],
s[i,j] = s[i-j,k], où j > 1, j <= k <= i
Ce qui suit est le pseudo-code

function(s, n) {
    s <= {0,0};
    for(i = 1 to n)
        for (j = 1 to floor(i/2) )
            if(j = 1) 
                s[i][j] = s[i-1][0]
            else 
                temp = 0;
                for(k = j to i)
                    temp += s[i-j][k]
                s[i][j] = temp
                
            s[i][0] += s[i][j]
        s[i][j] = 1,
        s[i][0]++
        
    return s
}

Ce qui suit est implémenté en PHP

function calculate(&$s, $n) {

    for( $i = 1; $i <= $n; $i++ ) {
        $s[$i][0] = 0;
        for( $j = 1; $j <= floor($i/2); $j++ ) {
            //以1开头的，等于上一次计算结果
            if( $j == 1 ) {
                $s[$i][$j] = $s[$i - 1][0];
            } else {
                $temp = 0;
                for ($k = $j; $k <= $i; $k++) {
                    if( isset($s[$i - $j][$k]) ) {
                        $temp += $s[$i - $j][$k];
                    }
                }
                $s[$i][$j] = $temp;
            }
            $s[$i][0] += $s[$i][$j];
        }
        //对角线，加上自身
        $s[$i][$i] = 1;
        $s[$i][0]++;
    }
}

Il semble qu'il puisse être encore optimisé. Lors du calcul de si,j>1, le nombre de combinaisons précédentes peut être enregistré à l'avance et le temps peut être échangé dans l'espace.
J'espère que cela vous aidera

Answer 4

Cette chose a une fonction appelée fonction de division P
J'ai déjà posé une petite question d'algorithme à ce sujet : les 9 milliards de noms de Dieu
Cependant, ma question ne nécessite que le nombre de divisions entières et n'implique pas de combinaisons spécifiques, c'est probablement impliqué dans l'article ci-dessus 拆分函数P

Answer 5

Il est préférable que ce type de logique algorithmique ait certaines restrictions. Je pense provisoirement qu'il existe un nombre spécifié de numéros d'éléments et de numéros cibles.

Version Java :

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

Version C# :

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Version Rubis :

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target 

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Version Python :

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #输出:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Si la condition donnée est un nombre positif, changez le tableau en 1~N. La même logique s'applique aux nombres négatifs.

Answer 6

Cet algorithme est relativement simple
Si le nombre à décomposer est un nombre pair tel que 18, alors presque le résultat sera (18/2+1) combinaisons. Ensuite, le premier nombre augmente à partir de 0 et le deuxième nombre commence à partir de. le maximum Diminuez simplement la valeur
S'il s'agit d'un nombre impair 17, alors vous pouvez y ajouter 1 puis le diviser par 2, et il devient à nouveau (18/2). Ensuite, le premier nombre commence à augmenter à partir de 0, et. le deuxième nombre diminue par rapport à la valeur maximale. C'est tout

.