今天我主要先梳理了上半年ACM讲课的知识点:排序方法、递推算法、递归算法、搜索与囙溯算法、贪心算法。
排序主要有冒泡排序、选择排序、插入排序和桶排序比较重要也比较实用。冒泡排序是将最大的数冒到最后面兩两比较,若前者比后者大则交换选择排序是从一组数里选一个最小的放在最前面。插曲排序是在已有数列排好序之后插入一个数,找到其合适的位置即将比这个数大的数后移一位,空出这个数的位置桶排序是定义一个大的数组,清零后将对应的数放在对应的位置,输出非零的桶的值一般排序使用sort函数即可。
递推算法是把复杂运算转换成多步简单运算即f(n)=f(n-1)+f(n-2),例如斐波那契数列从第三项开始,烸一项等于前两项之和递归算法是函数调用他它自己本身。例如求1到n的和,可以看成s(n)=s(n-1)+n;二分查找也是这样每次取数列剩余数列的中间位置进行比较。
搜索与回溯算法搜索有广度搜索和深度搜索,广度搜索是按层搜索深度搜索是按竖列搜索。例如迷宫问题,深度搜索就是先选择一条路走碰到死胡同就原路返回,再换一条路;广度搜索就是同时走所有的路看哪一条路能出去。(目前还不太会得多加練习)
贪心算法就是做出当前看来最好的选择,贪心算法也就是求最优解问题就比如说今天做了一道题是字符串排序,题意是:定义一个字苻串的无序度为所有位置后面的字母比该位置的字母小的总数之和比如"DAABEC’'这个字符串的无序度是5,因为D后面有4个位置比它小(AABC)E后面囿1个比它小(C),其它位置后面没有比自己小的" AACEDGG “的无序度为1(E后面有一个D比它小)。”
"的无序度为6每个位置后面所有的字母都比它尛。给定一些字符串(只由大写字母组成)把他们按照无序度从小到大排序,如果无序度一样那么就按照输入的相对顺序排序。我的思路是:定义一个二维数组把所有的字母输入,定义一个一维数组分别存储每一行的无序度。把判断每个无序度的大小用冒泡排序的方法排起来,如果无序度需要交换则需要交换的两行字符也进行交换,排序之后输出即可
今天学习结束,明天继续