首页 > ACM题库 > HDU-杭电 > HDU 1028 Ignatius and the Princess III-数学相关-[解题报告] C++
2013
11-26

HDU 1028 Ignatius and the Princess III-数学相关-[解题报告] C++

Ignatius and the Princess III

问题描述 :

"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.

"The second problem is, given an positive integer N, we define an equation like this:
  N=a[1]+a[2]+a[3]+…+a[m];
  a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
  4 = 4;
  4 = 3 + 1;
  4 = 2 + 2;
  4 = 2 + 1 + 1;
  4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"

输入:

The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.

输出:

For each test case, you have to output a line contains an integer P which indicate the different equations you have found.

样例输入:

4
10
20

样例输出:

5
42
627

Author
Ignatius.L
下面解答copy以下链接(并非本人想出来的):
http:[email protected]/blog/static/17044235820108203120482/
该解答很好、很强大/(^o^)/~
参考解答:
源代码及简单分析:

把加法变为幂运算

 

这里先给出2个例子,等会再结合题目分析:

 

第一种:

有1克、2克、3克、4克的砝码各一 枚,能称出哪几种重量?每种重量各有几种可能方案?

考虑用母函数来接吻这个问题:

我们假设x表示砝码,x的指数表示砝码的重量,这样:

1个1克的砝码可以用函数1+x表示,

1个2克的砝码可以用函数1+x2表示,

1个3克的砝码可以用函数1+x3表示,

1个4克的砝码可以用函数1+x4表示,

上面这四个式子懂吗?

我们拿1+x2来说,前面已经说过,x表示砝码,x的指数表示重量,即这里就是一个质量为2的砝码,那么前面的1表示什么?1代表重量为2的砝码数量为0个。(理解!)

不知道大家理解没,我们这里结合前面那句话:

“把组合问题的加法法则和幂级数的t的乘幂的相加对应起来”

1+x2表示了两种情况:1表示质量为2的砝码取0个的情况,x2表示质量为2的砝码取1个的情况。

 

这里说下各项系数的意义:

在x前面的系数a表示相应质量的砝码取a个,而1就表示相应砝码取0个,这里可不能简单的认为相应砝码取0个就该是0*x2(想下为何?结合数学式子)。

所以,前面说的那句话的意义大家可以理解了吧?

 

几种砝码的组合可以称重的情况,可以用以上几个函数的乘积表示:

(1+x)(1+x2)(1+x3)(1+x4)

=(1+x+x2+x3)(1+x3+x4+x7)

=1+x+x2+2×3+2×4+2×5+2×6+2×7+x8+x9+x10

从上面的函数知道:可称出从1克到10克,系数便是方案数。(!!!经典!!!)

例如右端有2×5 项,即称出5克的方案有2:5=3+2=4+1;同样,6=1+2+3=4+2;10=1+2+3+4。

故称出6克的方案有2,称出10克的方案有1 。

接着上面,接下来是第二种情况:

 

求用1分、2分、3分的邮票贴出不同数值的方案数:

大家把这种情况和第一种比较有何区别?第一种每种是一个,而这里每种是无限的。

 

以展开后的x4为例,其系数为4,即4拆分成1、2、3之和的拆分数为4;

即 :4=1+1+1+1=1+1+2=1+3=2+2

这里再引出两个概念整数拆分和拆分数(没有顺序):

所谓整数拆分即把整数分解成若干整数的和(相当于把n个无区别的球放到n个无标志的盒子,盒子允许空,也允许放多于一个球)。

整数拆分成若干整数的和,办法不一,不同拆分法的总数叫做拆分数。

 

#include <iostream>
using namespace std;

const int N=120;
int f[N+1],a[N+1],g[N+1];
int i,j,k,n,m;

int main()
{
 while(cin>>n)
 {
  for (i = 0; i <= n; ++i) // 母函数第一个因子,全为1 
   f[i]=1;

  for (i = 2; i <= n; ++i) // f[]保存前面i-1个因子相乘的结果 
  {
   for (j = 0; j <= n; ++j)
    a[j]=0;
   j=0;
   while (j <= n)   // a[j]=k表示的是k*(x^j),a[]数组表示母函数的第i个因子
   {
    a[j]=1;
    j+=i;
   }

   for (j = 0; j <= n; ++j) // 暂存f[]*a[]的结果
    g[j] = 0;

   for (j = 0; j <= n; ++j) 
    for(k = 0; k <= n-j; ++k)
     g[j+k] += f[j]*a[k]; // 为了不让f[]的值因为改动而影响以后的值,用g[]来暂存结果 
   // 两个母函数的因子相乘,若f[j],a[k]分别属于第1、2个因子,那么f[j]*(x^j)*a[k]*(x^k)==f[j]*a[k]*(x^(j+k)) 
   // 故有g[j+k]+=f[j]*a[k]  
   for (j = 0; j <= n; ++j) 
    f[j] = g[j];
  }
  cout<<f[n]<<endl;
 }
 return 0;
}

 


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.