离散实验 判断集合之间是单射,满射还是双射

离散实验 判断集合之间是单射,满射还是双射通过C++实现集合间映射关系判断思路:创建判断两个集合之间是否是单射,满射,双射的函数,同时也分别创建三个函数,里面存放两集合间的映射关系,再通过刚刚创建的判断函数,进行验证是否满足条件。涉及的数学知识1.单射:设f是由集合A到集合B的映射,如果所有x,y∈A,且x≠y,都有f(x)≠f(y),则称f为由A到B的单射。2.满射:如果每个可能的像至少有一个变量映射其上(即像集合B中的每个元素在A中都有一个或一个以上的原像),或者说值域任何元素都有至少有一个变量与之对应,那这个映射就叫做满射。3.双

大家好,又见面了,我是你们的朋友全栈君。

通过C++实现集合间映射关系判断

思路:
创建判断两个集合之间是否是单射,满射,双射的函数,同时也分别创建三个函数,里面存放两集合间的映射关系,再通过刚刚创建的判断函数,进行验证是否满足条件。

涉及的数学知识

1.单射:设f是由集合A到集合B的映射,如果所有x,y∈A,且x≠y,都有f(x)≠f(y),则称f为由A到B的单射。
2.满射:如果每个可能的像至少有一个变量映射其上(即像集合B中的每个元素在A中都有一个或一个以上的原像),或者说值域任何元素都有至少有一个变量与之对应,那这个映射就叫做满射。
3.双射:既是单射又是满射的映射称为双射,亦称“一一映射”。

插入相应集合

思路:大体一致以单射举例
vector<int> srcvector<int> dst作为参数传进我们创建的map<int, int> BuildInjection
我们创建一个新的map<int, int> injection;函数用来存放两个集合间的映射关系。
由单射定义可以知道,当我们的x中的元素大于y中的元素时一定不满足我们的单射,然后我们按照x中的元素个数进行遍历将y中的元素与之对应,这个我们使用到pair<int,int> p(src[i],dst[i]);pair是将2个数据组合成一组数据,当需要这样的需求时就可以使用pair,其中我们的map就是将key和value放在一起来保存。我们将pair里面的数据插入到map中来,进行保存,方便我们下一次在判断是否为单射的时候使用

/* BuildInjection 功能:构造集合src到集合dst的单射,将建立的映射保存在返回值injection中 例如,将src中的元素1映射为dst中的元素3,则injection[1] = 3 */
map<int, int> BuildInjection(vector<int> src, vector<int> dst)
{ 
   
	map<int, int> injection;
	if(src.size()>dst.size()){ 
   
		cout<<"不能创建单射"<<endl;
	}else{ 
   
		for(int i=0;i<src.size();i++){ 
   
			pair<int,int> p(src[i],dst[i]);
			injection.insert(p);
		}
	}
	return injection;
}

/* BuildSurjection 功能:构造集合src到集合dst的满射,将建立的映射保存在返回值surjection中 */


map<int, int> BuildSurjection(vector<int> src, vector<int> dst)
{ 
   
	map<int, int> surjection;
	if(src.size()<dst.size()){ 
   
		cout<<"不能创建满射"<<endl;
	}else{ 
   
		for(int i=0;i<src.size();i++){ 
   
			pair<int,int> p(src[i],dst[i%dst.size()]);
			surjection.insert(p);
		}
	}

	return surjection;
}

/* BuildBijection 功能:构造集合src到集合dst的双射,将建立的映射保存在返回值bijection中 */

map<int, int> BuildBijection(vector <int> src, vector<int> dst)
{ 
   
	map<int, int> bijection;
	if(src.size()!=dst.size()){ 
   
		cout<<"不能创建双射"<<endl;
	}else{ 
   
		for(int i=0;i<src.size();i++){ 
   
			bijection[src[i]]=dst[i];
		}
	}
	return bijection;
}

1.1 判断是否是单射

