• [N诺] 复旦大学历年上机题解

    1、n阶Hanoi塔问题

    (n阶Hanoi塔问题）假设有三个分别命名为A、B、C的塔座，在塔座A上插有n(n<20)个直径大小各不相同、依小到大编号为1，2，…，n的圆盘。现要求将A轴上的n个圆盘移至塔座C上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则： 1）每次只能移动一个圆盘； 2）圆盘可以插在A、B、C中的任一塔座上； 3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 请通过编程来打印出移动的步骤。

    1. #include
    2. using namespace std;
    3.  
    4. int cnt = 0;
    5.  
    6. void pprint(char A,char B){
    7.     printf("%c-->%c   ", A, B);
    8.     cnt++;
    9.     if(cnt%5==0){
    10.         printf("\n");
    11.     }
    12. }
    13.  
    14. void hanoi(char A,char B,char T,int n){  // 起点A，终点B，中间量T
    15.     if(n==1){
    16.         pprint(A,B);
    17.     }else{
    18.         hanoi(A,T,B,n-1); // 把上面的n-1个圆盘从A移动到T 借助B
    19.         hanoi(A,B,T,1); // 把最大的圆盘从A移动到目标柱B
    20.         hanoi(T,B,A,n-1); // 将剩下的在中间量T（现在视作起始柱）通过起点A（现在视为中间量柱）移动到终点B
    21.     }
    22. }
    23.  
    24.  
    25. int main() {
    26.     int n;
    27.     while(cin>>n && n!=0 ){
    28.         hanoi('A','C','B',n); // 起点A，终点B，中间量T
    29.         printf("\n"); // 新一次游戏也要换行
    30.         cnt = 0; // 计数器置为0
    31.     }
    32. }

    2、求众数

    众数就是一个序列中出现次数最多的数字。 如果不唯一，则输出小的那个值。

    此题需要模拟哈希表。 

    1. #include
    2. using namespace std;
    3.  
    4. int main() {
    5.     int n;
    6.     cin >> n;
    7.     int count[100000] = {0};
    8.     for(int i=0;i
    9.         int num;
    10.         cin >> num;
    11.         count[num]++;
    12.     }
    13.     int ret;
    14.     int max = -1;
    15.     for(int j = 0;j<100000;j++){
    16.         if(count[j]>max){
    17.             max = count[j];
    18.             ret = j;
    19.         }
    20.         else if(count[j]==max && j
    21.             ret = j;
    22.         }
    23.     }
    24.     cout<
    25. }

    区别于用数组模拟哈希表统计字母次数，数字的多可能性带来了浪费空间，为了避免此现象，改用为map count;进行存储。

    1. #include
    2. using namespace std;
    3.  
    4. int main() {
    5.     int n;
    6.     cin >> n;
    7.     int ret; // 众数值
    8.     int max = -1; // 众数次数
    9.     map<int,int> count;
    10.  
    11.     for(int i=0;i
    12.         int num;
    13.         cin >> num;
    14.         count[num]++;
    15.         if(count[num]>max){
    16.             max = count[num];
    17.             ret = num;
    18.         }else if(count[num]==max && num
    19.             ret = num;
    20.         }
    21.     }
    22.     cout<
    23. }

    3.连续最大子序列

    给定一个数字序列A1,A2…An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大和。

    1. #include
    2. using namespace std;
    3.  
    4. int main() {
    5.     int n;
    6.     int num;
    7.     int pos = 0;
    8.     cin >> n;
    9.     int len = n;
    10.     int dp[n];
    11.     while(n--){
    12.         cin>>num;
    13.         dp[pos] = num;
    14.         pos++;
    15.     }
    16.  
    17.     int i;
    18.     for(i=1;i
    19.         dp[i] = max(dp[i-1]+dp[i],dp[i]);
    20.     }
    21.  
    22.     int res = *max_element(dp, dp+len);
    23.     cout << res;
    24. }

    4.字符串编辑距离

    问题描述：给定两个字符串A和B，求字符串A至少经过多少步字符操作变成字符串B。

    我们先以一个例子分析，比如eat变成tea。对于第一个字符，e != a，所以要想让这两个字符相等，有三种可以选择的办法

    • 修改字符，将e直接变成a，需要走1步。
    • 插入字符，在e的前面插入a，也需要走1步。
    • 删除字符，将e删除，然后比较后面的与a，也需要走1步。
    1. #include
    2. using namespace std;
    3. int dp[1001][1001]={0}; //长度为i的s1,转化为长度为j的s2，共需要多少步
    4.  
    5. int main(){
    6.     string s1,s2;
    7.     cin>>s1>>s2;
    8.     int len1 = s1.size();
    9.     int len2 = s2.size();
    10.  
    11.     // i=0时，只能对s1进行插入操作
    12.     for(int j = 1;j<=len2;j++){
    13.         dp[0][j] = dp[0][j-1] + 1;
    14.     }
    15.     // j=0时，只能对s2进行删除操作
    16.     for(int i = 1;i<=len1;i++){
    17.         dp[i][0] = dp[i-1][0] + 1;
    18.     }
    19.     for(int i = 1;i<=len1;i++){
    20.         for(int j = 1;j<=len2;j++){
    21.             if(s1[i-1]==s2[j-1]){
    22.                 dp[i][j] = dp[i-1][j-1];
    23.             }else{
    24.                 dp[i][j] = min(min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;
    25.             }
    26.         }
    27.     }
    28.     cout<
    29. }

    5.a与b得到c

    给出a,b,c（3个整数），判断a,b能否通过+-*/得到c，ab可以交换位置，可以输出YES，不可以则输出NO.

    1. #include
    2. using namespace std;
    3.  
    4. bool cal(int a,int b,int c){
    5.     bool ret = false;
    6.     if(a+b==c || a-b==c || a*b == c){
    7.         ret = true;
    8.     }
    9.     else if(b!=0 && a*1.0/b == c){  // 避免8/3==2
    10.         ret = true;
    11.     }
    12.     return ret;
    13. }
    14.  
    15. int main(){
    16.     int a,b,c;
    17.     cin >> a >> b >> c;
    18.     if(cal(a,b,c)||cal(b,a,c)){
    19.         cout << "YES";
    20.     }else{
    21.         cout << "NO";
    22.     }
    23. }

    6.集合交并

    输入两个集合，分别求其交集和并集中元素的个数，每个集合中可能存在相同的元素，而最终的交集和并集中应该不存在。

    1. #include
    2. using namespace std;
    3.  
    4. int main(){
    5.     int n,m;
    6.     cin>>m>>n;
    7.     int num;
    8.     map<int,int> a;
    9.     map<int,int> b;
    10.  
    11.     int jiao = 0;
    12.     int bing = 0;
    13.  
    14.     for(int i =0;i
    15.         cin >> num;
    16.         a[num]=1;
    17.     }
    18.  
    19.     bing = a.size();
    20.     for(int i =0;i
    21.         cin >> num;
    22.         if(b[num]!=1){
    23.             b[num]=1;
    24.             if(a[num]==1){
    25.                 jiao++;
    26.             }else{
    27.                 bing++;
    28.             }
    29.         }
    30.     }
    31.     cout<" "<
    32. }

    map在对某个key未指定value时，默认value为0.

    找交集的简单方法：

    1. 	int count = 0;
    2. 	for (auto iter = A.begin(); iter != A.end(); iter++) {
    3. 		if (B.find(*iter)!=B.end()) {
    4. 			count++;
    5. 		}
    6. 	}
    7.     // auto的原理就是根据后面的值，来自己推测前面的类型是什么；

    7.骨牌

    有2*n 的地板，用1*2和 2*1 的骨牌进行铺地板。问共有多少种情况。结果对 999983 取余，1<=n<=10000

    斐波那契数列的变体

    1. #include
    2. using namespace std;
    3. int dominoes(int n){
    4.     int ret;
    5.     if(n==1){
    6.         ret = 1;
    7.     }else if(n==2){
    8.         ret = 2;
    9.     }else{
    10.         ret = (dominoes(n-1)+dominoes(n-2))%999983;
    11.     }
    12.     return ret;
    13. }
    14.  
    15. int main(){
    16.     int n;
    17.     cin >> n;
    18.     cout << dominoes(n);
    19. }

    递归的解法超时

    1. #include
    2. using namespace std;
    3.  
    4. int main(){
    5.     int n;
    6.     cin >> n;
    7. 	int dp[n+1];
    8. 	dp[1] = 1;
    9. 	dp[2] = 2;
    10. 	for(int i = 3;i<=n;i++){
    11. 		dp[i] = (dp[i-1]+dp[i-2])%999983;
    12. 	}
    13.     cout << dp[n];
    14. }

    8.长方形中的正方形

    给出长方形的长和宽，每次从长方形里撕去最大的正方形，输出最后能得到多少正方形

    1. #include
    2. using namespace std;
    3.  
    4. int main(){
    5.     int n,m;
    6.     cin >> n >> m;
    7.     // 终止条件：剩余部分就是一个正方形
    8.     int ret = 0;
    9.     while(n!=m){
    10.         if(n
    11.             swap(n,m);
    12.         }
    13.         n = n - m;
    14.         ret++;
    15.     }
    16.     cout << ret+1;
    17. }

    C++ 自带了swap函数

    9.约数求和

    输入一个数n，输出前n个数的约数的和。

    1. #include
    2. using namespace std;
    3.  
    4. int Divisor_sum(int x){
    5.     int sum = 0;
    6.     for(int i = 1;i<=x;i++){
    7.         if(x%i==0)
    8.             sum = sum + i;
    9.     }
    10.     return sum;
    11. }
    12.  
    13. int main(){
    14.     int x;
    15.     cin >> x;
    16.     int sum = 0;
    17.     for(int i = 1;i<=x;i++){
    18.         sum = sum + Divisor_sum(i);
    19.     }
    20.     cout << sum;
    21. }

    上述写法超时，故进行优化

    11
    21 2
    31 3
    41 4 2
    51 5
    61 2 3 6
    71 7

     当输入为x时，1到x所有因数合计共有i的个数是(x/i);（如有1的个数是7,2的个数是3）

    1. #include
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.     int x;
    7.     cin>>x;
    8.     long long sum=0;
    9.     for(int i=1;i<=x;i++)
    10.     {
    11.         sum+=i*(x/i);
    12.     }
    13.     cout<
    14.     return 0;
    15. }

    10.解一元一次方程

    解方程，给定一个字符串，代表一个一元一次方程。如果有解求解，输出格式“x=数字“，如果解的个数无穷，输出 “infinite solutions”。如果没有解输出“no solution”，字符串长度不超过 256 。

    参考答案：

    Code (noobdream.com)

    1. #include
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.     string str;
    7.     cin >> str;
    8.     int a = 0, b = 0;   //系数、常数
    9.     int sym = 1, flag = 1; //sym表示数字之前的符号，flag表示等号的左右（初始值为1，表示在左面）
    10.     int i = 0;   //访问字符串的下标
    11.     while(i < str.size()) {
    12.         if (str[i] == '=') {
    13.             sym = 1;
    14.             flag = -1;
    15.         }
    16.         else if(str[i] == '+'){
    17.             sym = 1;
    18.         }
    19.         else if(str[i] == '-'){
    20.             sym = -1;
    21.         }
    22.         else{
    23.             int t = 0;      //暂存遇到的数字值
    24.             while(i < str.size() && str[i] >= '0' && str[i] <= '9'){    //遇到数字，计算数值
    25.                 t = 10 * t + (str[i] - '0');
    26.                 ++i;
    27.             }
    28.             if(i >= str.size()){ // 最后一位是数字
    29.                 b = b - t * sym;
    30.                 break;
    31.             }
    32.             if(str[i] == 'x' && t == 0){    //如果x之前的系数为正负1时，要单独判断，因为此时t=0
    33.                 a = a + sym * flag;
    34.             }
    35.             else if(str[i] == 'x'){     //处理系数
    36.                 a = a + t * sym * flag;
    37.             }
    38.             else{                       //处理常数
    39.                 b += t * sym * flag;
    40.                 continue;
    41.             }
    42.         }
    43.         i++;
    44.     }
    45.     if(a == 0 && b == 0){
    46.         printf("infinite solutions\n");
    47.     }
    48.     else if(a != 0 && b % a == 0){
    49.         printf("x=%d\n", -b/a);
    50.     }
    51.     else{
    52.         printf("no solution\n");
    53.     }
    54. }

     11.相隔天数

    输入日期格式：YYYYMMDD，求与20190205相隔天数。

    1. #include
    2. using namespace std;
    3. int dt[2][12] = {{31,28,31,30,31,30,31,31,30,31,30,31},
    4.                  {31,29,31,30,31,30,31,31,30,31,30,31}};
    5.  
    6. int isleapyear(int year){
    7.     if((year%4==0 && year%100!=0)||year%400 == 0){
    8.         return 1;
    9.     }else{
    10.         return 0;
    11.     }
    12. }
    13.  
    14. int main()
    15. {
    16.    string date;
    17.    cin >> date;
    18.    string year = date.substr(0,4);
    19.    string month = date.substr(4,2);
    20.    string day = date.substr(6,2);
    21.  
    22.    // 20190205
    23.    long long day1 = 0,day2 = 0;
    24.    for(int i=1;i<2019;i++){
    25.        if(isleapyear(i)){
    26.            day1 = day1 + 366;
    27.        }else{
    28.            day1 = day1 + 365;
    29.        }
    30.    }
    31.    day1 = day1 + 31 + 5;
    32.  
    33.    for(int i=1;i<stoi(year);i++){
    34.        if(isleapyear(i)){
    35.            day2 = day2 + 366;
    36.        }else{
    37.            day2 = day2 + 365;
    38.        }
    39.    }
    40.     if(isleapyear(stoi(year))){
    41.         day2 = day2 + stoi(day);
    42.         for(int i = 0;i<(stoi(month))-1;i++){
    43.             day2 = day2 + dt[1][i];
    44.         }
    45.     }else{
    46.         day2 = day2 + stoi(day);
    47.         for(int i = 0;i<(stoi(month))-1;i++){
    48.             day2 = day2 + dt[0][i];
    49.         }
    50.     }
    51.  
    52.     cout << abs(day2 - day1);
    53. }

    注意字符串转整形函数stoi，在此篇博文有详细的总结；

    C/C++字符(char/string)与整型(int)的相互转换——PAT常用知识点（三）__Pooooooocky的博客-CSDN博客_c字符转换https://blog.csdn.net/BBBling/article/details/115540073

    12.求交点

    求线段交点，输入两组线段端点，求其交点，若无交点或无穷个交点输出一句"Parallel or coincident"，输出交点保留两位小数。

    1. #include 
    2. using namespace std;
    3.  
    4. int main(){
    5.     double x1,x2,x3,x4;
    6.     double y1,y2,y3,y4;
    7.     cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
    8.     double k1=(y2-y1)/(x2-x1),k2=(y4-y3)/(x4-x3);
    9.     if(k1==k2) cout<<"Parallel or coincident"<
    10.     else{
    11.         double b1=y1-k1*x1,b2=y3-k2*x3;
    12.         double x=(b2-b1)/(k1-k2);
    13.         double y=k1*x+b1;
    14.         printf("%.2f %.2f",x,y);
    15.     }
    16.     return 0;
    17. }

    13.期望值

    给定一个非负整数序列x 1 , x 2 , ⋯   , x n，可以给每一个整数取负数或者取原值，求有多少种取法使得这些整数的和等于期望值E。请写出程序，并解释解题思路。

    01背包问题的变体

    解题思路详见如下链接：

    一道算法题，求用背包问题解决_博问_博客园 (cnblogs.com)

    1、如果将等式左边的负值移到右边，等式两边仍然相等。等式左边的值加上等式右边的值等于非负序列的和加上期望的值。那么就可以有一个结论，如果非负序列的和+期望不是偶数的话，就一定没有符合题意的取法。（如果为奇数，那么我们无法将其平均分配为两个整数部分）显然，如果期望值大于非负序列的和，也没有符合题意得取法。

    2、（非负序列的和+期望）/ 2 = 左值 = 右值  等于每个取法中 取原值的和。

    3、如果令（非负序列的和+期望）/ 2 = k,那么就可以转化为：将体积为k的01背包装满，有几种装法。其中如果不选择某个物品，实际上相当于某个整数取了负值。

    4、那么只需要将01背包问题的状态转移方程中的max ，变为sum即可。即dp[i][j] = d[i-1][j] +dp[i-1][j-num[i]] ,其中 dp[i-1][j]表示不装，也就是选择了负值，dp[i-1][j-num[i]] 表示装，也就是选择了原值。
    5、在经过滚动数组优化，状态转移方程就变成了dp[j]=dp[j]+dp[j-num[i]].

    1. #include
    2. using namespace std;
    3.  
    4. const int mod = 1e9 + 7;
    5.  
    6. int main()
    7. {
    8.     int n,E;
    9.     cin >> n;
    10.  
    11.     long long int a[n+1];
    12.  
    13.     for (int i = 1; i <= n; i++) {
    14.         cin >> a[i];
    15.     }
    16.     cin >> E;
    17.  
    18.     int sum = 0;
    19.     for (int i = 1; i <= n; i++) {
    20.         sum = sum + a[i];
    21.     }
    22.     int cap = (E + sum) / 2; // 原值和 01背包问题中的背包总容量
    23.  
    24.     if ((E + sum) % 2 != 0) { // 无解
    25.         cout << 0;
    26.     }else{
    27.         long long int dp[cap+1];
    28.         memset(dp,0,sizeof dp);
    29.         dp[0] = 1;
    30.         for (int i = 1; i <= n; i++) {
    31.             for (int j = cap; j >= a[i]; j--) {
    32.                 dp[j] = dp[j] + dp[j - a[i]];
    33.                 dp[j] = dp[j] % mod;//取模
    34.             }
    35.         }
    36.         cout << dp[cap] << endl;
    37.     }
    38. }
    39.

    long long int的取值范围非常大。

    14.斗牛

    给定五个 0~9 范围内的整数 a1, a2, a3, a4, a5。如果能从五个整数中选出三个并且这三个整数的和为10 的倍数（包括 0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对 10 取余的结果，显然如果有多个三元组满足和是 10 的倍数，剩下两个数之和对 10 取余的结果都是相同的；如果选不出这样三个整数，则这五个整数的权值为 -1。
    现在给定 T 组数据，每组数据包含五个 0~9 范围内的整数，分别求这 T 组数据中五个整数的权值。

    1. #include
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.     int n;
    7.     cin >> n;
    8.     vector<int> answer;
    9.     while(n--){
    10.         int sum = 0;
    11.         vector<int> a;
    12.         int num;
    13.         int flag = 0;
    14.         for(int i = 0;i<5;i++){
    15.             cin >> num;
    16.             a.push_back(num);
    17.         }
    18.         for(int i = 0;i<5;i++){
    19.             for(int j = 0;j<5;j++){
    20.                 for(int k = 0;k<5;k++){
    21.                     if(i!=j && j!=k && i!=k && (a[i]+a[j]+a[k])%10==0){
    22.                         flag = 1;
    23.                         for(int p = 0;p<5;p++){
    24.                             if(p==i || p==j || p==k){
    25.                                 continue;
    26.                             }
    27.                             sum = sum + a[p];
    28.                         }
    29.                         goto label;
    30.                     }
    31.                 }
    32.             }
    33.         }
    34.         label:
    35.         if(flag==0)
    36.             sum = -1;
    37.         answer.push_back(sum%10);
    38.     }
    39.     for(int i = 0;isize();i++){
    40.         cout<
    41.     }
    42. }
    43.

    由于要跳出多重循环，我在这里使用的是goto语句，好的解答方式是将其写成一个函数，然后用return跳出。

    15.跳台阶

    训练场上有一个台阶，总共有 n 级。一个运动员可以跳 1 级，也可以跳 2 级。求运动员有多少种跳法。请写出程序，并解释解题思路。

    1. #include
    2. using namespace std;
    3.  
    4. int main(){
    5.     int n;
    6.     cin >> n;
    7.     int dp[n+1];
    8.     memset(dp,0,sizeof dp);
    9.     dp[0] = 0;
    10.     dp[1] = 1;
    11.     dp[2] = 2;
    12.     for(int i = 3;i<=n;i++){
    13.         dp[i] = dp[i-1] + dp[i-2];
    14.     }
    15.     cout << dp[n];
    16. }

    16.打地鼠

    给定 n 个整数 a1, a2, …, an 和⼀个 d，你需要选出若⼲个整数，使得将这些整数从小到大排好序之后，任意两个相邻的数之差都不⼩于给定的 d，问最多能选多少个数出来。

    1. #include
    2. using namespace std;
    3.  
    4. int main(){
    5.     int n, d;
    6.     cin >> n >> d;
    7.     int data[n];
    8.     for (int i = 0; i < n; i++){
    9.         cin >> data[i];
    10.     }
    11.     sort(data,data+n); // 如果定义了一个vector 则为sort(data.begin(),data.end())
    12.     int num = 0;
    13.     if (n < 2) {	//只有一个整数
    14.         cout << num << endl;
    15.         return 0;
    16.     }
    17.     for (int i = 0, j = 1; j < n;j++) {
    18.         if (data[j] - data[i] >= d) {
    19.             num++;
    20.             i = j;
    21.         }
    22.     }
    23.     if (num == 0)	cout << num << endl;	//没有符合条件的数
    24.     else  cout << num + 1 << endl;	//由于每次只将较小的数加入结果集，因此最后还需将最后的大数加入结果集
    25.     return 0;
    26. }

    17.二叉树个数

    求N个结点能够组成的二叉树的个数。 1<=n<=20

    1. #include
    2. using namespace std;
    3.  
    4. long long f(int n)
    5. {
    6. 	if(n==0) return 1;
    7. 	else
    8. 		return f(n-1)*(4*n-2)/(n+1);
    9. }
    10. int main()
    11. {
    12. 	int m;
    13. 	cin>>m;
    14. 	cout<<f(m)<
    15. }

    卡特兰数：

    Catalan数—求解n个节点能组成的二叉树个数问题_猫小时候的博客-CSDN博客https://blog.csdn.net/onever_say_love/article/details/4942063118.给定一颗二叉树，树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点，那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序，并解释解题思路。

    输入：3,1,4,3,null,1,5

    输出：4

  • 相关阅读:
    深度学习神经网络实战：多层感知机，手写数字识别
    为数字化深水区“量身定制”，华为品质服务再迭代
    西部数码云快照立大功-助力众多用户解决勒索病毒危机！
    如何准确且可解释地评估大模型量化效果？
    网站交换友情链接是否对SEO优化有帮助?
    GBase8s数据库SET CONSTRAINTS 语句
    Flutter 教程之 Flutter CI/CD 和自托管的 GitHub Action
    如何处理使用MindSpore Lite的converter_lite工具转换模型失败的问题
    java计算机毕业设计高校实习管理平台系统MyBatis+系统+LW文档+源码+调试部署
    任务调度线程池-应用定时任务
  • 原文地址：https://blog.csdn.net/tangchujiang/article/details/126659542