ACM程序设计课内实验（1）数学问题

女爷i 2024-04-17 13:40 81阅读 0赞

## 1.The Hardest Problem Ever ##

> Description  
> Julius Caesar生活在一个危险而又充斥着阴谋的时代。Caesar面对的最难的情况关系着他的存亡。为了让自己生存，他决心去创造第一种加密方法之一。这个加密方法听起来是这样的令人难以置信，没有一个人可以指出它（的原文）除非知道它怎样工作。  
> 你是Caesar军队的一个分队长。你的工作是破译Caesar送来的信息并汇报给你的上级。  
> 密码很简单，每一个字母对应着一个明文，你将明文向右五步来得到安全的信息。（比如，假如那个字母是‘A’，密文就是‘F’）当你将Caesar的信息中找出明文后，你要反过来做：  
> 加密文本  
> A B C D E F G H I J K L M N O P Q R S T U V W X Y Z  
> 明文文本  
> V W X Y Z A B C D E F G H I J K L M N O P Q R S T U  
> 密文中只有字母被切换了，非字母的字符应该保持不变，所有的字母都是大写的。
> 
>   
> Input  
> 这个问题的输入包括一系列（非空）最多100个数据。每一个数据的格式会按照以下格式，并且在不同组数据间不会有空行分隔。所有的字符都是大写的。  
> 一个单独的测试数据包括三个部分：  
> 1. 开始行：单独的一行“START” 。  
> 2. 加密的信息：单独的一行，由1~200个字符组成来自Caesar的一行信息。  
> 3. 结束行：单独的一行“END” 。  
> 最后一组测试数据结束会跟着单独的一行“ENDOFINPUT”。
> 
>   
> Output  
> 对每一个测试数据只会有一行输出。它是Caesar的原文。
> 
>   
> Sample Input
> 
>   
> START  
> NS BFW, JAJSYX TK NRUTYFSHJ FWJ YMJ WJXZQT TK YWNANFQ HFZXJX  
> END  
> START  
> N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ  
> END  
> START  
> IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ  
> END  
> ENDOFINPUT
> 
>   
> Sample Output
> 
>   
> IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES  
> I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME  
> DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

#include <iostream>
    #include <string>
    #include <cctype>
    using namespace std;
    
    int main() {
        string input;
        string plaintext;
    
        while (getline(cin, input) && input != "ENDOFINPUT" ) {
    
            if (input != "START" && input != "END") {
    
                plaintext = "";
    
                for (char c : input) {
    
                    if (isalpha(c)) {
                        // 将字符转换为大写字母，然后减去'A'，加上21，再对26取模，最后加上'A'，得到解密后的字符
                        plaintext += (c - 'A' + 21) % 26 + 'A';
                    } else {
                        // 如果字符不是字母，则直接添加到明文中
                        plaintext += c;
    
                    }
                }
                 cout<<plaintext<<endl;
    
            }
    
    
        }
        return 0;
    }

> `getline`函数是C++标准库中的一个函数，用于从输入流（如文件、字符串等）中读取一行文本。它的原型如下：
> 
>     istream& getline(istream& is, string& str);
> 
> 参数说明：
> 
>  *  `is`：输入流对象，通常为`cin`或文件流对象。
>  *  `str`：一个字符串对象，用于存储从输入流中读取的一行文本。
> 
> 返回值：
> 
>  *  返回引用到输入流对象的引用，以便进行链式操作。

## 2.数的长度 ##

> Description  
> N! (N的阶乘) 是非常大的数，计算公式为：N! = N \* (N - 1) \* (N - 2) \* ... \* 2 \* 1)。现在需要知道N!有多少（十进制）位。  
> Input  
> 每行输入1个正整数N。0 < N < 1000000  
> Output  
> 对于每个N，输出N!的（十进制）位数。  
> Sample Input  
> 1  
> 3  
> 32000  
> 1000000  
> Sample Output  
> 1  
> 1  
> 130271  
> 5565709

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        long long int n;
        while(cin>>n)
        {
            double res=0;
            for(long long int i=1; i<=n; i++)
                res=res+log10(i);//推出数学公式
            printf("%ld\n",(long long int)res+1);
        }
        return 0;
    }

## 3.最左的数 ##

> 描述  
> 给定一个正整数N，您应该输出N^N的最左边数字。  
> 输入  
> 输入包含几个测试用例。输入的第一行是一个整数T，它是测试用例的数量。接下来是T个测试案例。  
> 每个测试用例都包含一个正整数N（1<=N<=1000000000）。  
> 输出  
> 对于每个测试用例，您应该输出N^N的最左边数字。  
> 样本输入  
> 2.  
> 3.  
> 4.  
> 样本输出  
> 2.  
> 2.  
> 暗示  
> 在第一种情况下，3\*3\*3=27，因此最左边的数字是2。  
> 在第二种情况下，4\*4\*4=256，因此最左边的数字是2。

#include<stdio.h>
    #include<math.h>
    int main()
    {
        int t;scanf("%d",&t);
        while(t--){
    	    int n,ans;
    	    double b;
    	    scanf("%d",&n);
    	    b=n*log10(1.0*n);       //求A.B
    	    b=b-(int)b;             //求0.B
    	    ans=(int)pow(10.0,b);   //求10^0.B的整数部分
    	    printf("%d\n",ans);
    	
        }
        return 0;
    }

