杭电ACM基础题目（1000 1001 1004 1005 1008 1012 1014）

心已赠人 2023-07-17 06:43 13阅读 0赞

### 文章目录 ###

*   *  1001、Sum Problem
     *  1004、 Let the Ballon Rise
     *  1005、 Number Sequence
     *  1008、 Elevator
     *  1012、 u Calculate e
     *  1013、 Digital Roots
     *  1014、Uniform Generator

## 1001、Sum Problem ##

Code:  
1、注意：输出格式的要求，因为题目要求空一行，所以需要cout<<endl<<endl;  
2、计算从1-n的和并输出

#include<iostream>
    using namespace std;
    int main() {
        
        int n,sum;
        while (cin >> n) {
        
            sum = 0;
            if (n == 0) return 0;
            for (int i = 1; i <= n; i++) {
        
                sum = sum + i;
            }
            cout << sum << endl<<endl;
        }
    
    }

## 1004、 Let the Ballon Rise ##

**Input**  
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) – the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.  
A test case with N = 0 terminates the input and this test case is not to be processed.  
**Output**  
For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.  
**Sample Input**

5
    green
    red
    blue
    red
    red
    3
    pink
    orange
    pink
    0

**Sample Output**

red
    pink

**Code:**  
1、二维数组输入字符串，字符串的长度有限定  
2、strcmp()函数  
3、比较数组中元素相同的个数

#include<iostream>
    using namespace std;
    int main() {
        
        int n;
        while (cin >> n) {
        
            if (n == 0) return 0;
            int num[1000] = {
        0};
            char color[1000][15];//借用二维数组输入字符串
            for (int i = 0; i < n; i++) {
        
                cin >> color[i];
            }
            //寻找color[]中个数最多的元素
            for (int i = 0; i < n; i++) {
        
                for (int j = i + 1; j < n; j++) {
        
                    if (strcmp(color[i], color[j]) == 0) {
        //strcmp()字符串比较函数
                        num[i]++;
                    }
                }
            }
            int max =0;
            for (int i = 1; i < n; i++) {
        
                if (num[i] > max)
                    max = i;
            }
            cout << color[max] << endl;
        }
    
    }

## 1005、 Number Sequence ##

**Problem Description**  
A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A \* f(n - 1) + B \* f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).  
**Input**  
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.  
**Output**  
For each test case, print the value of f(n) on a single line.  
**Sample Input**

1 1 3
    1 2 10
    0 0 0

**Sample Output**

2
    5

**Code:**  
方法一：使用递归的方式，但会出现内存超限的问题

#include<iostream>
    using namespace std;
    int f(int a, int b, int n) {
        
        int result;
        if (n == 1||n==2) {
        
            return 1;
        }
        else {
        
            result=(a * f(a,b,n - 1) + b * f(a,b,n - 2))%7;
        }
        return result;
    }
    int main() {
        
        int a, b, n;
        while (cin >> a >> b >> n) {
        
            if (a==0&&b==0&&n==0) return 0;
            if (a>=1&&a<=1000&&b>=1&&b<=1000&&n>=1&&n<=100000000) {
        
                cout << f(a, b, n) << endl;
            }
        }
    
    }

方法二：找规律

//每隔49出现一次相同的数
    #include<iostream>
    using namespace std;
    int main() {
        
        int a, b, n,arr[49]={
        1,1};
        while (cin >> a >> b >> n) {
        
            if (a==0&&b==0&&n==0) return 0;
            for(int i=2;i<49;i++){
        
             arr[i]=(a*arr[i-1]+b*arr[i-2])%7;
      }
      cout<<arr[(n-1)%49]<<endl;
        }
     return 0;
    }

## 1008、 Elevator ##

**Problem Description**  
The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.  
For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.  
**Input**  
There are multiple test cases. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed.  
**Output**  
Print the total time on a single line for each test case.  
**Sample Input**

1 2
    3 2 3 1
    0

**Sample Output**

17
    41

**Code:**  
比较简单，借助floor\[\]数组存储请求的楼层，通过相邻两个数组之间的大小判断上楼还是下楼

