DSP

南邮2018第二批选拔试题

2019-07-13 18:56发布

站内文章 / DSP
12106 0 1473
class="markdown_views prism-atelier-sulphurpool-light">

2019年3月10日，第二次写了一遍这些题目

https://blog.csdn.net/qq_37360631/article/details/88374981 这里写图片描述 题解：
比较水的一道题目，但当时自己写了很久。原因是我想先整体读入到字符串数组里，然后遍历处理。
开始读取的时候没把空格读进去。浪费了很多时间。 #include #include int main() { char ch; int ans=0; while(scanf("%c",&ch)!=EOF){ if(ch!=' ') { ans++;} if(ch==' ') { printf("%d ",ans); ans=0; } if(ch=='.'){ printf("%d",ans-1); break; } } } 回顾一下字符串
(1)C++语言关于字符串的读取，用string类型，getline()读取：
C中没有string类型！ #include using namespace std; int main(){ string ss; getline(cin,ss); cout< (2)C语言中，可以用字符数组存储，gets和puts输入和输出。 #include #include int main() { char ss[1010]; gets(ss); //将用户输入的字符串（可以包括空格）读入ss puts(ss); //printf("%s",ss); return 0; } 这里写图片描述 水题：分为分子分母能不能整除两种情况。不能整除，求分子和分母的最大公约数，然后同除以最大公约数得到最终结果。 #include int gcd(int a,int b){ int min=0; int i; if(a>b) min=b; else min=a; for(i=min;i>=1;i--){ if(a%i==0 && b%i==0){ return i; } } return 1; } int main(){ int a1,b1,a2,b2; scanf("%d/%d %d/%d",&a1,&b1,&a2,&b2); int fenzi=a1*b2+a2*b1; int fenmu=b1*b2; if(fenzi%fenmu==0){ printf("%d",fenzi/fenmu); } else{ int q=gcd(fenzi,fenmu); fenzi=fenzi/q; fenmu=fenmu/q; printf("%d/%d",fenzi,fenmu); } return 0; } 这里写图片描述
这里写图片描述 看了分析才知道这是一道拓扑排序的题目。
http://blog.csdn.net/dm_vincent/article/details/7714519
假设我们在学习完了算法这门课后，可以选修机器学习或者计算机图形学。这个或者表示，学习机器学习和计算机图形学这两门课之间没有特定的先后顺序。
因此，在我们所有可以选择的课程中，任意两门课程之间的关系要么是确定的(即拥有先后关系)，要么是不确定的(即没有先后关系)，绝对不存在互相矛盾的关系(即环路)。
那么这道题目，就是利用拓扑排序判断是否有无回路。 //拓扑排序判断是否存在环 #include #define maxn 510 using namespace std; int G[maxn][maxn]; //记录路径 int in_degree[maxn]; //记录入度 int ans[maxn]; int n,m,x,y; int i,j; int flag=0; void toposort(){ flag=0; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(G[i][j]) in_degree[j]++; } } for(i=1;i<=n;i++){ //从最小的开始找 //这样保证有多个答案时候序号小的先输出 int k=1; while(!in_degree[k]){ //寻找入度为0的点 k++; if(k>n){ flag=1; break; } } ans[i]=k; in_degree[k]=-1; //更新为-1,后面检测补受影响，相当于删除结点 for(int j=1;j<=n;j++){ if(G[k][j]){ in_degree[j]--; //相连的入度减1 } } } } int main(){ while(cin>>n){ memset(in_degree,0,sizeof(in_degree)); memset(ans,0,sizeof(ans)); memset(G,0,sizeof(G)); for(i=1;i<=n;i++){ cin>>m; for(j=0;j>y; G[i][y]=1; } } toposort(); if(flag) cout<<"0"< 这里写图片描述 这里不贴完整的代码了，学习一下怎么处理保留一位小数（四舍五入原则下）。 #include using namespace std; float one(float a){ if(a>=0) return (float)(int(a*10+0.5))/10; else if(a<0) return (float)((int)(a*10-0.5))/10; return a; } int main(){ float a; cin>>a; a=one(a); return 0; } 这里写图片描述 prime生成最小生成树。 #include #include #define maxn 1010 #define inf 0x3f3f3f using namespace std; int map[maxn][maxn]; int d[maxn],vis[maxn]; int N,M; //N个结点,M条边 int Vcount=0; int prim(){ int i,j,min,v,ans=0; for(int i=1;i<=N;i++){ d[i]=map[1][i]; //d[i]表示原点到其他点的距离，这里原点是1 vis[i]=0; } vis[1]=1; Vcount++; for(i=1;imap[v][j]) d[j]=map[v][j]; } if(Vcount>N>>M; for(i=0;i>sta>>ed>>cost; map[sta][ed]=map[ed][sta]=cost; } cout< 这里写图片描述 约瑟夫环问题。
可以用递归的方法解决这道题。
记f(n,k)是当n个人，报数间隔为k的人出去，最后剩下人的序号。
有f(n,k)=(f(n-1,k)+k)%n; #include #include #define maxn 1010 using namespace std; int num[maxn]; int f(int n,int k){ if(n==1){ return 0;} else return (f(n-1,k)+k)%n; } int main(){ int n,k; cin>>n; k=3; cout< 这里写图片描述 当时写这道题快没时间了呃，随便贴了一下，后面改错。 #include #include using namespace std; int main(){ int i,j,k,t; int N,U,D; int height=0; cin>>N>>U>>D; for(i=1;i<10000;i++){ height+=U; if(height>N){ break;} height-=D; i++; } cout< 这里写图片描述 #include using namespace std; int n; char pre[60],in[60]; typedef struct node{ int data; struct node *lchild,*rchild; }BTnode; //还原二叉树 BTnode * restoreTree(char pre[],char in[],int n){ int i; char lpre[60],rpre[60]; char lin[60],rin[60]; //n1记录前序遍历序列左子树的长度，n2记录前序遍历序列右子树的长度 int n1=0,n2=0; int m1=0,m2=0; if(n==0) return NULL; BTnode *T=(BTnode *)malloc(sizeof(BTnode)); if(T==NULL) return NULL; T->data=pre[0]; //根节点 //通过中序遍历分成左子树和右子树 for(i=0;ilchild=restoreTree(lpre,lin,n1); T->rchild=restoreTree(rpre,rin,n2); return T; } int getDepth(BTnode *T){ int LD,RD; if(T==NULL) return 0; else{ LD=getDepth(T->lchild); RD=getDepth(T->rchild); return (LD>RD?LD:RD)+1; } } int main(){ cin>>n; //输入树的高度 cin>>pre; //前序 cin>>in; //中序 BTnode *T; T=restoreTree(pre,in,n); //建树 int height; height=getDepth(T); //求树的高度 cout< 这里写图片描述 单源最短路径，dijkstra算法。
这里还要考虑收费的影响，当两条路径相等的时候，比较一下花费。更新原点到各个点距离的时候同时更新一下原点到各个点的收费。 //prim，单源最短路径 #include #include #include #define inf 0x3f3f3f #define maxn 510 using namespace std; int n,m; int map[maxn][maxn]; int vis[maxn],dis[maxn]; //dis存储起点到各个点的最短距离 int money[maxn][maxn],cost[maxn]; void dijkstra(int s,int e){ int i,j,min,pos; memset(vis,0,sizeof(vis)); dis[s]=0; vis[s]=1; //起点 for(int i=0;idis[pos]+map[pos][j] && !vis[j]){ dis[j]=dis[pos]+map[pos][j]; cost[j]=cost[pos]+money[pos][j]; } else if(dis[j]==dis[pos]+map[pos][j] && cost[pos]+money[pos][j]>n>>m>>sta>>end){ //n个城镇，m条道路 for(int i=0;i>x>>y>>len>>spend; if(len

热门文章