题目1：二分查找
题目标签
二分查找,只需定义一个count
题目描述
大家一定都能熟练掌握二分查找啦！那么来计算二分的次数吧！
约定二分的中点mid = (left + right) / 2。
输入描述
第一行输入一个整数N（N<=10000）。
第二行输入N个升序整数。
第三行输入一个待查找的整数（必定在第二行中出现过）。
输出描述
输出二分查找该整数时，进行过多少次二分。
输入样例：
5
18 53 54 74 99
53
输出样例：
2
参考代码
#include<iostream>
#include<set>
using namespace std;
int main(){
int n;
cin >> n;
int a[n];
for(int i = 0;i < n;i++) cin >> a[i];
int target;
cin >> target;
int low = 0,high = n - 1,count = 0;
while(low < high){
count++;
int mid = low + high >> 1;
if(a[mid] == target) break;
if(a[mid] > target) high = mid - 1;
else low = mid + 1;
}
cout << count;
}
拓展：二分的思想，能想起题目找0-n之间缺的数字
题目2：字符串距离编辑
题目标签
经典dp，轻松拿下
题目描述
把两个字符串变成相同的三个基本操作定义如下：
1.修改一个字符（如把a变成b）
2.增加一个字符(如abed 变成abedd)
3.删除一个字符（如jackbllog 变成jackblog）
如针对于jackbllog到jackblog 只需要删除一个l就可以把两个字符串变为相同。
把这种操作需要的最小次数定义为两个字符串的编辑距离L。
输入描述
编写程序计算指定文件中字符串的距离。
输入两个长度不超过512 字节的ASCII 字符串
，在屏幕上输出字符串的编辑距离。
输入样例：
Hello world!
Hello word!
输出样例：
1
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int m, n;
char a[N],b[N];
int dp[N][N];
int main()
{
scanf("%d%s", &m, a + 1); // a + 1 这里的小技巧
scanf("%d%s", &n, b + 1);
for(int i = 0; i <= m; i++) dp[i][0] = i; //全删除
for(int i = 0; i <= n; i++) dp[0][i] = i; //全插入
for(int i = 1; i <=m; i++)
for(int j = 1; j <=n; j++)//外层是a数组，下标从1开始
{
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1;//表示修改增删
//替换或者不变
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a[i] != b[j])); // 注意这里 i的原因 是 scanf("%d%s", &m, a + 1);
}
printf("%d\n",dp[m][n]);
return 0;
}
题目3：二叉树前中后序遍历
题目标签
二叉树前中后序遍历
题目描述
输入一棵二叉树，输出树的前、中、后序遍历结果。
输入一个整数N（N<= 10000)，表示树中有N个结点（编号0~N-1）。
接下来N行，依次为结点0~结点N-1的左右孩子情况。
每行3个整数，F,L,R。L,R为F的左右孩子。L,R如果为-1表示该位置上没有孩子。
分三行分别输出树的前中后序遍历。
同一行中的数字，用一个空格间隔。
输入样例：
5
0 3 1
1 2 -1
2 -1 4
3 -1 -1
4 -1 -1
输出样例：
0 3 1 2 4
3 0 2 4 1
3 4 2 1 0
参考代码
#include <stdio.h>
const int maxn=10010;
struct node{
int lchild,rchild;
}Node[maxn];
int n,num=0;
bool flag[maxn]={false};
void print(int id){
printf("%d",id);
num++;
if(num<n)
printf(" ");
else
printf("\n");
}
void preOrder(int root){
if(root==-1)
return;
print(root);
preOrder(Node[root].lchild);
preOrder(Node[root].rchild);
}
void inOrder(int root){
if(root==-1)
return;
inOrder(Node[root].lchild);
print(root);
inOrder(Node[root].rchild);
}
void postOrder(int root){
if(root==-1)
return;
postOrder(Node[root].lchild);
postOrder(Node[root].rchild);
print(root);
}
int main(){
int x,left,right;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d%d",&x,&left,&right);
Node[x].lchild=left;
Node[x].rchild=right;
flag[left]=true;
flag[right]=true;
}
int root;
for(int i=0;i<n;i++){
if(flag[i]==false){
root=i;
}
}
preOrder(root);
num=0;
inOrder(root);
num=0;
postOrder(root);
return 0;
}
题目4：Hanoi塔
题目标签
经典中的经典中的经典递归，初试练习过计算时间复杂度
题目描述
Hanoi 塔问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64 个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。
请编写程序，把A 柱上的n 个金片，搬动到C 柱（中间可以使用B 柱），使得搬动的次数最少。输入金片的个数n（1<=n<=64），输出总搬动次数，以及最后100 次搬动。如果搬动次数小于等于100 则全部输出；每个搬动占一行，加上是这第几次搬动的数字和”:”，格式见示例。
输入样例：
2
输出样例：
3
1:A->B
2:A->C
3:B->C
参考代码
#include<iostream>
using namespace std;
int dp[65],current,n;
//输出
void printfs(char from,char to){
current++;
if(dp[n] <= 100 || dp[n] - current < 100)
printf("%d:%c->%c\n",current,from,to);
return;
}
//将n个环从 x杆移动到y杆
void move1(char from,char to,char helper,int n){ //helper
if(n == 1) {
printfs(from,to);
return;
}
// 将n-1个环从x移动到z
move1(from,helper,to,n-1);
//把第n个环从x移动到y
move1(from,to,helper,1);
//把n-1个环从z移动到y
move1(helper,to,from,n-1);
}
int main(){
cin >> n;
dp[1] = 1;
dp[2] = 3;
for(int i = 3;i <= n;i++)
dp[i] = dp[i - 1] * 2 + 1; //dp[i]为将i个环从a杆移动到c杆的最少次数
cout << dp[n] << endl;
move1('A','C','B',n);
return 0;
}
