近期几个基础算法(高级算法分析与设计)
高级算法分析与设计
- 排序算法(BubbleSort，Quicksort）
- 数组(容器)
- 递归与优化迭代
- 二分查找
- DP(动态规划)
1.字符串的冒泡排序
我们已经知道了将N个整数按从小到大排序的冒泡排序法。本题要求将此方法用于字符串序列，并对任意给定的K（<N），输出扫描完第K遍后的中间结果序列。
输入格式： 输入在第1行中给出N和K（1≤K<N≤100），此后N行，每行包含一个长度不超过10的、仅由小写英文字母组成的非空字符串。
输出格式： 输出冒泡排序法扫描完第K遍后的中间结果序列，每行包含一个字符串。
输入样例：
6 2
best
cat
east
a
free
day
输出样例：
best
a
cat
day
east
free
# include <stdio.h>
# include <string.h> //需要用到字符串中字典序等操作函数
int main(){ //主函数
char a[100][10], temp[11]; //定义字符串数组a，后面冒泡需要的交换数组temp
//题目中限定1≤K<N≤100，此后N行，每字母长度不超过10
int K,N,i,j; //定义整型变量
scanf("%d %d", &N, &K); //输入N行，K次遍历次数
for (i = 0; i <= N; i++){ //循环输出字符串
scanf("%s",a[i]); //gets()字符串函数的输入，并将其存放在二维数组的一维中
}
for (i = 1; i <= K; i++){ //冒泡排序算法
for(j = 0;j <= N - i;j++) {
/* 因为字符串交换不能用通常的方法，需要strcpy()函数进行操作，
即strcpy(A,B)，将B复制到A，而strcmp()函数用来字符串间的大小比较
将a[j]与a[j+1]即比较首字母排序
如果在字典序，a[j]>a[j+1]则进行：
将a[i]复制到temp数组中，
再将a[j+1]复制到a[j],
最后将temp复制到a[j+1]。
以上操作即为交换，
如：temp = a；
a = b；
b = temp； */
if (strcmp(a[j], a[j + 1]) > 0){
strcpy(temp, a[j]);
strcpy(a[j], a[j + 1]);
strcpy(a[j + 1], temp);
}
}
}
for (i = 0; i <= N; i++){ //循环遍历N次运用字符串输出方式puts
printf("%s",a[i]);
}
return 0;
}
在Dev-C++ 编译情况：
对于排序算法，BubbleSort是最最最基础最基本的排序算法。
其主要思想就是交换。
记得前不久某厂面试题中，提到了Quicksort。
算法课上，老师在讲分治策略时，第一讲了快排。
2.统计工龄
给定公司N名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。
输入格式: 输入首先给出正整数N（≤10 5 ），即员工总人数；随后给出N个整数，即每个员工的工龄，范围在[0, 50]。
输出格式: 按工龄的递增顺序输出每个工龄的员工个数，格式为：“工龄:人数”。每项占一行。如果人数为0则不输出该项。
输入样例:
8
10 2 0 5 7 2 5 2
输出样例:
0:1
2:3
5:2
7:1
10:1
#include <iostream> //c++ 头文件预处理
#include <vector> //vector头文件预处理
using namespace std;
int main() { //主函数main()
vector<int> scope(51, 0); //选用vector代替数组，作为容器存入工龄
/* vetcor <变量类型> 标识符 (最大容量,初始值) */
int N, a, i; //定义整型变量N，a为工龄，i为增序排序需要的变量
cin >> N ; //输入流N，N名工人
while (N--) { /*这里使用while循环，原本打算使用for循环，
但运用while代码效率有明显提高。*/
cin >> a; //输入工龄a。
scope[a]++; //这里运用vector容器中数组scope存入工龄
}
for (i = 0;i < 51 ;i++) { /*运用for循环，进行增序排序，
从[0,51)进行对已经存入的工龄数值使用遍历排序。*/
if (scope[i]) /*这里我设定的数组[] ！=0，若不等于0，
且表明输入并存在容器中的工龄符合0~50岁，
则进行输入，并对重复的工龄实现i++，累加统计。*/
cout << i << ":" << scope[i] << endl; //输出流cout，工龄：工龄个数。
}
return 0; //正确即返回值。
}
在Dev-C++ 编译情况：
这里主要用到了C++ STL中vector容器的使用，跟数组用法相似，
这里也可以去使用数组去存储数据。详解我已经在代码块中注释出来。
也可以用到桶排序。
3.递归求Fabonacci数列
本题要求实现求Fabonacci数列项的函数。Fabonacci数列的定义如下：
f(n)=f(n−2)+f(n−1) (n≥2)，其中f(0)=0，f(1)=1。
函数接口定义：
int f( int n );
函数f应返回第n个Fabonacci数。题目保证输入输出在长整型范围内。建议用递归实现。
裁判测试程序样例：
#include <stdio.h>
int f( int n );
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", f(n));
return 0;
}
/ 你的代码将被嵌在这里 /
输入样例：
6
输出样例：
8
int f(int n){
if(n <= 0){
return 0;
}
if(n==1 || n==2){
return 1;
}
return f(n-1)+f(n-2);
}
已知Fibonacci数列就是前两个数相加得到第三个数。
定义函数f后，考虑情况：当小于等于0，等于1or2。
分别return数值多少。
4.Fibonacci数列优化版
求Finonacci数列的第n项，n<=60，其中第1项为1，第2项为1。
输入格式: 输入在第一行给出一个正整数N（≤100），是待求取的数的个数。随后N行，输入n个数字num。
输出格式: 对每一组输入num，在一行中输出Finonacci数列的第num项的值。
输入样例: 在这里给出一组输入。例如：
3
3
5
6
输出样例: 在这里给出相应的输出。例如：2
5
8
#include<iostream>
using namespace std;
int Fib(int num){
if(num <= 0){
return 1;
}
if(num==1|| num==2){
return 1;
}
return Fib(num-1)+Fib(num-2);
}
int main(){
int N,num,i;
int j=1;
int a[60];
cin >> N;
for(i=1;i<=N;i++){
cin >> num;
a[j] = Fib(num);
j++;
}
for(j=1;j<=N;j++){
cout << a[j] <<endl;
}
return 0;
}
Dev-C++ 编译情况：
这里并没有ac这道题，问题在于递归会引发TLE(超时)。
对于给出的测试点会正确，但是在后续的运行会导致很高的时间复杂度。
不断的会进行很多重复性问题的计算。
5.二分查找
函数接口定义：
Position BinarySearch( List L, ElementType X );
其中List结构定义如下：
typedef int Position;
typedef struct LNode *List;struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */};
L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 10
#define NotFound 0 typedef int ElementType;typedef int Position; typedef struct LNode List; struct LNode {
ElementType Data[MAXSIZE];
Position Last; / 保存线性表中最后一个元素的位置 / };
List ReadInput(); / 裁判实现，细节不表。元素从下标1开始存储 */ Position BinarySearch(
List L, ElementType X );int main() {
List L;
ElementType X;
Position P;
L = ReadInput();
scanf("%d", &X);
P = BinarySearch( L, X );
printf("%d\n", P);
return 0;
}/* 你的代码将被嵌在这里 */
输入样例1：
5
12 31 55 89 101 31
输出样例1： 2
输入样例2：
3
26 78 233
31
输出样例2： 0
Position BinarySearch( List L, ElementType X ){
if(L==NULL){ //表为空，返回0
return 0;
}
int right=L->Last;
int left=1;
int mid; //mid为left和right中点
while(left <= right)
{ //如果left>right就没办法形成闭区间
mid = (left + right) / 2; //取中点
if(L->Data[mid]==X){ //找到目标，返回下标
return mid;
}
else if(L->Data[mid]>X){ //中间数大于K
right = mid - 1; //往左子区间[left,mid - 1]查找
}
else{ //中间的数小于K
left = mid + 1; //往右子区间[mid + 1,right]查找
}
}
return NotFound; //没有找到，返回NotFound
}
6.动态规划
对于青蛙跳台阶，亦或者是跳台阶问题，和Fibonacci数列有相似之处。
可以采用递归、迭代、dp动态规划的算法思想。
在清华版《算法设计与分析》P52，对DP进行了概述。
对时间复杂度进行消减，优化处理，进一步优化算法，
提高计算机计算效率有很大意义。