acmicpc编程基础_6

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

1、ACM/ICPC编程基础第六节递归与分治ACM/ICPC编程基础课前的话•1、作业及选课（见BBS）–实验记录册：–期末大作业：•2、下学期选课：•3、关于退出作业•1、DOJ1317–题目：好大呀！•2、DOJ1190–题目：二叉树的遍历什么是递归•先通过一个小例子来为大家讲一下。•Fibonacci数列–a[n]=a[n-1]+a[n-2](n>=2)–=1(n==0&&n==1)•Fibonacci数列的递归算法ACM/ICPC编程基础什么是递归•递归，简单地说，是指函数自己调用自己。•递归算法，是将原问题分解为若干个子问题。子问题的求解方法与原问题完全相同，仅仅是规模

2、有所降低。ACM/ICPC编程基础为什么要使用递归•一、可以使程序思路清晰。•二、可以降低问题的规模–如上例中，将求第n个fibonacci数变为求第n-1个fibonacci数和第n-2个fibonacci。问题的规模下降了1~2。•在求fibonacci数列时，递归的优势还不是很明显，甚至比普通算法还要慢。ACM/ICPC编程基础分治•分治是一种特殊的递归。•分治是将原问题分解为规模大致相等的两个子问题，分别解决。然后再将子问题的解合并，得到原问题的解。•子问题与原问题是相同的问题，仅仅是规模差了一半。所以可以使用递归解决。ACM/ICPC编程基础分治方法举例•求a^32

3、（a的32次方，暂时忽略变量能够存储的数据范围问题）–一般算法，将需要进行大约32次乘法。–a^32=a^16*a^16;//第一次乘法–a^16=a^8*a^8;//第二次乘法–a^8=a^4*a^4;//第三次乘法–a^4=a^2*a^2;//第四次乘法–a^2=a*a;//第五次乘法–O(5)=O(log32);–分治方法可以将时间由O(n)降到O(logn)。ACM/ICPC编程基础思维扩展•a^33最少需要几次乘法可以求出？•a^n最少需要几次乘法可以求出？如何解？–例a^37–3710=001001012（我的思路，不知道是不是最少的）–a^37=a^32*a^4

4、*a^1;–5+2=7–a^n大约需要最多2*logn次乘法，时间复杂度为O(logn)（什么时候达到最多？70以内）–63•如何进行二进制分解？–位运算ACM/ICPC编程基础C++中的位运算操作•&•按位与•

5、•按位或•~•按位取反•^•按位异或•<<•左移位•>>•右移位Elephant讲图论&（按位与）•1&1→1•37→00100101•1&0→0•54→00110110•0&1→0•00100101•0&0→0•&•37&54→?•00110110•按位与•00100100•&&（逻辑与）•00100100→36Elephant讲图论

6、（按位或）•1

7、1→1•37

8、→00100101•1

9、0→1•54→00110110•0

10、1→1•00100101•0

11、0→0•

12、•37

13、54→?•00110110•按位或•00110111•

14、

15、（逻辑或）•00110111→55Elephant讲图论~（按位取反）•~1→0•~0→1•~37？•按位取反•！（逻辑非）Elephant讲图论^（按位异或）•1^1→0•37→00100101•1^0→1•54→00110110•0^1→1•00100101•0^0→0•^•异吗？•00110110–是1，非0•00010011•37^54→?•00010011→19•按位异或Elephant讲图论<<（左移

16、位）和>>（右移位）•1、抛弃原则•2、补零原则（平台相关）–嵌入式系统•37<<1？•37>>1？•<<相当于乘2•>>相当于整除2Elephant讲图论例1：判1•如何知道一个数第i位是0还是1？•n=00100101•i=76543210•发散思维•n&(1<

17、位置取反。Elephant讲图论负数与补码•~37？•~（-37）？Elephant讲图论美妙的二进制•二进制是计算机领域美妙而又神奇的东西，熟练掌握二进制的处理是所有计算机爱好者所必备的能力。•我们定义一个函数f(x)求x的二进制表示中最右边的1的位置所表示的十进制数。如6的二进制表示为：110，故f(6)=2，同理f(7)=1，f(8)=8。•输入：N•输出：f(N)树•什么是树？建设工程学部–具体的定义我也记不清了。水利工程学院土木工程学院交通工程学院•树是一种数据结构，港它有以下几个特点水口土建