算法ppt练习题（给黄成个大逼兜）

1、a.为假币问题的三分算法写一段伪码，请确保该算法能正确处理所 a.为 币
有的n值，而不仅仅是那些3的倍数。
b.为假币问题的三分算法的称重次数建立一个递推关系，并在 n=3*k情况下对它求解
C当n值非常大的时候，该算法比二分算法快多少倍(该答案应该 与n无关)
思路：当硬币的个数只有一个时，需要0次。当硬币个数为2时，需要1次。当硬币个数大于等于3时，我们按下面方法将硬币分为3堆：
n%3=0,分为n/3、n/3、n/3三堆。由于要求最坏情况，我们先用天平对n/3和n/3检测，失败后再对n/3个硬币做三分法。
n%3=1,分为(n/3)+1、n/3、n/3三堆。我们先用天平对n/3和n/3检测，失败后再对(n/3)_1个硬币做三分法。
n%3=2,分为(n/3)+1、(n/3)+1、n/3三堆。我们先用天平对(n/3)+1和(n/3)+1检测，由于要求最坏情况，再对(n/3)+1个硬币做三分法。
当n变为1的时候结束。

#include 
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        int count = 0;
        if (n == 0)
            break;
        while (n > 1)
        {
            ++count;
            //余数为1或2对(n/3)+1继续进行三分
            n = n/3 + (n%3 > 0);
        }
        cout << count << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、拿子游戏请考虑下面这个游戏
在桌子上有一堆火柴，其n根。两个玩家轮流移走1或2或3或4根。 准移走最后一根火柴(拿完)就赢了。请你为先走的玩家设计一个 致胜的策略，如果该策略存在的话。
提示:对于n=1.2.10找到一个致胜策略(若存在的话)，是对 连问题求通解的好方法。

1.问题分析
n根火柴，两位玩家每次只能取1，2，3，4根火柴；取走最后一根火柴为赢家；若电脑为先手，n为5的倍数时，只要与电脑游戏的玩家了解规律则一定会胜过电脑。
2.算法分析：
电脑前期每走的一步尽量让剩下的火柴为5的倍数，最后剩下小于5的火柴一并取走

#include
using namespace std;
int n;//火柴个数
void print()//打印火柴个数
{
	cout << "剩余火柴个数：" << endl << n << endl;
}
void computer()
{
	if (n < 5)
	{
		cout << "抱歉，火柴我全取走了，我赢了，hhhhh" << endl;
		n = 0;
	}
	else if (n % 5 == 0)
	{
		cout << "awsl，如果你是懂游戏的玩家我认输，哼" << endl;
		n--;
		print();
	}
	else if (n % 5 != 0)
	{
		for (int i = 1; i <= 4; i++)
		{
			n--;
			if (n % 5 == 0)
			{
				break;
			}
		}
		print();
		cout << "hhhh,你要输了，不信的话就接着来玩呀" << endl;
	}
}
int main()
{
	int m;
	cout << "咱们来玩个取火柴的游戏吧" << endl << "游戏规则：" << endl << "总共有n根火柴，每次只能分别取其中的1，2，3，4根，取到最后一根的玩家赢哦" << endl;
	cout << "下面咱们来玩一局，这样，你先规定火柴数，本电脑先取火柴，玩家您后取火柴" << endl;
	cout << "请输入火柴数：" << endl;
	cin >> n;
	cout << "本电脑操作中" << endl;
	computer();
	while (n > 0)
	{
		cout << "接下来轮到你了（请输入要取走的火柴数）：" << endl;
		cin >> m;
		n = n - m;
		print();
		if (n == 0)
		{
			cout << "恭喜玩家你赢了，哼，这次是让你的" << endl;
		}
		else
		{
			cout << "本电脑操作中" << endl;
			computer();
		}
	}
}

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

3、对序列E,X,A,M,P,L,E按字母顺序排序、要求应用:
(1)选择排序 (2)冒泡排序

