最大子序列和
动态规划的算法：
#include<stdio.h>
int MaxSubsequenceSum(const int A[],int n)
{
int i,sum,MaxSum;
sum=MaxSum=0;
for(i=0;i<n;i++)
{
sum+=A[i];
if(sum>MaxSum)
MaxSum=sum;
if(sum<0)
sum=0;
}
return MaxSum;
}
void main()
{
int arr[10]={3,4,-2,5,-4,6,-2,8,-9,-23};
int max=MaxSubsequenceSum(arr,10);
printf("%d
",max);
}
最小公共子序列的和
#include<stdio.h>
int MinSubsequenceSum(const int A[],int n)
{
int i,sum,MinSum;
sum=MinSum=0;
for(i=0;i<n;i++)
{
sum+=A[i];
if(sum<MinSum)
MinSum=sum;
if(sum>0)
sum=0;
}
return MinSum;
}
void main()
{
int arr[10]={3,4,-2,5,-4,6,-2,8,-9,-23};
int min=MinSubsequenceSum(arr,10);
printf("%d
",min);
}
非递归版求幂函数
#include<stdio.h>
int MinSubsequenceSum(const int A[],int n)
{
int i,sum,MinSum;
sum=MinSum=0;
for(i=0;i<n;i++)
{
sum+=A[i];
if(sum<MinSum)
MinSum=sum;
if(sum>0)
sum=0;
}
return MinSum;
}
void main()
{
int arr[10]={3,4,-2,5,-4,6,-2,8,-9,-23};
int min=MinSubsequenceSum(arr,10);
printf("%d
",min);
}
参考如下：
快速求正整数次幂，当然不能直接死乘。举个例子：
3 ^ 999 = 3 * 3 * 3 * … * 3
直接乘要做998次乘法。但事实上可以这样做，先求出2^k次幂：
3 ^ 2 = 3 * 3
3 ^ 4 = (3 ^ 2) * (3 ^ 2)
3 ^ 8 = (3 ^ 4) * (3 ^ 4)
3 ^ 16 = (3 ^ 8) * (3 ^ 8)
3 ^ 32 = (3 ^ 16) * (3 ^ 16)
3 ^ 64 = (3 ^ 32) * (3 ^ 32)
3 ^ 128 = (3 ^ 64) * (3 ^ 64)
3 ^ 256 = (3 ^ 128) * (3 ^ 128)
3 ^ 512 = (3 ^ 256) * (3 ^ 256)
再相乘：
3 ^ 999
= 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)
= (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3
这样只要做16次乘法。即使加上一些辅助的存储和运算，也比直接乘高效得多（尤其如果这里底数是成百上千位的大数字的话）。
我们发现，把999转为2进制数：1111100111，其各位就是要乘的数。这提示我们利用求二进制位的算法（其中mod是模运算）：
REVERSE_BINARY(n)
1 while (n > 0)
2 do output (n mod 2)
3 n ← n / 2
这个算法给出正整数n的反向二制进位，如6就给出011（6的二进制表示为110）。事实上这个算法对任意的p进制数是通用的，只要把其中的2换成p就可以了。
如何把它改编为求幂运算？我们发现这个算法是从 低位向高位做的，而恰好我们求幂也想从低次幂向高次幂计算（参看前面的例子）。而且我们知道前面求出的每个2^k次幂只参与一次乘法运算，这就提示我们并 不把所有的中间结果保存下来，而是在计算出它们后就立即运算。于是，我们要做的就是把输出语句改为要做的乘法运算，并在n减少的同时不断地累积求2^k次 幂。
还是看算法吧：
POWER_INTEGER(x, n)
1 pow ← 1
2 while (n > 0)
3 do if (n mod 2 = 1)
4 then pow ← pow * x
5 x ← x * x
6 n ← n / 2
7 return pow
不难看出这个算法与前面算法的关系。在第1步给出结果的初值1，在while循环内进行运算。3、4中的if语句就来自REVERSE_BINARY的输出语句，不过改成了如果是1则向pow中乘。5句则是不断地计算x的2^k次幂，如对前面的例子就是计算2^2、2^4、2^8、…、2^512。
应该指出，POWER_INTEGER比 前面分析的要再多做两次乘法，一次是向pow中第一次乘x，如2^1也要进行这个乘法；另一次则是在算法的最后，n除以2后该跳出循环，而前面一次x的自 乘就浪费掉了（也可以考虑改变循环模式优化掉它）。另外，每趟while循环都要进行一次除法和一次模运算，这多数情况下除法和模运算都比乘法慢许多，不 过好在我们往往可以用位运算来代替它。
相应的C++代码如下
NumberType pow_n(NumberType x, unsigned int n)
{
NumberType pw = 1;
while (n > 0) {
if ((n % 2) == 1)
pw *= x;
x *= x;
n /= 2;
}
return pw;
}
进行简单的优化后则有：
NumberType optimized_pow_n(NumberType x, unsigned int n)
{
NumberType pw = 1;
while (n > 0) {
if (n & 1) // n & 1 等价于 (n % 2) == 1
pw *= x;
x *= x;
n >>= 1; // n >>= 1 等价于 n /= 2
}
return pw;
}
注1：快速求幂算法POWER_INTEGER常被写成递归的形式，算法实质完全相同，但却是无必要的。
注2：这个算法并不是做乘法数最少的，但多数情况下是足够快并且足够简单的。如果单纯追求做乘法数最少，则未必应该用2^k次幂进行计算。如果还允许做除法，则问题会进一步复杂化。
如：
x ^ 2 = x * x
x ^ 4 = (x ^ 2) * (x ^ 2)
x ^ 8 = (x ^ 4) * (x ^ 4)
x ^ 16 = (x ^ 8) * (x ^ 8)
x ^ 31 = (x ^ 16) * (x ^ 8) * (x ^ 4) * (x ^ 2) * x
要8次乘法。
x ^ 2 = x * x
x ^ 4 = (x ^ 2) * (x ^ 2)
x ^ 8 = (x ^ 4) * (x ^ 4)
x ^ 10 = (x ^ 8) * (x ^ 2)
x ^ 20 = (x ^ 10) * (x ^ 10)
x ^ 30 = (x ^ 20) * (x ^ 10)
x ^ 31 = (x ^ 30) * x
只要7次乘法。
x ^ 2 = x * x
x ^ 4 = (x ^ 2) * (x ^ 2)
x ^ 8 = (x ^ 4) * (x ^ 4)
x ^ 16 = (x ^ 8) * (x ^ 8)
x ^ 32 = (x ^ 16) * (x ^ 16)
x ^ 31 = (x ^ 32) / x
只要6次乘或除法。
不过具体得出上述乘（除）法数更少的算法会变得相当复杂，在许多情况下时间收益还会得不偿失。因此往往并不实用。ACM Japan 2006中有一道题即要求计算最少乘法数，可参看：
http://acm.pku.edu.cn/JudgeOnline/problem?id=3134
不大于N的所有素数
算法如下：
#include<stdio.h>
#include<math.h>
void Sieve(int n)
{
int p,j,i;
int A[n+1],L[n+1];
for(p=2;p<=n;p++)
A[p]=p;
for(p=2;p<=sqrt(n);p++)
{
if(A[p]!=0)
{
j=p*p;
while(j<n)
{
A[j]=0;
j=j+p;
}
}
}
i=0;
for(p=2;p<=n;p++)
{
if(A[p]!=0)
{
L[i]=A[p];
i++;
}
}
for(p=0;p<i;p++)
printf("%d ",L[p]);
printf("
");
}
void main()
{
Sieve(25);
}
链表实现多项式求和求积
#include <iostream>
#include <cstdio>
#include<cstdlib>
using namespace std;
struct Node {
double coef;
int expn;
Node *next;
};
void CreatPolynomial(Node *&head, int n) // 生成带表头结点的单链表，除头结点外另生成n个结点
{
head = (Node *)malloc(sizeof(Node));
head->coef = 0;
head->expn = 0;
head->next = NULL; // 初始化头结点
cout << "请输入各项系数及指数：" << endl;
Node *p = head;
for(int i = 0; i < n; i++) {
p->next = (Node *)malloc(sizeof(Node)); // 生成新结点，尾插入生成链表
p = p->next;
cin >> p->coef >> p->expn;
p->next = NULL;
}
}
void PrintPolynomial(Node *&head)
{
if(head->next == NULL) // 结果是0时直接输出0
putchar('0');
else {
for(Node *p = head->next; p != NULL; p = p->next) {
if(p != head->next && p->coef >0) // 当p非首项且指向的系数为正时才输出'+'
putchar('+'); // 之前只判定了p->coef >0
if(p->coef == 1) { // 系数为1或-1时特殊处理
if(p->expn == 0)
putchar('1'); // 判断条件不能写在一起：
} // if(p->coef == 1 && p->expn == 0) putchar('1');
else if(p->coef == -1)
putchar('-');
else
cout << p->coef;
switch(p->expn) { // 指数为0或1时特殊处理
case 0:
break;
case 1:
putchar('x');
break;
default:
p->expn < 0 ? printf("x^(%d)", p->expn) : printf("x^%d", p->expn); // 指数小于0时打括号
break;
}
}
}
cout << endl;
}
// 上面的函数中若系数为int型，那么也可以改为switch结构，这是C语言的缺陷？
void Free(Node *&head)
{
Node *q = NULL;
for(Node *p = head; p != NULL; p = q) {
q = p->next;
free(p);
}
}
char cmp(int a, int b)
{
if(a > b)
return '>';
if(a < b)
return '<';
return '=';
}
//求乘积
Node * mul(Node *&pA,Node *&pB)
{
cout<<"mul :"<<endl;
Node *ha=pA->next;
Node *hb=pB->next;
Node *pC=(Node*)malloc(sizeof(Node));
Node *p=pC;
while(ha)
{
hb=pB->next;
while(hb)
{
p=pC;
int expn=ha->expn+hb->expn;
double coef=ha->coef*hb->coef;
cout<<expn<<" mul "<<coef<<endl;
while(p->next&&p->next->expn!=expn)
{
p=p->next;
}
if(!p->next)
{
Node* new1=(Node*)malloc(sizeof(Node));
new1->expn=expn;
new1->coef=coef;
p->next=new1;
new1->next=NULL;
}
else if(p->next->expn==expn)
{
p->next->expn=expn;
p->next->coef+=coef;
}
hb=hb->next;
}
ha=ha->next;
}
return pC;
}
void AddPolynomial(Node *&pA, Node *&pB) // 传进两个链表的头指针
{
Node *ha = pA;
Node *hb = pB;
Node *qa = ha->next; // ha, hb分别跟在qa, qb的后一位置
Node *qb = hb->next; // qa, qb分别指向Pa, Pb中当前比较元素
while(qa && qb)
{
double sum = 0;
int a = qa->expn;
int b = qb->expn;
switch( cmp(a, b) ) {
case '<':
ha = qa;
qa = qa->next; // 非ha = ha->next;
break;
case '=':
sum = qa->coef + qb->coef;
if(sum != 0.0) {
qa->coef = sum;
ha = qa;
}
else {
if(ha->next != qa)
cout << "Error: ha->next != qa" << endl;
ha->next = ha->next->next; // 删除和为0的结点，ha不变，还在qa后一位置
free(qa);
}
if(hb->next != qb)
cout << "Error: hb->next != qb" << endl;
hb->next = hb->next->next;
free(qb);
qb = hb->next;
qa = ha->next;
break;
case '>':
hb->next = hb->next->next; // 删除qb指向的结点
qb->next = ha->next; // 将qb插入ha后qa前
ha->next = qb;
qb = hb->next; // not qb = ha->next
ha = ha->next;
break;
default:
cout << "Error!" << endl;
break;
}
}
if(qb)
ha->next = qb;
free(hb);
}
int main(void)
{
// freopen("cin.txt", "r", stdin);
Node *A = NULL;
Node *B = NULL;
int lenA;
int lenB;
while(cout << "请输入A的项数：" << endl, cin >> lenA) {
CreatPolynomial(A, lenA); // 生成A链表
cout << "请输入B的项数：" << endl; // 生成B链表
cin >> lenB;
CreatPolynomial(B, lenB);
cout << " A = "; // 输出A链表
PrintPolynomial(A);
cout << " B = "; // 输出B链表
PrintPolynomial(B);
cout<<"A*B= ";
Node *C=mul(A,B);
PrintPolynomial(C);
AddPolynomial(A, B); // A = A + B
cout << "A+B= ";
PrintPolynomial(A); // 输出和
cout << endl;
Free(A); // 务必释放结点
}
return 0;
}