凑数程序（WPS-JS版本）

wodewan

目前，还没见过WPS-JS版本的凑数程序（非递归版本），代码量很少，主函数也就10多行，加上读取数据，设置Excel格式啥的加起来也就40多行，程序执行和查看源码必须使用支持JS的WPS版本查看。
1. 对于正数和小数的凑数以及少量负数的凑数，JS的执行效率还是很高的，同时因为不是用字典去重，而是算法去重，所以如果数量含有大量重复值，反而效率会很高。
2. 同时因为是非递归版本，数据个数可以支持更多，试了个论坛里有个10万数据随机正数凑2亿的目标值的前100个组合，（如下图演示）也是可以秒出的，JS的效率还是不错的，仅供大家参考。
3。另外说明一下，这个程序并不是为了比较什么，只是兴趣爱好，因为算法的问题，缺点也很明显：如果含有大量负数，而且不设置误差的话可能就跑不出来。
4. 写的时候也发现，不同的算法对于不同的数据集的分布和目标值所在的区间，效率上差异很大，之前看过的凑数程序大多数都是倒叙的方式，这个程序是正序的方式，算另一种实现方式吧。

bjzzxhzl

太强大了！

lhgcore

太牛了，膜拜大神！

zpy2

查看源码必须使用支持JS的WPS版本

没有支持的版本，能否贴出来源码学习一下。

wodewan

zpy2 发表于 2023-1-10 14:52
查看源码必须使用支持JS的WPS版本

没有支持的版本，能否贴出来源码学习一下。

wodewan

把JS改写成了VBA，做了个小测试，同样的代码和数据，JSA,VBA在计算和写入的效率上差异有点意思,源数据用的也是论坛上的一个例子，1至100，求结果为100的所有组合。
总输出：44万4793组

	计算耗时	写入耗时	合计耗时
JSA	0.3-0.4秒	2.3-2.4秒	2.6-2.7秒
VBA	1.9-2.1秒	1.1-1.2秒	3.0-3.2秒

可以看出JSA的计算效率要高，但写入单元格的效率没有VBA高，VBA的计算效率比JS低很多，但如果用VB6.0编译的话，估计计算速度应该会提升不少，总体来说，两者各有特点。附上测试动图：

雪之花

值得学习学习，太强大了！

一执成念

老板，来个vba版的

micch

JSA看不懂，有VBA还好能学习一下

wodewan

micch 发表于 2023-1-12 13:50
JSA看不懂，有VBA还好能学习一下

哈哈，好啊，JSA看不懂没关系，凑数主要是个逻辑，学习不敢当，还请多指教。难得2位大佬有兴趣，既然这样，就多写点，有些细节要说明一下才能知道讨论啥，不然肯定一脸懵，看不下去，先贴个图，可能好对应下面说的啥，也可以下载附件自己看程序。







1. 首先这个代码的最初目的是想学习下递归转循环，简单的单层递归还好搞，用个栈结构去模拟递归压栈和出栈就可以。

2. 不过写着写着就发现对于凑数的递归是：递归里有循环，循环里又有递归，而且当一层递归结束后，还有对应的回溯操作，这些要改成循环就没那么简单了，必须记录每次递归的状态和代码运行的位置，还要进行对应的回溯才能模拟出来。




3. VBA的代码思路和JS的是一样的，VBA没自己的栈，是用数组模拟的，但大体上栈的功能是可以实现的，也就是先进后出，这个程序里有两个栈结构，一个path用于记录深度搜索时的路径，一个stack用于记录递归时的状态。而数组索引的跳动就是模拟的入栈和出栈。



4. 对于凑数功能，可以看的出来这个代码，除了主循环最后面的一个去重的功能，基本上没做什么剪枝和额外的判断，纯粹的暴力搜索。

5. 还有个观点是目标值在原始数据中的分布对程序首次获取到有效解的计算效率有很大影响，举个例子，如果目标值很大，那倒叙可能会更快找到结果，反之，正序会比较快，有负数也是一个道理，如果是正序的话，先必须把所有的负数消耗了才能去向目标值靠拢，但如果要获取所有解，感觉效率应该是差不多的，不同的数据集合目标值对于不同的程序会出现巨大的差异，至于如果做到尽量通用，就看各位大佬有没什么好的思路了，如何去判断数据的分别和目标值的关系，然后使用不同的方案去求解等等。

6. 递归的程序就不贴了，论坛上看的到的凑数的递归，感觉大框架都差不多，一层for循环里嵌套一个递归函数。这个程序就是将这个结构转换为while循环。

好了说了这么多，毕竟各有所好，如果有兴趣的话可以重点看看以下两点，第一就是循环的这个结构（用于解决数量个数多时递归栈溢出的问题），第二就是去重的那个逻辑没用字典，只是索引的判断就达到了去重，这样对于重复元素个数比较多的凑数效率会有很大的提升。