【算法】稳定匹配(C++版)

2024-09-03 06:08
文章标签 算法 c++ 匹配 稳定

本文主要是介绍【算法】稳定匹配(C++版),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

由于学习需要,然后花费将近两天时间研究这个问题,然后用C++描述出来,具体内容看下面:

问题描述(见百度百科):
https://baike.baidu.com/item/%E7%A8%B3%E5%AE%9A%E5%A9%9A%E5%A7%BB%E9%97%AE%E9%A2%98/12760040

为了解决稳定匹配问题(Stable Matching Problem),前辈们提出了GS算法。

下面就是博主使用GS算法完成的本题,同时在研究过程中发现了一个新的匹配思路,将会在下面发出来(不知道前辈们有没有提出过),大家可以积极提出宝贵意见:

问题分析:

1.首先输入男士(女士)人数,这里男士,女士人数相同并且要求最后每个人都有对象。

2.初始化所有男士,女士追求过对象人数better=0,对异性喜欢排名数组rank[],当前是否在约会状态Yuehui,以及现任为-1;

3.既然男的需要主动,那就让所有单身状态的男士向自己最喜欢的女士表白,不管结局成功与否,该男士追求过的人数都加1;

4.如果女士单身,那么两个人就暂时在一起先处着,更改两个人是否约状态为true,设置对方为自己的现任;

5.如果女士不是单身,此时就出现了小三,那么主动权就交给女士了,此时女士比较现任小三,如果更喜欢现任。跳过当前追求者;如果更喜欢小三,抛弃现任,此时小三终于扬眉吐气成功上位,并与当前追求者结合成暂时情侣去约会。

6.判断是否全部找到对象,都找到了结束查找,否则重复步骤:2-5,直到全部由对象;

7.结束,输出;

程序设计
这里使用历史人物,(得到的最终匹配结果可能不与现实相同),男女各5名,对其进行编号。由编号代替其姓名。
这里写图片描述

各男士喜欢排名表:
(仅供实验参考,最终数据为自行输入)
这里写图片描述
各女士喜欢排名表:
(仅供实验参考,最终数据为自行输入)
这里写图片描述

定义人类(是人 ):

//人类
class People
{private:int better;             //追求过几位女生int rank[NUM];          //喜欢排名bool Yuehui;            //是否在约会int present;            //现任public:People(){better = 0;Yuehui = false;present = -1;}void setRank(int mRank, int i);int getRank(int i) { return rank[i]; };void setYuehui(bool mYuehui);bool getYuehui() { return Yuehui; };void setBetter(int mBetter);int getBetter() { return better; };void setPresent(int mPressent);int getPressent() { return present; };
};

完整代码:

