测试卷1.0

1. 旧事重提

二分法实现幂函数x的n次方pow(x,n)

这里的二分法是指减少乘法的次数，把重复的运算省去。我要求x的n次方，那么先求x的n/2次方，然后两个相乘起来。如此递归下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int pow(int x,int n){
    int t=1;
    while(n){
        if(n%2==1){
            n=n-1;
            t*=x;
        }
        x*=x;
        n/=2;
    }
    return t;
}

double fun(double x,int n){
    if(n==0)//递归结束条件
        return 1;
    double half;
    if(n%2==1){//递归转移方程
        half=fun(x,n/2);//x的n/2次方
        return x*half*half;
    }else{
        half=fun(x,n/2);
        return half*half;
    }
}
double pow(double x,int n){
    double result=fun(x,n);
    if(n<0)
        result=1/result;
    return result;
}

2. 有两个n维向量相乘，求其点乘的最小值

两个n维的向量，相乘的点是指将向量对应维度的乘积相加，但是我们可以将向量维度交换下可以得到更小的向量点乘，例如3维向量：1,3,-5和4,-2,-1最小向量点乘为-27，即将维度变为：3,1,-5和-2,-1,4。只需要把第一个向量进行全排列，就可以得到所有的乘积

程序设计要求：输入一个整数n为向量的维度，然后输入两个n维度的向量，用空格区别向量元素，输出为一行，包含一个整数，为最小的点乘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
1. 进行全排列:三行代码 交换 进入下一层 再交换
2. 当排列好之后进行点乘，当结果小于当前最小值时候进行更新
*/

