Basic Computer Science – Learning Function and implement the required methods specified in the lab specification.
这是 计算机科学基础 课程中的第二个实验，主要是借助计算机语言来验证Function, Injectice, Surjective。
本次实验主要考察函数相关的概念，主要包含三部分：Function, Injective, Surjective。即函数、单射、满射。
为了达到实验效果，在该实验中禁止使用STL容器。
Explain
由于Lab中给出的数据实在是太过于水，数据范围极小且不存在特殊样例，因此在此文中的程序没有对所有可能的情况进行判断，有可能在实际上无法对任意样例作出可靠的判断，具有一定的局限性。
Analysis
本次实验主要考察函数相关的概念，主要包含三部分：Function, Injective, Surjective。即函数、单射、满射。
Function
A relation that is defined for every possible element of the domain space and each is related to exactly one element in the range space.
Function 即为函数。是一种在定义域和值域之间存在的一对一或多对一的关系；如果存在一对多的关系，则说明这不是一个函数。
Injective
A function and no two elements of its domain are related to the same element in the range space.
Injective 即为单射(left-unique)。在函数的基础上要求定义域和值域之间是一对一的关系，不能出现多对一的关系。
Surjective
A function which is right-total, i.e. its range equals its range space.
Surjective 即为满射(right-total)。在函数的基础上要求定义域中的任何值都可以被取到。
Method
我们规定：
- 对于domainSpace, rangeSpace, domain, range输入均为一个形如:{a1,a2,a3,…,ai,…,an}的字符串，其中ai为整数；
- domain 以及 range 输入的内容为对应的domainSpace, rangeSpace 中元素的下标。
struct element
为了便于函数传递以及代码的可读性，我们使用一个结构体来存储domainSpace, rangeSpace, domain和range。
struct element
{
int a[100];
int len;
int log[100];
element()
{
memset(a,0,sizeof a);
memset(log,0,sizeof log);
len=0;
}
};
- a数组：表示输入的元素；
- len：表示当前结构体中的元素数量；
- log数组：下标与a数组一一对应，其存储的值为在domainSpace或者rangeSpace中元素的下标；
- 构造函数：初始化元素的值，log数组为0时表示没有对应的元素。
判断元素是否在domainSpace或rangeSpace内
我们需要遍历整个domainSpace和rangeSpace进行判断。
朴素算法的时间复杂度是O(n^2),我们也可以通过排序以及二分将时间复杂度优化到O(nlogn)，在此只给出朴素算法的实现：
Function
在代码中我们可以通过判断每一个Domain是否对应多个Range来实现对Function的判断。
int isFunction(element domainSpace,element rangeSpace,element domain,element range)
{
for(int i=1;i<domain.len;i++)
{
int u=domain.a[i];
int v=range.a[i];
if(u>=domainSpace.len||v>=rangeSpace.len||u<1||v<1)
{
return 0;
}//判断是否在domainSpace或rangeSpace内
if(domain.log[u]==0)
{
domain.log[u]=v;
}//判断是否为Function
else return 0;
}
return 1;
}
Injective
在代码中我们可以在Function成立的基础上，进一步判断每一个Range是否和多个Domain对应，当且仅当一个Range只和一个或者零个Domain对应时成立。
int isInjective(element domainSpace,element rangeSpace,element domain,element range)
{
for(int i=1;i<domain.len;i++)
{
int u=domain.a[i];
int v=range.a[i];
if(u>=domainSpace.len||v>=rangeSpace.len||u<1||v<1)
{
return 0;
}//判断是否在domainSpace或rangeSpace内
if(domain.log[u]==0)
{
domain.log[u]=v;
}
else return 0;//判断是否为Function
if(range.log[v]==0)
{
range.log[v]=u;
}else return 0;//判断是否为Injective
}
return 1;
}
Surjective
在代码中我们可以在Function成立的基础上，进一步判断rangeSpace中的每一个元素是否都存在一个一一对应的domain。
int isSurjective(element domainSpace,element rangeSpace,element domain,element range)
{
for(int i=1;i<domain.len;i++)
{
int u=domain.a[i];
int v=range.a[i];
if(u>=domainSpace.len||v>=rangeSpace.len||u<1||v<1)
{
return 0;
}//判断是否在domainSpace或rangeSpace内
if(domain.log[u]==0)
{
domain.log[u]=v;//判断是否为Function
rangeSpace.log[v]=u;
}
else return 0;
}
for(int i=1;i<rangeSpace.len;i++)
{
if(!rangeSpace.log[i])
{
return 0;
}
}//判断是否为Surjective
return 1;
}
Example
Task1
For a relation, write a method to determine if the relation is a function. The signature of the method is as follows:Int isFunction(int domainSpace[], int rangeSpace[], int domain[], int range[])
#include <bits/stdc++.h>
using namespace std;
struct element
{
int a[100];
int len;
int log[100];
element()
{
memset(a,0,sizeof a);
memset(log,0,sizeof log);
len=0;
}
};
void input(element &t)
{
int cnt=1;
char key=',';
getchar();
while(key!='}')
{
cin>>t.a[cnt++];
key=getchar();
}
t.len=cnt;
}
int isFunction(element domainSpace,element rangeSpace,element domain,element range)
{
for(int i=1;i<domain.len;i++)
{
int u=domain.a[i];
int v=range.a[i];
if(u>=domainSpace.len||v>=rangeSpace.len||u<1||v<1)
{
return 0;
}
if(domain.log[u]==0)
{
domain.log[u]=v;
}
else return 0;
}
return 1;
}
int main()
{
element domainSpace=element();
element rangeSpace=element();
element domain=element();
element range=element();
input(domainSpace);
getchar();
input(rangeSpace);
getchar();
input(domain);
getchar();
input(range);
if(isFunction(domainSpace,rangeSpace,domain,range))
{
cout<<"It is a function.";
}else cout<<"It is not a function.";
return 0;
}
Task2
Given a mathematical function write a method to determine if the function is injective. The signature of the method is as follows:Int isInjective(int domainSpace[], int rangeSpace[], int domain[], int range[])
#include <bits/stdc++.h>
using namespace std;
struct element
{
int a[100];
int len;
int log[100];
element()
{
memset(a,0,sizeof a);
memset(log,0,sizeof log);
len=0;
}
};
void input(element &t)
{
int cnt=1;
char key=',';
getchar();
while(key!='}')
{
cin>>t.a[cnt++];
key=getchar();
}
t.len=cnt;
}
int isInjective(element domainSpace,element rangeSpace,element domain,element range)
{
for(int i=1;i<domain.len;i++)
{
int u=domain.a[i];
int v=range.a[i];
if(u>=domainSpace.len||v>=rangeSpace.len||u<1||v<1)
{
return 0;
}
if(domain.log[u]==0)
{
domain.log[u]=v;
}
else return 0;
if(range.log[v]==0)
{
range.log[v]=u;
}else return 0;
}
return 1;
}
int main()
{
element domainSpace=element();
element rangeSpace=element();
element domain=element();
element range=element();
input(domainSpace);
getchar();
input(rangeSpace);
getchar();
input(domain);
getchar();
input(range);
if(isInjective(domainSpace,rangeSpace,domain,range))
{
cout<<"It is an injective.";
}else cout<<"It is not an injective.";
return 0;
}
Task3
Given a mathematical function write a method to determine if the function is surjective. The signature of the method is as follows: Int isSurjective(int domainSpace[], int rangeSpace[], int domain[], int range[])
#include <bits/stdc++.h>
using namespace std;
struct element
{
int a[100];
int len;
int log[100];
element()
{
memset(a,0,sizeof a);
memset(log,0,sizeof log);
len=0;
}
};
void input(element &t)
{
int cnt=1;
char key=',';
getchar();
while(key!='}')
{
cin>>t.a[cnt++];
key=getchar();
}
t.len=cnt;
}
int isSurjective(element domainSpace,element rangeSpace,element domain,element range)
{
for(int i=1;i<domain.len;i++)
{
int u=domain.a[i];
int v=range.a[i];
if(u>=domainSpace.len||v>=rangeSpace.len||u<1||v<1)
{
return 0;
}
if(domain.log[u]==0)
{
domain.log[u]=v;
rangeSpace.log[v]=u;
}
else return 0;
}
for(int i=1;i<rangeSpace.len;i++)
{
if(!rangeSpace.log[i])
{
return 0;
}
}
return 1;
}
int main()
{
element domainSpace=element();
element rangeSpace=element();
element domain=element();
element range=element();
input(domainSpace);
getchar();
input(rangeSpace);
getchar();
input(domain);
getchar();
input(range);
if(isSurjective(domainSpace,rangeSpace,domain,range))
{
cout<<"It is a surjective.";
}else cout<<"It is not a surjective.";
return 0;
}