Basic-Computer-Science:Lab 2 Function(计算机科学基础)

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

我们规定:

  1. 对于domainSpace, rangeSpace, domain, range输入均为一个形如:{a1,a2,a3,…,ai,…,an}的字符串,其中ai为整数;
  2. 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;
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