#include<iostream>
#include<cstring>
using namespace std;const int NUM = 5;
int flag = 0;//人类
class People
{private:int better;             //追求过几位女生int rank[NUM];          //喜欢排名bool Yuehui;            //是否在约会int present;            //现任public:People(){better = 0;Yuehui = false;present = -1;}void setRank(int mRank, int i);int getRank(int i) { return rank[i]; };void setYuehui(bool mYuehui);bool getYuehui() { return Yuehui; };void setBetter(int mBetter);int getBetter() { return better; };void setPresent(int mPressent);int getPressent() { return present; };
};
void People::setRank(int mRank, int i)
{rank[i] = mRank;
}
void People::setYuehui(bool mYuehui)
{Yuehui = mYuehui;
}
void People::setBetter(int mBetter) 
{better = mBetter;
}
void People::setPresent(int mPressent)
{present = mPressent;
}int main()
{People man[NUM];People lady[NUM];for (int i = 0; i < NUM; i++){for (int j = 0; j < NUM; j++){int temp;cout << "请输入第" << i+1 << "个人喜欢的第" << j+1 << "个人:";cin >> temp;man[i].setRank(temp, j);}}cout << "男士初始化完毕" << endl;for (int i = 0; i < NUM; i++){for (int j = 0; j < NUM; j++){int temp;cout << "请输入第" << i + 1 << "个人喜欢的第" << j + 1 << "个人:";cin >> temp;lady[i].setRank(temp, j);}}cout << "女士初始化完毕" << endl;while (true){flag = 1;                                       //设定全部脱单标记//所有男士向自己最喜欢的女士表白for (int i = 0; i < NUM; i++){if (man[i].getYuehui() == false)            //男士单身{flag = 0;                               //还有单身狗标记int num_Y = man[i].getBetter();                 //男士应向第几位喜欢的表白int girl = man[i].getRank(num_Y);               //获取喜欢女士的位置man[i].setBetter(num_Y + 1);                    //无论表白失败与否,下次表白对象位置if (lady[girl].getYuehui() == false)    //喜欢的女士单身{man[i].setYuehui(true);                 //男士改为约会状态man[i].setPresent(girl);                //设置现任为该女士lady[girl].setYuehui(true);             //喜欢的女士也更改为约会状态lady[girl].setPresent(i);               //设置现任为该男士
//                  cout << girl<<" ";                      //输出最喜欢的女士}if (lady[girl].getYuehui() == true) //喜欢的女士不单身{//女士通过比较与自己最喜欢的那位男士在一起int before, now;//通过循环判断现任和小三在女士心中的位置for (int j = 0; j < NUM; j++){if (lady[girl].getRank(j) == i){now = j;}if (lady[girl].getRank(j) == lady[girl].getPressent()){before = j;}}//如果女士喜欢现任if (before < now){//小三滚蛋吧~~//man[i].setBetter(man[i].getBetter() + 1);}//女士喜欢else if (before>now){man[lady[girl].getPressent()].setYuehui(false); //现任变前任man[lady[girl].getPressent()].setPresent(100);  //变单身狗man[i].setYuehui(true);                         //小三上位man[i].setPresent(girl);lady[girl].setPresent(i);}}}}if (flag == 1){break;}   }//输出for (int i = 0; i < NUM; i++){cout << i << "和" << man[i].getPressent() << "在一起" << endl;}
}

最后,看下结果吧~~
这里写图片描述

最最后,画了张图并结合上面三张表述我的新思路:
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述

最最最后,感谢你的访问,有问题欢迎提出。

Tony-Chen
2017.10.25

心的强大因为鉴定!

这篇关于【算法】稳定匹配(C++版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1132237

相关文章

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》:本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数:不用传参就可以

C++类和对象之默认成员函数的使用解读

《C++类和对象之默认成员函数的使用解读》:本文主要介绍C++类和对象之默认成员函数的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、默认成员函数有哪些二、各默认成员函数详解默认构造函数析构函数拷贝构造函数拷贝赋值运算符三、默认成员函数的注意事项总结一

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

C/C++的OpenCV 进行图像梯度提取的几种实现

《C/C++的OpenCV进行图像梯度提取的几种实现》本文主要介绍了C/C++的OpenCV进行图像梯度提取的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录预www.chinasem.cn备知识1. 图像加载与预处理2. Sobel 算子计算 X 和 Y

C/C++和OpenCV实现调用摄像头

《C/C++和OpenCV实现调用摄像头》本文主要介绍了C/C++和OpenCV实现调用摄像头,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录准备工作1. 打开摄像头2. 读取视频帧3. 显示视频帧4. 释放资源5. 获取和设置摄像头属性

c/c++的opencv图像金字塔缩放实现

《c/c++的opencv图像金字塔缩放实现》本文主要介绍了c/c++的opencv图像金字塔缩放实现,通过对原始图像进行连续的下采样或上采样操作,生成一系列不同分辨率的图像,具有一定的参考价值,感兴... 目录图像金字塔简介图像下采样 (cv::pyrDown)图像上采样 (cv::pyrUp)C++ O

c/c++的opencv实现图片膨胀

《c/c++的opencv实现图片膨胀》图像膨胀是形态学操作,通过结构元素扩张亮区填充孔洞、连接断开部分、加粗物体,OpenCV的cv::dilate函数实现该操作,本文就来介绍一下opencv图片... 目录什么是图像膨胀?结构元素 (KerChina编程nel)OpenCV 中的 cv::dilate() 函