第4章 函数和递归_qibofang的博客-程序员宅基地

技术标签: 算法  递归  c++  算法竞赛入门经典第二版  C  

4.1 自定义函数和结构体

如果只是向屏幕输出一些内容,这时只需要定义一函数返回类型为void,而且无需使用return,有一个专门的函数来调用main函数,如操作系统,IDE,调试器,甚至是自动评判系统,这个return 0代表正常结束。
求欧几里得距离:
double dist(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 -x2)*(x1 - x2) + (y1- y2)*(y1 - y2));
}
化简得:
#include <stdio.h>
#include <math.h>
typedef struct point { double x; double y; } point;
double dist(point a, point b)
{
	return hypot(a.x - b.x, a.y - b.y);  //求直角三角形斜边长,此时看起来清爽多了
}
int main()
{
	point A, B;
	A.x = A.y = 1;B.x = B.y = 2;
	printf("%.3f\n", dist(A, B));
	return 0;
}
计算组合数:( ,其中m<=n<=25)
算法分析:如何避免factorial(n)/(factorial(m)*factorial(n-m))的分母溢出,办法就是约分,即对上面等式的最右边式子进行计算。
#include <stdio.h>
#include <math.h>
long long C(int n, int m){
	if(m < n-m) m = n - m;
	long long ans = 1;
	for(int i = m+1; i <= n; i++) ans *= i;
	for(int i = 1; i <= n-m; i++) ans /= i;
	return ans;
}
int main()
{
	int m,n;
	while(scanf("%d%d", &m, &n)!=EOF && n!=0)
		printf("%ld\n", C(n, m));
	return 0;
}
素数的判断
算法分析:对于for(int i = 2; i*i <= n; i++)若取i = 46321,则i*i = 2147488281超过了int的最大值从而变成负数,仍然满足i*i<=n;所以不应该以i*i<=n为评判条件,下面是标准的素数判定函数。
#include <stdio.h>
#include <math.h>
int is_prime(int n){
	if(n <= 1) return 0;
	int m = floor(sqrt(double(n) + 0.5)); //进行四舍五入避免了浮点误差
	for(int i = 2; i <=m; i++)
		if(n % i == 0) return 0;
	return 1;
}
int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
		printf("%d\n", is_prime(n));
	return 0;
}

4.2 函数递归调用与参数传递

