计算概论习题课

计算概论

(IntroductiontoComputing)习题课指针与递归指针指针的基本概念

地下工作者阿金接到上级指令，要去寻找打开密电码的密钥，这是一个整数。几经周折，才探知如下线索，密钥藏在一栋三年前就被贴上封条的小楼中。一个风雨交加的夜晚，阿金潜入了小楼，房间很多，不知该进哪一间，正在一筹莫展之际，忽然走廊上的电话铃声响起。艺高人胆大，阿金毫不迟疑，抓起听筒。只听一个陌生人说：“去打开211房间，那里有线索”。阿金疾步上楼，打开211房门，用电筒一照，只见桌上赫然6个大字：地址1000。阿金眼睛一亮，迅速找到1000房间，取出重要数据66，完成了任务。

P单元P所指向的地址

1000

66

地址211地址10001000…66…2111000P指针变量的类型，是指针所指向的变量的类型，而不是自身的类型指针的值是某个变量的内存地址指针变量——用来存放另一变量地址的变量指针的基本概念定义含义int*p;p是指向整型数据的指针变量

inta[n];定义数组a，元素类型为int，元素个数是nint*p[n];p是指针数组，包含n个指针变量，每一个指针变量可以指向整型数据

适用于多字符串操作

int(*p)[n];p是指向数组的行指针，数组有n个整型数 int*p[4];intscore[3][4];p=score;适用于多维数组

intf();f是函数，返回值是intint*p();p是函数，返回值是指针，指向整型数据

int(*p)();p是函数指针变量，可以指向返回int数据类型的函数的入口地址。

int**p;p是指针变量，指向一个指向整型数据的指针指针的定义小结空类型指针void*void*p，表示p是空类型指针，它可以指向任何数据类型。空类型指针与其他类型指针之间赋值时，应进行强制类型转换。例、char*p1;

void*p2;

p1=(char*)p2;

p2=(void*)p1;指向指针的指针：适合高速运算int*p;inta[3];p=a;p(动态数组)a(静态数组)指针的定义小结空指针的使用小结int*p=NULL;表示指针不指向任何内存地址.防止其指向任何未知的内存区域避免产生难以预料的错误发生.把指针初始化为

NULL

是好习惯.在stdio.h中，NULL被定义为0：

#defineNULL0习惯上，不使用p=0，而使用p=NULL指针变量p可以与NULL作比较，例：if(p==NULL)注意：空指针不指向任何数据，与p未赋值不同。当p未赋值时，其值是不确定的，而空指针的值是确定数0指针运算小结1、指针变量加/减运算p++、p--、p+i、p-i、p+=i、p-=i加1表示指向下一个数据。2、指针变量赋值

p=&a;变量a的地址赋给p，即指针p指向a

p=array;数组array首地址赋给p

p=&array[i];数组元素array[i]的地址赋给p

p=max;函数max的入口地址赋给p

p1=p2;指针p2的值赋给指针p1，即p1、p2所指的数据相同。3、指针变量相减。

当p1、p2指向同一个数组的元素，指针相假p2-p1等于p1、p2间的元素个数。

注意：指针相加无意义。指针与数组01234&a[0]&a[1]&a[2]&a[3]&a[4]&a[1]&a[2]&p1&p2p1p2P1和p2分别指向a[1],a[2]，这里&——取地址运算符*——指针运算符（间接访问运算符）*p1——间接访问p1所指向的内存单元，当然是输出a[1]的值*p2——间接访问p2所指向的内存单元，当然是输出a[2]的值指针与数组(1)p=a;这里数组名作为数组的起始地址，即a[0]的地址。数组名是一个常量指针

因此p=a等效于p=&a[0];(2)p=p+1;如p指向a[0],则p=p+1之后，p指向a[1](3)如果p=a等效于p=&a[0];

则p=a+4等效于p=&a[4];a[0]a[1]a[2]a[3]a[4]*p*(p+1)*(p+2)*(p+3)*(p+4)pp+1p+2pp+1p+2等效指针与字符串（字符数组）//***************************************//*主要功能：指针（字符串从右到左输出）*

//***************************************#include<stdio.h>//预编译命令intmain(){//主函数 charshuzi[]="987654321";//定义数组，

//赋初值为数字字符串 char*p=&shuzi[8];//让指针p指向shuzi[8]元素，

//该处是字符‘1’ do //直到型循环 { //循环体开始 printf(“%c”,*p); //输出由p指向的一个字符

