博客

14周离散数学机考考试范围及参考代码

  • Post author:
  • Post category:其他


1.1联结词真值运算

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

已知命题变元p和q的真值，求它们的合取式(p∧q)、析取式(p∨q)、蕴涵式(p→q)、等值式(A<=>B)、与非式(p↑q)、或非式(p↓q)的真值。

Input

多组输入，每组测试数据输入两个0或1的整数p和q，1表示真值为真，0表示真值为假

Output

每组测试数据单独占一行，以空格隔开的6个0或1的整数，分别为p和q的合取式(p∧q)、析取式(p∨q)、蕴涵式(p→q)、等值式(A<=>B)、与非式(p↑q)、或非式(p↓q)的真值。

Sample Input 

0 0

Sample Output 

0 0 1 1 1 1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
    int p,q,a,b,c,d,e,f;
    while(scanf("%d%d",&p,&q)!=EOF)
    {
     if(p==1&&q==1) a=1;
     else a=0;
     if(p==0&&q==0)  b=0;
     else b=1;
     if(p==1&&q==0)c=0 ;
     else c=1;
     if(p==q) d=1 ;
     else d=0 ;
     if(p==1&&q==1) e=0 ;
     else e=1 ;
     if(p==0&&q==0) f=1;
     else f= 0;
     printf("%d %d %d %d %d %d",a,b,c,d,e,f);
     printf("\n");
    }
    return 0;
}

哪款赛车最佳？

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

四名专家对四款赛车进行评论。

专家A说：a号赛车是最好的。

专家B说：b号赛车是最好的。

专家C说：c号不是最佳赛车。

专家D说：专家B说错了。

事实上只有一款赛车最佳，且只有一名专家说对了，其他三人都说错了。请编程输出最佳车的编号，以及哪位专家所对了。

Input

多组测试数据，对于每组测试数据，第 1 行输入3个正整数，表示a、b 、c的编号，编号x范围(1 <= x <= 4)，且编号互不相同。

Output

对于每组测试数据，输出正整数x和字符ch，表示最佳车的编号以及说对的专家的编号，详细格式请参考样例。

Sample Input 

2 4 3

Sample Output 

3 D
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int S1,S2,S3,S4,best,a,b,c;
    while(~scanf("%d %d %d",&a,&b,&c))
    {
        for(best=1; best<=4; best++)
        {
            S1=(best==a);
            S2=(best==b);
            S3=(best!=c);
            S4=!S2;
        if(S1+S2+S3+S4==1)
        {
            if(S1==1)
            {
                printf("%d %c\n",a,'A');
            }
            else if(S2==1)
            {
                printf("%d %c\n",b,'B');
            }
            else if (S3==1)
           {
               printf("c  is'n best\n");
              }
            else if(S4==1)
            {
                printf("%d %c\n",c,'D');
            }
        }
        }
    }
    return 0;
}
#include <stdio.h>  
#include <stdlib.h>  
  
int main()  
{  
    int a, b, c;  
    while(~scanf("%d %d %d", &a, &b, &c))  
    {  
        char ch;  
        int m;  
        for(m=1;m<5;m++)  
        {  
            if(!(m-a)+!!(m-b)+!!(m-c)+!(m-b)==1)  
            {  
                 if(m == a) ch = 'A';  
                 else if(m == b) ch = 'B';  
                 else if(m != c) ch = 'C';  
                 else if(m != b) ch = 'D';  
                 printf("%d %c\n", m, ch);  
            }  
        }  
    }  
    return 0;  
}  

#include <stdio.h>  
  
int main()  
{  
    int car;  
    int x[4];  
    int i, a, b, c;  
    while(~scanf("%d %d %d", &a, &b, &c))  
    {  
        for(car=1; car<5; car++)  
        {  
            x[0]=(car==a);  
            x[1]=(car==b);  
            x[2]=(car!=c);  
            x[3]=(car!=b);  
            if((x[0]+x[1]+x[2]+x[3])==1)  
            {  
                printf("%d ",car);  
                for(i=0; i<4; i++)  
                {  
                    if(x[i]) printf("%c\n",'A'+i);  
                }  
            }  
        }  
    }  
    return 0;  
}

