1、有序数组的中位数
两组升序排列的数组A[m]和B[n], 求他们的中位数。 注意，中位数的概念哦～相信你会百度一下的～
格式： 第一行输入数字m，接下来一行输入数组A[m], 第三行输入数字n，第四行输入数组B[n],接下来输出中位数。两个数组的长度都不超过1000。
注意，需要保留5位小数哦～所以，你设计函数的时候请设计成double类型哦～
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; /*void combine(int a[],int n,int b[],int m,int c[],int num){ int pa=0,pb=0,pc=0; while((pa<n)&&(pb<m)){ if(a[pa]<=b[pb]) c[pc++]=a[pa++]; else c[pc++]=b[pb++]; } while(pa<n) c[pc++]=a[pa++]; while(pb<m) c[pc++]=b[pb++]; }*/ void combine(int a[],int n,int b[],int m,int c[],int num){ //n,数组a的长度；m，数组b的长度；num，数组c的长度 int *pa,*pb,*pc,*pa_last,*pb_last; pa=a;//pa指向a的首元素地址 pb=b;//pb指向b的首元素地址 pc=c;//pc指向b的首元素地址 pa_last=a+n-1;//指向a的末尾 pb_last=b+m-1;//指向b的末尾 while((pa<=pa_last)&&(pb<=pb_last)){ if(*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; } while(pa<=pa_last) *pc++=*pa++; while(pb<=pb_last) *pc++=*pb++; } int main(){ int n,m,num; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); cin>>m; int b[m]; for(int i=0;i<m;i++) cin>>b[i]; sort(b,b+m); num=n+m; int c[num]={0}; combine(a,n,b,m,c,num); for(int i=0;i<num;i++) cout<<c[i]<<" "; cout<<endl; if(num%2==0) printf("%0.5lf ",(double(c[(num-1)/2])+c[(num+1)/2])/2); else printf("%0.5lf ",double(c[(num-1)/2])); return 0; }
2、回文质数
因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。 写一个程序来找出范围[a,b](5 ≤ a < b ≤ 100000000)( 一亿)间的所有回文质数。
输入包括一行，分别为两个整数a和b。
输出一个回文质数的列表，一行一个。
/* 1.偶数位数回文数（除11）必定不是质数，所以只要运行到10000000。 2.偶数肯定不是质数。 首先，整个讨论中，要排除一个数， 那就是11，11是最小的回文数，而且还是质数。 除了这个数之外， 11的整倍数有一个性质，那就是奇数位上数字之和=偶数位上数字之和。 一个数，如果是偶数长度回文数，那么同一个数x，必然出现在一次奇数位一次偶数位，所以这个偶数长度回文数可以被11整除。 举例来说： 123321符合条件 123321其中1出现在第1和6位，2出现在第2和5位，3出现在第3和4位。 这个数一定能被11整除，123321÷11=11211 综上所述：偶数位数回文数（除11）必定不是质数 */ #include<iostream> #include<stdio.h> #define M 10000000 bool A[M]; bool hw(int x){ int y=x,num=0; while(y){ num=num*10+y%10; y/=10; } if(num==x) return true; else return false; } void prime(int b){//筛法素数打表 int i,j; for(i=2;i<=b;i++){ if(!A[i]){ for(j=i+i;j<=b;j+=i) A[j]=1; } } } using namespace std; int main(){ int a,b; cin>>a>>b; if(b>10000000) b=10000000; prime(b); for(int i=a;i<=b;i++){ if(hw(i)&&!A[i]) cout<<i<<endl; } return 0; }
3、快速排序算法
#include<iostream> #define N 10 using namespace std; void quickSort(int a[],int,int); int main() { int a[N]; for(int i=0;i<N;i++) cin>>a[i]; quickSort(a,0,N-1); for(int i=0;i<N;i++) cout<<a[i]<<" "; return 0; } void quickSort(int s[], int l, int r){ if (l< r){ int i = l, j = r, x = s[l],t; while (i < j){ while(i < j && s[j]>= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quickSort(s, l, i - 1); // 递归调用 quickSort(s, i + 1, r); } }
4、出现次数最多的字符
一个字符串中可能包含a~z中多个字符串，并且可能会有重复，如 String data ="abcdaaa",这道字符串出现次数醉倒的字母就是a，出现了4次。现在用户输入一个字符串，我们需要求出出现次数最多的字母，并且求出次数，如果存在字母中出现最多的次数不唯一，但所有出现次数最多的字母及次数都要打印出来。
#include<iostream> #include<algorithm> #include<string.h> using namespace std; int main(){ char a[1000], b[30] = { 0 }; cin >> a; int charnum = strlen(a); int num[30] = { 0 }, sum = 0; b[0] = a[0]; num[0] = 1; int j; for (int i = 0; i < charnum; i++){ for ( j = 0; j < sum; j++){//查看之前是否有该字母， if (a[i] == b[j]){//有则对应+1 num[j]++; break; } } if (j >= sum){ b[sum] = a[i]; num[sum++] = 1; } } int maxi = 0;//找到最多字母的下标 for (int i = 0; i < sum; i++){ if (num[i] > num[maxi]) maxi = i; } for(int i=maxi;i<sum;i++) if(num[i]==num[maxi])//按照序列，如果有一样多的，则输出 cout << b[i] << " " << num[i] << endl; return 0; }
5、草药的价值
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
#include "stdio.h" #include "iostream" using namespace std; int w[105], val[105]; int dp[1005]; int main() { int t,m,res=-1; scanf("%d%d",&t,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&w[i],&val[i]); } for(int i=1;i<=m;i++) { for(int j=t;j>=0;j--) { if(j>=w[i]) { dp[j]=max(dp[j-w[i]]+val[i], dp[j]); } } } printf("%d",dp[t]); return 0; }