C++课程设计实验杭州电子科技大学ACM题目（下）

题目七：2060.Snooker

题目描述

Problem Description:

background:
Philip likes to play the QQ game of Snooker when he wants a relax, though he was just a little vegetable-bird. Maybe you hadn't played that game yet, no matter, I'll introduce the rule for you first.There are 21 object balls on board, including 15 red balls and 6 color balls: yellow, green, brown, blue, pink, black.The player should use a white main ball to make the object balls roll into the hole, the sum of the ball's fixed value he made in the hole is the player's score. The player should firstly made a red ball into the hole, after that he gains red-ball's value(1 points), then he gets the chance to make a color ball, then alternately. The color ball should be took out until all the red-ball are in the hole. In other word, if there are only color balls left on board, the player should hit the object balls in this order: yellow(2 point), green(3 point), brown(4 point), blue(5 point), pink(6 point), black(7 point), after the ball being hit into the hole, they are not get out of the hole, after no ball left on board, the game ends, the player who hasthe higher score wins the game. PS: red object balls never get out of the hole.I just illustrate the rules that maybe used, if you want to contact more details, visit http://sports.tom.com/snooker/ afterthe contest.for example, if there are 12 red balls on board(if there are still red ball left on board, it can be sure that all the color balls must be on board either). So suppose Philp can continuesly hit the ball into the hole, he can get the maximun score is 12 * 1 (12 red-ball in one shoot) + 7 * 12(after hit a red ball, a black ball which was the most valuable ball should be the target) + 2 + 3 + 4 + 5 + 6 + 7(when no red ball left, make all the color ball in hole).Now, your task is to judge whether Philip should make the decision to give up when telling you the condition on board(How many object balls still left not in the hole and the other player's score). If Philp still gets the chance to win, just print "Yes", otherwise print "No". (PS: if the max score he could get on board add his current score is equal to the opponent's current score, still output "Yes")

Input：The first line contains a numble N indicating the total conditions. Then followed by N lines, each line is made of three integers:
Ball_Left P_Score O_Score represeting the ball number left on board, Philp's current score, and the opponent's current score.
All the input value are in 32 bit integer value range.

Output：You should caculate the max score left Philp can gain, and judge whether he has the possiblity to win.

运行代码

#include <iostream>
using namespace std;
int main()
{
    int N, a, b, c;
    cin >> N;
    while (N--)
    {
        cin >> a >> b >> c;
        int t = 0;
        if (a> 6)
            t = (a- 6) * 7 + a- 6 + 27;
        else
            t = 27 - (9 - a) * (6 - a) / 2;
        if (b + t>= c)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

代码思路

1. 输入处理:首先读取测试用例的总数N。使用while循环处理每个测试用例，读取三个整数：a（剩余球数）、b（Philp当前分数）、c（对手当前分数）。

2. 计算理论最高分:依据斯诺克游戏规则，程序通过条件判断来计算Philp可能得到的最高分数。如果剩余球数a大于6，意味着至少有一个红球和所有彩球在桌上。此时，策略是尽可能多地交替击打入红球和黑球（最高分的彩球），公式为：(a-6)*7 + a-6（红球得分）+ 27（所有彩球得分）。如果剩余球数a小于等于6，说明红球几乎全被打入，剩下的球应为彩球。这里采用了一个简化的计算方法来估计剩余彩球可能带来的分数，公式为：27 - (9-a)*(6-a)/2。这个公式基于组合数学原理，考虑了剩余彩球的不同击球顺序，但由于实际游戏中顺序固定，这里的简化处理可能并不精确匹配题目要求的最优解法，但旨在快速估算一个可能的高分。

3. 胜负判断:将计算出的理论最高分t加上Philp当前的分数b，与对手的分数c进行比较。如果总和大于等于对手的分数，输出"Yes"，表明Philp有获胜的可能；否则，输出"No"。

注意：代码中的计算方法对于剩余彩球的处理进行了简化的估计，并非严格遵循斯诺克游戏的最优策略（尤其是剩余彩球少于6个时的处理）。在实际比赛中，彩球的击球顺序是固定的，上述代码简化了这一复杂度，可能在特定条件下给出不太准确的结果。不过，从题目要求来看，这段代码提供了一种快速判断是否有可能胜利的思路。

题目八：2061.Treasure the new start, freshmen!

题目描述

Problem Description

background:A new semester comes , and the HDU also meets its 50th birthday. No matter what's your major, the only thing I want to tell you is:"Treasure the college life and seize the time." Most people thought that the college life should be colorful, less presure.But in actual, the college life is also busy and rough. If you want to master the knowledge learned from the book, a great deal of leisure time should be spend on individual study and practise, especially on the latter one. I think the every one of you should take the learning attitude just as you have in senior school.
"No pain, No Gain", HDU also has scholarship, who can win it? That's mainly rely on the GPA(grade-point average) of the student had got. Now, I gonna tell you the rule, and your task is to program to caculate the GPA.If there are K(K > 0) courses, the i-th course has the credit Ci, your score Si, then the result GPA isGPA = (C1 * S1 + C2 * S2 +……+Ci * Si……) / (C1 + C2 + ……+ Ci……) (1 <= i <= K, Ci != 0)If there is a 0 <= Si < 60, The GPA is always not existed.

Input：The first number N indicate that there are N test cases(N <= 50). In each case, there is a number K (the total courses number), then K lines followed, each line would obey the format: Course-Name (Length <= 30) , Credits(<= 10), Score(<= 100).
Notice: There is no blank in the Course Name. All the Inputs are legal

Output：Output the GPA of each case as discribed above, if the GPA is not existed, ouput:"Sorry!", else just output the GPA value which is rounded to the 2 digits after the decimal point. There is a blank line between two test cases.

运行代码

#include<iostream>
using namespace std;
int main()
{
    int i, j, n, m, ok;
    double s, c, sum, k;
    char w[100];
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> m;
        sum = 0; k = 0; ok = 0;
        for (j = 1; j <= m; j++)
        {
            cin >> w >> c >> s;
            k += c;
            sum += s * c;
            if (s < 60) ok = 1;
        }
        if (ok) 
            printf("Sorry!\n");
        else 
            printf("%.2lf\n", 1.0 * sum / k);
        if (i != n) 
            cout<<endl;
    }
    return 0;
}

代码思路

1. 初始化变量：首先，程序初始化了一些基本变量，包括用于循环的计数器（i, j），课程总数（n, m），布尔标记（ok），以及用于计算总学分（k）和总成绩（sum）的变量。另外，定义了一个字符数组w[100]来临时存储课程名称。

2. 读取测试用例数量：通过cin >> n;读取需要处理的测试用例数量。

3. 遍历每个测试用例：使用外层循环（for (i = 1; i <= n; i++)）来遍历每个测试用例。

   • 读取课程总数：对于每个测试用例，先读取该案例中的课程总数m。

   • 初始化变量：在处理每个测试用例前，重置sum（总成绩乘学分之和）、k（总学分）、ok（是否有课程成绩低于60分的标记）为初始值。

   • 遍历每门课程：通过内层循环（for (j = 1; j <= m; j++)）处理每门课程。

     读取课程信息：依次读取课程名称（实际上并未使用）、学分（c）和成绩（s）。累加计算：将学分乘以成绩累加到sum，并将学分累加到k。同时检查成绩是否低于60分，如果是，则将ok设为1，表示有不合格课程。

   • 输出结果：根据ok的值判断是否有不合格课程。如果有（ok == 1），输出"Sorry!\n"；如果没有，输出计算得到的GPA，即总成绩乘学分之和除以总学分，并四舍五入到小数点后两位（printf("%.2lf\n", 1.0 * sum / k);）。

   • 添加分隔符：如果这不是最后一个测试用例，输出一个换行符，以便于区分不同用例的输出。

4. 结束程序：所有测试用例处理完毕后，程序正常结束。

题目九：2064.汉诺塔III

题目描述

Problem Description

约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。
Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？

Input：包含多组数据，每次输入一个N值(1<=N=35)。

Output：对于每组数据，输出移动最小的次数。

运行代码

#include <iostream>
using namespace std;
#include<math.h>
int main()
{
    int n;
    long long  a[10000];
    while (cin>>n)
    {
        a[1] = 2;
        for (int i = 1; i < n; i++)
        {
            a[i + 1] = 3 * a[i] + 2;
        }
       cout<<a[n]<<endl;
    }
    return 0;
}

代码思路

1. 初始化: 首先，程序定义了一个整型变量n用于接收用户输入，以及一个足够大的长整型数组a来存储数列的元素。数组a预先设置a[1] = 2，这表明数列的首项为2。

2. 数列生成: 通过一个for循环，循环变量i从1开始，到n-1结束，循环内部计算数列的每一项。数列的生成规则是当前项a[i+1]等于前一项a[i]的三倍再加2。这是一个线性递推关系式，即数列的第i+1项基于第i项计算得出。

3. 输出结果: 循环结束后，数组a[n]存储的是数列的第n项值，程序将其输出到控制台。

题目十：2069.Coin Change

题目描述

Problem Description：Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.
For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.
Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 coins.

Input：The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.

Output：For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.

运行代码

#include <iostream>  
using namespace std;
int main()
{
    int n;
    while (cin>>n)
    {
        int ans = 0;
        for (int a = 0; a <= 5; a++)               // 50
            for (int b = 0; b <= 10 - 2 * a; b++)        // 25
                for (int c = 0; c <= 25 - 5 * a; c++)      // 10
                    for (int d = 0; d <= 50 - 2 * c; d++)    // 5
                        for (int e = 0; e <= 100; e++)     // 1
                            if (50 * a + 25 * b + 10 * c + 5 * d + e == n && a + b + c + d + e <= 100)
                                ans++;
     cout<<ans<<endl;
    }
    return 0;
}

代码思路

直接枚举法

1. 输入与循环处理：程序首先读取一个整数n，表示目标金额。使用while(cin>>n)循环结构，持续接受输入，直到输入结束。

2. 多重循环遍历组合：接下来的嵌套for循环遍历了所有可能的硬币组合。每个循环变量分别代表一种硬币的数量：

   • a代表50美分硬币的数量，
   • b代表25美分硬币的数量，
   • c代表10美分硬币的数量，
   • d代表5美分硬币的数量，
   • e代表1美分硬币的数量。

3. 条件判断：在循环体内，有一条if语句用来判断当前硬币组合是否符合条件：

   • 50 * a + 25 * b + 10 * c + 5 * d + e == n确保组合的总金额等于目标金额n。
   • a + b + c + d + e <= 100确保硬币总数不超过100枚。 如果这两个条件都满足，就说明找到了一个有效的组合，此时ans计数器加1。

4. 输出结果：当所有可能的组合都被检查过后，循环结束，程序输出累计的组合数ans。

通过这种方式，程序有效地遍历了所有可能的硬币组合，并计算出了符合限制条件的组合总数。这种穷举法虽然简单直接，但对于较大的输入值可能会导致性能问题，因为它的时间复杂度较高。