1， 最大子序列和问题(四种解法)
class Test
{
public static void Main()
{
int[] a = {-2,11,-4,13,-5,-2};
int result = MaxSubsequenceSumFour(a,6);
Console.WriteLine(result);
Console.Read();
}
public static int MaxSubsequenceSumOne(int[] A,int n)
{ //算法1
int CurSum,MaxSum=0,i,j;
for(i=0;i<n;i++)
{
CurSum = 0;
for(j=i;j<n;j++)
{
CurSum += A[j];
if(CurSum > MaxSum)
{
MaxSum = CurSum;
}
}
}
return MaxSum;
}
public static int MaxSubsequenceSumTwo(int[] A,int n)
{//算法2
int CurSum,MaxSum=0,i,j,k;
for(i=0;i<n;i++)
for(j=i;j<n;j++)
{
CurSum = 0;
for(k=i;k<=j;k++)
CurSum += A[k];
if(CurSum > MaxSum)
MaxSum = CurSum ;
}
return MaxSum;
}
public static int MaxSubsequenceSumThree(int[] A,int n)
{//算法3
return MaxSubSum( A, 0, n - 1 );
}
public static int MaxSubsequenceSumFour(int[] A,int n)
{//算法4
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for( j = 0; j < n; j++ )
{
ThisSum += A[ j ];
if( ThisSum > MaxSum )
MaxSum = ThisSum;
else if( ThisSum < 0 )
ThisSum = 0;
}
return MaxSum;
}
public static int Max3( int A, int B, int C )
{
return A > B ? A > C ? A : C : B > C ? B : C;
}
public static int MaxSubSum(int[ ] A, int Left, int Right )
{
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int Center, i;
if( Left == Right ) /* Base case */
if( A[ Left ] > 0 )
return A[ Left ];
else
return 0;
Center = ( Left + Right ) / 2;
MaxLeftSum = MaxSubSum( A, Left, Center );
MaxRightSum = MaxSubSum( A, Center + 1, Right );
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for( i = Center; i >= Left; i-- )
{
LeftBorderSum += A[ i ];
if( LeftBorderSum > MaxLeftBorderSum )
MaxLeftBorderSum = LeftBorderSum;
}
MaxRightBorderSum = 0;
RightBorderSum = 0;
for( i = Center + 1; i <= Right; i++ )
{
RightBorderSum += A[ i ];
if( RightBorderSum > MaxRightBorderSum )
MaxRightBorderSum = RightBorderSum;
}
return Max3( MaxLeftSum, MaxRightSum,MaxLeftBorderSum + MaxRightBorderSum );
}
}
2， 高效率的取幂运算
class Test
{
public static void Main()
{
Console.WriteLine(Pow( 3, 4 ));
Console.Read();
}
static long Pow( int X, int N )
{
if( N == 0 )
return 1;
if( N == 1 )
return X;
if(N%2==0) //偶数
return Pow( X * X, N / 2 );
else
return Pow( X * X, N / 2 ) * X;
}
static long PowTwo( int X, int N )
{
if( N == 0 )
return 1;
if(N%2==0)
return Pow( X * X, N / 2 );
else
return Pow( X , N -1 ) * X;
}
}
3，一元多项式运算（链表表示）
＃include<stdio.h>
＃include<malloc.h>
＃include<stdlib.h>
#define LEN sizeof(node)
typedef struct polynode
{
int coef;//系数
int exp;//指数
struct polynode *next;
}node;
node * create(void)
{
node *h,*r,*s;
int c,e;
h=(node *)malloc(LEN);//头结点
r=h;
printf("coef:");
scanf("%d",&c);
printf("exp: ");
scanf("%d",&e);
while(c!=0)
{
s=(node *)malloc(LEN);
s->coef=c;
s->exp=e;
r->next=s;
r=s;
printf("coef:");
scanf("%d",&c);
printf("exp: ");
scanf("%d",&e);
}
r->next=NULL;//表尾
return(h);
}
polyadd(node *polya, node *polyb)
{
node *p,*q,*pre,*temp;
int sum;
p=polya->next;
q=polyb->next;
pre=polya;
while(p!=NULL&&q!=NULL)
{
if(p->exp<q->exp)
{
pre->next=p;pre=pre->next;
p=p->next;
}
else if(p->exp==q->exp)
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
pre->next=p;pre=pre->next;
p=p->next;temp=q;q=q->next;free(temp);
}
else
{temp=p->next;free(p);p=temp;
temp=q->next;free(q);q=temp;
}
}
else
{pre->next=q;pre=pre->next;
q=q->next;
}
}
if(p!=NULL)
pre->next=p;
else
pre->next=q;
}
void print(node * p)
{
while(p->next!=NULL)
{
p=p->next;
printf(" %d*x^%d",p->coef,p->exp);
}
}
main()
{
node * polya,* polyb;
printf("Welcome to use!\n");
printf("\nPlease input the ploya include coef && exp:\n");
polya=create();
print(polya);
printf("\nPlease input the ployb include coef && exp:\n");
polyb=create();
print(polyb);
printf("\nSum of the poly is:\n");
polyadd(polya,polyb);
print(polya);
printf("\n");
}
datastruct.h
typedef struct list
{
int c; //多项式的项数
int e; //多项式的指数
struct list *next; //下一结点
};
typedef struct list *LinkList;
typedef struct list Node;
另一个示例:
//File: ListOper.h
#ifndef DATASTRUCT
#define DATASTRUCT
#include "datastruct.h"
#endif
//some functions declaretioin
bool CreateList(LinkList &L);
Node *CreateNode(int e, int c);
void FreeList(LinkList &L);
void SortList(LinkList &L);
void DeleteNextNode(Node *d);
void SweepNextNode(Node *s);
void OutPutList(LinkList &L);
相关函数的实现，对应文件ListOper.cpp:
//File: ListOper.cpp
#include <stdlib.h>
#include <iostream>
#ifndef DATASTRUCT
#define DATASTRUCT
#include "datastruct.h"
#endif
#include "ListOper.h"
using namespace std;
bool CreateList(LinkList &L)
{
//TODO: 创建线性链表
Node *head;
head=(Node *)malloc(sizeof(Node));
if(head==NULL)
{
cout << "内存分配错误" << endl;
return false;
}
head->next=NULL;
head->c=0;
head->e=0;
L=head;
return true;
}
Node *CreateNode(int e, int c)
{
//TODO: 创建结点
Node * pos;
pos=(Node *)malloc(sizeof(Node));
if(pos==NULL)
{
cout << "内存分配错误" << endl;
exit(1);
}
pos->e=e;
pos->c=c;
pos->next=NULL;
return pos;
}
void FreeList(LinkList &L)
{
//TODO: 释放整个线性表所占用的内存空间
Node *pos;
Node *next;
pos=L;
while(pos!=NULL)
{
next=pos->next;
free(pos);
pos=next;
}
}
void SortList(LinkList &L)
{
bool flag=true; //是否需要排序标志
Node *head=L->next;
Node *pos;
Node *last;
Node *temp;
if(head->next==NULL)
{
return;
}
while(flag)
{
flag=true;
last=head;
pos=last->next;
if(last==NULL||last->next==NULL)
{
break;
}
while(last!=NULL && last->next!=NULL)
{
flag=false;
pos=last->next;
if(last->e<pos->e) //哈哈哈哈哈，HTML代码
{
SweepNextNode(last);
flag=true;
}
if(last->e==pos->e)
{
last->c+=pos->c;
DeleteNextNode(last);
flag=true;
/*last=last->next;
pos=last->next;*/
}
last=last->next;
}
}
}
void DeleteNextNode(Node *d)
{
Node *temp;
temp=d->next;
d->next=temp->next;
free(temp);
}
void SweepNextNode(Node *s)
//一点偷懒的办法，只交换值，不修改指针
{
int c,e;
c=s->c;e=s->e;
s->c=s->next->c;s->e=s->next->e;
s->next->c=c;s->next->e=e;
}
void OutPutList(LinkList &L)
{
Node *pos;
pos=L->next;
cout << "输出表达式：";
while(pos!=NULL)
{
if(pos->c>0)
{
cout << "+";
}
if(pos->c!=1)
{
cout << pos->c;
}
if(pos->e!=0)
{
cout << "x^";
cout << pos->e;
}
pos=pos->next;
}
cout << endl;
}
主单元文件main.cpp:
#include <iostream>
#include <stdlib.h>
#include <ctype.h>
#include "ListOper.h"
using namespace std;
LinkList AnayString(char aString[], int aLength);
int main(int argc, char *argv[]) //-------------------------------
{
LinkList L;
char InStr[1024];
int len;
cout << "一元稀疏多项式计算器" << endl;
cout << "请输入一个1024个字符以内的稀疏多项式：";
cin >> InStr;
len=strlen(InStr);
L=AnayString(InStr,len);
SortList(L);
OutPutList(L);
FreeList(L);
system("PAUSE");
return 0;
}
LinkList AnayString(char aString[], int aLength) //---------------
//TODO: 字符串分析函数
{
LinkList L=NULL;
Node *pos=NULL;
Node *last;
Node *head;
CreateList(L);
head=L;
last=head;
int c=0;
int e=0;
char temp[1];
char tp;
bool plus=true;
char status='n'; //状态指示符,我省略了系数为负的情况
/*
n: 非运算状态
c: 正在计算系数
e: 正在计算指数
p: 指数为0
f: 完成了一个项目的输入
*/
for(int i=0;i<aLength;i++)
{
temp[0]=aString[i];
tp=temp[0];
switch(status)
{
case 'n':
{
c=0;e=0;
status='c';
if(tp=='-')
{
plus=false;
continue;
}
if(isdigit(tp))
{
c=atoi(temp);
continue;
}
if(tp=='x')//多项式以x开头
{
c=1;
status='e';
continue;
}
}
case 'c':
{
if(isdigit(aString[i]))
{
if(plus)
{
c=c*10+atoi(temp);
}
else
{
c=c*10-atoi(temp);
}
continue;
}
if(tp=='x')
{
if(c==0)
{
c=1;
}
status='e';
e=0;
continue;
}
//此处考虑了常数项出现在其他位置的可能
if(tp=='+')
{
plus=true;
status='p';
continue;
}
if(tp=='-')
{
plus=false;
status='p';
continue;
}
/*if(temp[0]=='^')
{
status='e';
e=0;
continue;
}*/ //此种情况不可能出现
continue;
} //正在解析系数
case 'e':
{
if(tp=='^')
{
continue;
}
if(isdigit(tp))
{
e=e*10+atoi(temp);
continue;
}
if(tp=='+')
{
plus=true;
status='f';
continue;
}
if(tp=='-')
{
plus=false;
status='f';
continue;
}
} //正在解析系数
case 'p':
{
e=0;
status='f';
continue;
}
case 'f':
{
pos=CreateNode(e,c);
last->next=pos;
last=pos;
c=0;e=0;
status='c';
i--;
continue;
}
}
}
pos=CreateNode(e,c);
last->next=pos;
return L;
}
4， 中缀表达式转换为后缀表达式
#include<iostream.h>
const int MAX=40;
void main(void){
char infix[MAX]={'#'};
char oprator[MAX]={'@','#'};
int opr=1;
char postfix[12]={'#'};
int post=0;
int i,j,cnt=0,cntl;
char c;
//输入表达式，以等号结束
cin.get(c);
while(c!='='){
infix[cnt]=c;
cnt++;
cin.get(c);
}
cntl=cnt;
for(i=0;i<cnt;i++){
switch(infix[i]){
//左括号就直接入栈
case '(':
cntl=cntl-2;
oprator[opr]=infix[i];
opr++;
break;
//右括号则先退栈，直到遇见第一个左括号
case ')':
for(j=opr-1;j>0;j--){
if(oprator[j]!='('){
postfix[post]=oprator[j];
oprator[j]='#';
post++;
}
else{
oprator[j] = '#';
break;
}
}
opr=j;
break;
case '*':
case '/':
//如果前一个运算符为*或/，则先退栈,再入栈,否则直接入栈
if (oprator[opr] == '*' || oprator[opr] == '/') {
postfix[post] = oprator[opr];
oprator[opr]='#';
post++;
}
oprator[opr] = infix[i];
opr++;
break;
case '+' :
case '-' :
//如果上一个运算符不是左括号也不是栈顶，则先退栈再入栈
if (oprator[opr-1] != '(' && oprator[opr-1] != '@') {
postfix[post] = oprator[opr];
oprator[opr]='#';
}
oprator[opr] = infix[i];
opr++;
break;
default :
//如果是数字则直接进入后缀表达式数组
postfix[post] = infix[i];
post++;
break;
}
}
//如果扫描完成，则退栈
for(j=opr-1;j>0;j--){
if(oprator[j]!='@'){
postfix[post]=oprator[j];
oprator[j]='#';
}
else
break;
}
//输出结果
for(i=0;i<cntl;i++)
cout << postfix[i];
cout << endl;
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2006/11/01/547289.html，如需转载请自行联系原作者
