当前位置：首页 > news >正文

模拟笔试：卡码网2023年快手笔试真题

news 来源：原创 2024/9/19 3:53:41

1.158同余方程

思路

纯数学的思路，想不出来的话很难做。

欧几里得算法视频讲解

代码

#include <iostream>
using namespace std;// 扩展欧几里得：计算 ax + by = gcd(a, b) 的解
long long extended_gcd(long long a, long long b, long long &x, long long &y) {if (b == 0) {x = 1;y = 0;return a;}long long x1, y1;long long gcd = extended_gcd(b, a % b, x1, y1);x = y1;y = x1 - (a / b) * y1;return gcd;
}int main() {long long a, b;cin >> a >> b;long long x, y;long long gcd = extended_gcd(a, b, x, y);// 由于我们只需要模 b 的正整数解，所以我们要保证 x 是正数x = (x % b + b) % b;cout << x << endl;return 0;
}

2.159大整数乘法

思路

从低到高按位相乘进位累加。

具体实现

1.先对其进行输入，分配给s1和s2分别代表两个大数，长度分别为n1和n2

2.由简单的数学知识可得n1*n2的数相乘的范围在(n1+n2-1,n1+n2),所以生成一个n1+n2全为'0'的字符串来存放相乘后的结果。

3.遍历，从右到左进行遍历（在代码中为了统一，我使用的是从左到右遍历，i,j,k分别代表与对应的最右端的距离来实现从右到左）

注意事项：这个里面只遍历n1+n2-1位，最高位是不进行遍历的，而是最后根据进位来进行计算的。

4遍历的内部逻辑：i,j分别代表相应的位数，根据数学知识可以知道（百位 = 百位*个位 + 十位*十位 + 个位*百位），所以第k位的值我们可以从s1[i]和s2[j]相乘获取。在这个里面，0代表个位，1代表十位等。所以k = i + j;

add表示进位，sum代表相应的累加和。得到乘法的结果之类，根据累加和得到对应的进位，然后sum只保留个位作为最后的当前位的值。

注意事项：要将'0'变成0才能参与相乘。先更新进位再更新累加和。

5.每次遍历前需要将sum = sum +add来获取当前位的累加值。同时将add = 0表示遍历前的进位为0，在遍历结束之后将sum = 0。

6.对最高位的处理，根据前面的进位来得到最高位，同时如果最高位最后的结果为0的话，要删除。

代码

#include<iostream>
#include<string>
using namespace std;
int main(){string s,s1,s2;getline(cin,s);int i = 0;int j = 0;int n = s.size();for(;i<n;i++){if(s[i] == ' '){s1 = s.substr(0,i);break;}}int n1 = i;//代表两个的长度int n2 = n-i-1;s2 = s.substr(i+1,n - i - 1);//获得对应的两个数//cout<<n1<<" "<<n2<<endl;string ret = string(n-1,'0');//最长的长度为这个，后序把0给消掉int add = 0;//代表的是进位int sum = 0;//代表的是累加和for(int k = 0;k<n-2;k++){//最高位是不参与计算的，直接算最后的进位即可sum = sum + add;//前面的进位add = 0;//此时计算的就是当前位的进位了for(i = 0;i<n1&&i<=k;i++){//满足两个情况1：长度在这个之内，2，位数要满足j = k - i;//代表s2对应的位数if(j>=n2){continue;}int multi = (s1[n1-1-i]-'0')*(s2[n2-1-j]-'0');//cout<<multi<<endl;sum = sum + multi;add += sum/10;sum = sum%10;}ret[n-2-k] = sum + '0';//cout<<n-2-k<<" "<<ret[n-2-k]<<endl;sum = 0;//所有进位结束之后对应的累加和变为下一位，累加和设置为0}//再将最高位设置为进位ret[0] = add + '0';//最高位为进位//cout<<ret<<endl;if(ret[0] == '0'){ret.erase(0,1);//删除最高位}cout<<ret;return 0;
}

3.160二维平面上的折线段

思路

计算当前值和需要到达的结点的距离分两种情况

1.距离大于s，此时更新位置并将此时的位置写入

2.距离小于s，此时更新位置和长度，同时指向的结点更新。

具体实现

len:代表的是还需要移动的距离。

diff:代表的是当前位置与结点的距离。

注意事项：需要使用#include<iomanip>来控制输出的精度。

代码

#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
int main(){int N;cin>>N;vector<vector<double>> mp(N,vector<double>(2,0));for(int i = 0;i<N;i++){cin>>mp[i][0]>>mp[i][1];}double s;cin>>s;double len = s;//代表剩余的长度vector<vector<double>> ret;ret.push_back(mp[0]);int i = 1;vector<double> cur = mp[0];double sz = 0;while(i<N){//代表在这个范围之内double diff = sqrt((mp[i][0]-cur[0])*(mp[i][0]-cur[0]) + (mp[i][1]-cur[1])*(mp[i][1]-cur[1]));//cout<<diff<<" "<<len<<endl;if(diff >= len){sz = len/diff;cur[0] = cur[0] + sz * (mp[i][0]-cur[0]);cur[1] = cur[1] + sz * (mp[i][1]-cur[1]);ret.push_back(cur);len = s;//此时长度重新回到了原来的长度}else{len = len - diff;//还需要操作的距离cur = mp[i];i++;}}int n= ret.size();std::cout << std::fixed << std::setprecision(5);for(int i = 0;i<n;i++){cout<<ret[i][0]<<", "<<ret[i][1]<<endl;}return 0;
}