您现在的位置是:首页 > 正文

【螺钉和螺母问题】【算法分析与设计】假设我们有n个直径各不相同的螺钉以及n个相应的螺母...

2024-01-30 23:09:17阅读 0

教材原题

假设我们有n个直径各不相同的螺钉以及n个相应的螺母。我们一次只能比较一对螺钉螺母,来判断螺母是大于螺钉、小与螺钉还是正好适合螺钉。然而我们不能拿两个螺母做比较,也不能拿两个螺钉做比较

我们的问题是要找到每一对匹配的螺钉和螺母。为该问题设计一个算法,它的平均效率必须属于Θ(n log n)。

题意分析

可能看完题目,不知道它到底要我们干什么,又没有规定输入,也没有要求输出。这跟我们做oj的题很不一样,oj的题目只要在规定时间和空间内给出正确答案就行了。而这种算法分析设计题,输入、输出、算法和代码都要我们设计。

有的同学可能直接对 螺钉 和 螺母 两个数组分别进行快排,然后输出结果。很显然,分别快排,就违背了上面 标粗 的题意要求。

在正式设计算法和写代码之前,我们简单想想输入、输出。输入肯定就是螺母和螺钉两个数组,输出我们可以简单一点,直接输出两个排序后的数组,但是中间的算法是符合我们题意要求的。

还有一个问题!划分时,元素下标不断变化,而一开始我们也没有对各个螺钉和螺母进行编号。我们这样输入和输出,怎么体现 上面标粗的 “找到” 呢? 输出是两个有序数组,一一对应就可以体现我们 “找到” “匹配到”了。就好比现实中,我们可以不需要通过编号标识,而直接通过手动移动位置,让匹配螺钉和螺母放到一块。

说这么多,是因为:在真正写代码之前,进行一定的逻辑分析是有必要的。

算法分析

 假设我们一开始随便选一枚螺钉A,假设就取区间最左侧那一枚(一开始区间是[0, n-1])。然后在螺母的对应区间([0, n-1])首先找到与螺钉A对应的螺母a。然后把螺母a与区间最左侧的螺母调换位置。然后根据螺钉A,在区间内,对螺母a进行划分。注意,这里是根据 螺钉A , 而不是根据调换了位置的螺母a!!!不然就违背题意了。螺母一次划分后。同理以 螺母a 来划分 螺钉,注意此时的区间还是 [0, n-1]。

上面是一次划分的算法。我们需要多次划分,每次划分都要缩小区间。详见代码。

快排的模板代码

先贴一下快排的模板代码,这个实现比教材的要更简单一点,虽然算法思路是一样的。

void quicksort(int x[],int left,int right)  //快速排序 
{
    if(left<right)
    {
        int i=left,j=right,key=x[left];
        while(i<j)
        {
            while(i<j&&x[j]>=key)
                j--;
            if(i<j)
                x[i++]=x[j];

            while(i<j&&x[i]<=key)
                i++;
            if(i<j)
                x[j--]=x[i];
        }
        x[i]=key;
        
        quicksort(x,left,i-1);
        quicksort(x,i+1,right);
    }
}

解题代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 9;

void print(int ld[], int lm[]) {
	printf("ld:");
	for (int i = 0; i < N; i++) {
		printf("%d ", ld[i]);
	}
	printf("\n");
	printf("lm:");
	for (int i = 0; i < N; i++) {
		printf("%d ", lm[i]);
	}
	printf("\n");
}

// 进行一次划分 
// [l, r] { 5, 2, 4, 3, 1 }
int partition(int x[], int l, int r, int key) {
	
	// 假设key是螺钉,则首先在螺母中找到与之匹配的螺母
	// 然后与最左侧的螺母交换,使之称为中轴,方便之后作partition 
	for(int i=l; i<=r; i++)
		if(x[i]==key)
		{
			swap(x[i], x[l]);
			break;
		}
	
	// 以key划分螺母 
	int i=l,j=r;
	int t=x[l]; // 暂存中轴 
    while(i<j)
    {
        while(i<j&&x[j]>=key) // 注意,这里要与key做比较,不要用t来比较 
            j--;
        if(i<j)
            x[i++]=x[j];

        while(i<j&&x[i]<=key)
            i++;
        if(i<j)
            x[j--]=x[i];
    }
    x[i]=t;
    
//    printf("i=%d\n", i);
//    for(int i = l; i <= r; i++ ) {
//    	printf("%d ", x[i]);
//	}
	return i;
} 

