关于算法与逻辑的粗浅认识

大灰狼1976

【无任何代码贴】
看到过一个有趣的智力题，A\B\C各代表不同的一位数字（非0数），通过下面的算式推算出各个字母代表的具体数字：

   A B C
+A B C
+A B C
-----------
   8 8 8
根据此类题的一般套路，先看3个C怎么算出个位数8，应该6*3=18（进1位）；
然后再看3个B+1怎么算出十位数8，应该是9*3=27+1（进2位）；
最后算出3个A+2=8，可得A=2。那ABC代表的就是296三个数字。
这个是推理法，用程序来实现的话可能代码会比较复杂，但执行效率应该很高。

既然使用程序了，那也可以考虑遍历法，三位数逐个尝试就行了，毕竟数据量不多，这个是最无脑的方法，代码很少，但遇到大数效率就非常低。

最后是大跌眼镜，直接用大道至简的数学，888/3=296

对三种算法粗浅总结一下：
推理法：逻辑要求高，效率较高；
遍历法：逻辑要求低，效率低
数学法：逻辑要求低，效率高

小凡、、、

三个相同数相加=888，结果不就是888/3么，没毛病

大灰狼1976

接下来题目稍微进化一点，这是我自己改的，A/B/C仍然为非0数字，各不相同，算式如下：

    A B C
  +B C A
  +C A B
-------------
   2 1 0 9
看上去不能直接用平均法了，貌似用推理也很难，小数据量时遍历是一个好的选择。
但再深入考虑一下，也能找到数学规律，每个字母分别在个十百位各出现一次，那就相当于乘以了111。
三个字母均如此，它们的总和是2109，那直接2109/111=19，这个19是三个字母代表的一位数字的合计，
然后1-9找出3个不同的数，加起来总和等于19的全都符合（多个解）。

再总结一下：
推理法：暂无
遍历法：3位数123~987遍历（考虑无重复数，略剪枝），需要865次，效率较低
简化法后遍历：9选2（第3个数可以算出来）=combin(9,2)=36次，效率较高
简化法效率是遍历法的24倍左右

如果是4位数的话，遍历法需要8642次，简化法需要combin(9,3)=84次，效率差不多相差100倍

我的结论：算法>逻辑>变量类型，算法才是效率的根本，越往后的因素，影响越轻微

大灰狼1976

小凡、、、 发表于 2024-10-9 16:09
三个相同数相加=888，结果不就是888/3么，没毛病

是的，掉入惯性思维陷阱，但其实这个是简单示例，有很多情况下我们掉入惯性思维陷阱并不能马上发现。

小凡、、、

大灰狼1976 发表于 2024-10-9 16:15
接下来题目稍微进化一点，这是我自己改的，A/B/C仍然为非0数字，各不相同，算式如下：

    A B C

补单位(100A+10B+c)+(100B+10C+A)+(100C+10A+B)=2019
换算111A+21B+201C=2109
到这一步，已知ABC（1-9），尝试找到最大系数（201C），使用2019/201>9,同时判断剩余AB大的系数*2，小的系数*1（最小计算逻辑是否超过22109）（201*9+111*1+21*2=1962）未超过2109，则先带入9尝试
带入C=9后尾数2019-201*9=300，剩余AB系数都不超过300，则取大的111A提算，300/111=2.7向下取值A等于2尝试
按照这个逻辑写成vba代码应该是比较简单的

不规则结构

Sub 三个数相加2019()
    '三个数可以互换，只考虑a>b>c的情形。显然c不为0.
    '个位数相加为9，十位数同样的三个数相加尾数0，由此可知三个数相加为19.
    '三个数不相等，c必然小于int(19/3)即6，最小值是2，所以c取值在2到5之间
    'a只能为8或9
    '假设b为5，那c最大是4，a是10，和题设矛盾！b为6到8之间
    '以下无脑循环
    Dim co As New Collection
    For a = 2 To 5
        For b = 6 To 8
            For c = 8 To 9
                If a <> b And b <> c And a <> c And a + b + c = 19 Then co.Add a & "," & b & "," & c
            Next
        Next
    Next
End Sub

不规则结构

循环次数24次

不规则结构

算轮换，次数就多了

一招秒杀

当今市面主流的CPU,每秒轻易可以进行1万亿次以上的计算，如果是GPU 算力卡什么的 每秒能进行的计算更可能高达几百万亿次，对于这种偶发性的需求，哪怕用 最原始的循环计算，怎么也用不了1秒，为它花几分钟甚至更长时间去优化算法代码，感觉不划算啊。当今CPU 太快了，偶发性的简单需求，可能不那么迫切需要考虑什么优化算法。

大灰狼1976

一招秒杀 发表于 2024-10-9 19:09
当今市面主流的CPU,每秒轻易可以进行1万亿次以上的计算，如果是GPU 算力卡什么的 每秒能进行的计算更可能高 ...

我不这么认为，偶发性的需求确实不重要，但这只是思维拓展的一环，假设有一万种偶发性的需求，找到了最优的算法，那这一万种需求可以高效解决大部分问题。两个效率差10倍的算法，0.01秒和0.1秒没啥区别，但1分钟和10分钟的区别可能是无法忍受的。优秀的程序员应该是吝啬的。