// (2)选择排序
    let arr = ["E", "X", "A", "M", "P", "L", "E"]
        console.log('初始数据是：'+arr)
        function quickSort(arr) {
            for (let i = 0; i < arr.length; i++) {
                for (let j = i + 1; j < arr.length; j++) {
                    if (arr[j] < arr[i]) {
                        let t = arr[j];
                        arr[j] = arr[i];
                        arr[i] = t;
                    }
                }
                arr[i] = arr[i];
                console.log(arr[i])
            }
            return arr;
        }
        console.log('最终结果是：'+quickSort(arr))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

        //(1)冒泡排序
        var arr = ["E", "X", "A", "M", "P", "L", "E"]
        console.log("原始数据" + arr)
        var tem;
        (function () {
            for (var i = 0; i < arr.length - 1; i++) {//确定轮数
                for (var j = 0; j < arr.length - i - 1; j++) {//确定每次比较的次数
                    if (arr[j] > arr[j + 1]) {
                        tem = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tem;
                    }
                }
            }
        })();
        function b(){
            console.log("最终排序：" + arr)
        }
        b()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

对数字同上

/**
 * 选择排序
* @param array
* @return
*/
public static int[] selectionSort(int[] array) {
    if (array.length == 0)
        return array;
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i; j < array.length; j++) {
            if (array[j] < array[minIndex]) //找到最小的字母
                minIndex = j; //将最小字母的索引保存
        }
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
    return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public void bubbleSort(int[] array){
    int len = array.length;
    int temp;
    //外层循环是排序的趟数
    for(int i=0;i<len-1;i++){
        //内层循环是当前趟数需要⽐较的次数
        for(int j=0;j<len-i-1;j++){
            //前⼀位与后⼀位与前⼀位⽐较，如果前⼀位⽐后⼀位要⼤，那么交换
            if(array[j]>array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4、为蛮力字符串匹配写一段伪码，对于给定的模式，它能返回给定文本 中所有匹配子串的数量和位置。

5、用蛮力字符串匹配算法在1000个0组成的二进制文本中查找下列模式 需要做多少次比较(包括成功的和不成功的)?
(1) 00001
(2) 10000
（3）01010


// 具体算法
(1)00001 [共匹配4984]
1000个0 减去4个0 (末尾的0的个数小于子字符串的长度跳出循环)
再 乘 5 (子字符串的长度)
再加 4(由于末尾字符串的长度不满足余子字符串的长度，
子字符串最后只匹配的4次就跳出来循环)
=> (1000-4)*5 +4 = 4984

(2)10000 [1000次]
1000为父字符串的长度（按理来说应该只匹配了1000-4=996次 减4是因为父字符串的最后4个的字符串长度小于子字符串的长度，不满足与比较）

// 用蛮力字符串匹配算法在1000个0组成的二进制文本中查找下列模式需要做多少次比较(包括成功的和不成功的）?
// (1)00001 [4984]
// 具体算法
// 1000个0 减去4个0 (末尾的0的个数小于子字符串的长度跳出循环)
// 再 乘 5 (子字符串的长度)
// 再加 4(由于末尾字符串的长度不满足余子字符串的长度，子字符串最后只匹配的4次就跳出来循环)
// => (1000-4)*5 +4 = 4984
// (2)10000 [1000次]
// 每一个子字符串匹配一次
let sum = 0;
(function () {
    let s = "00000000.....";//(共1000个)
    let t = "1000"; //t ="00001"
    let i = 0, j = 0
    console.log(s.length)
    while (i < s.length) {
        if (s[i] === t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
        sum++;
    }
})()
console.log("子字符串的数量是： " + sum)
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

6、两个点P1(X1:y1)和P2(x2，Y2)之间的距离有多种不同的定义方式 有一种曼哈顿距离的定义: dm(P1,P2)=|x1-x2|+ly1-y2l (1)在xy坐标平面上绘出所有与原点(0,0)的曼哈顿距离等于1的点。 再对欧儿里得的距离de也做一遍。 (2)对错题:最近对问题的解不依赖于用何种距离。-de或dm
在x-y坐标平面上绘出所有与原点(0,0)的曼哈顿距离等于1的点。再对欧几里得的距离dE也做一遍。

曼哈顿距离的定义：
dM(P1,P2)=︱x1-x2︱+︱y1-y2︱

答：曼哈顿距离绘图如下

欧氏距离（欧几里得）的定义：
dE = √((x1-x2)2 +(y1-y2)2 )

答：欧式距离绘图如下

题解2
对错题:最近对问题的解不依赖于用何种距离——dE或dM
答：曼哈顿距离（这里我不太明白老师的意思，这题是我靠下图的主观判断的出来的结论）

7、对于 一个包含n个不同点的集合，它的凸包中极点的最大数量和最小 数量分别会是多少?

8、用伪码写一个解凸包问题的蛮力算法

package com.liuzhen.chapterThree;

public class ConvexHull {
    //蛮力法解决凸包问题，返回点集合中凸多边形的点集合
    public static Point[] getConvexPoint(Point[] A){
        Point[] result = new Point[A.length];
        int len = 0;  //用于计算最终返回结果中是凸包中点的个数
        for(int i = 0;i < A.length;i++){
            for(int j = 0;j < A.length;j++){
                if(j == i)     //除去选中作为确定直线的第一个点
                    continue;
                
                int[] judge = new int[A.length];   //存放点到直线距离所使用判断公式的结果
                
                for(int k = 0;k < A.length;k++){
                    int a = A[j].getY() - A[i].getY();
                    int b = A[i].getX() - A[j].getX();
                    int c = (A[i].getX())*(A[j].getY()) - (A[i].getY())*(A[j].getX());

                    judge[k] = a*(A[k].getX()) + b*(A[k].getY()) - c;  //根据公式计算具体判断结果
                }
                
                if(JudgeArray(judge)){  // 如果点均在直线的一边,则相应的A[i]是凸包中的点
                    result[len++] = A[i];
                    break;
                }    
            }
        }
        Point[] result1 = new Point[len];
        for(int m = 0;m < len;m++)
            result1[m] = result[m];
        return result1;
    }
    
    //判断数组中元素是否全部大于等于0或者小于等于0，如果是则返回true，否则返回false
    public static boolean JudgeArray(int[] Array){
        boolean judge = false;
        int len1 = 0, len2 = 0;
        
        for(int i = 0;i < Array.length;i++){
            if(Array[i] >= 0)
                len1++;
        }
        for(int j = 0;j < Array.length;j++){
            if(Array[j] <= 0)
                len2++;
        }
        
        if(len1 == Array.length || len2 == Array.length)
            judge = true;
        return judge;
    }
    
    public static void main(String[] args){
        Point[] A = new Point[8];
        A[0] = new Point(1,0);
        A[1] = new Point(0,1);
        A[2] = new Point(0,-1);
        A[3] = new Point(-1,0);
        A[4] = new Point(2,0);
        A[5] = new Point(0,2);
        A[6] = new Point(0,-2);
        A[7] = new Point(-2,0);
        
        Point[] result = getConvexPoint(A);
        System.out.println("集合A中满足凸包的点集为：");
        for(int i = 0;i < result.length;i++)
            System.out.println("("+result[i].getX()+","+result[i].getY()+")");
    }
}

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
70
71

package com.liuzhen.chapterThree;

public class Point {
    private int x;
    private int y;
    
    Point(){
        x = 0;
        y = 0;
    }
    
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
    
    public void setX(int x){
        this.x = x;
    }
    
    public int getX(){
        return x;
    }
    
    public void setY(int y){
        this.y = y;
    }
    
    public int getY(){
        return y;
    }
}

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

9、概要描述 一个蛮力算法，判断一个邻接矩阵表示的连通图是否具有 欧拉回路。该算法的效率类型如何?欧拉回路:包含图的每一条边, 且每条边仅出现一次的回路，就是欧拉回路。即:要求边不能重复, 结点可以重复
用深度优先搜索判断

typedef struct
{
	char vex[Max];
	int arc[Max][Max];
	int vexnum,arcnum;
}MGraph;
bool visited[Max];
bool Judge(MGraph G)
{
	for(int v=0,v<G.vexnum,v++)
	{
		visited[v]=false;
	}
	DFS(G,0);
	for(int v=0;v<G.vexnum;v++)
		if(!visited[v])
			return false;
	return true;
}
void DFS(MGraph G,int v)
{
	visited[v]=true;
	for(w=FistNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
	{
		if(!visited[w])
			DFS(G,w);
	}
}
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

时间复杂的为O(1）

        // m为节点的数量
        // n为边的数量
        let m = 6
        let n = 6
        if (n < m) {
            console.log('不具有欧拉回路')
        } else if (m % 2 === 0) {
            if (n % 2 === 0) {
                console.log('具有欧拉回路')
            } else {
                console.log('不具有欧拉回路')
            }
        } else {
            if (n % 2 === 0) {
                console.log('不具有欧拉回路')
            } else {
                console.log('具有欧拉回路')
            }
        }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

10、考虑完备子图问题:给定一个图G和正整数k，确定该图是否包含
个大小为k的完备子图即具有k个顶点的完全子图。请为该问题 设计一个穷举查找算法

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=111; //设置矩阵的大小
int graph[N][N]; //用邻接矩阵存储图
bool x[N]; //是否将i个顶点加入团中
bool bestx[N]; //记录最优已经放入团中的顶点
int bestn; //记录最优值
int cn; //已经放入团中的结点数
int n;//顶点个数
int m; //边的个数
 
bool place(int t) //判断是否能放进团中
{
    bool OK =true;
    for (int j=1;j<t;j++)  //判断目前扩展的t顶点和前面t-1个顶点是否相连。
    {
        if(x[j] && graph[t][j]==0) //如果不相连
        {
            OK=false; //返回false
            break;
        }
    }
    return OK; //如果相连。返回true
}
 
void backtrack(int t) //回溯，递推
{
    if(t>n) //当到达叶子结点
    {
        for(int i=1;i<=n;i++)
        {
            bestx[i]=x[i]; //记录最优值结点号
        }
        bestn=cn; //记录最优值
        return;
    }
    if(place(t)) //如果能放进团中
    {
        x[t]=1;//标为1
        cn++; //个数+1
        backtrack(t+1); //向下递推
        cn--; //向上回溯
    }
    if(cn+n-t>bestn) //限界条件，进入右子树，不能加入团中。
    {
        x[t]=0; //不能放入团中，标为0
        backtrack(t+1); //向下递推。
    }
}
 
int main()
{
    int u; //结点1
    int v; //结点2
    cout << "请输入结点的个数n；"<< endl;
    cin >> n;
    cout << "请输入边数m："<< endl;
    cin >>m;
    memset(graph,0,sizeof(graph));
    cout <<"请输入有边相连的两个顶点u和v："<< endl;
    for (int i=1;i<=m;i++)
    {
        cin >> u>> v;
        graph[u][v]=1;
        graph[v][u]=1;
    }
    bestn=0;
    cn=0;
    backtrack(1);
    cout << "最大团的结点个数有："<< bestn << endl;
    cout << "结点有："<< endl;
    for (int i=1;i<=n;i++)
    {
        if(bestx[i])
        {
            cout << i << "  "; //输出的是结点号
        }
    }
    return 0;
}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

11、考虑划分问题:给定n个实数，把它们划分为元素和尽量接近、但 不相交的两个子集。为该问题设计一个穷举查找算法，应尽量减少 生成子集的数量。

let array = [2, 3, 0, 4, 2, 9]
        function getSum(total, num) {
            return total + num;
        }
        function arrayChunk() {
            let cont = 0
            let max = array.reduce(getSum)
            let min = array.reduce(getSum)
            let data = []
            let arr1 = []
            let arr2 = []
            for (let i = 1; i < array.length; i++) {
                data = array.slice(i, array.length)
                cont = data.reduce(getSum)
                let sum = max - cont
                if (Math.abs(cont - sum)<min){
                    min = Math.abs(cont - sum)
                    arr1 = data
                    arr2 = array.slice(1, i)
                }
                // min = Math.min(min,Math.abs(cont - sum))
            }
            console.log('其中分割出来的子集为：'+arr2+'和'+arr1)
            console.log('相差的最小值为：'+min)
        }

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