我想大声告诉你2017-06-28 09:27:29
实数无解
负数无解
如果数字的个数一定很简单，两个的话枚举一半即可，多个可以参考下面的算法，修改为固定长度即可
如果数字的个数不一定，则也不能存在 0；参考一下
按公式的长度来遍历递归，因为可以剪枝，效率可观
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']
一开始想到的方式，将 1~n 每个的公式结果缓存起来递归，存起来很浪费空间，反复遍历也很慢
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"]给我你的怀抱2017-06-28 09:27:29
如果是实数.. 这题没什么意义
写个两两相加的
这里写个递归把.. 我也只懂一点点递归。。
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);
}
}
扔个三星炸死你2017-06-28 09:27:29
无解只是你没有给足条件，正整数是可以做的。用最简单的递归，时间复杂度是接受不了的。用n=100程序直接就崩了
我用的动态规划，用一个矩阵保存s[i,j]保存对应的结果，这样就不需要每次都重新算出之前的结果。
其中si,j，i=n,以j开头的组合数量，因为没有0的情况，所以是s[i,0]我放的是s[i,1]+s[i,2]+...+s[i,j]的结果
例如s[5,1]，就是表示n=5，1+1+1+1+1，1+1+1+2，1+1+1+3，1+1+1+4，1+2+2,5种情况，
其实按照这种方式可以很容易看出s[i,1]=s[i-1,0]，故
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]
其中我们去掉重复的条件，就只需要计算到s[i,i],
s[i,0]=s[i-1,0]+...+s[i,i]
由于s[i,i]=1，所以最后只需要计算出
s[i,2]+s[i,3]+...+s[i,i-1]的结果
由于后来的数的组合方式都可以重之前的组合拼接出来，
同s[i,1] = s[i-1,0],
s[i,j] = s[i-j,k],其中j > 1, j <= k <= i
下面是伪代码
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
}
下面是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]++;
}
}感觉还可以再优化，计算si,j>1的情况可以预先保存之前组合的数量，通过空间换时间。
希望对你有帮助
迷茫2017-06-28 09:27:29
这个东西有一个函数叫 拆分函数P
我之前做过一个跟这个有关的小算法题 神的90亿名字
不过我的题目中只需要求出整数拆分的数目，没有涉及具体的组合，在上面那篇拆分函数P中估计有涉及到
代言2017-06-28 09:27:29
这种算法逻辑最好有一定的限定条件，我姑且认为有指定数量的元数字和目标数字。
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);
}
}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);
}
}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)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如果给定条件是正数的话，把数组换成1~N。这个逻辑同样适用负数。
天蓬老师2017-06-28 09:27:29
这个算法还是比较简单的
如果要分解的数为双数 比如 18 那么几乎它的结果会是(18/2+1)种组合 然后第一个数从0开始递增，第二个数从最大值递减即可
如果为单数 17，那么可以让它加1后再除以2，又变成（18/2)了，然后第一个数从0开始递增，第二个数从最大值递减即可