#include<iostream>
using namespace std;
const int Maxnn=1e9+1;//数值的最大值
const int Maxn=1e2+1;//数组的最大值
int n;
int a[Maxn],b[Maxn];
int sum;
void backtrack(int t){
    if(t>n){
        sum=0;
        for(int i=1;i<=n;i++)
            sum+=a[i]*b[i];
        if(sum<ans)
            ans=sum;
    }else{
        for(int i=t;i<=n;i++)//从第t个元素交换到第n的元素
        {
            swap(a[t],a[i]);
            backtrack(t+1);
            swap(a[t],a[i]);//回溯，使得a[t]的值不变
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    backtrack(1);
    cout<<ans<<endl;
    return 0;
}

3. 二叉排序树删除某个结点。要求用非递归算法并释放掉该结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
1. 首先判断这个结点是否有右子树；无：直接用这个结点的左子树覆盖当前结点
2. 判断一下是否有左子树；无：直接用右子树来覆盖当前结点
3. 当左右子树都存在时候，从p的左子树的最右结点（最大值）赋值给当前结点p，左子树中的最右结点给删除。
*/
void Delete(BiTree *p){
    BiTree *q,*s;
    if(p->rchild==NULL)/*左子树空只需要重接它的左子树（待删节点是叶子也走此分支）*/
    {
        p=p->lchild;
        if(p==NULL) delete p;
    }else if(p->lchild==NULL){
        p=p->rchild;
    }else{
        q=p;
        s=p->lchild;
        while(s->rchild){
            q=s;
            s=s->rchild;
        }
        p->data=s->data;//s指向被删结点的直接前驱
        if(q!=p)//s有右子树
        {
            q->rchild=s->lchild;//重接q的右子树
        }else{
            q->lchild=s->lchild;//重接q的左子树
        }
    }
}

4. 用回溯法来解决装载问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>//子集树
using namespace std;
const int Maxn=1e3+7;
int c;//第一个轮船装载量
int n;
int w[Maxn];
int r;//剩余重量
int x[Maxn];//记录n个集装箱是否被装入
int cw;//当前载重量
int bestw;//最优载重量
int bestx[Maxn];//最优装载情况
void backtrack(int t){
    if(t>n){
        if(cw>bestw){
            bestw=cw;
            for(int i=1;i<=n;i++)
                bestx[i]=x[i];
        }
        return;
    }
    r-=w[t];//搜索左子树 i---i+1---n
    if(vw+w[t]<=c){
        cw+=w[t];
        x[t]=1;
        backtrack(t+1);
        cw-=w[t];//回溯到上一层
    }
    if(r+cw>bestw)//当前载重量加上剩余集装箱的重量大于最优质才能进行右子树
    {
        x[t]=0;
        backtrack(t+1);
    }
    r+=w[t];//回溯到上一层
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<=n;i++)
        r+=w[i];
    backtrack(1);
    for(int i=0;i<=n;i++)
        cout<<bestx[i]<<"\t";
    cout<<endl;
    return 0;
}

5. 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，才用二叉链表存储，结点结构为：left weight right，其中叶结点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，请设计求T的WPL的算法。要求：

  1. 给出算法的基本设计思想
  2. 使用C或C++语言，给出二叉树结点的数据类型定义
  3. 根据设计思想，采用C或C++语言描述算法，关键之处给出注释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
1. 本问题采用递归算法实现，根据定义:
二叉树的WPL值=树中全部也结点的带权路径长度之和
=根结点左子树中全部叶节点的带权路径长度之和+根结点右子树中全部叶节点的带权路径长度之和
叶节点的带权路径长度=该点的weight域的值*该节点的深度 
设根结点的深度为0，若某结点的深度为d时，则其孩子结点的深度为d+1。
*/
struct BTree{
    int weight;
    BTree *left,*right;
};
int WPL(BTree *root)//根据WPL的定义采用递归算法实现
{
    return WPL1(root,0);
}
int WPL1(BTree *root,int d)//d为结点的深度
{
    if(root->left==NULL&&root->right==NULL)//递归结束调剂
        return root->weight*d;
    else
        return WPL1(root->left,d+1)+WPL1(root->right,d+1);//递归转移方程
}

6. 二路插入排序是将待排关键字序列r[1…n]中关键字分二路分别按序列插入到辅助向量d[1..n]前半部和后半部，其原则为，先将r[1]赋为d[1]，再从r[2]记录开始分二路插入。编写实现二路插入排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
二路插入排序是对直接插入的改进，特别注意在前半部插入时元素的移动。
1.判断待插入的元素是否大于 d[1];是:插入到 d[1]后面，否:插入到 d[1]前面
*/
#include <iostream>
using namespace std;
const int Maxn=1e3+2;
int r[Maxn],d[Maxn];
int n;
void fun()
{
	d[1]=r[1];//初始化
    int first=1,final=1;//first 指前半部”最前面”的下标;final 指后半部”最后面”的下标
    for(int i=2;i<=n;i++)//初始化 d[1]=r[1];first=1,final=1
        if(r[i]>d[1])//插入后部
        {
            low=1;
            high=final;
            while(low<=high)//折半查找插入位置
            {
                m=(low+high)/2;
                if(r[i]<d[m])
                	high=m-1;
                else
                	low=m+1;
            }//最后跳出循环时 low>high high+1 是插入的位置
    		for(j=final;j>=high+1;j--)//移动元素
                d[j+1]=d[j];
    		d[high+1]=r[i];//插入有序位置
    	final++;//后半部的下标+1
    }
    else//插入前部
    {
        if(first==1)
        {
            first=n;
            d[n]=r[i];
        }
        else
        {
            low=frst;
            high=n;
            while(low<=high)
            {
                m=(low+high)/2;
                if(r[i]<d[m])
                    high=m-1;
                else
                    low=m+1;
            }
            for(int j=first;j<=high;j++)
            d[j-1]=d[j];
            d[high]=r[i];first--;
        }
    }
    r[1]=d[first];//存储最小值
    for(i=first%n+1,j=2;i!=first;i=i%n+1,j++)//通过循环赋值使得 r 中数据从小到大排序
        r[j]=d[i];
}
int main()
{
	cin>>n;
    for(int i=1;i<=n;i++)
        cin>>r[i];
    fun();
    for(int i=1;i<=n;i++)
    	cout<<r[i]<<" ";
    return 0;
}

7. 钱币找零问题

指定币值和相应数量，用最少的数量凑齐某金额

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <stdio.h>

using namespace std;
const int maxn=1e4+5;
int dp[100][maxn]; // dp[i][j] 表示用前 i 种钱币 凑 j 元的最少数量
int coin[maxn],num[maxn];

int main(){
    int m,n;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>coin[i]; // 钱币面值
    for(int i=1;i<=m;i++) cin>>num[i];  // 钱币数量
    for(int i=0;i<100;i++){ // 初始化
        for(int j=1;j<maxn;j++)
            dp[i][j]=1e9; // 求最小初始化为最大
        dp[i][0]=0;
    }
    for(int i=1;i<=m;i++){ // 枚举钱币
        for(int j=1;j<=num[i];j++){ // 枚举钱币数量
            for(int k=1;k<=n;k++){ // 枚举需凑 金额
                if(k>=coin[i]*j) //当前方案可以凑成 金额k
                    dp[i][k]=min(dp[i][k],dp[i-1][k-coin[i]*j]+j);
                else //当前方案超过金额k，不可凑
                    dp[i][k]=min(dp[i][k], dp[i-1][k]);
            }
        }
    }
    int ans=1e9; // 对前 i 种钱币凑 n 元取最小值
    for(int i=1;i<=m;i++) ans=min(ans,dp[i][n]);
    cout<<ans<<endl;
    return 0;
}