暑期培训课件23号下午c语言

C语言在数学建模中的应用数学建模常用方法蒙特卡罗方法(Monte-Carlo方法,MC)：用计算机仿真来检验结果。MATLAB数据拟合、参数估计、插值等数据处理算法。MATLAB数值分析方法：函数的数值逼近、数值微分与数值积分、非线性方程的数值解法、数值代数、常微分方程数值解等。MATLAB规划类问题：线性规划、整数规划、多元规划、二次规划等Lindo、Lingo统计方法：聚类分析、判别分析等SPSS图象处理算法MATLAB网格算法和穷举算法：最好在运算速度较快的计算机中进行，并用高级语言来做。算法设计问题：穷举、递归与分治、贪心、回溯、分枝定界等算法。图论问题：最短路径、最大流，二分匹配等问题。连续问题离散化的方法：如差分代替微分、求和代替积分等思想都是把连续问题离散化的常用方法。最优化理论的算法：模拟退火法(SA)、神经网络(NN)、遗传算法(GA)。主要内容一．数组和指针二．文件操作

三．常用算法穷举算法分治和递归贪心算法回溯法动态规划一维数组和指针二维数组和指针一、数组和指针1.一维数组定义：类型说明符数组名［常量表达式］；①int

a[10];//正确②int

n=10; int

a[n]; //错误③const

int

n=10;

int

a[n]; //正确④#define

N

10int

a[N]; //正确一、数组和指针a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]需要预先估计数组长度2.二维数组定义数组名［常量表达式］［常量表达式］；2类型说明符#define

M#define

N

3int

a[M][N];//

2行3列a[0][0]

a[0][1]a[1][0]

a[1][1]a[0][2]a[1][2]a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]需要预先估计数组长度a[i][j]：第i行第j列的元素a[i]：表示第i行这个一维数组3.

指针(地址)3a2000int a=3;//整型变量aint

*

p1;//（指向整型的）指针变量p1p1=&a;p1p指向afloat

f, *p2;//（指向float型的）指针变量p2p2=&f;2000通过指针访问变量*p1=10;

等价于a=10;*p2=10.5;

等价于f=10.5;int

a[5];a常量,类型为 指向int的指针int

a[2][3];a常量，类型为指向长度为3

