C++第二次作业
第二次作业分析
1. 约瑟夫问题
0,1,···,n-1这n个数字排成⼀个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后 从下⼀个数字开始计数）。求出这个圆圈里剩下的最后⼀个数字。
输入描述
输入为两行
第一行为⼀个正整数 n ，说明⼀共有 n 个数: 0, 1, 2 ... n - 1围成⼀个圆圈
第二行为⼀个正整数 m ，说明每次从这个圆圈里删除第 m 个数
输出描述
输出为一个int型正整数n
示例
示例1
输入
5
3输出
3示例2
输入
11
4输出
8提示
本题可以用三种方法解决
- 使用链表解决（有兴趣同学可以先尝试学习C++中链表的使用⽅式）
- 用数组模拟链表 5 3 3 11 4 8 使用数组模拟链表时会涉及到对数组中元素的删除操作，这里建议大家使用 vector 对链表进行模拟，删除 vector 中元素可以使用 erase 方法
//remove one element
vector::erase(iterator position);- 数学方法，使用递归解决
该方法较为巧妙，这里贴一下公式，感兴趣的同学可以查找相关资料
//f(n, m)表示有n个数字[0, n-1]组成圆圈，从数字0开始，每次删除第m个数字最
后剩下的数字
递推公式：f(n, m)=(f(n-1, m)+m)%n分析
约瑟夫问题，比较经典，助教的提示也很多了，不多说了。
值得注意的是遍历vec所用到的c++语法，也就是迭代器。
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n,m;
cin >> n;
cin >> m;
vector<int> vec;
for(int i = 0; i < n; ++i){
vec.push_back(i);
}
int cnt = 0;
while(vec.size() != 1){
for(auto iter = vec.begin(); iter != vec.end();){
cnt++;
if(cnt == m){
iter = vec.erase(iter);
cnt = 0;
}else{
iter++;
}
}
}
cout << *vec.begin();
}
2. 解释器
基于指定的指令类型，实现一个简单的解释器，用于解释指令序列的运行结果
若解释的过程中出现错误，则终止对后续指令的解释
操作指令
1. 常量赋值：[var] = [constantInt]
指令含义
- [var]指代变量，例如x, y, z
- [constantInt]指代整型常量，例如1, 100
- 指令执行后，[var]对应的值为[constantInt]
注意点: 需支持重新赋值
- 例如已有
x = 1指令，后接x = 2指令，则在后续指令解释过程中，x对应的值为2
2. 变量赋值：[var1] = [var2]
指令含义
- [var1]和[var2]指代变量
- 指令执行后，[var1]对应的值为[var2]对应的值
注意点：变量未定义错误
- 如果[var2]未定义，即之前的指令序列不包含对[var2]的赋值，则认为产生错误，结束程序
3. 算数运算和赋值：[var] = [operand1] [operator] [operand2]
指令含义
[var]指代变量
[operand]指代操作数，既可以是变量[var]，也可以是整型常量[constantInt]
[operator]指代操作符，包括
+ - * /四种，分别指代整数运算的加 减 乘 除指令执行时
- 首先解析[operand]对应的值，如果为常量，直接使用常量值；如果是变量，则使用变量当前的值
- 接着求解等号右侧表达式的结果
- 最后将上述求解的结果赋值给变量[var]
注意点
- 变量未定义错误：如果[operand]为变量[var]，且该变量未定义，则结束程序
- 除零错误：如果[operator]为整数除法运算符，且[operand2]对应的值解析为0，则结束程序
4. 打印：print [var]
指令含义：打印变量[var]对应的值
注意点：变量未定义错误
- 如果[var]未定义，则认为产生错误，并结束程序
提示
可以使用std::map来存储和更新变量对应的值
可以使用getline(cin, line)来接收一整行的输入
可以使用exit(0)来提前终止程序
测试用例
第1行为指令数量n
第2到n+1行为具体的指令
示例1
输入
8
x = 1
print x
x = 2
print x
y = x + 1
z = x + y
print y
print z输出
1
2
3
5示例2
输入
4
x = 1
print x
y = a
print y输出
1
error解释
指令
y = a使用未定义的变量 a ，产生错误，终止程序后续指令
print y由于程序已经终止，因此没有执行
分析
典型的结构化编程，条件比较多，第一遍的时候遇到了一个运行异常re，检查之后发现，原来是忘了除0异常这个条件。。。
#include <iostream>
#include <map>
using namespace std;
int check_operator(const string& s){
if (s.find('+') != -1)return 1;
else if(s.find('-') != -1)return 2;
else if(s.find('*') != -1)return 3;
else if (s.find('/') != -1)return 4;
else return 0;
}
int main(){
int n;
cin >> n;
cin >> ws;
map<string, int> params;
for(int i = 0; i < n; ++i){
string line;
getline(cin, line);
if (line.find("print") == 0){
string s1 = line.substr(6);
if (params.count(s1)){
cout << params[s1] << endl;
}else{
cout << "error" << endl;
exit(0);
}
}else{
string s1 = line.substr(0,line.find('=') - 1);
string s2 = line.substr(line.find('=') + 2);
if(check_operator(s2) == 0){
if (s2[0] >= 48 && s2[0] <= 57)params[s1] = stoi(s2);
else if (!params.count(s2)){
cout << "error" << endl;
exit(0);
}else
params[s1] = params[s2];
}else{
char op;
switch (check_operator(s2)) {
case 1:
op = '+';
break;
case 2:
op = '-';
break;
case 3:
op = '*';
break;
case 4:
op = '/';
break;
}
string a = s2.substr(0, s2.find(op) - 1);
string b = s2.substr(s2.find(op) + 2);
int a_,b_;
if (a[0] >= 48 && a[0] <= 57) a_ = stoi(a);
else {
if (!params.count(a)){
cout << "error" << endl;
exit(0);
}
a_ = params[a];
}
if (b[0] >= 48 && b[0] <= 57) b_ = stoi(b);
else{
if (!params.count(b)){
cout << "error" << endl;
exit(0);
}
b_ = params[b];
}
if(op == '+'){
params[s1] = a_ + b_;
}else if (op == '-'){
params[s1] = a_ - b_;
}else if (op == '*'){
params[s1] = a_ * b_;
}else if (op == '/'){
if (b_ == 0){
cout << "error" << endl;
exit(0);
}
params[s1] = a_ / b_;
}
}
}
}
}
3. 不重叠时间段
给定一个时间段的集合，找到需要移除时间段的最小数量，使剩余的时间段互不重叠。
输入描述
先输入一个整数 n 表示有 n 个时间段，其中 n>=2
接下来是 n 行输入
hh:mm-hh:mm
hh:mm-hh:mm
……
00<=hh<=23
00<=mm<=59
输入时间保证存在，且不会跨天
输出描述
整数 k ，表示需要移除的时间段数量
示例
示例1
输入：
2
06:30-09:40
01:30-06:30输出
0解释
不存在重叠的时间段，需要移除的时间段数量为 0
示例2
输入：
3
09:30-11:40
08:00-11:00
11:50-12:00输出
1解释
通过移除 08:00-11:00 时间段可以使得剩下的时间段没有重叠，需要移除的时间段数量为 1
分析
这题就是LeetCode435 无重叠区间 的一个变形。思想是贪心算法。我们可以先将各个时间转换为以秒为单位，于是我们就可以得到相同数量级的二维数组，然后我们需要用每个数组中的第二个元素进行排序。用第二个排序的理由很简单，因为可以保证我们每次选择左边的端点与之前的区间的右端点比较的时候，我们能筛选并留下尽可能小的区间，这保证了我们删除的元素尽量的少。画个图想想就明白了。
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<vector<int>> vec;
for(int i = 0; i < n; ++i){
string s;
cin >> s;
string s1,s2;
s1 = s.substr(0, s.find('-'));
s2 = s.substr(s.find('-') + 1);
string s11 = s1.substr(0,s1.find(':'));
string s12 = s1.substr(s1.find(':') + 1);
string s21 = s2.substr(0,s2.find(':'));
string s22 = s2.substr(s2.find(':') + 1);
vector<int> temp;
temp.push_back(stoi(s11) * 60 + stoi(s12));
temp.push_back(stoi(s21) * 60 + stoi(s22));
vec.push_back(temp);
}
for(int i = 0; i < vec.size(); i++){
int min_index = i;
for (int j = i; j < vec.size(); ++j) {
if (vec[j][1] < vec[min_index][1])min_index = j;
}
vector<int> temp = vec[min_index];
vec[min_index] = vec[i];
vec[i] = temp;
}
int r = vec[0][1];
int ans = 1;
for (int i = 1; i < vec.size(); ++i) {
if (vec[i][0] >= r){
ans++;
r = vec[i][1];
}
}
cout << vec.size() - ans;
}4. 登山台阶
乔治是一名登山爱好者，这天他来到登山台阶前，假设该登山台阶共有N阶，乔治可以一步上1阶，也可以一步上
2 阶，请计算乔治总共有多少种走法到达山顶？
输入描述
输入仅包含一个 int 类型的整数 N
（1≤ N ≤3000）。
输出描述
输出走法总数
示例
示例1
输入
4输出
5示例2
输入
99输出
354224848179261915075分析
这题看上去无脑，实则。。。
因为输入的数字太大，会导致long long都不够存。。。
正常来写的话有递归和数学两种方法，其实公式就是\[f(n) = f(n - 1) + f(n - 2) \]，但是问题就坏在了输入的数字太大了，因此还得实现一个全加法器。。。
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
string ans = "0";
string pre = "0";
for(int i = 1; i <= n; i++){
if(i == 1)ans = "1";
if(i == 2){
ans = "2";
pre = "1";
}else{
string temp = ans;
int nums[1000] = {0};
int a[1000] = {0};
int b[1000] = {0};
for (int j = 0; j < ans.size(); ++j) {
a[ans.size() - 1 - j] = ans[j] - '0';
}
for (int j = 0; j < pre.size(); ++j) {
b[pre.size() - 1 - j] = pre[j] - '0';
}
int C = 0;
for (int j = 0; j < 1000; ++j) {
nums[j] = a[j] + b[j] + C;
C = 0;
if (nums[j] >= 10){
C = 1;
nums[j] -= 10;
}
}
ans.clear();
int pos = 0;
for (int j = 999; j >= 0 ; --j) {
if (nums[j] != 0){
pos = j;
break;
}
}
for (int j = 0; j <= pos; ++j) {
ans += to_string(nums[pos - j]);
}
pre = temp;
}
}
cout << ans;
}5. reflection
有一个边长为10的上面开口的正方体容器，内侧表面均为镜面材料。我们考察这个容器的横截面，建立 如下图所示的坐标系。现有一束光以一定的角度θ，θ∈(0, 45°)，紧贴着容器的左侧上方边缘（0, 0）射入，光束会在碰到容器底部之后反射离开容器。
现需要进行如下计算：我们假设该横截面被坐标系分割成了一个10x10的网格，每个网格都有其权重 \[w_{ij}\]，请计算光线所经过的所有网格的权重之和。
输入描述
第1行为两个正整数x和y，表示光线入射方向的向量（x，y）。例如上图光线的入射向量为（1，2）。
第2~11行每行包括了10个整数，表示每个网格的权重大小。其排列分布与上图一致。
输出描述
光线所经过的所有网格的权重之和。
示例
示例1
输入
1 2
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5输出
60示例2
输入
1 3
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9
10 10 10 10 10 10 10 10 10 10输出
100提示
注意考虑反射两次的情况。
分析
这题我感觉是这次作业里面最难的，因为BF其实数据结构运用的好的话，并不是很困难，当然那题直接模拟栈也不是不行（但我懒）。这道题目我一开始想模拟路径，后来发现我考虑欠周到了，因为需要涉及到诸如（2，3）这种输入，然后大佬提示用数学方法，直接算tan，不过这又涉及到了double的精度问题了，写的过程中还顺便发现了原来教我这题的人是运气好过的（xswl），因为他加了错误的格子，但是数值正好一样。有人说这题把地图对称两次，但是我觉得也有麻烦，就是要去重交界处的格子。不如直接三个基准点求tan。
#include <iostream>
using namespace std;
int main(){
int x,y;
cin >> x >> y;
int nums[10][10];
int ans = 0;
double k = x * 1.0 / y;
double bottom_x = 10.0 * x / y;
double right_y = 20 - 10 / k;
for(int i = 0; i < 10; ++i){
for(int j = 0; j < 10; ++j){
cin >> nums[i][j];
// 必定经过（0，0）
if(i == 0 && j == 0){
ans += nums[i][j];
continue;
}
if(j < k * (i + 1) && k * i < (j + 1)){
ans += nums[i][j];
}
else if(((j - bottom_x > 0 && k > (j - 10.0 * k)/ (10 - i)) || j - bottom_x <= 0 ) && (j + 1 - bottom_x) > k * (9 - i)){
ans += nums[i][j];
}
else if(right_y > 0 && 9 - j < k *(right_y - i) && k * (right_y - i - 1) < 10 - j){
ans += nums[i][j];
}
}
}
cout << ans;
return 0;
}6. ArrayList
用数组实现一个简单的 ArrayList ，数组元素的类型为 int ,支持如下操作
数组的初始大小为0，在增加第一个元素时将数组大小设为10。数组填满之后再增加元素时需要进行扩容，按照1.5倍扩容（建议使用
oldCapacity + (oldCapacity / 2) 或
oldCapacity + (oldCapacity >> 1)
），数组容量不能减小。
add x: 在数组的末尾增加x
remove x: 删除第一个值为x的元素，如果数组中包含多个x，只删除第一个，后面元素往前移动；有可能删除的数在数组中并不存在
get x: 输出索引位置为x的元素的值，如果该位置没有元素或者索引不合法，输出-1
getSize: 输出数组中的实际元素个数
getCapacity: 输出数组的容量
输入描述
第一行为正整数 N ，表示有 N 条命令，下面 N 行为命令， 0 < N <= 50
示例1
输入:
5
add 0
add 1
remove 1
get 1
getSize
输出:
-1
1示例2
输入:
15
add 0
add 1
add 2
add 3
add 4
add 5
add 6
add 7
add 8
add 9
get 1
add 10
get 10
getSize
getCapacity
输出：
1
10
11
15
解释：在add 10操作之后需要进行扩容注意
不允许使用 STL 中的容器（包括但不限于 string 、 vector 和 list ），一旦发现，本题 0 分！
分析
简单的结构化编程，用数组实现ArrayList罢了。
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int N;
cin >> N;
int capacity = 0;
int *nums;
int index = 0;
for(int i = 0; i < N; i++){
char ch[20] = {0};
cin >> ch;
if (strcmp(ch, "add") == 0){
int k = 0;
cin >> k;
if(capacity == 0){
capacity = 10;
nums = new int[10];
}
if(index == capacity){
int *a = new int [capacity];
for (int j = 0; j < capacity; ++j) {
a[j] = nums[j];
}
int old_capacity = capacity;
capacity = old_capacity + (old_capacity >> 1);
nums = new int [capacity];
for (int j = 0; j < old_capacity; ++j) {
nums[j] = a[j];
}
}
nums[index] = k;
index++;
}
else if(strcmp(ch, "getSize") == 0){
cout << index << endl;
}
else if(strcmp(ch, "getCapacity") == 0){
cout << capacity << endl;
}
else if(strcmp(ch, "remove") == 0){
int k = 0;
cin >> k;
for(int i1 = 0; i1 < index; i1++){
if(nums[i1] == k) {
if (i1 < index - 1) {
for (int j = i1; j < index; j++) {
nums[j] = nums[j + 1];
}
}
index--;
}
}
}
else if(strcmp(ch, "get") == 0){
int k = 0;
cin >> k;
if(k >= index || k < 0){
cout << -1 << endl;
}
else{
cout << nums[k] << endl;
}
}
}
return 0;
}7. BF解释器
Brainfuck 是一种极小化的程序语言，可以模拟图灵机进行工作。它基于一个简单的机器模型，除了指 令，这个机器还包括：一个以字节为单位、元素全部被初始化为零并且大小无限的数组、一个指向该数 组的指针（初始时指向数组的第一个字节，后文称为“数据指针”）以及用于输入输出的两个字节流。
基本知识
输入描述
输入包含若干行，第一行为 BF 程序，其余行为该 BF 程序所需要的输入（若有）。
保证 BF 程序一定是有意义、正确且能够结束的。保证模拟的数组长度不大于 1000.
输出描述
输出所有.命令的结果。
示例
示例1
读取一个字符并输出
输入
,.
a输出
a示例2
打印“Hello”，五个字符的 ASCII 码分别是
72 101 108 108 111 .
输入
+++++++++[->++++++++<]>.[[-]<]++++++++++[->++++++++++<]>+.[[-]<]+++++++++[-
>++++++++++++<]>.[[-]<]+++++++++[->++++++++++++<]>.[[-]<]+++++++++[->++++++++++++
<]>+++.输出
Hello注：末尾没有换行符
提示
分析
我在处理左右中括号的时候使用的是栈和map，但其实也可以不这么做，帮同学debug的时候发现他们就在循环里面嵌套while循环就行了，就是在模拟，用一个cnt来表示右括号之前有几个左括号，是0的话则找到了对应的位置。
另外这题尽量按照助教的处理指令写，u8和char作为bf的基本类型会产生不一样的结果，因为char是有符号的，而u8不是。
另外要注意EOF的处理。CLion输入EOF可以用debug调试终端输入ctrl + d。
#include <iostream>
#include <string>
#include <cstdint>
#include <stack>
#include <list>
#include <map>
using namespace std;
int main(){
string bf;
getline(cin, bf);
stack<int> Left_bracket;
map<int, int> bracket_index;
for(int i = 0; i < bf.size(); i++){
if(bf[i] == '['){
Left_bracket.push(i);
}else if(bf[i] == ']'){
int index = Left_bracket.top();
Left_bracket.pop();
// 对右括号记录与其对应的左括号的地址
bracket_index[i] = index;
// 对左括号记录与其对应的右括号的地址
bracket_index[index] = i;
}
}
uint8_t bytes[10000] = {0};
uint8_t *pt = bytes;
for(int i = 0; i < bf.size(); ++i){
if(bf[i] == '+'){
(*pt)++;
}else if(bf[i] == '-'){
(*pt)--;
}else if(bf[i] == '>'){
pt++;
}else if(bf[i] == '<'){
pt--;
}else if(bf[i] == ','){
char c;
if(cin.get(c)){
*pt = c;
}
else{
*pt = 0;
}
}else if(bf[i] == '.'){
cout << *pt;
}else if(bf[i] == '['){
if(*pt == 0){
i = bracket_index[i];
}
}else if(bf[i] == ']'){
if(*pt != 0){
i = bracket_index[i];
}
}
}
return 0;
}
/*
* u8：无符号字符型，相当于unsigned char
char：有符号字符型
*/8. 最长连续递减序列
给定⼀个未经排序的整数数组，找到最⻓且连续递减的⼦序列，并返回该序列的长度。
连续递减的子序列 可以由两个下标 l 和 r（l < r）确定，假定这个数组名为nums，如果对于每个 l <= i < r，都有 nums[i] > nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递减⼦序列。
输入描述
输入⼀个整数数组。第⼀行是数组的长度，从第二行开始每行都是⼀个整数。
输出描述
最长且连续递减的长度
示例
示例1
输入
5
4
3
2
1
5输出
4示例2
输入
3
2
2
2输出
1提示
1 <= 数组长度 <= 10^4-10^9 <= 数组元素 <= 10^9
分析
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
int nums[n];
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
int max_len = 1;
for (int i = 0; i < n; ++i) {
int len = 1;
for (int j = i; j < n; ++j) {
if (j == i)continue;
if (nums[j] < nums[j - 1])len++;
else break;
}
if (len > max_len)max_len = len;
}
cout << max_len;
}9. 旋转矩阵
给定一个 N * N大小的方阵，顺时针旋转给定的度数，然后打印旋转后的矩阵。
输入描述
第一行给定正整数 N 和旋转的度数 x ，空格隔开，接下来有 N 行数据，每行 N 个数据，空格隔开。
矩阵的元素都是 int 类型，0 <= x <= 1000000 ，保证 x 是90的倍数。
输出描述
按行输出旋转后的矩阵。
示例1
输入：
3 90
1 2 3
4 5 6
7 8 9
输出：
7 4 1
8 5 2
9 6 3示例2
输入：
4 180
5 1 9 11
2 4 8 10
13 3 6 7
15 14 12 16
输出：
16 12 14 15
7 6 3 13
10 8 4 2
11 9 1 5分析
#include <iostream>
using namespace std;
void rotate(int **matrix, int n){
int nums[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
nums[j][n - 1 - i] = matrix[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix[i][j] = nums[i][j];
}
}
}
int main(){
int n,x;
cin >> n;
cin >> x;
int cnt = x / 90 % 4;
int **matrix = new int * [n];
for(int i = 0; i < n; i++){
matrix[i] = new int[n];
for(int j = 0; j < n; j++){
cin >> matrix[i][j];
}
}
for (int i = 0; i < cnt; ++i) {
rotate(matrix, n);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}10. 螺旋矩阵
给定 m 行 n 列的矩阵，请顺时针打印矩阵的元素
输入描述
第一行为两个数，空格隔开，分别为 m 和 n 。接下来为 m 行 ，每行 n
个元素，空格隔开。矩阵元素都是 int 类型。
其中 1 <= m,n <= 100
输出描述
元素之间以空格隔开。
示例
输入:3 4
1 2 3 4
5 6 7 8
9 10 11 12
输出:1 2 3 4 8 12 11 10 9 5 6 7分析
题目来源：LeetCode54
有很多种方法，比如模拟啥啥的。
我用的是我上学期在评论区看到的骚操作。
#include <iostream>
#include <vector>
using namespace std;
int main(){
int m,n;
cin >> m;
cin >> n;
int matrix[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
cin >> matrix[i][j];
}
}
vector<int> ans;
int up = 0;
int left = 0;
int right = n - 1;
int bottom = m - 1;
while (true){
// 上方
for (int i = left; i <= right; ++i) {
ans.push_back(matrix[up][i]);
}
if (++up > bottom)break;
// 右边
for (int i = up; i <= bottom; ++i) {
ans.push_back(matrix[i][right]);
}
if (--right < left)break;
// 下方
for (int i = right; i >= left ; --i) {
ans.push_back(matrix[bottom][i]);
}
if (--bottom < up)break;
// 左边
for (int i = bottom; i >= up; --i) {
ans.push_back(matrix[i][left]);
}
if (++left > right)break;
}
for (int k : ans) {
cout << k << ' ';
}
}
- 标题: C++第二次作业
- 作者: Kiyotaka Wang
- 创建于 : 2022-10-23 11:18:08
- 更新于 : 2022-11-21 13:03:00
- 链接: https://hmwang2002.github.io/2022/10/23/c-di-er-ci-zuo-ye/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。