acmicpc编程基础_5

《acmicpc编程基础_5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM/ICPC编程基础第五节1、排序2、递归ACM/ICPC编程基础作业（一）•题目：考试排名•内容：DOJ1264作业（二）•题目：放苹果•内容：POJ1664•注意：自己去实验室的FTP上下载一本书《程序设计导引及在线实践》，自己学习这题的解法。•9.5节，放苹果•如果FTP无法打开，请联系张超学长。思考题•汉诺塔•3•有三根金刚石柱子，在柱•A-->C子a上从下往上按大小顺序摞着n片圆盘。要求把圆盘•A-->B按大小顺序重新摆放在另一根柱子上。并且规定，•C-->B在小圆盘上不能放大圆盘•A-->C，在三根柱子之间一次只能移动一个圆盘。•B-->A•B-->C•A

2、-->C排序•C语言中排序使用qsort函数。–使用起来不方便，不作详细介绍。•C++中排序使用库中的sort函数。•两个函数的时间复杂度都是O(nlogn)。•冒泡排序是O(n^2)C语言中的qsort函数•voidqsort(void*base,intnelem,intwidth,int(*fcmp)(constvoid*,constvoid*));•参数：–base待排序数组首地址–nelem数组中待排序元素数量–width各元素的占用空间大小–fcmp指向函数的指针，用于确定排序的顺序qsort整数数组qsort结构体C++中的sort函数•

3、#include•voidsort(iteratorstart,iteratorend);•voidsort(iteratorstart,iteratorend,StrictWeakOrderingcmp);•start是排序开始位置。•end是排序结束位置的下一个位置•cmp是一个模板比较函数。C++sort整型数组C++sort结构体在C++中可以直接比较的数据类型•全部基本类型–int;double;char•string类需要引入比较函数的数据类型•结构体•数组–自己搜索相关资料学习递归•递归做为一种算法在程序设计语言中广泛应用•是指函数/过

4、程/子程序在运行过程中直接或间接调用自身而产生的重入现象•递归是计算机科学的一个重要概念•递归的方法是程序设计中有效的方法•采用递归编写程序能使程序变得简洁和清晰.。fibonacci处理递归的一般思路•1、如何定义状态–f(n)表示第n个fibonacci数•2、边界条件–在什么条件下可以结束递归–当n为0或1时，可以结束递归。•3、递归公式–当前状态可以由哪几个更小的状态得到。–f(n)=f(n-1)+f(n-2)汉诺塔•有三根金刚石柱子，在•3柱子a上从下往上按大•A-->C小顺序摞着n片圆盘。要求把圆盘按大小顺序•A-->B重新摆放在另一根柱子•C-->B上。并且

5、规定，在小圆盘上不能放大圆盘，在•A-->C三根柱子之间一次只能•B-->A移动一个圆盘。•B-->C•A-->C汉诺塔的一般思路•1、如何定义状态–voidf(intn,chara,charb,charc)–f(n,a,b,c)表示a上面有n个盘，b作为中转，全部移动到c上面。•2、边界条件–当n为1的时候，直接输出a->c–printf(“%c->%c”,a,c);•3、递归公式–首先把a上面的n-1个移动到b上。–然后把a的最后一个移动到c上–最后把b的n-1个移动到c上。汉诺塔的基本代码