// [l, r]
void match(int ld[], int lm[], int l, int r) {
	
	if (l < r) {
		// 随便选一个 ld,此处以区间的最左侧(第1个)那个 ld 为例子 
		int ldKey = ld[l];
		// 返回划分之后 lm 的位置 
		// 此时与选的ld对应的lm,(划分之后)在下标为 pos 的位置
		int pos1 = partition(lm, l, r, ldKey);
		
		// 选这个 lm,来划分 ld 
		int lmKey = lm[pos1]; 
        int pos2 = partition(ld, l, r, lmKey); 
        
        // 在这里pos1与pos2相等的 
        print(ld, lm);
        printf("pos1=%d pos2=%d\n", pos1, pos2);
       
		match(ld, lm, l, pos1-1); 
		match(ld, lm, pos1+1, r); 
	}
}


int main() {
    // 为了方便模拟,螺钉和螺母都以数字1-9编号
    // 而且,约定编号越大,直径越大
	int ld[N] = { 5, 9, 3, 7, 1, 8, 2, 4, 6 };
	int lm[N] = { 7, 1, 4, 2, 5, 6, 9, 8, 3 };
		
	match(ld, lm, 0, N-1);
	
	return 0;
}

“注意,这里要与key做比较,不要用t来比较 ”

可能有人不太理解注释这句话。因为螺钉和螺母都是用相同的数字来表示,可能感觉不到差别。

假如你以 小写字母 来 表示螺钉,以大写字母 来 表示螺母。那么上面代码中比较的地方就需要改动,那样可能会更能理解上面这句注释和原题的题意要求!

网站文章

  • Mysql-慢日志详解

    Mysql-慢日志详解

    Mysql-慢日志详解 mysql慢日志是什么? 慢查询日志由 long_query_time 执行时间超过几秒钟并且至少 min_examined_row_limit 需要检查行的 SQL 语句组成...

    2024-01-30 23:08:46
  • 攻防世界-MISC新手练习题集(三)

    攻防世界-MISC新手练习题集(三)

    攻防世界-MISC新手练习题集 Erik-Baleog-and-Olaf can_has_stdio? Training-Stegano-1 simple_transfer 2017_Dating_in_Singapore pure_color

    2024-01-30 23:08:38
  • python爬虫学习入门1 urllib 库

    python爬虫 学习学习爬虫因为爬取的一般都是网站,在后期可能会出现需要登陆网站等等的信息, 因此在学爬虫前需要大致的了解一下html 网站的架构,以及前端向后端传递参数时候的大致要求.http ...

    2024-01-30 23:08:31
  • Minikube vs. kind vs. k3s vs k3d vs MicroK8s

    Minikube vs. kind vs. k3s vs k3d vs MicroK8s

    另一个不同之处是,k3s 的设计易于在生产环境中部署,这使其成为在本地环境中为生产级工作负载运行 Kubernetes 的最受欢迎的选择之一,而 k3d 更适合在更小的环境中使用,例如 Raspber...

    2024-01-30 23:08:23
  • 福大计算机专业排名,2019福州大学专业排名

    福州大学是国家“211工程”重点建设高校。在福州大学众多的优秀专业中,称得上最好的专业有7个专业,这些专业是国家级重点学科,也可以说是福州大学的人才聚集地。为了让大家更好的了解这所大学的专业排名,下面...

    2024-01-30 23:07:53
  • Android之简洁天气

    Android之简洁天气

    为什么80%的码农都做不了架构师?>>> ...

    2024-01-30 23:07:46
  • [LeetCode258] Add Digits

    Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.For example:Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has on

    2024-01-30 23:07:38
  • 指令

    指令 指令的定义 指令又称为机器指令,是指计算机执行某种操作的命令,是计算机运行的最小功能单位,一台计算机的所有指令的集合构成的指令系统,又称为指令集 一台计算机只能够执行自己指令系统中的指令,不能够...

    2024-01-30 23:07:07
  • js基础篇:3、浅谈js的七种数据类型

    js的数据类型js有七种数据类型,其中又可以划分为基本数据类型(Number、String、Null、Boolean、undefined、Symbol(ES6新增))和引用数据类型(Object)。基本数据类型NumberStringNullBooleanundefin...

    2024-01-30 23:07:00
  • SSH实例(简单地增删改查功能) 热门推荐

    SSH实例(简单地增删改查功能) 热门推荐

    在网上看到一篇写的很不错的关于SSH 整合实现简单的增删改查功能的实例。 因为也是初次使用SSH框架,如有不足,请多指教。 先看一下我们完整的工程目录: 好了 我们废话不多说 直接上操作: 1.(1.)Dept 我们的Bean 包名:com.bdqn.entity(根据自己的习惯定义就可以) package com.bdqn.entity; import java.io...

    2024-01-30 23:06:53