山东科技大学计算机学院2023级《程序设计基础（C语言）》期末考试题目和部分题解

Problem J: 第k位小数

Time Limit:?1 Sec??Memory Limit:?2 MB
Submit:?1090??Solved:?49
[Submit][Status]

Description

求a/b转换成小数后，小数点后第k位数字是多少？

Input

输入三个正整数a,b,k，用一个空格分开。0<a<=b<100，1<=k<=10000。

Output

一个数字。

Sample Input

1 2 1

Sample Output

5

HINT

Append Code

[Submit][Status]

先将a/b化为小数

模拟除法的过程，第K位就是第K次计算的商

#include <stdio.h>
int main()
{
    int a,b,k;
    scanf("%d%d%d",&a,&b,&k);
    a %= b;
    for(int i = 1; i < k; ++ i){
        a *= 10;
        a %= b;
    }
    printf("%d", a * 10 / b);
    return 0;
}

Problem K: 中国象棋

Time Limit:?1 Sec??Memory Limit:?32 MB
Submit:?1131??Solved:?186
[Submit][Status]

Description

???

中国象棋在中国有着悠久的历史，属于二人对抗性游戏的一种。由于用具简单，趣味性强，成为流行极为广泛的棋艺活动。是我国正式开展的78个体育项目之一，为促进该项目在世界范围内的普及和推广，在中国古代，象棋被列为士大夫们的修身之艺，现在则被视为怡神益智的一种有益的活动。在棋战中，人们可以从攻与防、虚与实、整体与局部等复杂关系的变化中悟出某种哲理。

象棋是由两人轮流走子，以“将死”或“困毙”对方将（帅）为胜的一种棋类运动，对局时，由执红棋的一方先走，双方轮流各走一着，直至分出胜、负、和，对局即终了。轮到走棋的一方，将某个棋子从一个交叉点走到另一个交叉点，或者吃掉对方的棋子而占领其交叉点，都算走一着。双方各走一着，称为一个回合。

在今天这个游戏中，每个玩家有七种棋子。它们有三种属性值，分别为“name”、“offense power” and “symbol letter”。具体见下表：

???现在给出红色棋子玩家和黑色棋子玩家的棋子，你的任务是比较哪名玩家的offense power值大，注意：如果一名玩家没有马或没有炮或两者都没有，那么这名玩家的offense power会减少 1，但是offense power值不会减少到0，也就是最小为 1。

Input

输入的第一行为一个整数?T(0 < T <=20)，代表有?T?组测试数据。

对于每组测试数据：

第一行为红色棋子玩家的棋子，第一行的第一个为一个整数?n (0 < n <= 16)。代表该玩家有?n?个棋子，接下来用空格隔开的n?个字符表示该名玩家的棋子。

第二行为黑色棋子玩家的棋子，格式同红色棋子玩家。

Output

?对于每组测试数据，如果红色棋子玩家的offense power较大，输出“red”；如果黑色棋子玩家的offense power只较大，输出“black”；否则输出“tie”(输出均不含引号)。

Sample Input

3 2 A B 2 A B 7 A A B C D D F 7 A A B B C C F 5 A A B B F 3 A B F

Sample Output

tie black red

HINT

Append Code

[Submit][Status]

小模拟，细心读题即可。

#include <stdio.h>
int a[10],b[10];
int cnt[10]={16,7,8,1,1,2,3};
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        for(int i = 0; i < 10; ++ i){
            a[i] = b[i] = 0;
        }
        int n,m;
        char c;

        scanf("%d",&n);
        for(int i = 0; i < n; ++i){
            scanf(" %c", &c);
            a[c-'A']++;
        }

        scanf("%d",&m);
        for(int i = 0; i < m; ++i){
            scanf(" %c", &c);
            b[c-'A']++;
        }

        int x = 0, y = 0;
        for(int i = 0; i < 7; ++ i){
            x += cnt[i] * a[i];
            y += cnt[i] * b[i];
        }

        if(!a[1]&&!a[2]){
            if(x>1)x--;
        }
        if(!b[1]||!b[2]){
            if(y>1)y--;
        }

        if(x>y){
            printf("red\n");
        }
        else if(x<y){
            printf("black\n");
        }
        else{
            printf("tie\n");
        }
    }
    return 0;
}