集合的包含

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

已知含n个元素的集合的子集A和B，用位串表示法判断是否有A⊆B。

Input

多组测试数据，每组测试数据第1行输入正整数n(1 <= n <= 100)，表示集合元素个数，第2行输入位串表示法形式的集合A，第3行输入位串表示法形式的集合B。

Output

对于每组测试数据，若A⊆B则输出yes，反之则输出no。

Sample Input 

10
1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0
10
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1

Sample Output 

yes
no

Hint

集合{1, 3, 5, 7, 9}，位串表示法：1 0 1 0 1 0 1 0 1 0

集合{6 7, 8, 9, 10}，位串表示法：0 0 0 0 0 1 1 1 1 1

集合{7, 8, 9, 10}，位串表示法：0 0 0 0 0 0 1 1 1 1 

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, n;
    while(~scanf("%d", &n))
    {
        int flag = 1;
        int a[110];
        int b[110];
        for(i=0; i<n; i++)
        {
            scanf("%d", &a[i]);
        }
        for(i=0; i<n; i++)
        {
            scanf("%d", &b[i]);
        }
        for(i=0; i<n; i++)
        {
            if(!b[i])
            {
                if(a[i])
                {
                    flag = 0;
                    break;
                }
            }
        }
        if(flag) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

偏序关系

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

给定有限集上二元关系的关系矩阵，确定这个关系是否是偏序关系。

Input

多组测试数据，对于每组测试数据，第1行输入正整数n（1 <= n <= 100），第2行至第n+1行输入n行n列的关系矩阵。

Output

对于每组测试数据，若为偏序关系，则输出yes，反之，则输出no。

Sample Input 

4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
4
1 0 0 1
0 1 0 0
0 0 1 0
1 0 0 1

Sample Output 

yes
no

Hint

偏序关系形式定义：设R是集合A上的一个二元关系，若R满足自反性、反对称性、传递性，则称R为A上的偏序关系。 

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, j, k, n;
    int a[110][110];
    while(~scanf("%d", &n))
    {
        int flag = 1;
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                scanf("%d", &a[i][j]);
            }
        }
        for(i=0; i<n; i++)
        {
            if(!a[i][i])
            {
                flag = 0;
                break;
            }
            for(j=0; j<n; j++)
            {
                if(a[i][j] && a[j][i] && i!=j)
                {
                    flag = 0;
                    break;
                }
                if(a[i][j])
                {
                    for(k=0; k<n; k++)
                    {
                        if(a[j][k])
                        {
                            if(!a[i][k])
                            {
                                flag = 0;
                                break;
                            }
                        }
                    }
                }
            }
        }
        if(flag) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

传递闭包

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

已知有n头牛，m次战斗关系，询问最终可以确定排名的牛的数量。

Input

多组测试数据，对于每组测试数据，第1行输入两个整数n(1 <= n <= 100)和m(0 <= m <= 4950)，分别表示有n头牛和m次战斗关系，之后m行每行输入两个正整数x和y表示编号为x的牛可以战胜编号为y的牛，数据保证合法，询问可以确定排名的牛的数量。

Output

对于每组测试数据，输出整数ans，表示可以确定排名的牛的数量。

Sample Input 

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output 