思路:
在判断一组映射关系是否是单射时,我们主要去判断x中的元素在y中都有与之对应的,而且一个x对应一个y,主要采用的还是一种标记的思想,在传入进来的y中进行遍历,让y中的元素全部标记为1,我们再在那段映射关系中进行遍历,如果说有不等于1的就证明在这段映射关系中,有不是y中的元素,所以我们可以让他返回一个false;同时要注意的是即使y存在在这段映射关系中,也不能直接就判断这个映射是单射,因为其中有两个x对应同一个y的情况,所以我们可以通过一个计数的思想将这段映射关系中符合y中标记为1的自加,如果我们自加的个数>1就说明其中存在两个x对应同一个y,我们也让其返回false,反之,返回true
:在我们去判断自加数是否>1的时候,我们应该在我们创建的那个flag中及逆行遍历
:由于我们是写了一个变量通过改变这个变量的值进行改变这个函数的返回值的,所以要在我们发现自加数>1存在就让其停止循环,加上break

/* ValidateInjection 功能:验证给定的两个集合src和dst之间的映射injection是否为单射。 如果是单射则返回true,不是单射返回false */
bool ValidateInjection(vector<int> src, vector<int> dst, map<int, int> injection)
{ 
   
	bool bIsInjection = false;
	map<int,int>mp,flag; 
	map<int,int>::iterator it=injection.begin();
	if(injection.size()<src.size()){ 
   
		return false;
	} else{ 
   
	
		for(int i=0;i<dst.size();i++){ 
   
			mp[dst[i]]=1; flag[dst[i]]=0;
		}
		for(;it!=injection.end();it++){ 
   
			if(	!mp[it->second]) bIsInjection = false;
			flag[it->second]++;
		}
	}
	for(it=flag.begin();it!=flag.end();it++){ 
   
		if(it->second>1) { 
   
			bIsInjection = false;
			break;
		}else { 
   
			bIsInjection = true;
		}
		
	}
	
	return bIsInjection ;
}

1.2判断是否是满射

思路:
在判断一个映射是否是满射时,我们主要去判断每一个x都有y与之对应,同时y中都有x与之对应,采用的还是标记和计数的思想,主要和上面单射的区别就是在于计数,这一块,如果我们自加数要是少于我们y中的元素个数,就证明在我们这个映射关系中有y存在剩余,这不满足满射定义。返回false,否则返回true。

/* ValidateSurjection 功能:验证给定的两个集合src和dst之间的映射surjection是否为满射。 如果是满射则返回true,不是满射返回false */
bool ValidateSurjection(vector<int> src, vector<int> dst, map<int, int> surjection)
{ 
   
	bool bIsSurjection=false;
	map<int,int>mp,flag; 
	map<int,int>::iterator it= surjection.begin();
		for(int i=0;i<dst.size();i++){ 
   
			mp[dst[i]]=1; flag[dst[i]]=0;
		}
		for(;it!=surjection.end();it++){ 
   
			if(	!mp[it->second])  bIsSurjection = false;
			flag[it->second]++;
		}
	for(it=flag.begin();it!=flag.end();it++){ 
   
		if(it->second<dst.size())  bIsSurjection = false;
			 bIsSurjection = true;
	}
	return bIsSurjection;
}

1.3判断是否是双射

思路:
双射:即使单射也是满射,二者同时满足,所以我们可以使用上面我们判断单射和满射的函数及逆行判断是否是双射。

/* ValidateBijection 功能:验证给定的两个集合src和dst之间的映射bijection是否为双射。 如果是双射则返回true,不是满射返回false */
bool ValidateBijection(vector<int> src, vector<int> dst, map<int, int> bijection)
{ 
   
	bool bBiSurjection = false;
	if(bijection.size()!=src.size()){ 
   
		return false;
	} else{ 
   
		bBiSurjection = (ValidateInjection(src, dst, bijection) && ValidateSurjection(src, dst, bijection));
	}
	return bBiSurjection;
}

