思路:这是一个典型的母函数问题,一般的典型母函数如 G(x) =
(1+x+x^2+x^3+x^4+x^5+....)*(1+x^2+x^4+x^6+x^8+x^10+....)*(1+x^3+x^6+x^9+x^12....).....
这个题目中的每个纸币只能够使用0次或1次,在上面的那个一般的母函数的基础上修改一下就行了,就很简单了。。具体代码如下:
#include
using namespace std;
const int lmax = 10000;
int c1[lmax + 1], c2[lmax + 1];
int main(void)
{
int m, n, i, j, k, a[110];
//计算的方法还是模拟手动运算,一个括号一个括号的计算,从前往后
while (cin >> m && m)
{
n = 0;
for (i = 0; i < m; i++)
{
scanf("%d", &a[i]);
n += a[i];
}
n += 5; //有可能无法表示的那个数比所有纸币面额的总和还要大
for (i = 0; i <= n; i++)
{
c1[i] = 0;
c2[i] = 0;
}
for (i = 0; i < 2 * a[0]; i += a[0]) //母函数的表达式中第一个括号内的各项系数
c1[i] = 1;
//第一层循环是一共有 n 个小括号,而刚才已经算过一个了,所以是从2 到 n
// i 就是代表的母函数中第几个大括号中的表达式
for (i = 2; i <= m; i++)
{
for (j = 0; j <= n; j++) //j 就是指的已经计算出的各项的系数
{
for (k = 0; k < 2 * a[i - 1]; k += a[i - 1]) //k 就是指将要计算的那个括号中的项
{
c2[j + k] += c1[j]; //合并同类项,他们的系数要加在一起,所以是加法
}
}
for (j = 0; j <= n; j++) // 刷新一下数据,继续下一次计算,就是下一个括号里面的每一项
{
c1[j] = c2[j];
c2[j] = 0;
}
}
for (i = 1; i <= n; i++)
{
if (c1[i] == 0)
{
cout << i << endl; //找出第一个无法表示的纸币面额
break;
}
}
}
return 0;
}