以下内容除了代码全都借鉴自Tianyi Cui童鞋的《背包九讲》，在此表示感谢ing
一，01背包问题
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
优化空间复杂度
以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。
过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1]，这是显然的。
有了这个过程以后，01背包问题的伪代码就可以这样写：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的细节问题
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。
一个常数优化
前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。
由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
这对于V比较大时是有用的。
小结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
code：
#include <iostream>
#include <stdlib.h>
const int MAXSIZE = 0xFFF;;
const int MINIMUM = -0xFFFF;
int cost[MAXSIZE];//数组下标从1开始
int weight[MAXSIZE];//数组下标从1开始
int f[200][MAXSIZE];
int f2[MAXSIZE];
using namespace std;
//对于要恰好装满背包的情况，只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了
//如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
int ZeroOnePack(int n, int v)//运用递归
{//前n件物品恰放入一个容量为v的背包可以获得的最大价值
int val=0;
if (v<0)
return MINIMUM;
if (n==1 && v<cost[1])
return 0;
if (n==1 && v>=cost[1])
return weight[1];
val=max(ZeroOnePack(n-1, v-cost[n])+weight[n], ZeroOnePack(n-1, v));
return val;
}
int ZeroOnePack2(int n, int v)//运用空间复杂度为O(n*v)递推
{
int i, j;
for (i=0; i<=n; i++){//初始化
for (j=0; j<=v; j++)
{
f[i][j]=0;
}
}
for (i=1; i<=n; i++)
{
for (j=0; j<=v; j++)
{
if (j>=cost[i])
f[i][j]=max(f[i-1][j-cost[i]]+weight[i], f[i-1][j]);
else
f[i][j]=f[i-1][j];
}
}
return f[n][v];
}
int ZeroOnePack3(int n, int v)//运用空间复杂度为O(n)递推
{
int i, j;
for (i=0; i<=v; i++)
{//初始化
f2[i]=0;
}
for (i=1; i<=n; i++)
{
for (j=v; j>=cost[i]; j--)
{
f2[j]=max(f2[j-cost[i]]+weight[i], f2[j]);
}
}
return f2[v];
}
//再次经过优化的ZeroOnePack3:
int ZeroOnePack3Ex(int n, int v)//运用空间复杂度为O(n)递推
{
int i, j, sum=0, bound;
for (i=0; i<=v; i++)
{//初始化
f2[i]=0;
}
weight[0]=0;
for (i=1; i<=n; i++)
{
sum+=weight[i];
}
for (i=1; i<=n; i++)
{
sum-=weight[i-1];
bound=max(v-sum, cost[i]);
for (j=v; j>=bound; j--)
{
f2[j]=max(f2[j-cost[i]]+weight[i], f2[j]);
}
}
return f2[v];
}
int main(int argc, char *argv[])
{
int N,V;
int i, res;
// freopen("01.txt", "r", stdin);
while (cin>>N>>V)
{
for (i=1; i<=N; i++)
cin>>cost[i]>>weight[i];
res=ZeroOnePack2(N, V);
cout<<res<<endl;
cout<<ZeroOnePack(N,V)<<endl;
cout<<ZeroOnePack3(N,V)<<endl;
cout<<ZeroOnePack3Ex(N,V)<<endl;
}
return 0;
}
利用在数组长度N很大的情况下能达到压缩存储的作用。一般还是用在DP题目中，因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的解，而每次用到的只是解集中的最后几个解，所以以滚动数组形式能大大减少内存开支。
用法：
#include <iostream>
using namespace std;
int d[3];
int main()
{
d[0] = 1;d[1] = 1;
for( int i = 2; i < 100; i++)
d[i % 3] = d[(i - 1) % 3] + d[(i - 2] % 3];
cout << d[99 % 3] << endl; // Fibonacci
return 0;
}
int i,,j,d[2][100];//比d[100][100]省多了
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];
// DP .
滚动数组 举个简单的例子：
int i,d[100];
d[0]=1;d[1]=1;
for(i=2;i<100;i++)
d[i]=d[i-1]+d[i-2];
printf("%d",d[99]);
上面这个循环d[i]只需要解集中的前2个解d[i-1]和d[i-2];
为了节约空间用滚动数组的方法
int d[3];
d[0]=1;d[1]=1;
for(i=2;i<100;i++)
d[i%3]=d[(i-1)%3]+d[(i-2)%3];
printf("%d",d[99%3]);
注意上面的运算，我们只留了最近的3个解，数组好象在“滚动‿一样，所以叫滚动数组
对于二维数组也可以用这种方法 例如：
int i,j,d[100][100];
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i][j]=d[i-1][j]+d[i][j-1];
上鿢的d[i][j]忪便赖于d[i-1][j],d[i][j-1];
迿用滚动数组
int i,,j,d[2][100];
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];
滚动数组实际是一种节约空间的办法，时间上没什么优势，多用于DP中，举个例子先：
一个DP，平常如果需要1000×1000的空间，其实根据DP的特点，能以2×1000的空间解决问题，并且通过滚动，获得和1000×1000一样的效果。
【Catalan数——卡特兰数】
Catalan数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。 原理：
令h(0)=1,h(1)＝1,catalan数满足递归式：
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)
该递推关系的解为：
h(n)=C(2n,n)/(n + 1) (n=1,2,3,...)
前几项为 （OEIS中的数列A000108）: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
二.Catalan数的典型应用：
1.括号化问题。矩阵链乘： P=A1×A2×A3×……×An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
2.将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数?
类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
3.出栈次序问题。一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
类似：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
类似：一位大城市的律师在他住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
分析：对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n 位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1 和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。
在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。
不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有 n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的 2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累 计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应。
显然，不符合要求的方案数为c(2n,n+1)。由此得出 输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。（这个公式的下标是从h(0)=1开始的）
1.括号化问题。
矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
2.出栈次序问题。
一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
类似：
(1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
(2)在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。
3.将多边行划分为三角形问题。
将一个凸多边形区域分成三角形区域的方法数?
类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她
从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
4.给顶节点组成二叉树的问题。
给定N个节点，能构成多少种形状不同的二叉树？
(一定是二叉树!
先去一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,就是h(0)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(0)=h(n))
（能构成h（N）个）
以前写过的一个大整数catlan数计算程序：
#include <iostream>
#include <string>
#include <iomanip>
#include <memory.h>
const long MaxLength=100;//数字最大位数是MaxLength *4
using namespace std;
class BigInt
{
public:
long *a;
long length;
long max;
BigInt()//构造函数
{
a = new long [MaxLength];
memset(a,0,sizeof(long)*MaxLength);
length = 1;
max = MaxLength;
}
BigInt(const BigInt&t)
{
long *a = new long [t.length];
for(int i=0;i<t.length;i++)
a[i] = t.a[i];
length = t.length;
max = t.max;
}
~BigInt()//析构函数
{
delete [] a;
}
void clear()//清零函数
{
memset(a,0,sizeof(long)*max);
length = 1;
}
friend ostream &operator << (ostream & output,BigInt &t)
{
output << t.a[t.length-1];
for(int i=t.length-2;i>=0;i--)
output << setw(4) << setiosflags(ios::right) << setfill('0') << t.a[i];
return output;
}
void operator = (const BigInt & t)
{
if(t.a==a)
return;
delete a;
a = new long [t.length];
for(int i=0;i<t.length;i++)
a[i] = t.a[i];
length = t.length;
}
void operator = (const string & temp)
{
int tLength = temp.length() - 1;
length=tLength/4+1;
for(int i=0;tLength>2;i++,tLength-=4)
a[i]=(temp[tLength]-'0')+(temp[tLength-1]-'0')*10+(temp[tLength-2]-'0')*100+(temp[tLength-3]-'0')*1000;
if(tLength==2)
a[length-1]=(temp[tLength]-'0')+(temp[tLength-1]-'0')*10+(temp[tLength-2]-'0')*100;
else if(tLength==1)
a[length-1]=(temp[tLength]-'0')+(temp[tLength-1]-'0')*10;
else if(!tLength)
a[length-1]=(temp[tLength]-'0');
}
BigInt operator + (const BigInt & t)
{
BigInt sum;
for(int i=0;i<t.length||i<length;i++)
{
sum.a[i]+=a[i]+t.a[i];
if(sum.a[i]>9999)
{
int j=i;
while(sum.a[j]>9999)
{
sum.a[j+1]+=sum.a[j]/10000;
sum.a[j]%=10000;
j++;
}
}
}
for(int i=sum.max-1;i>=sum.length;i--)
if(sum.a[i])
{
sum.length=i+1;
break;
}
return sum;
}
BigInt operator * (const BigInt & t)
{
BigInt product;
for(int i=0;i<t.length;i++)
for(int j=0;j<length;j++)
{
product.a[i+j]+=a[j]*t.a[i];
if(product.a[i+j]>9999)
{
int q=i+j;
while(product.a[q]>9999)
{
product.a[q+1]+=product.a[q]/10000;
product.a[q]%=10000;
q++;
}
}
}
for(int i=product.max-1;i>=product.length;i--)
if(product.a[i])
{
product.length=i+1;
break;
}
return product;
}
};
BigInt s[MaxLength+1];
int main()
{
int n;
s[0]= "1";
s[1]="1";s[2]="2";s[3]="5";
for(int i=4;i<101;i++)
for(int j=0;j<i;j++)
// s[i] = add(s[i],mult(s[j],s[i-j]));
s[i] = s[i]+s[j]*s[i-j-1];
while(cin>>n && n != -1)
{
cout<<s[n]<<endl;
}
return 0;
}
/**//*==================================================*\
| GCD 最大公约数
\*==================================================*/
int gcd(int x, int y)
{
if (!x || !y) return x > y ? x : y;
for (int t; t = x % y; x = y, y = t);
return y;
}
/**//*==================================================*\
| 快速 GCD
\*==================================================*/
int kgcd(int a, int b)
{
if (a == 0) return b;
if (b == 0) return a;
if (!(a & 1) && !(b & 1))
return kgcd(a>>1, b>>1)<<1;
else if (!(b & 1))
return kgcd(a, b>>1);
else if (!(a & 1)) return kgcd(a>>1, b);
else return kgcd(abs(a - b), min(a, b));
}
/**//*==================================================*\
| 扩展 GCD
| 求x, y使得gcd(a, b) = a * x + b * y;
\*==================================================*/
int extgcd(int a, int b, int & x, int & y)
{
if (b == 0) { x=1; y=0; return a; }
int d = extgcd(b, a % b, x, y);
int t = x; x = y; y = t - a / b * y;
return d;
}
欧几里得算法
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a – kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证.
扩展欧几里德算法
扩展欧几里德算法是用来在已知a, b求解一组p，q使得p * a+q * b = Gcd(a, b) (解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。下面是一个使用C++的实现：
int exGcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int r = exGcd(b, a % b, x, y);
int t = x;
x = y;
y = t – a / b * y;
return r;
}
把这个实现和Gcd的递归实现相比，发现多了下面的x,y赋值过程，这就是扩展欧几里德算法的精髓。
可以这样思考:
对于a’ = b, b’ = a % b 而言，我们求得 x, y使得 a’x + b’y = Gcd(a’, b’)
由于b’ = a % b = a – a / b * b (注：这里的/是程序设计语言中的除法)
那么可以得到:
a’x + b’y = Gcd(a’, b’) ===>
bx + (a – a / b * b)y = Gcd(a’, b’) = Gcd(a, b) ===>
ay +b(x – a / b*y) = Gcd(a, b)
因此对于a和b而言，他们的相对应的p，q分别是 y和(x-a/b*y)
补充：关于使用扩展欧几里德算法解决不定方程的办法
对于不定整数方程pa+qb=c，若 c mod Gcd(p, q)=0,则该方程存在整数解，否则不存在整数解。
上面已经列出找一个整数解的方法，在找到p * a+q * b = Gcd(p, q)的一组解p0,q0后，p * a+q * b = Gcd(p, q)的其他整数解满足：
p = p0 + b/Gcd(p, q) * t
q = q0 – a/Gcd(p, q) * t(其中t为任意整数)
至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(p, q)的每个解乘上 c/Gcd(p, q) 即可
#include <iostream>
using namespace std;
//int gcd(int a, int b); //两个数的最大公约数
//int ngcd(int *pa, int n) //N个数的最大公约数
//int lcm(int a, int b) //两个数的最小公倍数
//int nlcm(int *pa, int n) //N个数的最小公倍数
int gcd (int a,int b)
{
if (b==0)
return a;
return gcd(b,a%b);
}
int ngcd(int *pa, int n)
{
if(n == 1)
return *pa;
return (gcd(pa[n-1], ngcd(pa, n-1)));
}
int lcm(int a, int b) //最小公倍数 ＝ 两数乘积 / 最大公约数
{
return a*b/gcd(a, b);
}
int nlcm(int *pa, int n)
{
if(n == 1)
return *pa;
return lcm(pa[n-1], nlcm(pa, n-1));
}
int main()
{
int a,b,n,rgcd,rlcm,rngcd,rnlcm;
int pa[10];
printf("please input tow number:");
scanf("%d %d",&a,&b);
rgcd=gcd(a,b);
rlcm=lcm(a,b);
printf("最大公约数是：%d\n",rgcd);
printf("最小公倍数是：%d\n",rlcm);
printf("please input the n:");
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&pa[i]);
rngcd=ngcd(pa,n);
rnlcm=nlcm(pa,n);
printf("最大公约数是：%d\n",rngcd);
printf("最小公倍数是：%d\n",rnlcm);
return 0;
}
摘要: 整数划分是把一个正整数 N 拆分成一组数相加并且等于 N 的问题.比如:65 + 1 (序列)4 + 2, 4 + 1 + 13 + 3, 3 + 2 + 1, 3 + 1 + 1 + 12 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 11 + 1 + 1 + 1 + 1 + 1
假设F(N,M) 整数 N 的划分个数,其中 M 表示将 N 拆分后的序列中最大...
阅读全文
先筛出来效率会高一些
#include <iostream>
#include <cmath>
using namespace std;
void findPrime(int *prime, int k, int r)
{
int i;
for(i=0; i<r; i++)
prime[i]=1;
int j, t, s=-1,
u=((int)sqrt(k*1.0)-3)/2;
for(i=0; i<=u; i++)
{
if(prime[i])
{ // 是素数
prime[++s]=t=2*i+3;
for(j=2*i*(i+3)+3; j<r; j+=t)
prime[j]=0;
}
}
for(; i<r; i++)
if(prime[i])
prime[++s]=2*i+3;
prime[s+1]=k+1; // 哨兵(用作后面的因子分解中for循环的条件判断的边界)
}
void solve(int n, int *prime)
{
int m=2, k=(int)sqrt(n*1.0), r;
for(int t=-1; m<=k; m=prime[++t])
{
r=0;
for(; !(n%m); n/=m)
r++;
if(r)
{ // r>0
if(r==1) // 此时n肯定不等于1，需要继续分解
printf("%d * ",m);
else
{ // r>1
printf("%d^%d", m, r);
if(n!=1) // 需要继续分解
printf(" * ");
else { // n==1, 分解完毕，返回
printf("\n");
return;
}
}
k=(int)sqrt(n*1.0); // r>0，说明n发生了改变(才需要重新计算k值)
} // if(r)
}
printf("%d\n",n); // 输出最后一个因子
}
int main()
{
int m=1000000000,
k=(int)sqrt(m*1.0),
r=(k-1)/2,
*prime = new int[r];
findPrime(prime, k, r);
int n;
while(scanf("%d",&n)!=EOF)
{
printf("%d = ",n);
if(n==1)
{
printf("1\n");
continue;
}
solve(n, prime);
}
delete[] prime;
return 0;
}
摘要: 最大子矩阵问题：问题描述：(具体见http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1050 ) 给定一个n*n(0<n<=100)的矩阵，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最大，输出这个最大的值。Example： 0 -2 -7 0 9 ...
阅读全文
思路：首先想到的是把乘法化加法，逐步计算后500位，代码很简单，唯一的缺点就是每次提交都是超时，嘿嘿..后来看书竟然发现原来求长度有个很好的方法p*log10(2)，系统函数库果真强大。然后就是有一个公式可以把2的p次幂化为二进制求法，如果p的二进制某位为0，自然少了计算过程。
#include <cmath>
#include <iostream>
using namespace std;
#define MAX 125
unsigned int num[MAX];
unsigned int key[MAX];
void multiply(unsigned int* num,unsigned int* key)
{
unsigned int temp[MAX];
memset(temp,0,sizeof temp);
for (int i=0;i<MAX;i++)
{
int nCarry = 0;
for (int j=0;j<MAX-i;j++)
{
int nTmp = temp[i+j] + num[j]*key[i] + nCarry;
temp[i+j] = nTmp%10000;
nCarry = nTmp/10000;
}
}
memcpy(num,temp,sizeof(unsigned int)*MAX);
}
int main()
{
int m;
cin>>m;
//use the math.h ,perfect
cout<<(int)(m*log10(2.0F)+1)<<endl;
memset(num,0,sizeof num);
memset(key,0,sizeof key);
num[0] = 1;
key[0] = 2;
while (m>0)
{
if (m&1)
{
multiply(num,key);
}
multiply(key,key);
m >>= 1;
}
num[0]--;
for (int i=MAX-1;i>=0;i--)
{
if (i%25==12)
{
printf("%02d\n%02d",num[i]/100,num[i]%100);
// cout<<'.';
}
else
{
printf("%04d",num[i]);
if (i%25==0)
{
cout<<endl;
// cout<<num[i]<<endl;
}
}
}
return 0;
}