串的模式匹配问题实验总结(用C实现)

第一篇：串的模式匹配问题实验总结(用C实现)

串的模式匹配问题实验总结

1实验题目：

实现Index(S,T,pos)函数。其中，Index(S,T,pos)为串T在串S的第pos个字符后第一次出现的位置。

2实验目的：

熟练掌握串模式匹配算法。

3实验方法：

分别用朴素模式匹配和

KMP快速模式匹配来实现串的模式匹配问题。具体方法如下：

朴素模式匹配：输入两个字符串，主串S和子串T，从S串的第pos个位置开始与T的第一个位置比较，若不同执行 i=i-j+2；j=1两个语句；若相同，则执行语句 ++i;++j;一直比较完毕为止，若S中有与T相同的部分则返回主串（S字符串）和子串（T字符串）相匹配时第一次出现的位置，若没有就返回0。

KMP快速模式匹配：构造函数get_next(char *T,int *next)，求出主串S串中各个字符的next值，然后在Index_KMP(char *S,char *T,int pos)函数中调用get_next(char *T,int *next)函数并调用next值，从S串的第pos 位置开始与T的第一个位置进行比较，若两者相等或j位置的字符next值等于0，则进行语句++i;++j;即一直向下进行。否则，执行语句 j=A[j]；直到比较完毕为止。若S中有与T相同的部分则返回主串（S字符串）和子串（T字符串）相匹配时第一次出现的位置，若没有就返回0

4实验过程与结果：

（1）、选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl, 输入子串T：gh,输入pos的值为：2。选择2功能 “朴素的模式匹配算法”，输出结果为 5； 选择3功能 “KMP快速模式匹配算法”，输出结果为 5； 选择0功能，退出程序。截图如下：

（2）、选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl, 输入子串T：wp, 输入pos的值为：2。选择2功能 “朴素的模式匹配算法”，输出结果为 0； 选择3功能 “KMP快速模式匹配算法”，输出结果为 0； 选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl, 输入子串T：sd, 输入pos的值为：4。选择2功能 “朴素的模式匹配算法”，输出结果为 0； 选择3功能 “KMP快速模式匹配算法”，输出结果为 0；

选择0功能，退出程序。截图如下：

5实验体会与收获：

（1）C语言中无法用string型直接定义字符串，所以要用char型的数组来实现字符串的定义。

（2）在char S[]数组，数组的首位即S[0]表示数组长度，用stolen()计算长度，输入的字符串逐步后移一位，此时S[1]存放第一个字符。

（3）在主函数中，用get(S+1)；get(T+1);两个语句无法同时实现字符的输入，最后改用C++语句 cin>>S+1;cin>>T+1;使字符的输入得到了实现。（4）程序用有必要的文字说明，以便运行时更加清晰明了。

第二篇：求解Josephus问题实验总结(用C语言循环单链表实现)

求解Josephus问题实验总结

1实验题目: josephus问题可描述如下：

设有n个人围成一个环，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人从新开始报数，数到第m的人又出列，如此重复，直至所有人均出列为止。求这些人出列的顺序。

2实验目的：

熟练掌握线性表的顺序实现和链式实现的基本操作。

3实验方法：

通过运用已学的向量和循环单链表编写程序，并在电脑上运行，实现josephus问题的求解。4实验过程与结果：

（1）输入n值为6，s值为3，m值为2，输入A[i]的值为1 2 3 4 5 6 输出结 果为：4 6 2 5 3 1 截图如下：

（2）

1、输入n值为-1, s值为3，m值为2，显示：ERROR。截图如下：

2、输入n值为6, s值为0，m值为3，显示：ERROR。截图如下：

3、输入n值为6, s值为3，m值为0，显示：ERROR。截图如下

：

5试验体会与收获：

（1）写程序是要随时注意缩进，使得程序层次清晰，便于寻找错误，同时也让别人看的更加方便。（2）构造循环单链表，要以单链表为单元指针指向把最后个单元与第一个即可（3）建立好循环单链表后，通过三个指针（p,q,tmp）的指示，来确定报数，出列人的位置，得以完成。具体过程如下：p指向head头指针,通过s次循环将p指向报数的起始位置s，用q记录p的位置，再经过m次循环另p指向出列者的位置，将其数值保存在一维数组中，并将其从链表中删除，p指向下一次起始位置，结束时返回数组A[j]。（4）删除节点时，注意要释放节点。

