凑数(1)

wils
wils

创作者俱乐部成员

今天来试试凑数,如图,A列里有一些数,B1是求和,C1是找出一组满足求和的数,C2是找出所有满足求和的数。

📌

function* cs(arr, s)

{

arr.sort((x,y)=>x-y)

let len = arr.length

let dat = []

yield* rec(0, 0)

function* rec(start, index) {

if (index === len) return

for (let i = start; i < len; i++) {

dat[index] = arr[i]

let sd = dat.slice(0, index + 1).reduce((x,y)=>x+y)

if (sd < s) {

yield* rec(i + 1, index + 1)

}

else if (sd == s) {

yield dat.slice(0, index + 1)

}

else {

break

}

}

}

}

function coushu1(rng, s)

{

return JSON.stringify(cs(rng().flat(), s).next().value)

}

function coushu(rng, s)

{

return [...cs(rng().flat(), s)].map(x=>[JSON.stringify(x)])

}

生成器的写法花里胡哨,只是为了方便逐个生成结果,不这样写更简单

  • coushu1和coushu都是调用cs生成器,输入一个范围和一个和,得到结果

  • cs里有两个位置,一个指向arr里每个项目,一个指向结果dat当前尝试的位置,尝试把arr里每一个项目放入dat的当前位置

  • 过程中判断dat里项目的和是否满足条件,小于就保留当前项目,递归的尝试下一个位置;等于就返回结果;大于就停止尝试

目前这个写法有很多缺点:

  • 只支持整数,比如两位小数,需要乘以100截取整数部分

  • 升序排列速度慢,因为在较小的数这里尝试了太多无效的组合,明天试试降序排列

  • A列20行左右就已经慢的不行,算法得改进。。。

注意:最好只尝试15个以内,多了会卡死,明天继续优化。。。

海南省
浏览 520
收藏
9
分享
9 +1
3
+1
全部评论 3
 
清华学弟任泽岩
清华学弟任泽岩

创作者俱乐部成员

好专业....
· 辽宁省
1
回复
 
uibpqds
2
· 河南省
回复
 
LG
1
· 中国
回复