p--; //让p减1 } //循环体结束 while(p>=shuzi); //当p>=shuzi时，继续循环 printf(“\n”);//换行

return0；}指针数组概念元素为指针的数组称之为指针数组对比一般数组单元中装的是数据指针数组单元中装的是地址

指针数组指针数组的定义和初始化例

intar0[]={0,1,2};//定义一般数组

intar1[]={1,2,3};//定义一般数组

intar2[]={2,3,4};//定义一般数组

int*p[]={ar0,ar1,ar2};//定义指针数组地址

数组名就是地址指针数组

012

指针数组p&ar0[0]&ar0[1]&ar0[2]&p[0]&ar0&p[1]&ar1123&p[2]&ar2&ar1[0]&ar1[1]&ar1[2]

234&ar2[0]&ar2[1]&ar2[2]指针使用的注意事项1、若指针p指向数组a，虽然p+i与a+i、*(p+i)与*(a+i)意义相同，但仍应注意p与a的区别(a代表数组的首地址，是不变的；p是一个指针变量，可以指向数组中的任何元素)inta[10];*p;for(p=a;a<(p+10);a++)printf("%d",*a)；是否正确？指针使用的注意事项2、指针变量可以指向数组中的任何元素，注意指针变量的当前值。因此：使用指针时，应特别注意避免指针访问越界本例中第二次for循环p已经越过数组的范围但编译器不能发现该问题避免指针访问越界是程序员自己的责任main(){int*p,i,a[10];

p=a;

for(i=0;i<10;i++)

scanf("%d",p++);

printf("\n");

for(i=0;i<10;i++,p++)

printf("%d",*p);}指针使用的注意事项3、指针使用的几个细节。设指针p指向数组a（p=a），则：p++（或p+=1），则：*p=？*p++表示什么意义？*(p++)与*(++p)的分别表示什么意义？(*p)++表示什么意义？约瑟夫环问题描述有

n个人，编号为

1,2,...,n,站成一圈。沿着圈顺序数，每到第m个人就把他杀掉，这样一直进行下去，直到只剩下一个人，那个人就活下来。约瑟夫很聪明，他总会想办法站到一个合适的位置上，使得自己能够成为最后一个，从而活下来。例如：n=6，

m=5时，被杀的顺序是5,4,6,2,3，而

1最终活下来。

给定n,m,求出最后留下的人的编号位置12345612346123612313startendstartendstartendendstartstartend约瑟夫环1。使用数组，删除人移动数组2。使用数组，删除人用一个标记表示，不用移动数据12345612346123612313startendstartendstartendendstartstartend123456startendstartendstartendendstartstartend1234-16123-1-16123-1-1-11-13-1-16约瑟夫环一直到最后剩一个人1---标号x,记为number上一层的number

number=(number+m)%2一般化表示，对有i个人的序列，序号为number[i]=(number[i-1]+m)%iSourcecode#include<stdio.h>intmain(){ intn,m,i=0,j=0; inta[MAX]; printf("Pleaseinputn(<=1000):"); scanf("%d",&n); printf("Pleaseinputm:"); scanf("%d",&m); for(intk=0;k<n;k++){ a[k]=k;}

while(n>1)

{

j=(i+m-1)%n; for(intk=j;k<n;k++) a[k]=a[k+1]; i=j; n--;

} printf("JosephshouldstandatNo.%d\n",a[0]+1); return0;}约瑟夫环数学解法，复杂度低n个人的序列1234……m-1mm+1…..n杀掉一个人的序列1234……m-1m+1…..n重排序列m+1….n12….m-1x’序号重新编号序列—n-1人序列123….n-1

x序号x’=(m+x)%n…….最后剩1个人1约瑟夫环—续假设有

k个好人和

k个坏人。在圈上前

k个是好人，后

k个是坏蛋。现在让你来确定一个最小的

m使得所有的坏蛋被杀掉后，才开始杀第1个好人。输入输入有若干个k。

最后1个值是0。假设

0<k<14。输出对应每个输入的k，输出相应的m。样例输入样例输出

340530约瑟夫环—杀人问题问题分析1)求最小的m值可以用枚举的方法： 即依次看m=1，2，3，…时，是否满足条件。2)枚举的过程就是依次杀掉圈上的一半的人，并判断该人是否是好人，如果是好人，则当前的m不满足条件，否则m满足条件。3)一共有2k个人。4)k可以取1，2，3，…,13。可以一次算出所有相应的m，存在一个数组中，这样每次读入一个k，就输出相应的m。Sourcecode#include<stdio.h>intkill_bad_man(inta[],intm,intk){inti;for(i=1;i<=k;i++){a[i]=(a[i-1]+m-1)%(2*k-i+1);if(a[i]<k)return0;}return1;}voidmain(){inta[14],k,m;scanf(“%d”,&k);m=k;a[0]=0;