注意局部变量与全局变量的区别,局部变量的存储空间是临时分配的,函数执行完毕后,局部变量的空间奖杯释放。调用栈描述的是函数之间的调用关系,有多个栈帧组成,每个栈帧对应着一个未运行完的函数,且栈帧中保存了该函数的返回地址和局部变量。
在gdb(一个功能强大的源码级调试器)可以用bt命令打印所有的栈帧信息,用b命令设置断点,用r命令来运行程序直到程序结束或者遇到断点,等。
void swap(int *a, int *b){
	int *t;
	*t = *a; *a = *b; *b = *t;
}
上面的程序段是错误的,问题在于t存储的地址是什么,若赋初值int *t = 0;则内存地址“0”不一定可写。
将数组作为参数和返回值(不能使用sizeof(a)来得到数组大小,sizeof(a)将会得到数组所占字节数,应该再加一个数组大小的参数)
#include <iostream>
int sum1(int *a, int n){           //方法一
	int ans = 0;
	for(int i = 0; i < n; i++)
		ans += a[i];
	return ans;
}
int sum2(int *begin, int *end){   //方法二
	int n = end - begin;
	int ans = 0;
	for(int i = 0; i < n; i++)
		ans += begin[i];
	return ans;
}
int sum3(int *begin, int *end){   //方法三
	int ans = 0;
	for(int *p = begin; p != end; p++)
		ans += *p;
	return ans;
}
int main(){
	int b[5] = {1, 3, 5, 7, 9};
	std::cout << sum1(b+1, 4) << '\n' << sum2(b+1, b+5) << '\n' << sum3(b+1, b+5) << std::endl;
	return 0;
}
例题4.1 古老的密码(给定两个长度不超过100的字符串A,B,先对第一个字符串A的字母进行重排,再对每个字母进行一一映射,看能否变为字符串B)
算法分析:既然字母可以重排,故每个字母的位置不一样,先统计出两个字符串中各字符出现的次数,存到cnt1[26]和cnt2[26]中,又由于一个字母可以随意映射到另一个字母,故只需要对两个数组里面的数字由大到小进行排序,最终判断两个数组是否完全相等即可。这里使用了stdlib.h中的qsort函数,void qsort(void *base, size_t num, size_t size, int (*comparator)(const void*, const void*));分别对应数组地址,元素个数,每个元素大小,比较函数。
#include <cstdio>
#include <cstring>
#include <cstdlib>
int cmp(const void *a, const void *b){  //qsort中当cmp分别返回负数,0和正数时,分别表示a<b,a==b,a>b
	return *(int *)a - *(int *)b;       //这里的新内容是指向常数的万能指针const void*,可进行强制类型转换,转换为int型指针
}
int main(){
	char str1[105], str2[105];
	int cnt1[26], cnt2[26];
	memset(cnt1, 0, sizeof(cnt1));
	memset(cnt2, 0, sizeof(cnt2));
	while(scanf("%s%s", str1, str2) !=EOF){
		for(int i = 0; i < strlen(str1); i++){
			cnt1[str1[i] - 'A']++;
			cnt2[str2[i] - 'A']++;
		}
		qsort(cnt1, 26, sizeof(int), cmp);
		qsort(cnt2, 26, sizeof(int), cmp);
		int tag = 1;
		for(int i = 0; i < 26; i++)
			if(cnt1[i] != cnt2[i]) tag = 0;
		if(tag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
当然也可以#include<algorithm>,来使用其中的sort排序函数,用法为sort(buf, buf+n)或者sort(buf,buf+n,cmp),第二个sort函数前两个参数为数组范围(前闭后开区间),第三个参数为自己定义的比较函数,返回值为bool型。

4.3 递归

对于计算n!的递归函数f(n),把main()函数中的f(3)换成f(100000000)后会没有输出此时使用-g编译生成可执行文件后用gdb载入,再用r执行,gdb中会显示程序收到了SIGSEGV信号,即段错误。
编译后产生的可执行文件中保存的OS相关的内容,,对factorial.c编译后在windows使用的是PE文件格式。若执行:
D:\>size a.exe
     text      data   bss     dec   hex   filename
     2756     740  224   3720   e88    a.exe
此结果表示a.exe由正文段,数据段和bss段组成,总大小为3720。
调用栈并不存储在可执行文件中,而是在运行时创建,调用栈所在的段称为堆栈段,而堆栈段有自己的大小,每次递归调用都需要往调用栈中增加一个栈帧,久而久之就越界了,即段溢出。而局部变量也放在堆栈段中,故栈溢出不一定是递归调用太多,也可能是局部变量太大。
在某一个时刻,用gdb来查看递归函数的调用栈的栈帧信息,可以帮助我们了解递归,从上往下为程序即将处理的顺序:
(gdb) bt
#0 f (n = 0) at factorial.c: 4
#1 0x00401308 in f (n = 1) at factorial.c: 3
#2 0x00401308 in f (n = 2) at factorial.c: 3
#3 0x00401308 in f (n = 3) at factorial.c: 3
#4 0x00401359 in main   () at factorial.c: 6

4.4 竞赛题目与选讲

例题4.2 刽子手游戏(计算机想一个单词让你猜,你每次只能猜一个字母,如果单词中有那个字母,所有该字母会显示出来,你最多只能猜错6次,猜错7次就输了,猜一个已经猜过的字母也算错,本题中,你只需要输入单词和玩家的猜测,判断玩家赢了,输了或者放弃了,输入-1为游戏结束标记)
算法分析:采用自顶向下的方法,就是先写框架,再写细节,对于本题,先写主程序,包括对函数的调用,再实现函数本身,本题需要在每次猜字母时,调用guess函数。
如果我们猜对了一个字母,则用空格代替原单词中的对应字母,这是因为每次猜字母都要遍历一次单词,可以避免重复比较的麻烦,又符合题意中的“猜一个已经猜过的字母也算错”。用left表示剩余未显示的字符个数,chance表示剩余的猜错机会。再分析三种输出状态,则赢了表示在还未猜错7个字母前,单词已经全部显示出来,即left = 0而chance != 0;输了表示猜错了7个字母,而单词中还有未显示的字符,即chance = 0而left != 0;放弃了表示其他情况,可能是未猜错7个字母并且单词未全部显示出来。最后用win和lose来表示输了或者赢了的标记。
#include <cstdio>
#include <cstring>
char word[105],gue[105];
bool win, lose;
int left, chance, rnd; //rnd表示轮数,当输入-1时结束
void guess(char ch);
int main(){
	while(scanf("%d%s%s", &rnd, word, gue) != EOF && rnd != -1){
		printf("Round %d\n", rnd);
		chance = 7;
		left = strlen(word);
		win = lose = false;
		for(int i = 0; i < strlen(gue); i++){
			guess(gue[i]);
			if(lose || win) break;
		}
		if(win) printf("You Win.\n");
		else if(lose) printf("You Lose.\n");
		else printf("You chickened out.\n");
	}
	return 0;
}
	
void guess(char ch){
	int bad = 1;
	for(int i = 0; i < strlen(word); i++){
		if(ch == word[i]){ left--; word[i] = ' '; bad = 0; }
	}
	if(bad) chance--;
	if(!left && chance) win = true;
	if(!chance && !left) lose = true;
}
如count, min, max, round等都是库函数中使用过的名字,最好在程序中避免使用它们。本题也可设置一个标记数组guessed[256]来表示对应单词中的字母是否已经显示出来。
例题4.3 救济金发送(n(n<20)个人站成一圈,逆时针编号为1~n,A从1开始顺时针数,B从n开始逆时针数,每一次,A选k个就停下来,B数m个就下来,选中的两个人(也有可能是正好是同一个人)离开队伍,如此反复,至全部出队,例如n = 10, k = 4, m = 3,输出4 8, 9 5, 3 1, 2 6,10, 7)
算法分析:设置一个数组,存放每个人对应的编号,当选中某个人后,对应的编号设置为0,这样就能省去重复比较的麻烦。可以写一个循环函数,int go(int p, int d, int t);其中p为上一次计数结束对应的数组下标,d表示顺时针或者逆时针,t为步长m或k。返回选中的数组下标。
<span style="font-size:10px;">#include <cstdio>
int go(int p, int q, int t);
int num[30];
int n, k, m, left;
int main(){
	while(scanf("%d%d%d", &n, &k, &m) != EOF){
		left = n;
		int p1 = n, p2 = 1;
		for(int i = 1; i <= n; i++) num[i] = i;
		while(left){
			p1 = go(p1, 1, k);
			p2 = go(p2, -1, m);
			printf("%3d", p1); left--;
			if(p2 != p1) { printf("%3d", p2); left--; }
			num[p1] = num[p2] = 0;
			if(left) printf(",");
		}
		printf("\n");
	}
	return 0;
}

int go(int p, int q, int t){
	while(t--){
		do{ p = (p - 1 + q + n) % n + 1; }while(num[p] == 0); //p-1使标号由1~n变为0~n-1,再按照常规方式寻找p-1的下一位置,最后将标号加1由0~n-1还原至1~n
	}                         //走到下一个非0的数字
	return p;
}</span>
例题4.4 信息解码(考虑下面的01串序列:0,00,01,10,000,001,010,011,100,101,110,……它对应着一个编码头的各个字符,每小节以三个二进制位表示本节编码长度,以编码长度个1表示本节结束,以三个0位表示本文本结束。题目要求对给定二进制编码文本解码。例如编码头为$#**,编码文本为0100000101101100011100101000,则应该这样解码:010(编码长度为2)00(#)00(#)10(*)11(小节结束)011(编码长度为3)000(\)111(小节结束)001(编码长度为1)0($)1(小节结束)000(编码结束)。
算法分析:首先考虑编码的存放,用codes[len][value]来表示一个字符编码,其中len表示编码长度,value表示对应十进制数,则对于上面的codes[1][0] = '$',codes[2][0] = '#',codes[2][1] = '*',codes[3][1] = '*'。
程序的大致思路为:1,编写readcode函数读取编码头,并按上述规则存放至数组code中。
2,设置一个无条件循环,循环内部每次先读取前三个二进制位来获悉本节编码长度(如果当读取三个0时表示文本结束,break),然后对本节的每个编码长度个二进制位进行解码并输出,直到遇到全1(十进制数为2^len - 1),此时可以编写一个readint函数来得到编码长度个二进制位对应的十进制数。
<span style="font-size:10px;">#include<stdio.h>
#include<string.h>

int code[8][1<<8];
int readchar(){
  for(;;) {
    int ch = getchar();
    if(ch != '\n' && ch != '\r') return ch;
  }
}

int readint(int c){    //有些编码文本很长,可能会由多行组成,此函数是方便读取编码文本的
  int v = 0;
  while(c--) v = v * 2 + readchar() - '0';
  return v;
}

int readcodes(){
  memset(code, 0, sizeof(code));
  code[1][0] = readchar();   //直接调到下一行开始读取,先用readchar读取第一个字符再用普通的getchar读取剩余的字符直到遇到\n,防止不必要的错误
  for(int len = 2; len <= 7; len++) {
    for(int i = 0; i < (1<<len)-1; i++) {
      int ch = getchar();     
      if(ch == EOF) return 0;
      if(ch == '\n' || ch == '\r') return 1; //\n 换行,将当前位置移到下一行开头,\r 回车,将当前位置移到本行开头
      code[len][i] = ch;
    }
  }
  return 1;
}

int main() {
  while(readcodes()) {
    for(;;) {
      int len = readint(3);   //先读取字节头,来查看本节编码长度
      if(len == 0) break;
      for(;;) {
        int v = readint(len); //读取本节的编码,至遇到全1结束
        if(v == (1 << len)-1) break;
        putchar(code[len][v]);
      }
    }
    putchar('\n');
  }
  return 0;
}</span>
例题4.5 追踪电子表格中的单元格
例题4.6 师兄帮帮忙

4.5 注解与习题

在编写实用软件时,往往需要编写自己的头文件,以下是常用函数及其头文件

























版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qibofang/article/details/50041653

智能推荐

java动态规划算法_南风知易✓✓✓的博客-程序员宅基地

java 动态规划算法递归算法的时间复杂度=递归的次数递归函数本身的时间复杂度*

典型电路的收集与记录__Jason^_^的博客-程序员宅基地

5V to 3V3通过AMS1117-3.3,将电压降至3V3,钽电容是必须的。蜂鸣器电路通过ss8050的NPN三极管实现对蜂鸣器的控制LED电路通过限流电阻对LED的电流和亮度进行控制。但每种颜色所配合的电阻还需实验,达到LED能亮同时又不晃眼睛的效果。...

Spinner的两种调用数据放式_faith_boys的博客-程序员宅基地

ArrayAdapter adapter = new ArrayAdapter(this, android.R.layout.simple_spinner_item, mLmtdReptStr);adapter.setDropDownViewResource(android.R.layout.simple_spinner_dropdown_item);mSpinner.setAd

ROS arbotix踩坑:‘rospkg‘、except UnicodeDecodeError, exc、dynamic module does not define init function_#君君#的博客-程序员宅基地_ros 安装rospkg

在执行roslaunch mbot_description arbotix_mbot_with_camera_xacro.launch文件时,即包含arbotix模块的程序时,报错No module named ‘rospkg’ 。报错No module named 'rospkg'经过对大家文章的查看,发现基本集中在把环境配置为python3.或者安装rospkg。但是仍没有解决。查看opt/ros/melodic/lib/python2.7/dist-packages,发现根本没有ro.

面试题:实现数组扁平化_weixin_34056162的博客-程序员宅基地

什么是数组扁平化数组扁平化是指将一个多维数组变为一维数组reduce 方法实现reduce 本身就是一个迭代循环器,通常用于累加,所以根据这一特点有以下:const arr1 = [1,[4,6],[8,3,[19,38]]]function flatten(arr) { return arr.reduce((result, item)=&gt; { return re...

JfreeChart用法总结_shiyan0634的博客-程序员宅基地

一、简介 WW 的发展使得基于因特网的应用程序不再局限于静态或者简单的动态内容提供。传统的一些以软件包形式发布应用程序例如报表系统等都在逐渐搬到因特网上。但是这两者之间有着天壤之别,虽然对于数据获取、业务处理等方面基本类似,但是最大的差别在于用户界面。为了能在web浏览器上显示要求用户界面使用 HTML以及图片的方式来展现数据,而传统的一些利用操作系统本身的控件来开发的用户界面无法适应琳琅满目

随便推点

聊聊身份认证的那些事(开篇)_罗斯839的博客-程序员宅基地_cas流程

开篇身份认证,对于一个安全的应用来说,是第一道门槛,它为后续所有的安全措施提供了“身份”这样一个关键信息。通常每个公司会有好几个外部应用,如果每一个应用使用独立的账号体系,管理起来会非常复杂,用户也需要保存好几个账号密码,严重影响使用体验。而且公司内部的各个管理或开发系统,比如各种服务器、confluence、jira、gitlab等也都使用单独的账号,一个开发人员要记住各种纷繁杂乱的账号和密码,如果不提前保存下来,根本不可能能靠记忆完成输入。这时,如何设计一个简单易用的身份认证体系就显得尤为重要

Vscode的使用小技巧_weixin_30399821的博客-程序员宅基地

命令行启动code如果你的系统是Linux系统(我使用的是Ubuntu 16.04)这样就可以直接使用 code + filename来编辑文件(就像vi + filename)如果你的系统是MacOS 就需要在vscode里面按 command + shift + p 之后输入 shell 基本上在第一提示里面就会显示安装code,如图所示转载于:https://www.cnblo...

SpringMVC -> 转发(forward)和重定向(redirect)_欧皇小德子的博客-程序员宅基地_springmvc转发的关键字是redirect

默认写法就是转发:return的字符串将对应的前端页面转发到要求的url上配置了视图解析器的viewsresolver @RequestMapping("/hello/{a}/{b}") public String hello(@PathVariable int a, @PathVariable int b, Model model) { model.addAttribute("haha", "结果:" + (a + b)); return "hello"; }没有视图解析器

ros kinetic 自带opencv3 与 opencv 2 的兼容问题_原野寻踪的博客-程序员宅基地

问题分析自己写的系统必须基于opencv 2.x,而ros kinetic自带了opencv3的版本。于是在编译时报错:/usr/bin/ld: CMakeFiles/xxxx.cpp.o: undefined reference to symbol '_ZN2cv6String10deallocateEv'/opt/ros/kinetic/lib/x86_64-linux-gnu/l...

Latex002 | 详细教程:LaTeX 编译器哪个好?——如何在 Visual Studio Code 中全流程编写 LaTeX(上篇)_爱学习的Allan的博客-程序员宅基地_latex编译器

你是否在编写 LaTeX 过程中遇到了编译器“不给力”,无法自动补全、缩进等问题?本文比较了流行的 LaTeX 的编译器,并简要分析了其优势与不足,最终给出解决方案。