javascript - Algoritma: Diberi nombor, berapa banyak cara jumlahnya boleh sama dengan nombor ini?

Question

Contohnya, 8 boleh jadi 4 tambah 4, 2 tambah 5 tambah 1, dsb. Berapa banyak cara yang ada, dan senaraikan semua cara bersama

Answer 1

1. Nombor sebenar tiada penyelesaian

2. Nombor negatif tiada penyelesaian

3. Jika bilangan nombor mestilah sangat mudah, jika ada dua, hitungkan separuh daripadanya Jika terdapat lebih daripada satu, anda boleh rujuk algoritma di bawah dan ubah suai kepada panjang tetap

.

4. Jika bilangan nombor tidak pasti, 0 tidak boleh wujud;

Lintas rekursi mengikut panjang formula, kerana ia boleh dipangkas dan kecekapannya agak besar

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']

Cara yang saya fikirkan pada mulanya adalah untuk cache 1~n hasil formula setiap kali secara rekursif dan sangat lambat untuk dilalui berulang kali

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

Jika ia adalah nombor sebenar... soalan ini tidak masuk akal

Tulis tambah dua demi dua

Tulis rekursi di sini... Saya hanya tahu serba sedikit tentang rekursi. .

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

Tiada penyelesaian hanya kerana anda tidak memberikan syarat yang mencukupi, ia boleh dilakukan dengan integer positif. Dengan rekursi yang paling mudah, kerumitan masa tidak boleh diterima. Program dengan n=100 akan ranap serta-merta
Pengaturcaraan dinamik yang saya gunakan menggunakan matriks untuk menyimpan s[i,j] untuk menyimpan hasil yang sepadan, supaya tidak perlu mengira semula keputusan sebelumnya setiap kali.
Antaranya, si, j, i=n, ​​​​bilangan gabungan bermula dengan j, kerana tiada kes 0, jadi s[i,0] yang saya letakkan ialah s[i,1]. +s[i,2]+. Hasil daripada ..+s[i,j]
Sebagai contoh, s[5,1] bermaksud n=5, 1+1+1+1+1, 1+1+ 1+2, 1+1+1+ 3, 1+1+1+4, 1+2+2, 5 kes,
Malah, mengikut kaedah ini, ia boleh dilihat dengan mudah bahawa s[i,1] =s[i-1,0], jadi
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]
Antaranya, jika kita membuang syarat berulang, kita hanya perlu mengira s[i,i],
s[i,0]=s[i-1,0] +...+s[i,i]
Memandangkan s[i,i]=1, kita hanya perlu mengira
s[i,2] +s[i,3]+...+s[i pada akhirnya ,i-1] keputusan
Oleh kerana gabungan nombor seterusnya boleh disambungkan bersama oleh gabungan sebelumnya,
sama seperti s[i, 1] = s[i-1,0],
s[i,j] = s[i-j,k], dengan j > 1, j <= k <= i
Berikut ialah kod pseudo

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
}

Yang berikut dilaksanakan dalam 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]++;
    }
}

Rasanya ia boleh dioptimumkan lagi apabila mengira si,j>1, bilangan kombinasi sebelumnya boleh dijimatkan terlebih dahulu dan masa boleh ditukar melalui ruang.
Semoga ia membantu anda

Answer 4

Perkara ini mempunyai fungsi yang dipanggil fungsi split P
Saya telah melakukan soalan algoritma kecil yang berkaitan dengan ini sebelum ini: 9 bilion nama Tuhan
Namun, soalan saya hanya memerlukan bilangan pecahan integer, dan tidak melibatkan kombinasi tertentu, ia adalah mungkin terlibat dalam artikel di atas 拆分函数P

Answer 5

Logik algoritma jenis ini adalah yang terbaik untuk mempunyai sekatan tertentu, saya secara tentatif berpendapat bahawa terdapat bilangan nombor elemen dan nombor sasaran yang ditentukan.

Versi 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);
    }
}

Versi 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);
    }
}

Versi Ruby:

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)

Versi 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

Jika keadaan yang diberikan ialah nombor positif, tukar tatasusunan kepada 1~N. Logik yang sama digunakan untuk nombor negatif.

Answer 6

Algoritma ini agak mudah
Jika nombor yang akan diuraikan adalah nombor genap seperti 18, maka hampir hasilnya akan menjadi gabungan (18/2+1) Kemudian nombor pertama meningkat daripada 0, dan nombor kedua bermula dari maksimum Hanya kurangkan nilai
Jika ia adalah nombor ganjil 17, maka anda boleh menambah 1 padanya dan kemudian membahagikannya dengan 2, dan ia menjadi (18/2) semula Kemudian nombor pertama mula meningkat daripada 0, dan nombor kedua berkurangan daripada nilai maksimum