计科数据《算法设计与分析》第3次上机作业

article/2024/6/13 20:58:34

问题 A: 算法10-6~10-8:快速排序

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fer(i,a,b) for(int i=a;i<b;i++)
const int N=1e5+5,mod=1e9+7;
int a[N];
int partition(int a[],int l,int r){int i=l,j=r;int x=a[l];while(i<j){while(i<j&&a[j]>=x)j--;a[i]=a[j];while(i<j&&a[i]<=x)i++;a[j]=a[i];}a[i]=x;return j;
}
void quicksort(int a[],int l,int r){int t;if(l<r){t=partition(a,l,r);quicksort(a,l,t-1);quicksort(a,t+1,r); }
}
signed main(){int n;cin>>n;fer(i,0,n)cin>>a[i];quicksort(a,0,n-1);fer(i,0,n)cout<<a[i]<<" ";cout<<endl;return 0;
}

问题 B: 黑白棋子的移动

有2n个棋子(n≥4)排成一行,开始位置为白子全部在左边,黑子全部在右边,右边有两个空位,如下图为n=5的情形:
○○○○○●●●●●__
移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可以右移到空位上去,但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子(不能平移),要求最后能移成黑白相间的一行棋子,且棋子均在最右端。如n=5时,成为:__○●○●○●○●○●
n=7时输出

step 0:ooooooo*******--
step 1:oooooo--******o*
step 2:oooooo******--o*
step 3:ooooo--*****o*o*
step 4:ooooo*****--o*o*
step 5:oooo--****o*o*o*
step 6:oooo****--o*o*o*
step 7:ooo--***o*o*o*o*
step 8:ooo*o**--*o*o*o*
step 9:o--*o**oo*o*o*o*
step10:o*o*o*--o*o*o*o*
step11:--o*o*o*o*o*o*o*

观察发现,n>4时可递归至4,n==4时为边界条件可退出
万能头文件导致move函数被占用,自己写函数不要用move
输出要控制宽度
blank标记空位第一格的下标,可不断跳变

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fer(i,a,b) for(int i=a;i<b;i++)
const int N=1e5+5,mod=1e9+7;
char c[N];
int n,blank,cnt;
void print(){cout<<"step"<<fixed<<setw(2)<<cnt++<<":";fer(i,0,2*n+2)cout<<c[i];cout<<endl;
}
void mv(int k){fer(j,0,2){c[blank+j]=c[k+j];c[k+j]='-';}blank=k;print();
}
void solve(int n){if(n==3){mv(3);mv(7);mv(1);mv(6);mv(0);}else{mv(n);mv(2*n);solve(n-1);}
}
signed main(){cin>>n;blank=2*n;fer(i,0,n)c[i]='o';fer(i,n,2*n)c[i]='*';c[blank]='-';c[blank+1]='-';print();solve(n-1);return 0;}

问题 C: 4.4.3 矩阵连乘

题目描述
假设你必须评估一种表达形如 ABCDE,其中 A,B,C,D,E是矩阵。
既然矩阵乘法是关联的,那么乘法的顺序是任意的。然而,链乘的元素数量必须由你选择的赋值顺序决定。
例如,A,B,C分别是 50×10 ,10×20 和 20×5的矩阵。
现在有两种方案计算 A * B * C ,即(A * B) * C 和 A*(B * C)。
第一个要进行15000次基本乘法,而第二个只进行3500次。
你的任务就是写出一个程序判定以给定的方式相乘需要多少次基本乘法计算。
输入包含两个部分:矩阵和表达式。
输入文件的第一行包含了一个整数 n,(1≤n≤26), 代表矩阵的个数。
接下来的n行每一行都包含了一个大写字母,说明矩阵的名称,以及两个整数,说明行与列的个数。
第二个部分是若干个矩阵表达式,每行的数据保证是一个矩阵,一个括号以及其内部可视为一个矩阵,括号内部包含两个矩阵.
输出
对于每一个表达式,如果乘法无法进行就输出 " error "。否则就输出一行包含计算所需的乘法次数。
输入

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

输出

0
0
0
error
10000
error
3500
15000
40500
47500
15125