的int型数组的指针malloc和free函数(c4.new

和delete运算符（c++）//语言)（1）动态定义一维数组

int

n=100;//n为变量

int*p=newint[n];释放空间delete[]p;p[99]p[0]p[1]p[2]p[3]p访问第i个元素：p[i]或*(p+i)静态和动态定义一维数组的区别：int a[n];//静态：n必须为常量，大小提前确定int

*a;//动态:n可为变量或常量，需要时再确定

a=new

int[

n];（2）动态定义二维数组int

m=2,n=3;//变量int

(*p)[n];//p是指向长度为n的一维数组的指针p

=

new

int[m][n]

;访问第i行第j列元素：p[i][j]或

*( *(p+i)

+

j

)p[0][0]p[0][1]p[0][2]p[1][0]p[1][1]p[1][2]p释放空间delete[]p;二、文件的操作文件的打开与关闭文件的读写文件的定位文件的打开与关闭1.文件的打开(fopen函数)和关闭(fclose函数)函数调用:FILE

*fp；fp＝fopen（文件名，使用文件方式）；①需要打开的文件名，也就是准备访问的文件的名字；②使用文件的方式（“读”还是“写”等）；③让哪一个指针变量指向被打开的文件。fp=fopen( “d:\\f1.txt”,

“r”);zhangsan0001

18xi’anfp文件使用方式

含义(只读)为输入打开一个文本文件

(只写)为输出打开一个文本文件

(追加)向文本文件尾增加数据

(只读)为输入打开一个二进制文件(只写)为输出打开一个二进制文件“r”“w”“a”“rb”“wb”"ab“"r+“"w+”"a+”"rb+““wb+““ab+”(追加)向二进制文件尾增加数据

(读写)为读/写打开一个文本文件

(读写)为读/写建立一个新的文本文件

(读写)为读/写打开一个文本文件

(读写)为读/写打开一个二进制文件(读写)为读/写建立一个新的二进制文件

(读写)为读/写打开一个二进制文件文件的关闭(fclose函数)函数调用:fclose（文件指针）；函数功能:使文件指针变量不指向该文件，也就是文件指针变

量与文件“脱钩”，此后不能再通过该指针对原来与其相联系的文件进行读写操作。返回值:关闭成功返回值为０；否则返回EOF(-1)。文件的读写2.字符输入输出函数(fputc()和fgetc())fputc函数函数调用:fputc(ch，fp)；函数功能:将字符（ch的值）输出到fp所指向的文件中去。返回值:如果输出成功，则返回值就是输出的字符；如果输出失败，则返回一个EOF。fgetc函数函数调用:ch＝fgetc（fp）；函数功能:从指定的文件读入一个字符,该文件必须是以读或读写方式打开的。返回值:读取成功一个字符，赋给ch。如果遇到文件结束符，返回一个文件结束标志

EOF。3、数据块读写函数(fread()和fwrite())函数调用:fread

(buffer,size,count，fp);fwrite(buffer,size,count,fp);参数说明：buffer：是一个指针。对fread来说，它是读入数据的存放地址。对fwrite来说，是要输出数据的地址（均指起始地址）。size：

要读写的字节数。count：

要进行读写多少个size字节的数据项。fp：

文件型指针。使用举例：若有如下结构类型：struct

student_type{char

name[10];int

num;int

age;char

addr[30];}stud[40];可以用fread和fwrite来进行数据的操作：

for（ｉ＝０；ｉ＜40；ｉ＋＋）fread(&stud［i］，sizeof(struct

student_type)，1，fp);for（ｉ＝０；ｉ＜40，ｉ＋＋）fwrite(&stud［i］，sizeof(struct

student_type)，1，fp);文件内容：张三000119西安市李四000220北京市王五000319西安市……5.格式化读写函数(fprintf()和fscanf())函数调用:fprintf(文件指针，格式字符串，输出表列）；fscanf(文件指针，格式字符串，输入表列）；函数功能:从磁盘文件中读入或输出字符。例：

fprintf(fp,”%d,%6.2f”,i,t);fscanf

(fp,”%d,%f”,&i,&t);6.字符串读写函数fgets和fputsfgets函数函数作用：从指定文件读入一个字符串。函数调用：fgets(str,n,fp);从fp指向的文件输入n-1个字符，在最后加一个’\0’。返回值：str的首地址。fputs函数函数作用：向指定的文件输出一个字符串。函数调用：fgets(“china”,fp);第一个参数可以是字符串常量、字符数组名或字符型指针。字符串末尾的′＼０′不输出。返回值：输入成功，返回值为0；输入失败，返回EOF。文件的定位fseek函数（一般用于二进制文件）函数功能：改变文件的位置指针。函数调用形式：

fseek(文件类型指针，位移量，起始点)起始点：文件开头文件当前位置SEEK_SET

0SEEK_CUR

1文件末尾

SEEK_END

2位移量：以起始点为基点，向前移动的字节数。一般要求为long型。fseek函数应用举例fseek(fp，100L，０）；将位置指针移到离文件头100个字节处。

fseek(fp，50L，１）；将位置指针移到离当前位置50个字节处。

fseek(fp，50L，２）；将位置指针从文件末尾处向后退１０个字节。举例：2007B

乘公交看奥运——数据的读入三、常用算法穷举算法递归和分治贪心算法回溯法1.穷举算法基本思想：根据题目的条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。例1：一辆卡车违反交通规则，撞人后逃跑，现场有3位目击

者，但都没有记住车牌号，只记下车号的一些特征。甲说：牌照的前2位是相同的。乙说：后2位也是相同的，但与前2位不同；丙是位数学家，说4位牌照号刚好是一个整数的平方。请根据以上线索求出牌照号。穷举的思想，和条件限制例2：两个乒乓球队进行比赛，各出3人，甲队为A，B，C

3人，乙队为X,Y,Z

3人。A不和X比，C不和

X,Z比，找出3对赛手名单。甲：AB

C乙：X

YZ穷举的思想，和条件限制int

main(){ char

i,

j,

k;•/*

i是A的对手;j是B的对手;k是C的对手*/for

(i

=

'X';

i

<=

'Z';

i++

)for

(

j

=

'X';

j

<=

'Z';

j++)if

(

i

!=

j)for

(

k

=

'X';

k

<=

'Z';

k++)if

(

i

!=

k

&&

j

!=

k)if

(

i

!=

'X'

&&

k

!=

'X'

&&

k

!=

'Z')cout<<"A--"<<i<<" B--“<<j<<" C--"<<k<<endl;return

0;}2.分治和递归基本思想–将一个难以直接解决的大问题，分解成一些规

模较小的相同问题，以便各个击破，分而治之。何时能、何时应该采用分治法来解决问题呢？分治法的解题步骤步骤1：分解——即将问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题；步骤2：治理步骤2-1：求解各个子问题步骤2-2：合并函数的递归调用在定义一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。例1：求n!

(n>=0)分析：n!=n*

(n-1)!(n-1)!=(n-1)*

(n-2)!(n-2)!=(n-2)*

(n-3)!……2!

=2*1!1!=1*0!0!

=1例1：求n!int

fun(int n)//求规模为n的问题{

if(n==0) //最小规模，有直接解

return

0;elsereturn

n*

fun(n-1);

//求规模为n-1的问题}void

main(){ int

n;scanf(“%d”,&n);printf(“n!=%d\n”,fun(n)

);}例2：折半（二分）搜索技术（有序表）2.分治和递归查找215131921375664758088921

2

3

4

5

6

7

8

9

10

11MidLow513192137566475808892High1234567891011513192137566475808892Low

Mid

High1

2

3

4

5

6

7

8

9

10

11LowMidHigh(a)

查找成功示例查找71-5131723384656657881921

2

3

4

5

6

7

8

9

10

11-513172338465665788192-513172338465665788192-513172338465665788192Low

Mid

High1

2

3

4

5

6

7

8

9

10

11Low

Mid

High1

2

3

4

5

6

7

8

9

10

11LowMidHigh1

2

3

4

5

6

7

8

9

10

11Low

HighMid(b)

查找不成功示例折半查找示例例3. Hanoi（汉诺塔）问题:规则：（1）每次只能搬一个盘子（2）任何时候大盘在下，小盘在上n321由上面的分析可知：将ｎ个盘子从Ａ座移到Ｃ座可以分解为以下3个步骤：1.将Ａ上2-n共ｎ－１个盘借助Ｃ座先移到Ｂ座上。2.把Ａ座上剩下的一个盘移到Ｃ座上。3.将2-n共ｎ－１个盘从Ｂ座借助于Ａ座移到Ｃ座上。n321void

hanoi(int

n,char

A,char

B,char

C)//将n个盘从A座借助B座，移到C座{

if(n==1) cout<<A<<"->"<<C<<endl;else{

hanoi(n-1,A,C,B);//将n-1个盘从A座借助C座，移到B座cout<<A<<“->”<<C<<endl;//将第1个盘从A座移到C座hanoi(n-1,B,A,C);//将n-1个盘从B座借助A座，移到C座}}321nint

main(){

void

hanoi(int

n,char

A,char

B,char

C);

//声明int

m;cout<<"input

the

number

of

diskes:";cin>>m;cout<<"The

steps

of

moving

"<<m<<"

disks:"<<endl;//调用hanoi(m,‘A’,‘B’,‘C’);return

0;}例4：循环赛日程表问题描述–设有n=2k个运动员要进行羽毛球循环赛，现要设计一个满足以下要求的比赛日程表：每个选手必须与其它n-1个选手各赛一次；每个选手一天只能比赛一次；循环赛一共需要进行n-1天。–由于n=2k，显然n为偶数。分治法求解思路按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两（或一）个选手时，比赛日程表的制定就变得很简单。编号第1天第2天第3天第4天第5天第6天第7天123456788个人比赛安排122112342143341243213443566578875678658778568765n=23个人参加比赛14个人比赛安排编号第1天编号第1天编号第1天编号第1天编号第1

第2

第3天

天

天2个人比赛安排编号第1

第2

第3天

天

天23456788个人比赛安排编号第1天第2天第3天第4天第5天第6天第7天12345678214365873412785643218765567812346587214378563412876543213.贪心算法基本思想从问题的某一个初始解出发，在每一个阶段都根据贪心策略来做出当前最优的决策，逐步逼近给定的目标，尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，算法终止。得出的结论每个阶段面临选择时,贪心法都做出对眼前来讲是最有利的选择选择一旦做出不可更改，即不允许回溯根据贪心策略来逐步构造问题的解贪心法的解题步骤分解：将原问题分解为若干个相互独立的阶段。解决：对于每个阶段依据贪心策略进行贪心选择，求出局部的最优解。合并：将各个阶段的解合并为原问题的一个可行解。例1：有一批集装箱要装入一个装载质量为C的货船中，每个集装箱的质量由用户自己输入指定，在货船的装载体积不限的前提下，如何装载可将尽可能多的集装箱装入货船中。分析：b[0]b[1]b[2]…b[n-1]共n个集装箱，每次选出最轻的装入按照箱子的质量从小到大排序；依次装入，直至某个箱子的质量小于货船剩余的质量例2：会场安排问题问题描述设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi

。如果选择了活动i，则它在半开时间区间

[si,fi)内占用资源。若区间[si,

fi)与区间[sj,

fj)不相交，则称活动i与活动j是相容的。也就是说，当si>=fj或sj>=fi时，活动i与活动j相容。会场安排问题要求在所给的会议集合中选出最大的相容活动子集，也即尽可能地选择更多的会议来使用资源。算法设计将所有活动以其完成时间的非减序排列；算法每次总是选择具有最早完成时间的相容活动加入集合t中。【例】设有11个会议等待安排，用贪心法找出满足目标要求的会议集合。这些会议按结束时间的非减序排列如表2-1所示。11个会议按结束时间的非减序排列表：会议i1234567891011开始时间bi130535688212结束时间ei4567891011121314会议集合为{1,4,8,11}示例4.回溯法(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。通俗地讲：回溯法是一种“能进则进，进不了则换，换不了则退”的基本搜索方法回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。示例：n后问题问题描述：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1

2

3

4

5

6

7

812345678QQQQQQQQ求出所有合法布局…….四皇后问题的一种解空间树…….四皇后问题的一种解空间树printf("\n");

}return;

}//在第j列上放置不被攻击的皇后{if(

isCorrect(i,j,Q)

)

/*如果Q[i][j]可以放置皇后*/{ Q[i][j]=1;

/*放置皇后*/void

Queen(int j,int

Q[][4]){//在第j列上放置皇后if(

j==4)

/*得到了一个解*/{for(

inti=0;i<4;i++)//输出二维数组Q[4][4],即棋盘状态{ for(

int

k=0;k<