while(!kill_bad_man(a,m,k))m++;printf(“%d”,m);}约瑟夫环—杀人问题数学解法，复杂度低N个人的序列1234……m-1mm+1…..n杀掉一个人的序列1234……m-1m+1…..n重排序列m+1…n12…m-1x’序号重新编号序列—n-1人序列123…n-mn-m+1n-m+2….n-1

x序号由此得到：x’=(m+x)%n

(0实际编号为n)m+1m+2m+3…m+n-mm+n-m+1m+n-m+2…m+n-1…….最后剩k个人

递归递归调用函数返回值类型

函数名

（[参数1类型

参数名1，

参数2类型

参数名2，……]）多个返回值？？？调用过程中输入参数变化/不变递归函数递归调用函数出口voidrecursive（parameters）{recursive（parameters）函数出口}递归调用用递归算法求n!定义：函数fact(n)=n! fact(n-1)=(n-1)!

则有 fact(n)=nfact(n-1)

已知 fact(1)=1intfact(intn){ if(n>1)

{ returnn*fact(n-1);

} else

{ return1;

}}下面画出了调用和返回的递归示意图intfact(intn){ return(n>1?n*fact(n-1):1);}从图可以想象： 欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1)。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到1的阶乘，其值为1，到达了递归的边界。然后再用fact(n)=n*fact(n-1)这个普遍公式，从里向外倒推回去得到fact(n)的值递推与递归汉诺塔问题相传在古代印度的Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为5800亿年汉诺塔问题1、在A柱上只有一只盘子，假定盘号为1，这时只需将该盘从A搬至C，一次完成，记为

move1#fromAtoC(演示)ABC1汉诺塔问题2、在A柱上有二只盘子，1为小盘，2为大盘第（1）步将1号盘从A移至B，这是为了让2号盘能动；第（2）步将2号盘从A移至C；第（3）步再将1号盘从B移至C；ABC21汉诺塔问题3、在A柱上有3只盘子，从小到大分别为1号，2号，3号第（1）步将1号盘和2号盘视为一个整体；先将二者作为整体从A移至B，给3号盘创造能够一次移至C的机会。这一步记为move(2,A,C,B)意思是将上面的2只盘子作为整体从A借助C移至B。第（2）步将3号盘从A移至C，一次到位。记为

move3#fromAtoC第（3）步处于B上的作为一个整体的2只盘子，再移至C。这一步记为

move(2,B,A,C)意思是将2只盘子作为整体从B借助A移至C。move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(1,A,C,B)move(1,C,A,B)move(1,A,B,C)move(2,B,A,C)move(1,B,C,A)move(1,B,A,C)move(1,A,B,C)ABC213汉诺塔问题4、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将1号和2号盘当整体从A移至B的过程中move(2,A,C,B)实际上是分解为以下三步 第（1）.1步：move1#formAtoC; 第（1）.2步：move2#formAtoB; 第（1）.3步：move1#formCtoB;汉诺塔问题经过以上步骤，将1号和2号盘作为整体从A

移至B，为3号盘从A

移至C

创造了条件。同样，3号盘一旦到了C，就要考虑如何实现将1号和2号盘当整体从B

移至C的过程了。实际上move(2,B,A,C)

也要分解为三步： 第（3）.1步：move1#formBtoA; 第（3）.2步：move2#formBtoC; 第（3）.3步：move1#formAtoC;汉诺塔问题5、看move(2,A,C,B)

是说要将2只盘子从A

搬至B，但没有

C

是不行的，因为第（1）.1步就要将1#盘从A

移到C，给2#盘创造条件从A

移至B，然后再把1#盘从C

移至B。看到这里就能明白借助C

的含义了。因此，在构思搬移过程的参量时，要把3个柱子都用上。Sourcecode#include<stdio.h>

voidmove(charx,chary)

{

printf("%c-->%c\n",x,y);

}

voidhanoi(intn,intA,intB,intC)

{

if(n==1)

{

move(A,C);

}

else

{

hanoi(n-1,A,C,B);

move(A,C);

hanoi(n-1,B,A,C);

}

}

voidmain()

{

intm;