主函数

int main()
{ 
   
	vector<int> setA, setB, setC;
	for (int i = 0; i < 10; i++)
		setA.push_back(i);
	for (int i = 50; i < 70; i++)
		setB.push_back(i);
	for (int i = 130; i < 140; i++)
		setC.push_back(i);

	map<int, int>::iterator iter;
	
	map<int, int> injection;
	injection = BuildInjection(setA, setB);
	for (iter = injection.begin(); iter != injection.end(); iter++)
		cout << iter->first << "->" << iter->second << endl;
	cout << ValidateInjection(setA, setB, injection) << endl;
	system("pause");

	map<int, int> surjection;
	surjection = BuildSurjection(setB, setA);
	for (iter = surjection.begin(); iter != surjection.end(); iter++)
		cout << iter->first << "->" << iter->second << endl;
	cout << ValidateSurjection(setB, setA, surjection) << endl;
	system("pause");

	map<int, int> bijection;
	bijection = BuildBijection(setA, setC);
	for (iter = bijection.begin(); iter != bijection.end(); iter++)
		cout << iter->first << "->" << iter->second << endl;
	cout << ValidateBijection(setA, setC, bijection) << endl;
	system("pause");

    return 0;
}

总结

1.此次实验总体上采用的是一种计数和标记的思想,能实现这个想法主要是map函数它有两个参数,一个是key,一个是value值,:key值不能有重复的,有重复的会自动将其删除一个,但是value值可以有重复的,这让标记可以实现。本次计数也是通过创建map函数进行计数的flag[it->second]++;
2.同时注意我们要判断函数的范围即我们要在哪个for循环中进行遍历
3.对pair的元素进行操作的时候,通过first和sencond访问it->second

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/132991.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • rpm 安装与卸载

    rpm 安装与卸载rpm (RedHatPackageManager) 红帽软件包工具。在redhat,fedora,novellsuselinuxenterprise,openSUSE,centos等系统上使用。 用途:安装与卸载软件包用法:rpm -选项 包名选项:-vih   安装v显示安装过程h显示安装进度      -q    后跟包名查询指…

  • san交换机保存配置_交换机是一种什么设备

    san交换机保存配置_交换机是一种什么设备场景:1、两台服务器ESXi1,ESXi22、两台SAN交换机FC1,FC23、4台SAN存储:store1and2,store3and4:其中1和2,3和4分别做了级联,12和34之间做了双活。网络拓扑如图FC交换机1–创建zonezonecreate”Stor1_A_H2_GSJ_ESXI1_P0″,”1,8;2,12″ :做端口绑定,将

    2022年10月24日
  • 用dedecms做网站时,空间服务器选择IIS还是apache???

    用dedecms做网站时,空间服务器选择IIS还是apache???

  • 简单的二分法排序

    简单的二分法排序提起排序,记忆最深刻的就是冒泡法排序,因为这是程序员入门必学的第一个排序算法。但是冒泡法需要不断地遍历数组,不断地遍历数组,需要消耗更多的时间。相对于冒泡法,二分法排序的效率相对的更高一些。publicclassBisection{publicstaticvoidmain(String[]args){Integer[]a={74,81,…

  • 镁光(Micron)存储器根据丝印找具体型号(datasheet)的方法[通俗易懂]

    镁光(Micron)存储器根据丝印找具体型号(datasheet)的方法[通俗易懂]镁光(Micron)存储器根据丝印找具体型号(datasheet)的方法

  • 数据库-select查询语句

    数据库-select查询语句表结构如下:学生表:Student学生表(学号,姓名,性别,年龄,组织部门)       Course 课程表(编号,课程名称)       Sc 选课表(学号,课程编号,成绩)(1).写一个SQL语句,查询选修了’计算机原理’的学生学号和姓名select 学号,姓名from Student where 学号=

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号