本文主要是介绍算法设计与分析复习题 pta（第2章 递归算法设计技术），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
7-1 一元多项式的乘法与加法运算
#include<stdio.h>
int main()
{int n, m, a[3000] = {0}, a1[3000] = {0}, b[3000] = {0}, b1[3000] = {0};// 存放输入值int res[3000] = {0}, res1[3000] = {0}; // 存放乘积多项式运算结果int k = 0, k1 = 0, k2 = 0;int c[3000] = {0}, d[3000] = {0}; // 下标为指数，值为系数int ans1[3000] = {0}, ans11[3000] = {0}, ans2[3000] = {0}, ans22[3000] = {0};/// 存放输出结果scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d %d", &a[i], &a1[i]); /// a数组存放系数， a1数组存放指数c[ a1[i] ] += a[i]; /// 累加该指数的系数}scanf("%d", &m);for(int i = 0; i < m; i++){scanf("%d %d", &b[i], &b1[i]); /// b数组存放系数， b1数组存放指数c[ b1[i] ] += b[i]; /// 累加该指数的系数}k = 0;for(int i = 0; i < n; i++) /// 乘积多项式，系数相乘，指数相加{for(int j = 0; j < m; j++){res[k] = a[i] * b[j];res1[k] = a1[i] + b1[j];d[ res1[k] ] += res[k]; /// 累加该指数的系数k++;}}k1 = 0;for(int i = 2001; i >= 0; i--) /// 题目要求降幂输出{if( d[i] != 0 ){ans1[k1] = d[i]; /// 存放输出结果系数ans11[k1] = i; /// 存放输出结果指数k1++;}}for(int i = 0; i < k1; i++) /// 输出乘积多项式结果{printf("%d %d", ans1[i], ans11[i]);if(i < k1 - 1)printf(" ");}if(k1 == 0)printf("0 0");printf("\n");k2 = 0;for(int i = 2001; i >= 0; i--){if( c[i] != 0 ){ans2[k2] = c[i]; /// 存放输出结果系数ans22[k2] = i; /// 存放输出结果指数k2++;}}for(int i = 0; i < k2; i++) /// 输出和多项式结果{printf("%d %d", ans2[i], ans22[i]);if(i < k2 - 1)printf(" ");}if(k2 == 0)printf("0 0");printf("\n");return 0;
}
7-2 整数分解为若干项之和
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int a[30];
int n;
int Count = 0;
void fenjie(int index, int start, int num){
int i;
if (num!=0){for (i=start;i<=num;i++) {a[index]=i;start=i;fenjie(index+1,start,num-i); }
}
else
{printf("%d=",n);printf("%d",a[0]);for (i=1;i<index;i++){printf("+%d",a[i]);}Count++;if (Count!=4&&a[index-1]!=n)printf(";");if (Count==4){printf("\n");Count=0;}
}
}
int main()
{
scanf("%d",&n);
fenjie(0,1,n);
return 0;
}7-3 列车调度
#include<stdio.h>
int a[1000000];
int main()
{
int n;
scanf("%d",&n);
int i,m,j,top=0;
for(i=0;i<n;i++){scanf("%d",&m);if(top==0||a[top-1]<m){ a[top++]=m;}else //二分查找{ int high=top-1,low=0,mid;while(low<=high){mid=(low+high)/2;if(a[mid]>m){high=mid-1;}else{low=mid+1;}}//a[mid]=m;a[low]=m;}
}printf("%d",top); //轨道数
}
7-4 多项式A除以B
#include<cstdio>#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
double a[100010],b[100010],c[100010];
void fun(double arr[],int x)
{int num=0;for(int i=0;i<=x;i++)if(abs(arr[i])+0.05>=0.1)num++;//四舍五入 printf("%d",num);if(num==0) printf(" 0 0.0");for(int i=x;i>=0;i--){if(abs(arr[i])+0.05>=0.1)printf(" %d %.1lf",i,arr[i]);}}int main(){int n,m,x;cin>>n;int index1=-0x3f3f3f,index2=-0x3f3f3f;//两个多项式的最大指数 for(int i=1;i<=n;i++){scanf("%d",&x);scanf("%lf",&a[x]);if(x>index1)index1=x;}cin>>m;for(int i=1;i<=m;i++){scanf("%d",&x);scanf("%lf",&b[x]);if(x>index2)index2=x;}int temp=index1-index2;//商的最大指数while(index1-index2>=0){double q=a[index1]/b[index2];//cout<<index1<<" "<<index2<<" "<<q<<endl;c[index1-index2]=q;for(int i=index1,j=index2;i>=0&&j>=0;i--,j--){a[i]-=b[j]*q;}while(a[index1]==0)index1--;//系数为0 } fun(c,temp);cout<<endl;fun(a,index1);return 0;}7-5 阅览室
#include<stdio.h>
int main()
{int N, h, m, t, count, id, i, j;int arr[1005][2];char size;scanf("%d", &N);for (i = 0; i < N; i++){count = 0, t = 0;for (j = 0; j < 1005; j++){arr[j][0] = 0;arr[j][1] = 0;}scanf("%d %c %d:%d", &id, &size, &h, &m);while (id){if (size == 'S'){arr[id][0] = 1;arr[id][1] = h * 60 + m;}else if (size == 'E' && arr[id][0] == 1){t += h * 60 + m - arr[id][1];arr[id][0] = 0;count++;}scanf("%d %c %d:%d", &id, &size, &h, &m);}if (count > 1)printf("%d %.0lf\n", count, (double)t / count);elseprintf("%d %d\n", count, t);}return 0;
}
7-6 连续因子
#include<stdio.h>
#include<math.h>
int prime(int n)// 判断素数
{int i;for(i=2; i<=sqrt(n); i++){if(n%i==0)return 0;//返回0不为素数}return 1;//返回1为素数
}
int main()
{long long n,i,j;scanf("%lld",&n);int start=0,l=0;long long s=1;//特判：如果n为素数，则只有因数1和nif(prime(n))printf("1\n%d\n",n);else{for(i=2; i<=sqrt(n); i++){s=1;//s记录乘积for(j=i; s*j<=n; j++){s=s*j;if(n%s==0&&j-i+1>l){start=i;//记录连续序列左端点l=j-i+1;//不断更新l的值，求出最大的l}}}printf("%d\n",l);//按照输出格式输出，连续因子 最长序列的开始点为start，长度为lfor(i=start; i<start+l; i++){if(i==start)printf("%lld",i);elseprintf("*%lld",i);}printf("\n");}return 0;
}7-7 倒数第N个字符串
#include<stdio.h>
#include<math.h>
int main(){
int l,n,t;
scanf("%d%d",&l,&n);
int xx[l],i;
t = pow(26,l)-n;
for(i=0;i<l;i++){ xx[i]=t%26; t/=26;
}
for(i=l-1;i>=0;i--)printf("%c",'a'+xx[i]);
return 0;
}7-8 小字辈
#include <stdio.h>
int father[100000];
int beifen[100000]={0};
int Find(int m)
{if(father[m]==-1)beifen[m]=1;if(beifen[m]==0)beifen[m]=Find(father[m])+1;return beifen[m];
}
int main()
{int n,i,j;int max=0,flag=0,count=0;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&father[i]);}for(i=1;i<=n;i++){Find(i);}for(i=1;i<=n;i++){if(beifen[i]>max)max = beifen[i];}printf("%d\n",max);for(i=1;i<=n;i++){if(beifen[i]==max)count++;}for(i=1;i<=n;i++){if(beifen[i]==max){if(flag==count-1)printf("%d",i);else{printf("%d ",i);flag++;}}}
}7-9 h0122. 对称顺序
#include<stdio.h>
int main(void) {char a[50][50];int n = 0;int sum = 1;scanf("%d", &n);while (n!=0) {for (int i = 0; i < n; i++) {scanf("%s", a[i]);}printf("SET %d\n", sum);for (int i = 0; i < n; i++) {if (i % 2 == 0) {printf("%s\n", a[i]);}}for (int i = n-1; i >= 0 ; i--) {if (i % 2 != 0) {printf("%s\n", a[i]);}}scanf("%d", &n);sum++;}return 0;
}
7-10 h0116. 逆波兰表达式
#include<iostream>
using namespace std;
double exp(){char s[20];cin >> s;switch(s[0]){case '+':return exp()+exp();case '-':return exp()-exp();case '*':return exp()*exp();case '/':return exp()/exp();default: return atof(s);break;}
}
int main(){printf("%.6lf",exp());return 0;
}7-11 h0120. 递归实现排列型枚举
#include<stdio.h>
int a[10],book[10]={0};
int n;
void dfs(int x){
int i;
if(x>n){for(i=1;i<=n;i++)printf("%d ",a[i]);printf("\n");return;
}
for(i=1;i<=n;i++){if(!book[i]){book[i]=1;a[x]=i;dfs(x+1);book[i]=0;}
}
}
int main(){
int i;
while(scanf("%d",&n)!=EOF){dfs(1);
}
return 0;
}
7-12 h0119. 递归实现组合型枚举
#include <stdio.h>
#include <math.h>
int a;
int d;
void dfs(int b,int sum,int c){if(sum+a-b<d){return;}if(sum == d){for(int i=0;i<a;i++){if((c>>i)&1){printf("%d ",i+1);}}printf("\n");return;}dfs(b+1,sum+1,c|1<<b);dfs(b+1,sum,c);
}
int main()
{scanf("%d %d",&a,&d);dfs(0,0,0);return 0;
}7-13 h0109. 阶乘
#include<bits/stdc++.h>
using namespace std;unsigned long long del(int n){unsigned long long ans = 1;for(int i=1;i<=n;i++){ans *= i;if(ans>62270208000){cout<<"Overflow!\n";return 0;}}if(ans<10000){cout<<"Underflow!\n";return 0;}cout<<ans<<endl;return 0;
}int main()
{int n;while((scanf("%d",&n))!=EOF)del(n);return 0;
}7-14 h0110. 函数运行的乐趣
#include<bits/stdc++.h>
using namespace std;
int wa[21][21][21];
int w(int a,int b,int c){if(a<=0||b<=0||c<=0){wa[0][0][0]=1;return wa[0][0][0];}if(a>20||b>20||c>20){if(wa[20][20][20] == -1) wa[20][20][20] = w(20,20,20);return wa[20][20][20];}if(a<b&&b<c){if(wa[a][b][c]==-1) wa[a][b][c] =w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);return wa[a][b][c];}if(wa[a][b][c]==-1) wa[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1);return wa[a][b][c];
}int main()
{int x,y,z;memset(wa,-1,sizeof(wa));while(1){cin>>x>>y>>z;if(x==-1&&y==-1&&z==-1) break;printf("w(%d, %d, %d) = %d\n",x,y,z,w(x,y,z));}return 0;
}7-15 h0111. 简单的加法（14分得8分）
#include<bits/stdc++.h>
using namespace std;
int p,q;
inline int read(){int x=0,f=1;char o=getchar();while(o<'0'||o>'9'){if(o=='-') f=-1; o=getchar();}while(o>='0'&&o<='9'){x=(x<<3)+(x<<1)+o-'0';o=getchar();}return x*f;
}
inline void write(int x){if(x>9) write(x/10);putchar(x%10+'0');
}
int f(int x){if(x%10>0) return x%10;else if(x==0) return 0;else return f(x/10);
}
int s(int p,int q){int ans=0;for(int i=p;i<=q;i++){ans+=f(i);}return ans;
}int main()
{while(1){// scanf("%d%d",&p,&q);p=read();q=read();if(p<0&&q<0) break;write(s(p,q));putchar('\n');// cout<<s(p,q)<<endl;}return 0;
}这篇关于算法设计与分析复习题 pta（第2章 递归算法设计技术）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