（5）构造函数时，一定要明确函数的类型，即返回行还是不返回型，以免出现不必要的错误。

第三篇：实验二 用Mathematica实现单纯形法

实验二 用Mathematica实现单纯形法

一、实验目的

（1）学习并学会使用Mathematica软件。（2）掌握单纯形法的计算机实现的方法。

二、实验原理

算法的具体步骤如下：书30页 Matnmatica中基本语法的补充：

（一）LinnearProgramming[c,m,b],其中c是行向量，b是列向量，m是矩阵，自变量用列向量x表示，在满足mx>=b且x>=0的区域，求cx的最小值点。需要注意的几点是>=号，以及目标函数求最小值。

举例说明：

minfx 32x3x12x1x2x36x12x24x31s.t.3x2x4x20

231x1,x2,x30

分析与求解：

第三个式子可以改造成两个

3x12x24x32和03x12x24x320

x1x2x36x2x24x3121最后得到用于编写程序的表示形式为3x12x24x3203x2x4x20231x1,x2,x30

输入c={1,-2,-3};b={-6,12,20,-20};A={{-1,-1,-1},{1,-2,4},{3,2,4},{-3,-2,-4}};LinearProgramming[c,A,b] 得到最优解x={0,2,4} f=-16

（二）通用表的生成函数Table.表是存储多个数、变量或算式等对象的一种数据结构。一个表用一对花括号表示，它的成员在括号内用逗号隔开，同一个表的成员可以有不同的数据类型，表的成员还可以是一个表（子表）。可以用“t[[n]]”来提取表t中的第n个元素。Mathematica中常用的建表函数是“Table”，其调用格式如下：

Table[f,{i,imin,imax,stepi},{j,jmin,jmax,stepj}] 表的通项为f（f是变量i和j的函数），min，max，step规定了初值、终值、步长，min和step的默认值为1。例如

输入命令Table[n^3,{n,1,20,2}] 则输出 {1,27,125,343,729,1331,2197,3375,4913,6859} 输入命令Table[x*y,{x,3},{y,3}] 则输出 {{1,2,3},{2,4,6},{3,6,9}}

（三）表作为向量和矩阵

一层表在线性代数中表示向量, 二层表表示矩阵.例如,矩阵

24

35

可以用数表{{2,3},{4,5}}表示.输入A={{2,3},{4,5}} 则输出{{2,3},{4,5}} 命令MatrixForm[A]把矩阵A显示成通常的矩阵形式.例如,输入命令: MatrixForm[A] 则输出

2435

注:一般情况下,MatrixForm[A]所代表的矩阵A不能参与运算.（四）求矩阵A的转置的命令:Transpose[A].（五）求方阵A的逆的命令:Inverse[A]

（六）()圆括号表示项的结合顺序，如(x+(y^x+1/(2x)));[]方括号表示函数，如Log[x],BesselJ[x,1]；{}大括号表示一个“表”(一组数字、任意表达式、函数等的集合)，如{2x,Sin[12 Pi],{1+A,y*x}}；[[]]双方括号表示“表”或“表达式”的下标，如a[[2,3]]、{1,2,3}[[1]]=1。

（七）每次运行完成后程序会自动在输入的式子前面加上In[n],n表示输入命令的序列号，在输出的答案上自动加上out[n]。

三、单纯形法解题

maxZ70x1120x2100x3100x4150x58x14x25x33x42x53604x5x27x36x43x520013x110x29x35x49x5300s.t.6x19x25x38x49x51508x4x5x3x2x10012345x1,x2,x3,x4,x50

编写程序如下