#include<iostream>
    using namespace std;
    
    int main() {
        
        int n;
        while (cin >> n) {
        
            int floor[100] = {
         0 }, time = 0;
            if (n == 0) return 0;
            for (int i = 0; i < n; i++) {
        
                cin >> floor[i];
            }
            //对于floor[]数组的处理
            time = time + (floor[0] * 6 + 5);
            for (int i = 1; i < n; i++) {
        
                if (floor[i] > floor[i - 1]) {
        
                    time = time + ((floor[i] - floor[i - 1]) * 6 + 5);
                }
                else {
        
                    time = time + ((floor[i - 1] - floor[i]) * 4 + 5);
                }
            }
            cout << time << endl;

## 1012、 u Calculate e ##

A simple mathematical formula for e is

![在这里插入图片描述][20200320181026275.jpg]

where n is allowed to go to infinity. This can actually yield very accurate approximations of e using relatively small values of n.  
**Output**  
Output the approximations of e generated by the above formula for the values of n from 0 to 9. The beginning of your output should appear similar to that shown below.  
**Sample Output**

n e
    - -----------
    0 1
    1 2
    2 2.5
    3 2.666666667
    4 2.708333333

**Code:**  
1、阶乘的计算采用递归的方式  
2、输出结果注意格式要求，小数点的位数

#include<iostream>
    #include<iomanip>
    using namespace std;
    int f(int n) {
        
        if (n == 0 || n == 1) {
        
            return 1;
        }
        else {
        
            return n * f(n - 1);
        }
    }
    int main() {
        
        double    result_1,result,sum;
        cout << "n" << " " << "e" << endl;
        cout << "-" << " " << "-----------" << endl;
        for (int i = 0; i <= 9; i++) {
        
            sum = 0;
            for (int j = 0; j <= i; j++) {
        
                result_1 = f(j);
                result = 1 / result_1;
                sum = sum + result;
            }
            if (i == 0 || i == 1) {
        
                cout << i << " " << sum << endl;
            }
            else if (i == 2) {
        
                cout << setiosflags(ios::fixed);
                cout << i << " " <<setprecision(1)<< sum << endl;
            }
            else {
        
                cout << setiosflags(ios::fixed);
                cout << i << " " << setprecision(9) << sum << endl;
            }
        }
    }

## 1013、 Digital Roots ##

The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.

For example, consider the positive integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 yeilds 3, a single digit and also the digital root of 39.  
**Input**  
The input file will contain a list of positive integers, one per line. The end of the input will be indicated by an integer value of zero.  
**Output**  
For each integer in the input, output its digital root on a separate line of the output.  
**Sample Input**

24
    39
    0

**Sample Output**

6
    3

**Code:**  
方法一：未注意到范围，Wrong answer

#include<iostream>
    using namespace std;
    int root(int n) {
        
     	int rot,sum=0;
     	while (n != 0) {
        
      		rot = n % 10;
      		sum = sum + rot;
      		n = n / 10;
     	}
     	return sum;
    }
    int main() {
        
    	 int n,result;
     	while (cin >> n) {
        
     		 if (n == 0) return 0;
      		result = root(n);
     		 while (result / 10 != 0) {
        
      			 result=root(result);
       			if (result / 10 == 0) {
        
       			 break;
       			}
      		}
     	 cout << result << endl;
     	}
    }

方法二、因为涉及到大数、需要借助字符数组，结果终于正确了

#include<iostream>
    #include<string.h>
    using namespace std;
    int f(char c[]) {
        
        int sum=0,a,root;
        for (int i = 0; i < strlen(c); i++) {
        
            sum = sum + (c[i] - '0');//c[i]-0将字符型转化为整型
        }
        //sum的值大于10，要对sum进行分解求和
        while (sum >= 10) {
        
            root = 0;
            while (sum != 0) {
        
                a = sum % 10;
                root = root + a;
                sum = sum / 10;
            }
            sum = root;
        }
        return sum;
    }
    int main() {
        
        char c[100000];
        int result;
        while (cin >> c) {
        
            if (strcmp(c,"0")==0) return 0;//char[]比较字符串相等，只能用strcmp(),string可以
            cout << f(c) << endl;
        }
        return 0;
    }

## 1014、Uniform Generator ##

Computer simulations often require random numbers. One way to generate pseudo-random numbers is via a function of the form

seed(x+1) = \[seed(x) + STEP\] % MOD

where ‘%’ is the modulus operator.

Such a function will generate pseudo-random numbers (seed) between 0 and MOD-1. One problem with functions of this form is that they will always generate the same pattern over and over. In order to minimize this effect, selecting the STEP and MOD values carefully can result in a uniform distribution of all values between (and including) 0 and MOD-1.

For example, if STEP = 3 and MOD = 5, the function will generate the series of pseudo-random numbers 0, 3, 1, 4, 2 in a repeating cycle. In this example, all of the numbers between and including 0 and MOD-1 will be generated every MOD iterations of the function. Note that by the nature of the function to generate the same seed(x+1) every time seed(x) occurs means that if a function will generate all the numbers between 0 and MOD-1, it will generate pseudo-random numbers uniformly with every MOD iterations.

If STEP = 15 and MOD = 20, the function generates the series 0, 15, 10, 5 (or any other repeating series if the initial seed is other than 0). This is a poor selection of STEP and MOD because no initial seed will generate all of the numbers from 0 and MOD-1.

Your program will determine if choices of STEP and MOD will generate a uniform distribution of pseudo-random numbers.  
**Iuput**  
Each line of input will contain a pair of integers for STEP and MOD in that order (1 <= STEP, MOD <= 100000).  
**Output**  
For each line of input, your program should print the STEP value right- justified in columns 1 through 10, the MOD value right-justified in columns 11 through 20 and either “Good Choice” or “Bad Choice” left-justified starting in column 25. The “Good Choice” message should be printed when the selection of STEP and MOD will generate all the numbers between and including 0 and MOD-1 when MOD numbers are generated. Otherwise, your program should print the message “Bad Choice”. After each output test set, your program should print exactly one blank line.  
**Sample Input**

3 5
    15 20
    63923 99999

**Sample Output**

3         5    Good Choice
    
            15        20    Bad Choice
    
         63923     99999    Good Choice

**方法一：判断两个数是否互质**  
1、利用辗转相除寻找两个数的最大公因数，比较两个数的最大公因数是否为1  
2、输出格式setw()

#include<iostream>
    #include<iomanip>
    using namespace std;
    int main() {
        
        int step, mod, temp, c, a, b;
        //判断step和mod是否互质
        while (cin >> step >> mod) {
        
            a = step;
            b = mod;
            if (mod >= 1 && mod <= 1000000000 && step >= 1 && step <= 1000000000){
        
                if (a < b) {
        
                    temp = a;
                    a = b;
                    b = temp;
                }
                c = a % b;
                while (c!= 0) {
        
                    a = b;
                    b = c;
                    c = a % b;
                }
                if (b == 1) cout << setw(10) << step << setw(10) << mod << "    Good Choice" << endl << endl;
                else cout << setw(10) << step << setw(10) << mod << "    Bad Choice" << endl << endl;
        }
            else {
        
                cout << setw(10) << step << setw(10) << mod << "    Bad Choice" << endl << endl;
            }
        }
        return 0;
    }

**方法二：计算出所有的随机数，判断是否包含了0-mod-1之间的数**

#include<iostream>
    #include<iomanip>
    using namespace std;
    int num[100003];
    int main() {
        
        int step, mod, a, b, i;
        while (cin >> step >> mod) {
        
            a = 1, b = 0, num[0] = {
         0 }, i = 0;
            if (step >= 1 && step <= 1000000000 && mod >= 1 && mod <= 1000000000) {
        
                while (a != 0) {
        
                    a = (b + step) % mod;
                    num[i++] = a;
                    b = a;
                }
                if (i == mod) cout << setw(10) << step << setw(10) << mod << "    Good Choice" << endl << endl;
                else cout << setw(10) << step << setw(10) << mod << "    Bad Choice" << endl << endl;
            }
            else {
        
                cout << setw(10) << step << setw(10) << mod << "    Bad Choice" << endl << endl;
            }
        }
        return 0;
    }

[20200320181026275.jpg]: /images/20230528/d537a4209f91497da7b29a6159d7baa0.png