一.小数化分数2（简直就是个数学题）
整数化小数，不循环的小数容易化。对于循环小数化分数原理如下：
⑴ 把0.4747……和0.33……化成分数。
例1： 0.4747×100=47.4747
0.4747×100－0.4747=47.4747－0.4747
(100－1)×0.4747=47
即99×0.4747=47
那么 0.4747=47/99
例2： 0.33×10＝3.33
0.33×10－0.33=3.33－0.33
(10-1) ×0.33=3
即9×0.33=3
那么0.33=3/9=1/3
关键：化去无限的循环部分，需要无限循环减去无限循环。
⑵把0.4777……和0.325656……化成分数。
例1：0.4777×10=4.777①
0.4777×100=47.77②
用②－①即得:
0.4777×90=47－4
所以, 0.4777=43/90
例2：0.325656×100=32.5656①
0.325656×10000=3256.56②
用②－①即得:
0.325656×9900=3256.5656－32.5656
0.325656×9900=3256－32
所以, 0.325656=3224/9900
综上所述：就是要非循环部分提前到整数部分，之后再做差。
具体公式可以总结为：
设虚线循环小数为：0.abc(efgh)。括号表示为无限循环的部分。
- 应到求得abcefgh.efgh,和abc.efgh.然后做差得到（abcefgh-abc）
- 即：abcefgh.efgh-abc.efgh=0.abcefgh*（10^7-10^3）=abcefgh-abc
- 设非循环体长度为l1，循环体长度为l2。
- 0.abc(efgh)=（abcefgh-abc）/（10^(l1+l2)-10^l1）
- 无限循环小数=（非循环体+循环构成的整数-循环体构成整数）/（10^(l1+l2)-10^l1）
代码实现如下：
#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a,int b){
return b==0? a:gcd(b,a%b);
}
int main(){
string s;
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--,cin>>s){
int headl=0,head=0;
int loopl=0,loop=0;
int totl=s.length();
int i,fz,fm;
for(i=2;i<totl;i++){
if(s[i]=='('){
break;
}
head=head*10+s[i]-'0';
}
headl=i-2;
if(i!=totl){//有无限循环小数的情况
loopl=totl-2-i;
for(int j=i+1;j<totl-1;j++){
loop=loop*10+s[j]-'0';
}
fz=head*pow(10.0,loopl)+loop-head;
fm=pow(10.0,totl-4)-pow(10,headl);
}
else{//没有无限循环小数的情况
fz=head;
fm=pow(10.0,headl);
}
int GCD=gcd(fz,fm);
fz=fz/GCD;
fm=fm/GCD;
printf("%d/%d\n",fz,fm);
if(t==0)
break;
}
return 0;
}
ps：化简成分数：是通过求得分子分母的最大公因数之后，分子分母分别除以这个最大公因数得到互质的分子分母。
二.整数划分问题（介绍三种大法解决此问题:递归，动态规划，母函数)
本题参考：算法中的一个经典命题之一:整数划分问题
所谓整数划分，是指把正整数n拆分成许多小项的和，和为n。例如：4=4+0=3+1=2+2=1+1+2=1+1+1+1（一共有五个划分）。（ps：4=1+3和4=3+1被认为是同一个划分。）
现在就是要求出这些划分的划分数量。例如输入n=4.输出划分上=5
算法核心思想：把一个正整数n划分如下形式： n=m1+m2+m3+….+mi;（其中mi为正整数，并且1<=mi<=n），则{m1,m2,m3,….,mi}为n的一个划分。 如果{m1,m2,m3,….,mi}中的最大值不超过m，即max{m1,m2,m3,….,mi} <= m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m)；。这个题目的想法就是：n的划分看成n的一个m划分。该问题是求出n的所有划分个数，即f(n,n)。
1.递归法和动态规划法
下面我们考虑求f(n,m)的方法：（n划分中的所有小项必须<=m）
根据n和m的关系，考虑下面几种情况：
（1）当n=1时，不论m的值为多少（m>0），只有一种划分，即{1}；
（2）当m=1时，不论n的值为多少（n>0），只有一种划分，即{1,1,....1,1,1}；
（3）当n=m时，根据划分中是否包含n，可以分为两种情况：
（a）划分中包含n的情况，只有一个，即{n}；
（b）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有（n-1）划分=f(n,n-1)；
因此，f(n,n) = 1 + f(n, n - 1)。
（4）当n<m时，n的划分中最大值不过是n,划分中不可能出现负数，因此就相当于n<m时候f(n,m)=f(n,n)；
（5）当n>m时，根据划分中是否包含m，可以分为两种情况：
（a）划分中包含m的情况，即{m,{x1,x2,x3,...,xi}}，
其中{x1,x2,x3,...,xi}的和为n-m，并且{x1,x2,x3,...,xi}可能再次出现m，因此是（n-m）的m划分，因此这种划分个数为f(n-m, m)；
（b）划分中不包含m的情况，则划分中所有值都比m小，即n的（m-1）划分，个数为f(n, m - 1)；
因此，f(n,m) = f(n - m,m) + f(n, m - 1)。 ##### a.递归 综合以上各种情况，可以看出，上面的结论具有递归定义的特征：
- 其中（1）和（2）属于递归的终止条件条件
- （3）和（4）属于特殊情况
- 情况（5）为通用情况，属于递归的方法，其本质主要是通过减少n或m以达到递归终止条件，结束递归调用，从而解决问题。
递归表达式如下：
递归代码（时间复杂度高，n很大时运行慢，递归进行了很多重复计算，很可能TLE）：
#include<iostream>
using namespace std;
int divide(int n,int m){//n的m划分。就是n中划分出来的所有当个值均小于等于m
if(n==1)
return 1;
if(m==1)
return 1;
if(n<m)
return divide(n,n);
if(n>m)
return divide(n-m,m)+divide(n,m-1);
if(n==m)
return 1+divide(n,m-1);
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
printf("%d\n",divide(n,n));//n的划分，就是divide(n,n)
}
return 0;
}
递归优化版（此版本使用数组标记，如果之前计算过，则直接调用数组中内容，否则计算子递归，这样保证了每次计算一次，减少冗余量）：
#include <iostream>
#define MAXNUM 100 //最高次数
unsigned long ww[MAXNUM*11][MAXNUM*11];
unsigned long dynamic_GetPartitionCount(int n, int max);
using namespace std;
int main(int argc, char **argv)
{
int n;
int m;
unsigned long count;
while(1)
{
cin>>n;
cout<<dynamic_GetPartitionCount(n,n)<<endl;
}
return 0;
}
unsigned long dynamic_GetPartitionCount(int n, int max)
{
if(n == 1 || max == 1)
{
ww[n][max]=1;
return 1;
}
if(n < max)
{
ww[n][n]=ww[n][n]? ww[n][n] : dynamic_GetPartitionCount(n, n);
return ww[n][n];
}
if(n == max)
{
ww[n][max]=ww[n][n-1]?1+ww[n][n-1]:1 + dynamic_GetPartitionCount(n, n - 1);
return ww[n][max];
}
else
{
ww[n][max]=ww[n - max][max]? (ww[n - max][max]) : dynamic_GetPartitionCount(n - max, max);
ww[n][max]+=ww[n][max-1]? (ww[n][max-1]): dynamic_GetPartitionCount(n, max - 1);
return ww[n][max];
}
}
b.动态规划
考虑到使用递归中，很多的子递归重复计算，这样不仅在时间开销特别大，这也是运算太慢的原因，比如计算130的时候需要27秒钟，在计算机200的时候….计算10分钟还没计算出来。。。鉴于此，可以使用动态规划的思想进行程序设计（减少重复计算），原理如同上面一样，分成三种大情况，只是使用一个数组来代替原有的递归。
ps：考虑到计算ww[10][10]=ww[10][9]+1;所以在每次计算中都是用到之前的记录，这样就可以先从小到大计算出程序，使得计算较大数的时候调用已经计算出的较小的记录（因此循环从1到n进行），程序直接是用循环就可以完成任务，避免了重复计算和空间栈的开销。
递归代码如下：
#include<iostream>
#include<memory.h>
using namespace std;
int dp[1000][1000];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(dp,0,sizeof(dp));
int m=n;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j==1||i==1){
dp[i][j]=1;
continue;
}
if(i<j)
dp[i][j]=dp[i][i];
else if(i==j){
dp[i][j]=1+dp[i][j-1];
}
else if(i>j){
dp[i][j]=dp[i-j][j]+dp[i][j-1];
}
}
}
cout<<dp[n][n]<<endl;
}
return 0;
}
2.母函数
生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。生成函数有普通型生成函数和指数型生成函数两种。形式上说，普通型生成函数用于解决多重集的组合问题，而指数型母函数用于解决多重集的排列问题。母函数还可以解决递归数列的通项问题（例如使用母函数解决斐波那契数列的通项公式）。
所谓母函数，即为关于x的一个多项式G(x)：有G(x) = a0 + a1x + a2x^2 + a3*x^3 + ……则我们称G(x)为序列(a0, a1, a2,…..)的母函数。也就是，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。 如：序列{0,1，2，3，4，5…n}的生成函数（母函数）为：g(x)=0+x+2x^2+3x^3+4x^4+…+nx^n
以上介绍完母函数，先从母函数这个角度来考虑整数拆分的问题：
- 我们从整数划分考虑，假设n的某个划分中，1的出现个数记为a1，2的个数记为a2，…..，i的个数记为ai，显然有：ak <= n/k（0<= k <=n）因此n的划分数f(n,n)，也就是从1到n这n个数字抽取这样的1,2,3……n组合，每个数字理论上可以无限重复出现，即个数随意，使它们的综合为n。
- 显然，数字i可以有如下可能，出现0次（即不出现），1次，2次，……，k次等等。把数字i出现一次用（x^i）表示，出现k次的数字i用（x^(i*k)）表示，不出现用x^0=1表示。
-
例如，数字2用x^2表示，2个2用x^4表示，3个2用x^6表示，k个2用x^2k表示。
- 对于1这个数字可以出现n/1=n次，用母函数表示为： (1 + x + x^2 + x^3 + … + x^n)
- 对于2这个数字可以出现n/2次（除不尽的均向下取整)，用母函数表示为：(1 + x^2 + x^4 + x^6 + ….+x^(n/2))
- 分别考虑1，2……n的所有数字的出现次数的母函数……
- 则对于从1到N的所有可能组合结果我们可以表示为： - G(x) = ( 1 + x + x^2 + x^3 + … + x^n)* (1 + x^2 + x^4 + x^6 + ….)….(1 + x^n)= g(x,1)* g(x,2)* g(x,3)* ….* g(x,n)= a0 + a1* x + a2* x^2 +…+ an*x^n + ….//展开式
-
- 上面的表达式中，每个括号内的多项式代表了数字i的参与到划分中的所有可能情况。因此，该多项式展开后，由于x^a *x^b = x^(a+b)，因此x^i（x^(a+b)）就代表了i(a+b)的划分（i被划分为a+b），展开后（x^i）项的系数也就是i的所有划分个数，即n的划分数就是x^n的系数f(n,n) = an。
ps：例如5*x^4,就是整数4的划分数为5.这个次数4可以是4+0,1+3,2+2,1+1+2,1+1+1+1组成，也就是x^4=x^(4+0)=x^(1+3)=x^(2+2)=x^(1+1+2)=x^(1+1+1+1)
由此我们找到了关于整数划分的母函数G(x)；剩下的问题就是，我们需要求出G(x)的展开后的所有系数。为此，我们首先要做多项式乘法:我们把一个关于x的多项式用一个整数数组a[]表示，a[i]代表x^i的系数，即：g(x) = a[0] + a[1]x + a[2]x^2 + … + a[n]x^n; 则关于多项式乘法的代码如下，其中数组a和数组b表示两个要相乘的多项式，结果存储到数组c中。
代码如下：
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N=10005;
int c1[N],c2[N]; //c1储存最后的答案，表示当前已经乘上的多项式的各项系数值。c[i]=m表示次幂为i的x^i项的系数为m
//c2用于过渡
int main()
{
int n,i,j,k;
while(cin>>n)
{
if(n==0) break;
for(i=0;i<=n;i++)
{
c1[i]=1;
c2[i]=0;
}
for(i=2;i<=n;i++)//i表示要构成整数n的小项.一个i对应一整个括号的多项式
{
for(j=0;j<=n;j++) //比如n=4，虽然组合数=(1+x+x^2+x^3+x^4)*(1+x^2+x^4)*(1+x^3)*(1+x^4)
//但是这个表达式能够达到的最高次幂是4+4+3+4=15次幂，但是我们只要找到x^4次幂.所以这里遍历的之后都n作为终止
//大于n的次幂，不需要计算
//观察会发现每个每次乘完一个多项式，结果的次幂都是连续的从0-n+(n/i)*i。所以从0-n肯定次幂更是连续的。所以每次遍历只要j++从0-n次幂遍历即可
for(k=0;k+j<=n;k+=i) //k用于遍历新的多项式的次幂 ，j是前几个多项式的次幂
c2[k+j]+=c1[j]; //因为新的多项式系数都为1，所以新多项式系数*前几个多项式系数=前几个多项式系数，所以对c1来说这个操作相当于没做。
//只需要把次幂相同的项的系数（默认已经一个个小项乘完）累加即可。
for(j=0;j<=n;j++)
{
c1[j]=c2[j]; //结果赋给c1
c2[j]=0; //赋0方便累加
}
}
cout<<c1[n]<<endl;
}
return 0;
}
附题：HDU:1028：Ignatius and the Princess III
三.复杂的正整数划分
第二部分的参考中还有对于五边形数定理和树的算法分析。
对于简单的正整数划分只需要divide(n,m)，把n数做m的划分，即n划分成的k份中，每份的值都小于m. 可以参考二点中所述
复杂的正整数划分
简单的正整数划分是针对n个数划分的所有可能。那么如果题目有要求划分的条件，那么状态转移方程将有所不同。
可能出现的划分要求有：
- 将n划分成若干正整数之和的划分数。（简单正整数划分）
- 将n划分成k个正整数之和的划分数。
- 将n划分成最大数不超过k的划分数。
- 将n划分成若干奇正整数之和的划分数。
- 将n划分成若干不同整数之和的划分数。
不同情况下的状态转移方程
1.将n划分成不大于m的划分法（对划分每份的上限的要求做分类，状态量是需要划分的数以及每份数值上限）
1).若是划分多个整数可以存在相同的：
dp[n][m]= dp[n][m-1]+ dp[n-m][m]
含义：dp[n][m]表示整数 n 的划分中，每个数不大于 m 的划分数。
划分数可以分为两种情况:
a.划分中每个数都小于 m，相当于每个数不大于 m- 1, 故划分数为 dp[n][m-1].
b.划分中有一个数为 m. 那就在 n中减去 m ,剩下的就相当于把 n-m 进行划分， 故划分数为 dp[n-m][m];
（因为划分的整数可以相同，所以n-m后划分的最大上限还是m）
2).若是划分多个不同的整数：
dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]
含义：dp[n][m]表示整数 n 的划分中，每个数不大于 m 的划分数。
划分情况分为两种情况：
a.划分中每个数都小于m,相当于每个数不大于 m-1,划分数为 dp[n][m-1].
b.划分中有一个数为 m.在n中减去m,剩下相当对n-m进行划分，并且每一个数不大于m-1，故划分数为 dp[n-m][m-1].
（由于划分出的每份整数要求不同，所以n-m划分的最大上限是m-1）
2.将n划分成k个数的划分法：（对划分分数做分类，状态量是需要划分的数以及划分的份数）
dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
含义：dp[n][k],表示整数n的划分中，需要划分k份
方法可以分为两类：（分出的k份中是否包含值为1的份）
第一类: n 份中不包含 1 的分法。
为保证每份都 >= 2，可以先拿出 k 个 1 分。到每一份，然后再把剩下的 n- k 分成 k 份即可，分法有: dp[n-k][k]
（剩下n-k的值还要再分k分和原来拿出的k份1合并，使得每份必>1（即>=2））
第二类: n 份中至少有一份为 1 的分法。
可以先拿出一个 1 作为单独的1份，剩下的 n- 1 再分成 k- 1 份即可，分法有：dp[n-1][k-1]
（已经分出完成的一份1了，剩下n-1的值还需要分k-1份就可以）
3.将n划分成若干奇数的划分法：（计算奇数划分时候同时考虑偶数，状态量为需要划分的数和划分的份数）
方法一：
g[i][j] = f[i - j][j];
f[i][j] = f[i - 1][j - 1] + g[i - j][j];
含义：g[i][j]:将i划分为j个偶数
f[i][j]:将i划分为j个奇数
方法可以分为两个步骤：
第一步：g[i][j] = f[i - j][j];
i中拿出j个1分到每一份中，将剩余的i-j分成j个奇数
（这j个奇数和原来拿出的1变成j份偶数。分i为j个偶数（用g表示分偶数）=分i为1+j个奇数=分i-j为j个奇数（用f表示分奇数））
第二步：将i划分为j个奇数，等同于两种子问题的和
a.j份中包含有一份为1的情况：一份包含奇数1，剩余的i-1分成j-1个奇数（f表示分成奇数值）；
b.j份中不包含一份为1的情况：每份至少大于1，将j个1拿出来分到每一份中，其余i-j分成j份的偶数（j份的偶数和原来j份的1形成j份奇数f[i][j]）
方法二：
含义：f[i][j]表示数i划分成j个正奇数的方案数
初始值：
对于i为奇数 f[i][1]=1;f[i][2]=0;
对于i为偶数 f[i][1]=0;f[i][2]=(i/2+1)/2;
考虑f[i][j]，需满足i>=j,j>2时
若最小的正奇数是1即j份中包含有一份为1的情况。
对应的方案数是 f[i-1][j-1]
若最小的正奇数>1即j份中不包含一份为1的情况。
从每个正整数中抽调2，对应的方案数f[i-2*j][j];
(为什么要抽2个给每一份，而不是1个，原因是抽两个后还是把i-2*j的值分成j份的奇数值。如果凑1个给每份，就要引入分成j份的偶数值，也就是方法一中的g的含义)
状态转移方程：f[i][j]=f[i-1][j-1]+f[i-2*j][j];
对应代码如下：
for (int i=1;i<=n;i++){
if (i%2)
{
f[i][1]=1;
f[i][2]=0;
}
else
{
f[i][1]=0;
f[i][2]=(i/2+1)/2;
}
}
for (int i=3;i<=n;i++){
for (int j=1;j<=i;j++)
{
f[i][j]=f[i-1][j-1];
if (i-2*j>=j)
f[i][j]+=f[i-2*j][j];
}
}
for (int i=1;i<=n;i++)
ans+=f[n][i];
cout<<ans<<endl;//输出所有i分奇数组合的可能
//如果是i分成k份奇数值，那么直接输出F[i][k]
}
类似题目也可以考虑用母函数来解决。