A={{8,4,5,3,2,1,0,0,0,0}, {4,5,7,6,3,0,1,0,0,0}, {3,10,9,5,9,0,0,1,0,0}, {6,9,5,8,9,0,0,0,1,0}, {8,4,5,3,2,0,0,0,0,1}};c={70,120,100,100,150,0,0,0,0,0};b={360,200,300,150,100};a2=Length[b];a3=Dimensions[A][[2]];b1=Table[i+a3-a2,{i,a2}];b2=Table[i,{i,a3-a2}];b3=Table[i,{i,a3}];x=Table[0,{i,a3}];b4=Table[0,{i,a2}];c1=c[[b2]]-c[[b1]].Inverse[Transpose[Transpose[A][[b1]]]].Transpose[Transpose[A][[b2]]];

Label[100];For[i=1,i≤Length[b2],i=i+1,{ c1=c[[b2]]-c[[b1]].Inverse[Transpose[Transpose[A][[b1]]]].Transpose[Transpose[A][[b2]]];If[c1[[i]] ≤0,{Goto[endif]},{ For[j=1,j≤a2,j=j+1,{ If[(Inverse[Transpose[Transpose[A][[b1]]]].Transpose[A][[b2[[i]]]])[[j]] ≤0,{b4[[j]]=∞}, {b4[[j]]=((Inverse[Transpose[Transpose[A][[b1]]]].b)[[j]])((Inverse[Transpose[Transpose[A][[b1]]]].Transpose[A][[b2[[i]]]])[[j]])}] }];For[j=1,j≤a2,j=j+1,{ If[b4[[j]]==Min[b4],{m=b2[[i]];b2[[i]]=b1[[j]];b1[[j]]=m;Goto[100]}] }] }];Label[endif] }];x[[b1]]=Inverse[Transpose[Transpose[A][[b1]]]].b;Print[“the optimization is : ”];Print[N[x,4]];Print[“the optimization value is : ”];Print[N[c.x]];

实验练习： 1.设1A111122A131,B03124211,4求3AB2A及ATB.则输出3AB及ATB的运算结果分别为

1024414143310

42

41042124810252.设A0312123341231,求A.653.minf=-0.75x1+150x2-0.02x3+6x4

6x200.x304x90.2x5149x200.x302x30.5x014s.t

x13x1,x2,x，x034

00

第四篇：c语言迷宫问题代码实现

C语言迷宫问题代码如下：

#include

#include

#define LEN sizeof(SEAT)

#define MAXSIZE 100

#define LENGTH 30

typedef struct

{

int x;//横坐标

int y;//纵坐标

int di;//表示方向，0-3分别表示东南西北。

}SEAT;

struct StackList

{

SEAT stack[MAXSIZE];

int top;

}*Stack;

int EmptyStack(StackList*Stack)//判断是否为空栈

{

if(Stack->top==0)

return 0;

else

return 1;

}

int Move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//分别表示向东、西、南、北需要加上的坐标

int Mase[LENGTH][LENGTH]={0};//初始化为0

int length,width;

void InitMase()//在迷宫的外围添加一层“墙壁”（赋值为1），使得迷宫的任意一点都有四个方向

