啊哈！算法—坑爹的奥数

超、凢脫俗 2022-08-21 11:37 222阅读 0赞

下面等式：

？？？+？？？=？？？，将数字1~9分别填入9个？中，每个数字只能使用一次使得等式成立。

例如：173+286=459 和 286+173=459 是同一个组合。

思路：

利用标记法的枚举。

#include <iostream>
    using namespace std;
    
    int main()
    {
        int a[10],i,total=0,book[10],sum;
        for(a[1]=1; a[1]<=9; a[1]++)
            for(a[2]=1; a[2]<=9; a[2]++)
                for(a[3]=1; a[3]<=9; a[3]++)
                        for(a[4]=1; a[4]<=9; a[4]++)
                            for(a[5]=1; a[5]<=9; a[5]++)
                                for(a[6]=1; a[6]<=9; a[6]++)
                                    for(a[7]=1; a[7]<=9; a[7]++)
                                        for(a[8]=1; a[8]<=9; a[8]++)
                                            for(a[9]=1; a[9]<=9; a[9]++)
                                            {
                                                for(i=1; i<=9; i++) //初始化book数组
                                                    book[i]=0;
                                                for(i=1; i<=9; i++)
                                                    book[a[i]]=1;
                                                //统计共出现多少个不同的数
                                                sum=0;
                                                for(i=1; i<=9; i++)  //如果某个数出现过就标记一下
                                                    sum+=book[i];
                                                //如果刚好出现9个不同的数，并且满足等式条件，则输出
                                                if(sum==9&&a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])
                                                {
                                                    total++;
                                                    cout<<a[1]<<a[2]<<a[3]<<"+"<<a[4]<<a[5]<<a[6]<<"="<<a[7]<<a[8]<<a[9]<<endl;
                                                }
                                            }
        cout<<"共"<<total/2<<"种方法！"<<endl;
        return 0;
    }

运行结果：

![Center][]

学习心得：

和DFS相比，真正感觉到了枚举这种方法的慢了，呵呵。

[Center]: /images/20220724/b956f73376684a7aad9c1d03e734816a.png