火柴棒等式

火柴棒等式[1]

【问题简述】给你 n（n≤24）根火柴棍，你可以拼出多少个形如“A＋B＝C”的等式？等式中的 A、B、C 是用火柴棍拼出的整数（若该数非零，则最高位不能是0），数字的形状和电子表上的一样。

注意：

1.  加号与等号各自需要两根火柴棍。

2.  如果 A≠B，则 A+B=C 与 B+A=C 视为不同的等式（A，B，C≥0）。

3.  n 根火柴棍必须全部用上。

【分析】

直接枚举 A 和 B（事实证明只到3位数）。为了加快速度，事先把222以内各个数所用的火柴数算出来。

#include  <iostream> using namespace std;    int matches[223], n;    void  getmatches();   // 把火柴棍事先算好  int count=0;    int main()    {    getmatches();          cin>>n;  for (int i=0;i<=111;i++)   for (int j=0;j<=111;j++)      {       int k=i+j;       if(matches+matches[j]+matches[k]+4==n)        count++;      }    cout<<count;
return 0;    }  void getmatches()    {  matches[0]=6;  matches[1]=2;  matches[2]=5;    ……         matches[222]=15;    }		//  事先编一个程序来产生这一部分代码。

---

[1] 题目来源：NOIP2008第二题