{

int i,j;

for(i=0;i

{

for(j=0;j

Mase[i][j]=1;

}

for(i=0;i

{

for(j=0;j

Mase[j][i]=1;

}

}

void InitStack(StackList*Stack)//初始化

{

Stack->top=0;

return;

}

int PushStack(StackList*Stack,SEAT CurSeat)//进栈

{

if(Stack->top==MAXSIZE-1)

return false;

else

{

Stack->stack[Stack->top].x=CurSeat.x;

Stack->stack[Stack->top].y=CurSeat.y;

Stack->stack[Stack->top].di=CurSeat.di;

Stack->top++;

return true;

}

}

int PopStack(StackList*Stack)//出栈

{

if(Stack->top==0)

return false;

else

{

Stack->top--;

return true;

}

}

int Pass(SEAT p)//判断当前是否可行

{

if(Mase[p.x][p.y]==0)

{

return true;

}

else

return false;

}

SEAT NextSeat(SEAT CurSeat)//查找下一个点，并返回

{

SEAT temp;

temp.x=CurSeat.x+Move[CurSeat.di][0];

temp.y=CurSeat.y+Move[CurSeat.di][1];

return temp;

}

void Mark(SEAT p)//标记已经走过的点，避免重复

{

Mase[p.x][p.y]=-1;

}

int PathWay(SEAT start,SEAT end)//找路线

{

Stack=(struct StackList*)malloc(sizeof(struct StackList));

InitStack(Stack);

SEAT CurSeat;

CurSeat.x=start.x+1;//由于多加了一层墙壁，因此坐标的值要加1

CurSeat.y=start.y+1;//

CurSeat.di=start.di;//

do

{

if(Pass(CurSeat))

{

PushStack(Stack,CurSeat);

Mark(CurSeat);

if(CurSeat.x==end.x+1&&CurSeat.y==end.y+1)//如果找到出口，返回{

return true;

}

else

{

int find=0;

while(CurSeat.di<3&&find==0)//找下一个结点的方向

{

CurSeat.di++;

SEAT temp;

temp=NextSeat(CurSeat);

if(Mase[temp.x][temp.y]==0)

{

temp.di=-1;

CurSeat=temp;

find =1;

}

}

}

}

else

{

if(EmptyStack(Stack))//当前的点不能走，出栈

PopStack(Stack);

if(EmptyStack(Stack))//当前的点变为前一个点

{

CurSeat=Stack->stack[Stack->top-1];

}

while(CurSeat.di==3&&EmptyStack(Stack))////当前的点找不到下一个点，出栈

{

PopStack(Stack);

CurSeat=Stack->stack[Stack->top-1];//当前的点变为前一个点}

if(EmptyStack(Stack))

{

int find=0;

while(CurSeat.di<3&&find==0)////找下一个结点的方向

{

CurSeat.di++;

SEAT temp;

temp=NextSeat(CurSeat);

if(Mase[temp.x][temp.y]==0)

{

temp.di=-1;

CurSeat=temp;

find =1;

}

}

}

}

}while(EmptyStack(Stack));

return false;

}

void PrintStack(StackList*Stack)//输出路线

{

if(Stack->top==0)

printf(“There is no route can be out of the mazen”);

else

{

int i;

for(i=0;itop;i++)

{

if(i!=0)

printf(“->(%d,%d)”,Stack->stack[i].x-1,Stack->stack[i].y-1);

else

printf(“(%d,%d)”,Stack->stack[i].x-1,Stack->stack[i].y-1);

}

}

}

void PrintMase()//输出迷宫

{

int i,j;

for(i=1;i

{

for(j=1;j

{

if(j!=1)

printf(“ %d”,Mase[i][j]);

else

printf(“%d”,Mase[i][j]);

}

printf(“n”);

}

}

int main()

{

int n;

SEAT start,end;

printf(“Please enter the maze of the length and width:n”);

scanf(“%d%d”,&length,&width);

printf(“Please enter the number of the maze wall unit(0

printf(“Please enter the labyrinth of the coordinates of the wall unit(0<=row,column):n”);while(--n>=0)

{

int x,y;

scanf(“%d%d”,&x,&y);

Mase[x+1][y+1]=1;

}

InitMase();

PrintMase();

printf(“Please enter the coordinates entrance(0<=x<%d,0<=y<%d):n”,length,width);

scanf(“%d%d”,&start.x,&start.y);

start.di=-1;

printf(“Please enter the coordinates exports(0<=x<%d,0<=y<%d):n”,length,width);

scanf(“%d%d”,&end.x,&end.y);

end.di=0;

if(PathWay(start,end))

PrintStack(Stack);

else

printf(“There is no route can be out of the mazen”);return 0;

} of the of the maze maze

第五篇：用c语言实现单纯形法的编程

用c语言实现单纯形法的编程

#include “stdio.h” #include “math.h” #include int M,N;float c[100],a[100][100],b[100],CZ[100],Dn[100],th[100],x[100];int Fn[100];int K,L,ths;float zy;int shuru();void findmm();void chang();main(){ float max_Z,sum=0,s=0;int i,j,r=0;if(!shuru()){ printf(“ERROR！!n”);return 0;} while(r0){findmm();if(ths==M){goto loop;} else chang();} else r++;} } loop: if(ths==M){printf(“n此线性规划没有有限最优解！!n”);printf(“n此线性规划最终迭代结果为：”);printf(“n Cj ”);for(j=0;jDn[K])max=i;K=max;for(i=0;i0)&&(th[i]Dn[K])K=i;for(i=0;i