> 此题同样需要推数学公式，直接暴力时间太长且数据太大无法存放，推理过程如下：
> 
> 1、![$n^n = d \\times 10^\{(k-1)\}$][n_n _ d _times 10_k-1],其中![$k$][k]表示![$n^n$][n_n]的位数。
> 
> 2、等式两边取以10为底的对数得![$d.xxx = 10(\\log \_\{10\}n^n - k+1)$][d.xxx _ 10_log _10_n_n - k_1]。
> 
> 3、带入![$k$][k]得计算公式的整数部分加1,即![$k = \[\\log \_\{10\}n^n\]+1$][k _ _log _10_n_n_1]。
> 
> 4、得到![$d$][d]得表达式 ![$d = (int)(log10^\{(n^n)\}-(int)(logn^n))$][d _ _int_log10_n_n_-_int_logn_n],其中$k$表示$n^n$的位数。

## 4.最右数字 ##

> 描述  
> 给定一个正整数N，您应该输出N^N的最右数字  
> 输入  
> 输入包含几个测试用例。输入的第一行是一个整数T，它是测试用例的数量。接下来是T个测试案例。每个测试用例都包含一个正整数N（1<=N<=1000000000）。  
> 输出  
> 对于每个测试用例，您应该输出N^N的最右边数字。  
> 样本输入  
> 2.  
> 3.  
> 4.  
> 样本输出  
> 7.  
> 6.  
> 暗示  
> 在第一种情况下，3\*3\*3=27，因此最右边的数字是7。在第二种情况下，4\*4\*4=256，因此最右边的数字是6。

普通解法，由于数太大超时

#include <iostream>
    using namespace std;
    
    int main() {
        int T;
        cin >> T;
        while (T--) {
            int N;
            cin >> N;
            long long result = 1;
            for (int i = 0; i < N; i++) {
                result = (result * N%10) % 10;
            }
            cout << result << endl;
        }
        return 0;
    }

公式

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;
        scanf("%d",&n);
        int a[10][4]= {
       {0},{1},{6,2,4,8},{1,3,9,7},{6,4},{5},{6},{1,7,9,3},{6,8,4,2},{1,9}};
        //由末尾数字与自身相乘可到到相乘的规律
        while(n--)
        {
            long long int m;
            scanf("%ld",&m);
            int d=m%10;
            if(d==0||d==1||d==5||d==6)
                printf("%d\n",d);
            else if(d==4||d==9)
                printf("%d\n",a[d][m%2]);
            else if(d==2||d==3||d==7||d==8)
                printf("%d\n",a[d][m%4]);
        }
        return 0;
    }
    //另一种更加直接的方法是使用快速幂

快速幂

#include <iostream>
    using namespace std;
    
    int lastDigitOfPower(int base, int power) {
        int result = 1;
        while (power > 0) {
            if (power % 2 == 1) {
                result = (result * base) % 10;
            }
            base = (base * base) % 10;
            power /= 2;
        }
        return result;
    }
    
    int main() {
        int T;
        cin >> T;
        while (T--) {
            int N;
            cin >> N;
            int lastDigit = lastDigitOfPower(N, N);
            cout << lastDigit << endl;
        }
        return 0;
    }

## 5.求幂的长度 ##

> Description
> 
>     请你计算数a的b次幂共有多少位(十进制的数)!
> 
> Input
> 
>     输入数据有多组,每组二个正整数分别为a和b,其中(1<=a<=10000,1<=b<=10000)
> 
> Output
> 
>     输出a^b(a的b次幂)的值共有多少位?
> 
> Sample Input
> 
>     2 3
>     1 1
>     10 5
> 
> Sample Output
> 
>     1
>     1
>     6
> 
> Hint
> 
>     对数函数log10(x),头文件math.h

#include<bits/stdc++.h> // 包含所有标准库
    using namespace std;
    
    int main()
    {
        int a, b; // 定义整数a和b
        while(cin >> a >> b) // 当输入a和b时
        {
            double ans = 0; // 定义浮点类型变量ans，并初始化为0
            ans = int(b * log10(a)) + 1; // 计算a的b次幂的位数，取整后加1
            cout << ans << endl; // 输出结果
        }
        return 0;
    }

[n_n _ d _times 10_k-1]: https://latex.csdn.net/eq?%24n%5En%20%3D%20d%20%5Ctimes%2010%5E%7B%28k-1%29%7D%24
[k]: https://latex.csdn.net/eq?%24k%24
[n_n]: https://latex.csdn.net/eq?%24n%5En%24
[d.xxx _ 10_log _10_n_n - k_1]: https://latex.csdn.net/eq?%24d.xxx%20%3D%2010%28%5Clog%20_%7B10%7Dn%5En%20-%20k&plus;1%29%24
[k _ _log _10_n_n_1]: https://latex.csdn.net/eq?%24k%20%3D%20%5B%5Clog%20_%7B10%7Dn%5En%5D&plus;1%24
[d]: https://latex.csdn.net/eq?%24d%24
[d _ _int_log10_n_n_-_int_logn_n]: https://latex.csdn.net/eq?%24d%20%3D%20%28int%29%28log10%5E%7B%28n%5En%29%7D-%28int%29%28logn%5En%29%29%24