• 专业课-代码题记录

    目录

    讲义P25-将一个正整数分解质因数

    讲义P30-辗转相除法 

    讲义P32-给出年月日，计算该日是该年的第几天

    讲义P56-进制转换讲解

    讲义P59-打印集合M的前面100个最小数 

    讲义P61-输入正整数n，打印集合的所有子集 

    讲义P67-求所有元素个数为M的子集 

    讲义P68-实现任意两个不同进制非负整数之间的转换

    实现输入多组数据

    本题代码

    讲义P80-交换两个向量的位置 

    讲义P88-两个机器人的对话

    讲义P91-对n个字符串按字典序排序

    字符数组的相关操作

    本题代码

    讲义P92-将0元素移动到数组后面，非0元素保持有序

    讲义P93-删除数组中值在x到y之间的所有元素

    讲义P95-删除数组中值相同的元素

    讲义P25-将一个正整数分解质因数

    示例：

    1. int main()
    2. {
    3.     int i, n;
    4.     cout << "请输入一个数：";
    5.     cin >> n;
    6.     cout << n << " = ";
    7.     //为什么需要i++？比i小的数难道不能是新的n的质因子吗？
    8.     //答案是不会，因为如果比i小的数如果是n的质因子，那早就已经被分解掉了
    9.     //实际上在这个算法中，被分解的质因子是从小到大递增的
    10.     for (i = 2; i < n; i++)
    11.     {
    12.         while (n != i)  //若n == i，则n的质因数就是n本身
    13.         {
    14.             //这里不需要判断i是否为质数，因为根据这个算法的特性，在遇到i之前，n中关于i的因数都已经被分解掉了，
    15.             //在遇到6之前必定已经将这个6分解为了2*33，在遇到9之前必定已经将9分解为了3*3
    16.             //因此这里的i一定是个质数
    17.             if (n % i == 0) //若i是质因数，则打印i
    18.             {
    19.                 cout << i << " * ";
    20.                 n = n / i;
    21.             }
    22.             else break;     //若不能被i整除，则考虑i + 1
    23.         }
    24.     }
    25.     cout << n;  //打印最后一个质因数，也就是当n == i时的质因数
    26.     return 0;
    27. }

     打印如下：

    讲义P30-辗转相除法 

    非递归写法：

    1. int gcd(int a, int b)
    2. {
    3.     int r;
    4.     while (b != 0)
    5.     {
    6.         r = a % b;
    7.         a = b;
    8.         b = r;
    9.     }
    10.     return a;
    11. }

    更为简便的递归写法：

    1. int gcd(int a, int b)
    2. {
    3.     return b == 0 ? a : gcd(b, a % b);
    4. }

    讲义P32-给出年月日，计算该日是该年的第几天

    按讲义上的写法来的，主要是在于数据的健壮性判断十分繁琐

    1.  
    2. /*
    3. 非整百年：能被4整除的为闰年。
    4. 整百年：能被400整除的是闰年。
    5. */
    6. int is_leapyear(int year)
    7. {
    8.     if (year % 400 == 0 || year % 4 == 0 && year % 100 != 0)
    9.     {
    10.         return 1;
    11.     }
    12.     return 0;
    13. }
    14.  
    15. //判断该日是今年的第几天
    16. int whichday(int year, int month, int day)
    17. {
    18.     int mon[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    19.     mon[2] = is_leapyear(year); //如果是闰年，二月份就加1天
    20.     int count = 0;
    21.     for (int i = 1; i < month; i++)
    22.     {
    23.         count += mon[i];
    24.     }
    25.     count += day;
    26.     return count;
    27. }
    28.  
    29. int main()
    30. {
    31.     int year, month, day;
    32.     cout << "请输入年份" << endl;
    33.     while (1)
    34.     {
    35.         cin >> year;
    36.         if (year < 0)
    37.         {
    38.             cout << "月份必须非负，请重新输入" << endl;
    39.             continue;
    40.         }
    41.         break;
    42.     }
    43.  
    44.     cout << "请输入月份" << endl;
    45.     while (1)
    46.     {
    47.         cin >> month;
    48.         if (month < 1 || month > 12)
    49.         {
    50.             cout << "月份必须在1到12之间" << endl;
    51.             continue;
    52.         }
    53.         break;
    54.     }
    55.  
    56.     cout << "请输入天数" << endl;
    57.     while (1)
    58.     {
    59.         cin >> day;
    60.         if (day < 1)
    61.         {
    62.             cout << "天数不能小于1" << endl;
    63.             continue;
    64.         }
    65.         if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)
    66.         {
    67.             if (day > 31)
    68.             {
    69.                 cout << "您输入的天数大于" << month << "月的最大天数" << endl;
    70.                 continue;
    71.             }
    72.         }
    73.         else if (month == 2)
    74.         {
    75.             if (is_leapyear(year) == 1 && day > 29) //如果是闰年的话
    76.             {
    77.                 cout << "您输入的天数大于" << month << "月的最大天数" << endl;
    78.                 continue;
    79.             }
    80.             else if (is_leapyear(year) == 0 && day > 28)    //如果不是闰年的话
    81.             {
    82.                 cout << "您输入的天数大于" << month << "月的最大天数" << endl;
    83.                 continue;
    84.             }
    85.         }
    86.         else
    87.         {
    88.             if (day > 30)
    89.             {
    90.                 cout << "您输入的天数大于" << month << "月的最大天数" << endl;
    91.                 continue;
    92.             }
    93.         }
    94.         break;
    95.     }
    96.     printf("%d年%d月%d日是该年的第%d天", year, month, day, whichday(year, month, day));
    97.     return 0;
    98. }

    讲义P56-进制转换讲解

    讲义P59-打印集合M的前面100个最小数 

    讲义上的代码写得不好，于是在网上搜到了这一种很有意思的写法，该写法采用了归并排序的思想：

            该题的难点在于很难确定最小的n个数到底是哪n个数，现在我们假设可以将int型的y和z看成两个"数组"，y记录的是 2 * a[0] + 1、 2 * a[1] + 1、 2 * a[2] + 1....，z记录的是 3 * a[0] + 1、 3 * a[1] + 1、 3 * a[2] + 1....，只要a是个递增数组，y和z也都是递增"数组"，之后就可以利用归并排序的思想，每次对比y和z的大小，选取较小值入a数组，然后更新y或z的值。

    1. int main()
    2. {
    3.     int a[100];
    4.     a[0] = 1;
    5.     int i = 0, j = 0;   //i为y"数组"的指针，j为z"数组"的指针
    6.     int y = 3, z = 4;   //y"数组"的首元素为2 * a[0] + 1 = 3，z"数组"的首元素为3 * a[0] + 1 = 4
    7.  
    8.     //类似归并排序
    9.     for (int k = 0; k < 100; k++)
    10.     {
    11.         if (y < z)
    12.         {
    13.             a[k] = y;
    14.             y = 2 * a[i] + 1;   //y"数组"移动到下一个元素
    15.             i++;
    16.         }
    17.         else if (y == z)        //由于集合的互异性，所以当出现两边的值相等时只取一个，两边的"数组"都移动
    18.         {
    19.             a[k] = y;
    20.             y = 2 * a[i] + 1;
    21.             i++;
    22.             z = 3 * a[j] + 1;
    23.             j++;
    24.         }
    25.         else
    26.         {
    27.             a[k] = z;
    28.             z = 3 * a[j] + 1;   //z"数组"移动到下一个元素
    29.             j++;
    30.         }
    31.     }
    32.     
    33.     for (int i = 0; i < 100; i++)
    34.     {
    35.         if (i % 10 == 0) cout << endl;
    36.         printf("%4d ", a[i]); 
    37.     }
    38.     return 0;
    39. }

    打印结果如下：

    讲义P61-输入正整数n，打印集合的所有子集 

    居然用到了位运算，是我掌握较为薄弱的一个方法。

    对于数字0 ~ n-1而言，在一个子集每个数字有两种状态：存在和不存在，于是所有状态的组合就是所有的子集了，并且可知输入的正整数为n，子集的个数共有2 ^ n个。

    根据上述，我们可以采用二进制数来代表所有的子集，1表示存在，0表示不存在。

    例如输入3，则子集的总数为2^3 = 8个，集合为{0, 1, 2}。而二进制数也有8个，例如 001对应子集{2}，010对应子集{1}，011对应子集{1, 2}。

    1. void powerset(int n)
    2. {
    3.     int m = pow(2, n);  //共有2^n种子集，对应2^n个二进制数
    4.     int* subset = new int[n];   //记录子集
    5.     int len;    //记录每次生成的子集的长度
    6.     for (int i = 0; i < m; i++)     //大循环，遍历2^个二进制数，确定2^n种子集
    7.     {
    8.         len = 0;
    9.         for (int j = 0; j < n; j++) //遍历数字0 ~ n-1，检查每个数字是否存在于当前子集中
    10.         {
    11.             int tmp = 1 << j;       //将1左移j位，用tmp来检查第j个数字是否存在于当前子集中
    12.             if (i & tmp)
    13.             {
    14.                 subset[len++] = j;  //若存在则记录
    15.             }
    16.         }
    17.         cout << "{";
    18.         for (int j = 0; j < len; j++)
    19.         {
    20.             cout << subset[j];
    21.             if (j < len - 1) cout << ", ";
    22.         }
    23.         cout << "}" << endl;
    24.     }
    25. }
    26.  
    27. int main()
    28. {
    29.     int n;
    30.     cin >> n;
    31.     powerset(n);
    32.     return 0;
    33. }

    输出如下：

    讲义P67-求所有元素个数为M的子集 

    这道题用讲义上的位运算写法有点麻烦，可以直接用dfs来写。这里我直接让原集合中的元素都是1 ~ N - 1了。

    1. int subset[100];
    2. //N是集合中的元素个数，M表示要求元素个数为M的子集
    3. //cur数组用于保存当前子集中的元素，len为cur数组中当前的元素个数
    4. //index表示当前循环需要从下标为index的元素开始遍历
    5. //每调用一次dfs函数，会确定当前子集中len位置的元素
    6. void dfs(int cur[], int len, int M, int index, int N)
    7. {
    8.     //如果当前子集中的元素个数为M，打印
    9.     if (len == M)
    10.     {
    11.         cout << "{";
    12.         for (int i = 0; i < M; i++)
    13.         {
    14.             cout << cur[i];
    15.             if (i < len - 1) cout << ", ";
    16.         }
    17.         cout << "}" << endl;
    18.         return;
    19.     }
    20.     for (int i = index; i < N; i++)
    21.     {
    22.         cur[len] = subset[i];
    23.         dfs(cur, len + 1, M, i + 1, N);
    24.     }
    25. }
    26.  
    27. int main()
    28. {
    29.     int N, M;    
    30.     cin >> N >> M;
    31.     for (int i = 0; i < N; i++)
    32.     {
    33.         subset[i] = i + 1;
    34.     }
    35.     int cur[100];    
    36.     dfs(cur, 0, M, 0, N);
    37.     return 0;
    38. }

    输出如下：

    关于dfs函数中的遍历我原先写的是这样：

    1.     for (int i = index; i < N; i++)
    2.     {
    3.         //选取
    4.         cur[len] = subset[i];
    5.         dfs(cur, len + 1, M, i + 1, N);
    6.         //不选取
    7.         dfs(cur, len, M, i + 1, N);
    8.     }

    对于cur[i]，分为选取和不选取两种情况，但是这样会导致相同的子集重复打印，例如集合{1,2,3}，如果按照上面这种写法，会重复打印子集{2,3}两次。

    而下面这种正确的这种写法，其作用可以理解为每次调用dfs函数时，确定子集中len位置的元素，即每次确定cur[len]的值，这样一来可以保证在位置0~M - 1上，每个位置的元素不会重复出现

    1.     for (int i = index; i < N; i++)
    2.     {
    3.         cur[len] = subset[i];
    4.         dfs(cur, len + 1, M, i + 1, N);
    5.     }

    讲义P68-实现任意两个不同进制非负整数之间的转换

    实现输入多组数据

    这道题要求能够输入多组测试数据，先了解一下c++中如何输入多组数据：

    1. int a;
    2. string s;
    3. while (cin >> a >> s)
    4. {
    5.     cout << a << " " << s << endl;
    6. }

    利用while循环和cin即可，只要输入的a是int型、s是string型，就能够不断循环、不断输入下去。但是如果输入的a不是int型，或者输入的s不是string型，while循环就会中断。

    本题代码

    回到该题，实现代码如下：

    1. int main()
    2. {
    3.     int a, b;
    4.     string n;
    5.     //多组的测试数据，将a进制的整数n转换为b进制
    6.     while (cin >> a >> n >> b)
    7.     {
    8.         cout << a << "进制：" << n << endl;
    9.         int ten = 0;  //存储10进制数
    10.         //先将a进制转换为10进制
    11.         for (int i = 0; i <= n.size() - 1; i++)
    12.         {
    13.             int x = 0;  //记录该位数字
    14.             if ('0' <= n[i] && n[i] <= '9')
    15.             {
    16.                 x = n[i] - '0';
    17.             }
    18.             else if ('a' <= n[i] && n[i] <= 'z')
    19.             {
    20.                 x = n[i] - 'a' + 10;
    21.             }
    22.             else if ('A' <= n[i] && n[i] <= 'Z')
    23.             {
    24.                 x = n[i] - 'A' + 10;
    25.             }
    26.             ten = ten * a + x;  //这个地方就类似于10进制中的ten * 10 + x
    27.         }
    28.         cout << "10进制：" << ten << endl;
    29.         //再将10进制转换为b进制
    30.         string ans;
    31.         while (ten > 0)
    32.         {
    33.             char ch;
    34.             int x = ten % b;  //记录该位数字
    35.             ch = x < 10 ? x + '0' : x - 10 + 'A';
    36.             ans = ch + ans;
    37.             ten /= b;
    38.         }
    39.         cout << b << "进制：" << ans << endl;
    40.     }
    41.     return 0;
    42. }

    结果如下：

    与网站上所给的结果相同：

    讲义P80-交换两个向量的位置 

    讲义P88-两个机器人的对话

    不知道是不是原题就这样，这里描述了一下对话规则之后要没讲这题到底要我写什么。。

    看了给的代码，才明白了这题是要对任意给出的一个字符串，判断是不是符合规则的对话内容

    1. int main()
    2. {
    3.     string talk;
    4.     cout << "请输入字符串：";
    5.     cin >> talk;
    6.     int n = talk.size();
    7.     int i = 0;
    8.     //while循环即为对话过程
    9.     while(i < n)
    10.     {
    11.         //先由M1开始说话
    12.         //当机器人说的不是数字时，必须继续说话
    13.         while (i < n && (talk[i] == 'Y' || talk[i] == 'N')) i++;
    14.         //当机器人说出数字时，自己必须停止说话，此时对方可以选择接着说话或停止对话
    15.         if (i < n && talk[i] == '2') i++;
    16.         //这里有两种情况：1、说的既不是2也不是Y或N  2、还没说出数字时对话就已经结束了
    17.         else break;
    18.  
    19.         //接着由M2说话
    20.                 //当机器人说的不是数字时，必须继续说话
    21.         while (i < n && (talk[i] == 'y' || talk[i] == 'n')) i++;
    22.         //当机器人说出数字时，自己必须停止说话，此时对方可以选择接着说话或停止对话
    23.         if (i < n && talk[i] == '1') i++;
    24.         //这里有两种情况：1、说的既不是1也不是y或n  2、还没说出数字时对话就已经结束了
    25.         else break;
    26.     }
    27.     if (talk[i - 1] == '1' || talk[i - 1] == '2')
    28.     {
    29.         if (i == n) cout << "该字符串是两个机器人的对话" << endl;
    30.     }
    31.     else cout << "该字符串不是两个机器人的对话" << endl;
    32.     return 0;
    33. }

    结果如下： 

    讲义P91-对n个字符串按字典序排序

    字符数组的相关操作

    这题居然限定了只能用字符数组，字符数组一直是我大一时较为薄弱的点，重新熟悉一下用法

    1.     //字符数组的初始化，两种方式等价
    2.     char str1[20] = { 'a', 'b', 'c', 'd', '\0' }; //注意其中每个字符是char类型的，最后需要手动添加'\0'
    3.     char str2[20] = "abcd"; //可以自动添加'\0'
    4.  
    5.     char str3[20];
    6.     //可以直接用cin和cout输入和输出
    7.     scanf("%s", str3);    //也可以cin >> str3
    8.     printf("%s", str3);   //也可以cout << str3
    9.  
    10.     //字符串的赋值运算
    11.     strcpy(str1, str2); //将str2复制到str1中
    12.  
    13.     //字符串的比较运算
    14.     strcmp(str1, str2); //比较字典序，如果str1大于str2就返回正数，等于就返回0，小于就返回负数
    15.  
    16.     //字符串的拼接操作
    17.     strcat(str1, str2); //将str2拼接到str1后面  //单词concat：合并多个字符串
    18.  
    19.     //求字符串的长度
    20.     int len = strlen(str1);

    本题代码

    1. void Sort(char st[][10], int n)
    2. {
    3.     char tmp[10];
    4.     //简单选择排序
    5.     for (int i = 0; i < n; i++)
    6.     {
    7.         int mini = i;
    8.         for (int j = i + 1; j < n; j++)
    9.         {
    10.             if (strcmp(st[j], st[mini]) < 0)
    11.             {
    12.                 mini = j;
    13.             }
    14.         }
    15.         if (mini != i)
    16.         {
    17.             strcpy_s(tmp, st[i]);
    18.             strcpy_s(st[i], st[mini]);
    19.             strcpy_s(st[mini], tmp);
    20.         }
    21.     }
    22. }
    23. int main()
    24. {
    25.     char st[5][10] = { "bcd", "f", "abc", "adc", "bcde" };
    26.     Sort(st, 5);
    27.  
    28.     for (int i = 0; i < 5; i++)
    29.     {
    30.         printf("%s ", st[i]);
    31.     }
    32.     return 0;
    33. }

    输出如下：

    讲义P92-将0元素移动到数组后面，非0元素保持有序

    讲义P93-删除数组中值在x到y之间的所有元素

    见过几次的题型，还是忘记了移动的操作了

    1. //删除值在x到y之间的所有元素
    2. int del(int A[], int n, int x, int y)
    3. {
    4.     int k = 0;  //记录当前被删除的元素的个数
    5.     for (int i = 0; i < n; i++)
    6.     {
    7.         if (x <= A[i] && A[i] <= y)
    8.         {
    9.             k++;
    10.         }
    11.         else
    12.         {
    13.             A[i - k] = A[i];    //遇到非删除元素，就将其往前移动k个位置
    14.         }
    15.     }
    16.     return n - k;   //返回删除后的元素个数
    17. }
    18.  
    19. int main()
    20. {
    21.     int A[10] = { 21, 7, 6, 12, 1, 0, 5, 3, 4, 10 };
    22.     int n = del(A, 10, 3, 7);   //删除3到7之间的所有元素
    23.     for (int i = 0; i < n; i++)
    24.     {
    25.         cout << A[i] << " ";
    26.     }
    27.     return 0;
    28. }

    结果如下：

            

    讲义P95-删除数组中值相同的元素

    以往遇到这种问题直接用map，但是考研应该不能用这玩意吧，这题其实与上题大致相同，虽然我还是不会。

    主要是第二层循环时要将所有与a[i]不相同的元素都向前移动，我原先想的是第二层循环碰到第一个与a[i]不相同的元素就移动然后直接退出循环了，但是这种想法是错的，例如{ 1, 2, 3, 3, 3, 4, 4, 5 }，若采用我原先的思路将3去重后变为{ 1, 2, 3, 4, 3, 4, 4, 5 }，那问题来了，第一层循环下一次的i指针应该指向哪里呢？这三个无论指向哪个都不行：{ 1, 2, 3, 4, 3, 4, 4, 5 }

    1. //值相同的元素只保留一个，其他删除
    2. int del(int a[], int n)
    3. {
    4.     int k;  //记录当前被删除的元素的个数
    5.     //两层循环，第一层循环遍历数组中剩余的元素，第二层循环进行去重，并把其他元素向前移动
    6.     for (int i = 0; i < n; i++)
    7.     {
    8.         int tmp = a[i];
    9.         k = 0;  //每次要删除一个新的元素时都要重置一下删除的个数
    10.         for (int j = i + 1; j < n; j++)
    11.         {
    12.             if (a[j] == tmp)
    13.             {
    14.                 k++;
    15.             }
    16.             else a[j - k] = a[j];   //与a[i]不相同的元素往前移动k个位置
    17.         }
    18.         n -= k; //删除了k个元素，其他的元素都往前移动了k个位置，因此后面的几个位置上的元素没有意义，不用遍历
    19.     }
    20.     return n;   //返回删除后的元素个数
    21. }
    22.  
    23. int main()
    24. {
    25.     int a[10] = { 1, 2, 3, 3, 3, 4, 5, 5, 6, 7 };
    26.     int n = del(a, 10);
    27.     for (int i = 0; i < n; i++)
    28.     {
    29.         cout << a[i] << " ";
    30.     }
    31.     return 0;
    32. }

    结果如下：

                    

  • 相关阅读:
    Qt 学习(四) —— QBoxLayout盒模型布局
    【开源微服务项目】基于 AOP + Redis + 自定义注解 实现细粒度的接口IP访问限制
    如何准备毕业答辩
    YOLOv3&YOLOv5输出结果说明
    华为OD机试真题- 目录删除-2023年OD统一考试（B卷）
    nginx多端口多server_name监听同时支持https和http
    契约锁助力青岛市市立医院：报销、核酸检测及经济类合同电子签
    【运维心得】ApacheDirectory找不到java路径的解决方案
    【前端设计模式】之策略模式
    “京台高铁”亮相百度地图，真能在2035年建成吗？
  • 原文地址：https://blog.csdn.net/weixin_52629904/article/details/125451075