用结构体存储矩阵,栈里存的是int下标
遇到’('则从栈中弹出两个矩阵相乘,得到新矩阵保存并入栈
弹出顺序别弄反,先弹出的是第二个乘数
每次cin>>string后刷新矩阵及下标

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fer(i,a,b) for(int i=a;i<b;i++)
int n,blank,cnt;
struct node{int r,c;
};
int cal(int a,int b,int c,int d){if(b!=c)return -1;else return a*b*d;
}
int k;
signed main(){cin>>n;node m[2*n+1];fer(i,0,n){char c;cin>>c;int a,b;cin>>a>>b;m[c-'A'].r=a;m[c-'A'].c=b;}string s;while(cin>>s){k=n;int sum=0;bool f=1;if(s.size()==1){cout<<"0"<<endl;continue;}stack<int> matrix;fer(i,0,s.size()){if(s[i]=='(')continue;else if(s[i]>='A'&&s[i]<='Z'){matrix.push(s[i]-'A');}else if(s[i]==')'){int t1=matrix.top();matrix.pop();int t2=matrix.top();matrix.pop();int res=cal(m[t2].r,m[t2].c,m[t1].r,m[t1].c);if(res<0){f=0;break;}else{sum+=res;m[k].r=m[t2].r;m[k].c=m[t1].c;matrix.push(k);k++;}}}if(f)cout<<sum<<endl;else cout<<"error"<<endl;}return 0;
}

http://www.ngui.cc/article/show-1007691.html

相关文章

Oracle-CDC进程同步报错问题合集

前言: Oracle CDC是数据库自带的数据库数据复制和增量数据抽取工具&#xff0c;提供五种复制模式 1 Synchronous Change Data Capture Configuration(同步复制) 2 Asynchronous HotLog Configuration(异步在线日志CDC) 3 Asynchronous Distributed HotLog Configuratio…

史诗级详解面试中JVM的实战

史诗级详解面试中JVM的实战 1.1 什么是内存泄漏?什么是内存溢出?1.2 你们线上环境的JVM都设置多大?1.3 线上Java服务器内存飙升怎么回事?1.4 线上Java项目CPU飙到100%怎么排查?1.5 线上Java项目OOM了,怎么回事?1.1 什么是内存泄漏?什么是内存溢出? 内存溢出:OutOfMe…

Lua for 的使用

Lua 中的 for 循环有两种形式&#xff1a;数值型遍历和泛型遍历。 1&#xff0c;数值型遍历 语法为: for nameexp1, exp2 [,exp] do -- do something end [,exp] 这个不是必须的&#xff0c;是可选项。它表示步长&#xff0c;即从nameexp1 如何变化到 exp2&#xff0c;所…

HJ64 MP3光标位置(java详解)

就是一块诺基亚手机屏幕,只能显示四个歌曲,upper代表屏幕显示第一个歌曲(总歌曲中第几个),down代表屏幕显示的最后一个歌曲(总歌曲中第几个) 你要输入这个总歌曲数量n {初始值,cur0,upper0,downMath.min(3,n-1);}{为啥cur为0,例如打开QQ音乐光标不都是显示在第一个歌曲位置嘛} …

C++初阶——类和对象(3)赋值/运算符重载

目录 5.赋值运算符重载 5.1 运算符重载 5.2 赋值运算符重载 5.3 前置和后置重载 6.日期类的实现——流插入&#xff0c;流提取重载 Date.h&#xff1a; Date.cpp: 7.const成员 8.取地址及const取地址操作符重载 5.赋值运算符重载 5.1 运算符重载 C为了增强代码的可读性…

建堆、堆排序、TopK问题大合集

一、如何建堆 1、向上调整建堆法O(NlogN) 原理&#xff1a; 利用向上调整的方法进行建堆&#xff0c;是通过模仿之前堆的插入操作&#xff0c;从第二个数开始&#xff0c;每次插入一个数&#xff0c;就对这个数进行向上调整&#xff0c;这样子既保证了原有数据为堆&#xff…

测试开发进阶系列课程

测试开发系列课程1.完善程序思维--------案列&#xff1a;图书管理系统的创建**&#xff08;一&#xff09;图书管理系统的创建**1.完善程序思维--------案列&#xff1a;图书管理系统的创建 &#xff08;一&#xff09;图书管理系统的创建 1.在main中写入主函数&#xff0c;…

数位DP算法学习总结

一、数位dp简述模板数位dp是一种计数时使用的动态规划算法&#xff0c;一般是要统计一个区间 [left, right] 内符合给定条件数字的个数&#xff0c;例如HDU 2089 不要62中的统计给定区间内不包含4以及62数字的个数&#xff0c;数位dp其实是暴力枚举算法的优化&#xff0c;通过过…

添加Anaconda Powershell Prompt到右键

想要使用Anaconda Powershell Prompt每次还要去开始菜单打开&#xff0c;而且还要切换到特定目录下&#xff0c;十分麻烦。通过将Anaconda Powershell Prompt添加到鼠标右键&#xff0c;可在当前目录十分方便的打开Anaconda Powershell Prompt。步骤如下&#xff1a; 1. 首先开…

Java_Spring:4. 使用 spring 的 IoC 的实现CRUD【案例】

目录 1 需求和技术要求 1.1 需求 1.2 技术要求 2 环境搭建 2.1 拷贝 jar 包 2.2 创建数据库和编写实体类 2.3 编写持久层代码 2.4 编写业务层代码 2.5 创建并编写配置文件 3 配置步骤 4 测试案例 4.1 测试类代码 4.2 分析测试了中的问题 1 需求和技术要求 1.1 需求…