Problem L: 阶乘之和

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?647??Solved:?6
[Submit][Status]

Description

计算S=1!+2!+3!+?+n!。

其中!表示阶乘，定义为n!=n×(n?1)×(n?2)×?×1。

例如，5!=5×4×3×2×1=120。

Input

一个正整数n<50。

Output

一个正整数S。

Sample Input

3

Sample Output

9

HINT

测试点1～5 ： 0 < n <= 10

测试点6～8 ：10 < n <= 20

测试点9～11：20 < n <= 50

Append Code

[Submit][Status]

multiple函数实现大数a乘以k的计算并将结果再存储到a当中

f函数实现大数的进位操作，从最低位满十向前进位

add函数实现答案ans加上大数a的操作

#include <stdio.h>
#include <string.h>
int ans[1005];
int a[1005];
int b[1005];
void f(int h[]){
    for(int i = 2;i <= 1000; ++i){
        h[i] += h[i - 1] / 10;
        h[i - 1] %= 10;
    }
}
void multiple(int k){
    for(int i = 1; i <= 500; ++i){
        int j = i;
        int cnt = a[i] * k;
        while(cnt){
            b[j] += cnt % 10;
            cnt /= 10;
            ++j;
        }
    }
    f(b);
    for(int i = 1; i <= 1000; ++i){
        a[i] = b[i];
        b[i] = 0;
    }
}
void add(){
    for(int i = 1; i <= 1000; ++ i){
        ans[i] += a[i];
    }
    f(ans);
}
int main()
{
    int n;scanf("%d",&n);
    a[1]=1;
    ans[1]=1;
    for(int i=2;i<=n;++i){
        multiple(i);
        add();
    }
    int j = 1000;
    while(!ans[j])j--;
    for(int i = j; i >= 1; --i){
        printf("%d", ans[i]);
    }
    return 0;
}

Problem M: 数字三角形

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?92??Solved:?14
[Submit][Status]

Description

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以向左下方或右下方前进。

如图所示的样例中，从最高点开始的路径7→3→8→7→5产生了最大和。

Input

第一行是一个正整数n，（n<100），表示数字金字塔的层数。

后面是这个数字金字塔，所有输入数字在0～100范围内。

Output

一个整数最大和。

Sample Input

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

Sample Output

30

HINT

?测试点1～6 ： 1 <= n <= 6

测试点6～8 ： 6 < n < 30

测试点9～11：30 <= n <= 100

Append Code

[Submit][Status]

线性DP

状态转移方程为

? ? ? ? dp[i][j] = a[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])

????????(满足i !=?1 && j - 1 >= 1 && j != i)

最终的答案

? ? ? ? ans = max(dp[n][1], dp[n][2] ... dp[n][n])

#include <stdio.h>
#include <string.h>
int a[105][105];
int dp[105][105];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= i; ++ j){
            scanf("%d", &a[i][j]);
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= i; ++ j){
            int max = 0;
            if(i != 1){
                // 左上不越界
                if(j - 1 >= 1){
                    if(dp[i - 1][j - 1] > max){
                        max = dp[i - 1][j - 1];
                    }
                }
                // 不在右边缘
                if(j != i){
                    if(dp[i - 1][j] > max){
                        max = dp[i - 1][j];
                    }
                }
            }
            dp[i][j] = a[i][j] + max;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++ i){
        if(dp[n][i] >= ans){
            ans = dp[n][i];
        }
    }
    printf("%d", ans);
    return 0;
}

????????