2
#include<stdio.h>
#include<string.h>
int a[110][110];
void warshell(int n)
{
    int k, i, j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(a[j][i])
            {
                for(k=1; k<=n; k++)
                {
                    a[j][k] = a[j][k] + a[i][k];
                    if(a[j][k] >= 1)
                        a[j][k] = 1;
                }
            }
        }
    }
}
int main()
{
    int m, n, x, y, i, j, ans, num[110];
    while(~scanf("%d %d", &n, &m))
    {
        ans = 0;
        memset(a, 0, sizeof(a));
        memset(num, 1, sizeof(num));
        while(m--)
        {
            scanf("%d %d", &x, &y);
            a[x][y] = 1;
        }
        warshell(n);
        for(j=1; j<=n; j++)
        {
            for(i=1; i<=n; i++)
            {
                if(i == j)
                {
                    if(a[i][j])
                    {
                        num[j] = 0;
                        break;
                    }
                }
                else if(!a[i][j])
                {
                    if(!a[j][i])
                    {
                        num[j] = 0;
                        break;
                    }
                }
            }
            if(num[j])
            {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
//code 2
#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
const int maxn = 110;
int d[maxn];
int mp[maxn][maxn];
void wsh(int n)
{
    for(int k = 1;k <= n;k++)
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                mp[i][j] = mp[i][j] || (mp[i][k] && mp[k][j]);
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int a,b;
        memset(mp,0,sizeof(mp));
        while(m--)
        {
            scanf("%d%d",&a,&b);
            mp[a][b] = 1;
        }
        wsh(n);
        int ret = 0;
        for(int i = 1; i <= n;i++)
        {
            int ans = 0;
            for(int j = 1;j <= n;j++)
            {
                if(i == j)continue;
                if(mp[i][j] || mp[j][i])ans++;
            }
            if(ans == n - 1)ret++;
        }
        printf("%d\n",ret);
    }
    return 0;
}

离散题目11

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

给定一个数学函数写一个程序来确定该函数是否是双射的

Input

多组输入。 第一行输入三个整数n,m,k,分别表示集合a中的元素个数，集合b中的元素个数，集合a到b的映射个数。 第二行输入n个数，代表集合a中的元素。 第三行输入m个数，代表集合b中的元素。接下来k行，每行两个数，代表集合a中的元素x和x在集合b中的像y。

Output

每组数据输出一行，若F为a到b的双射，输出”YES”， 否则输出”NO”。

Sample Input 

5 5 5
1 2 3 7 8
2 5 6 9 0
1 9
3 2
2 6
7 0
8 5

Sample Output 

YES

Hint

保证集合a中元素无重复，集合b中元素无重复，映射关系无重复（如：{,}）

1<=n,m,k<=1000

1<=a[i], b[i]<=10000

x∈a， y∈b 

 
#include<stdio.h>

int main()
{
    int n, m, k;
    while(scanf("%d %d %d", &n, &m, &k) != EOF)
    {
        int flag = 1;
        int a[10005] = {0}, b[10005] = {0};
        int i;
        int x;
        for(i = 1; i <= n; i++)
            scanf("%d", &x);
        for(i = 1; i <= m; i++)
        {
            scanf("%d", &x);
            b[x] = 1;
        }
        int sum = 0;
        for(i = 1; i <= 2 * k; i++)
        {
            scanf("%d", &x);
            if(i % 2 != 0)
            {
                if(a[x] == 0)
                {
                    a[x]++;
                }
                else
                    flag = 0;
            }
            else
            {
                if(b[x] == 0)
                {
                    flag = 0;
                }
                else
                {
                    if(b[x] == 1)
                    {
                        sum++;
                        b[x]++;
                    }
                }
            }
        }
        if(sum < m)
            flag = 0;
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

离散题目12

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

给出两个集合，以及两个集合上的关系。判断该关系能不能构成函数

Input

多组输入。第一行数字表示集合A；第二行数字表示集合B；第三行一个数字N，表示关系的个数。以下N行，每行两个数字a b，用来描述关系a→b。0 < n < = 20000,集合A、B的大小不超过10000.

Output

每组数据输出一行，所给关系属于函数，输出’yes’ ，否则输出‘no’。

Sample Input 

1 2 3
4 5 6
3
1 4
2 5
3 6
1 2 3
4 5 6
3
1 4
1 5
1 6

Sample Output 

yes
no
 
#include<stdio.h>
char A[100005], B[100005];
int b[10005];
int c[20005];
int d[20005];
int main()
{
    while(gets(A))
    {
        gets(B);
        int n;
        scanf("%d", &n);
        int i;
        int s = 1;
        for(i = 0; A[i]; i++)
        {
            if(A[i] >= '0' && A[i] <= '9')
                b[s++] = A[i] - '0';
        }
        int flag = 1;
        int j;
        for(i = 1; i <= n; i++)
        {
            scanf("%d %d", &c[i], &d[i]);
            for(j = 1; j < i; j++)
            {
                if(c[i] == c[j])
                {

                    if(d[i] != d[j])
                        flag = 0;
                }
            }
        }
        if(flag)
            printf("yes\n");
        else
            printf("no\n");
        gets(A);
    }
    return 0;
}

建图

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

编程使得程序可以接受一个图的点边作为输入，然后显示出这个图。

Input

多组测试数据，对于每组测试数据，第一行输入正整数n(1 <= n <= 1000)和m，之后m行输入正整数x、y，表示在点x和点y之间存在有向边相连。

Output

对于每组测试数据，输出图的关系矩阵。

Sample Input 

4 5
1 1
2 2
2 4
3 3
4 4

Sample Output 

1 0 0 0
0 1 0 1
0 0 1 0
0 0 0 1
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#define MA 1010  
int G[MA][MA];  
  
int main()  
{  
    int n, m;  
    while(~scanf("%d %d", &n, &m))  
    {  
        int x, y;  
        int i, j;  
        memset(G, 0, sizeof(G));  
        while(m--)  
        {  
            scanf("%d %d", &x, &y);  
            G[x][y] = 1;  
        }  
        for(i=1; i<=n; i++)  
        {  
            for(j=1; j<=n-1; j++)  
            {  
                printf("%d ", G[i][j]);  
            }  
            printf("%d\n", G[i][j]);  
        }  
    }  
    return 0;  
}

指定长度路径数

Time Limit: 1000 ms Memory Limit: 65536 KiB


Submit


Statistic

Problem Description

题目给出一个有n个节点的有向图，求该有向图中长度为k的路径条数。方便起见，节点编号为1,2,…,n，用邻接矩阵表示该有向图。该有向图的节点数不少于2并且不超过500.

例如包含两个节点的有向图，图中有两条边1 → 2 ,2 → 1 。

长度为1的路径有两条：1 → 2 和 2 →1 ；

长度为2的路径有两条：1 → 2 → 1和2 → 1 → 2 ；

偷偷告诉你也无妨，其实这个图无论k取值多少 ( k > 0 )，长度为k的路径都是2条。

Input

多组输入，每组输入第一行是有向图中节点的数量即邻接矩阵的行列数n。接下来n行n列为该图的邻接矩阵。接下来一行是一个整数k.k小于30.

Output

输出一个整数，即为图中长度为k的路径的条数。

Sample Input 

3
0 1 0
0 0 1
0 0 0
2

Sample Output 

1
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#define MA 550  
int G[MA][MA], mu[MA][MA], g[MA][MA];  
  
int main()  
{  
    int n, m;  
    int i, j, k;  
    int num;  
    while(~scanf("%d", &n))  
    {  
        for(i=0; i<n; i++)  
        {  
            for(j=0; j<n; j++)  
            {  
                scanf("%d", &G[i][j]);  
                g[i][j] = G[i][j];  
            }  
        }  
        scanf("%d", &m);  
        while(--m)  
        {  
            memset( mu, 0, sizeof(mu));  
            for(i=0; i<n; i++)  
            {  
                for(j=0; j<n; j++)  
                {  
                    for(k=0; k<n; k++)  
                    {  
                        mu[i][j] += g[i][k] * G[k][j];  
                    }  
                }  
            }  
            for(i=0; i<n; i++)  
            {  
                for(j=0; j<n; j++)  
                {  
                    G[i][j] = mu[i][j];  
                }  
            }  
        }  
        num = 0;  
        for(i=0; i<n; i++)  
        {  
            for(j=0; j<n; j++)  
            {  
                //printf("%d ", G[i][j]);  
                num += G[i][j];  
            }//printf("\n");  
        }  
        printf("%d\n",num);  
    }  
    return 0;  
}


版权声明：本文为winner647520原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。