algorithm复习版终极版填空_在线真题试卷与模拟练习_algorithm复习版终极版填空

求最大公约数 #include <iostream> using namespace std; int gcd(int m,int n){ int r; do{ _1_=m%n; _2_=n;n=r; }while(r>0); return m; } int main(int argc,char *argv[]) { int m,n; cin>>m>>n; cout<<gcd(m,n)<<endl; return 0; }

#define MAX 50 using namespace std; int main(int argc,char *argv[]) { int arr[MAX][MAX] = { 0 };//这里限制了幻方的大小，大家可以自行修改 int n = 0; int k = 2; cin>>n;//n得是奇数， arr[0][n / 2] = 1;//这个就是初始的K arr[n-1][n/2+1]=2;//进一步限定答案 int a = 0;//行 int b = n / 2;//列 for (int i = 1; i <= n * n; i++) { if (a == 0 && b != n - 1)//在第一行但不在最后一列 { arr[n - 1][b + 1] = k; a = n - 1; b = b + 1; } else if (a != 0 && b == n - 1)//不在第一行但在最后一列 { arr[a - 1][0] = k; a = a - 1; b = 0; } else if (a == 0 && b == n - 1)//在第一行最后一列 { arr[a + 1][b] = k; a = a + 1; } else if (a != 0 && b != n - 1)//既不在第一行也不在最后一列 { if (arr[a - 1][b + 1] == 0) { arr[__1__][b + 1] = k; a = a - 1; b = b + 1; } else {//撞衫后，放当前那个的数下面 arr[a + 1][b] = k; a = a + 1; } } k++; } for (int i = 0; i < n; i++)//打印数组->幻方 { for (int j = 0; j < n; j++) { printf("%5d", __2__); } printf("\n"); } return 0; }

没有拆分为连续整数 #include <iostream> using namespace std; int main(int argc, char *argv[]) { int n,i,j; scanf("%d",&n); int c=0,s; for(i=1;i<=(n-1)/2;i++) { s=0; for(j=i;j<=(n+1)/2;j++) { s=s+j; if(s>=n) { if(s==n){ c++; printf("%d:%d+...+%d\n",c,i,j); } } } } return 0; }

汽水瓶，某学院有m个学生参加春游，休息时喝汽水。商家公告：买一瓶汽水定价1.40元，喝一瓶汽水（瓶不带走）1.00元。为节约资源，规定3个空瓶可换回一瓶汽水(1.4*2/3=0.93)，或20个空瓶可换回7瓶汽水。1.4*13/20=0.91 为方便顾客，可先借后还。例如借一瓶汽水还3个空瓶，或借七瓶汽水还20个空瓶 #include <stdio.h> int main() { long m, t, x, y; scanf("%ld", &m); _1_= m / 20; t = m - 20 * x; y = _2_ / 3; t = m - 20 * x - 3 * y; printf("%.2f\n",(13 * x + 2 * y)*1.40 + t); return 0; }

超越方程 #include <stdio.h> #include <iostream> #include <iomanip> #include<math.h> using namespace std; double fny(double x) // 自定义函数fny，用来定义方程式 {return 2*pow(x,2)*pow(sin(x),7)+3*pow(x,0.5)*cos(x)-exp(x)/5;} int main() { int i,t=0; double a,b,x,x1,x2,c; //printf(" 求方程在[a,b]中的一个解，请确定a,b: "); //scanf("%lf%lf",&a,&b); a=2,b=3; for(x=a;x<=b;x+=0.1) // 初步扫描 if(fny(x)*fny(b)<=__1__) // 调用自定义函数fny() {x1=x;x2=b;t=1;break;} if(t==0) { printf("无解!");return 0;} c=0.01; for(i=2;i<=9;i++) // 逐位求精 {for(x=x1;x<=x2;x+=c) if(fny(x)*fny(x2)>0) // 如果变为同号，缩小循环范围 {x2=x;x1=x-c;break;} // 调整循环的初值x1与终值x2 c=__2__; // 缩小循环步长求精 } x=(x1+x2)/2; int p; cin>>p; cout<<fixed; cout<<setprecision(p)<<x<<endl; //printf(" 所求方程的一个解为x=%.8f",x); // 输出解，小数点后6位 return 0; }

//埃氏筛法 /* 详细列出算法如下：列出2以后的所有序列： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 标出序列中的第一个素数，也就是2，序列变成： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 将剩下序列中，划掉2的倍数，序列变成： 2 3 5 7 9 11 13 15 17 19 21 23 25 如果现在这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。本例中，因为25大于2的平方，我们返回第二步：剩下的序列中第一个素数是3，将主序列中3的倍数划掉，主序列变成： 2 3 5 7 11 13 17 19 23 25 我们得到的素数有：2，3 25仍然大于3的平方，所以我们还要返回第二步：现在序列中第一个素数是5，同样将序列中5的倍数划掉，主序列成了： 2 3 5 7 11 13 17 19 23 我们得到的素数有：2，3，5 。因为23小于5的平方，跳出循环. */ #include<iostream> using namespace std; const int N = 1e6+10; int prime[N],cnt; bool st[N]; void get_primes(int n) { // 从2开始遍历到n，因为0和1不是素数 for(int i=2;i<=n;i++) { // 如果st[i]为false，说明i是素数 if(__1__) { // 将素数i存入prime数组，并将素数计数器cnt加1 prime[cnt++]=i; // 标记i的所有倍数为合数 for(int j=i+i;j<=n;j+=i) st[_2_]=true; } } } int main(){ int n; cin>>n; get_primes(n); cout<<cnt<<endl; return 0; }

佩尔方程 #include <iostream> #include <math.h> using namespace std; int main(int argc,char *argv[]) { int n; cin>>n; long long x,y; for(y=1;y<=10000000;y++) { double x_squared= 1 + n * pow((double)y,2.0); x= __1__(sqrt(x_squared)); if(x*x-n *__2__((double)y,2.0)==1) { x = sqrt(x_squared); cout<<"x="<<x<<endl; cout<<"y="<<y<<endl; return 0; } } cout<<"no"<<endl; return 0; }

分数不等式 m1<1/2+sqrt(2)/3+sqrt(3)/4…......sqrt(n)/(n+1)<m2 输入正整数m1和m2 输出n的区间 #include <iostream> #include <cmath> using namespace std; int main(int argc,char *argv[]) { int m1,m2; cin>>m1>>m2; double s=0; int i=0; while(s<=m1) { i++; s=s+sqrt(i)/(i+1); } int c=i; do{ i++; s=s+sqrt(i)/(i+1); }while(__1__<=m2); int d=i-1; cout<<__2__<<endl<<d; return 0; }

完美表达式 #include <iostream> #include "math.h" using namespace std; int main(int argc,char *argv[]) { int a,b,c,d,e,f,z,g[10],k,t,m,n,x; n=0; scanf("%d",&f); for(a=2; a<=9; a++) for(b=2; b<=9; b++) for(c=2; c<=9; c++) for(d=102; d<=987; d++) for(e=2; e<=9; e++) { for(t=1,k=1; k<=b; k++) t=t*a; z=(d*e+f-t)*c; if(z<10 || z>98) continue; for(x=0; x<=9; x++) g[x]=0; g[__1__]++; g[b]++; g[c]++; g[e]++; g[f]++; g[d%10]++; g[d/100]++; __2__=(d/10)%10; g[m]++; g[z%10]++; g[z/10]++; for(t=0,x=0; x<=9; x++) if(g[x]!=1) { t=1; break; } if(t==0) { n++; } } if(n==0) cout<<0; else{ cout<<n; } return 0; }

刘邦茫然而不知其数。你呢？你是一位优秀的程序员，请你帮刘邦解决这一问题。输入要求由键盘输入A,B,C,D,E,F,G,H,a,b,c,d,e,f,g,h十六个数，分别代表每A人一列余a、每B人一列余b、每C人一列余c、每D人一列余D、每E人一列余e、每F人一列余f、每G人一列余g、每H人一列余h，其中A,B,C,D,E,F,G,H为互不相等的质数输出输出总兵士数，要求输出满足条件的最小的一个，但要满足8种排法的每一种排法至少可排一列。（保证给的数据，有结果且计算的结果不会超过2的63次方）样例输入复制 2 3 5 7 11 13 17 19 1 1 1 1 1 1 1 2 #include <iostream> using namespace std; int main(int argc,char *argv[]) { int a[9], b[9]; for (int i = 1;i <= 8;i++) { cin >> a[i]; } for (int i = 1;i <= 8;i++) { cin >> b[i]; } for (int i = 1;;i++) { if (i % a[1] == b[1] && i % a[2] == b[2] && i % a[3] == b[3] && i % a[4] == b[4] && i % a[5] == b[5] && i % a[6] == b[6] && i % a[7] == b[7] && i % a[8] == b[8]) { cout << __1__; __2__; } } return 0; }

还是猴子摘桃问题，但是拓展为n天和每次剩余m个桃子猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了m个。第二天早上又将剩下的桃子吃掉一半，又多吃了m个。以后每天早上都吃了前一天剩下的一半m个。到第n天早上想再吃时，就只剩d个桃子了。求第一天共摘多少个桃子？输入输入n和m，最后一天只剩下d个桃子，以上均为正整数输出最初有多少桃子样例输入 6 7 8 样例输出 690 #include <iostream> using namespace std; int main(int argc,char *argv[]) { int n, m, d; cin >> n >> m >> d; for (int day =__1__; day >= 1; day --) { d = (d + m) * 2; } cout << d; return 0; }

没有格雷码 #include <iostream> #include <vector> #include <math.h> using namespace std; vector<string> getGray2(int n) { vector<string>v(pow(2,n)); if(n==1) { v[0]='0'; v[1]='1'; return v; } vector<string>prev=getGray2(n-1); for(int i=0; i b; string x; int n; cin>>n; b=getGray2(n); for(vector<string>::iterator it=b.begin();it!=b.end();++it) { cout<<*it<<endl; } return 0; }

二分查找 #include <iostream> using namespace std; int BiSearch(int a[],int left,int right,int x) {//a数组升序 int m; if(left>right) return -1; m=(left+right)/2; if(a[m]==x) return m; if(x<a[m])//左边 return BiSearch(a,__1__,m-1,x); else//右边 return BiSearch(a,m+1,__2__,x); } int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int main(int argc, char *argv[]) { int a[]={4,3,5,6,23,4,6,8,9}; qsort(a,8,sizeof(int),compare); cout<<BiSearch(a,0,7,4); return 0; }

归并排序 #include <iostream> #include <vector> using namespace std; // 合并两个有序子数组 void merge(vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; // 左子数组的大小 int n2 = right - mid; // 右子数组的大小 // 创建临时数组 vector<int> L(n1); vector<int> R(n2); // 复制数据到临时数组 L[] 和 R[] for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; // 合并临时数组到 arr[left..right] int i = 0; // 初始化第一个子数组的索引 int j = 0; // 初始化第二个子数组的索引 int k = left; // 初始化合并子数组的索引 while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; _1_; } else { arr[k] = R[j]; j++; } k++; } // 复制 L[] 中剩余的元素 while (i < n1) { arr[k] = L[i]; i++; k++; } // 复制 R[] 中剩余的元素 while (j < n2) { arr[k] = R[j]; j++; k++; } } // 归并排序函数 void mergeSort(vector<int>& arr, int left, int right) { if (left < right) { // 找到中间点 int mid = (left + right) / 2; // 递归排序左右两半 mergeSort(arr, left, mid); mergeSort(arr,_2_, right); // 合并两个有序子数组 merge(arr, left, mid, right); } } // 辅助函数：打印数组 void printArray(const vector<int>& arr) { for (int i = 0; i < arr.size(); i++) cout << arr[i] << " "; cout << endl; } // 主函数 int main() { vector<int> arr = {12, 11, 13, 5, 6, 7}; cout << "original array:\n"; printArray(arr); mergeSort(arr, 0, arr.size() - 1); cout << "\nsorted array:\n"; printArray(arr); return 0; }

没有快速排序 #include <cstdio> #include <cstdlib> #include <ctime> #include <iostream> //typedef int DataType; using namespace std; typedef struct { int key; }DataType; void BubbleSort(DataType a[],int n) { int i,j,flag=1; DataType temp; for(i=0;i<n-1;i++) { for(j=0;j<n-1-i;j++) if(a[j].key>a[j+1].key) { temp.key=a[j].key; a[j].key =a[j+1].key; a[j+1].key=temp.key; } } } int Division(int a[],int left,int right) { int base =a[left]; while(left<right) { while(left<right&&a[right]>base) --right; a[left]=a[right]; while(left<right&&a[left]<base) ++left; a[right]=a[left]; } a[left]=base; return left; } void QuickSort(int a[],int left,int right) { int i; if(left<right) { i=Division(a,left,right); QuickSort(a,left,i-1); QuickSort(a,i+1,right); } } int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } void printArray(int a[],int n) { for (int i = 0; i < n; i++) cout << a[i] << " "; cout << endl; } int main() { int i,n=348; double dif; time_t start,end; DataType t1[348]; int t2[348]; for(i=0;i<n;i++) { t1[i].key=rand(); t2[i]=t1[i].key; } time(&start); //BubbleSort(t1,n); QuickSort(t2,0,n-1); printArray(t2,n); time(&end); dif=difftime(end,start); printf("bubble:%.2fs\n",dif); return 0; }

斐波那契数列，用动态规划优化 #include <iostream> using namespace std; int a[100];//100个数以内 int f(int n){ if(a[n]==__1__) __2__=f(n-1)+f(n-2); return a[n]; } int main(int argc,char *argv[]) { a[0]=a[1]=a[2]=1; cout<<f(10); return 0; }

数塔问题 #include <iostream> using namespace std; int main(int argc, char *argv[]) { int n; int s[101][101]; cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { cin>>s[i][j]; } } for(int r=n-2;r>=0;r--) { for(int c=0;c<=r;c++) { if(s[r+1][c]>s[r+1][c+1]) { s[_1_][_2_]+=s[r+1][c]; } else { s[r][c]+=s[r+1][c+1]; } } } cout<<s[0][0]<<endl; return 0; }

0-1背包问题 #include<iostream> #include<cstring> using namespace std; int max(int a,int b) { return a>b?a:b; } int main() { // dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值 // m 表示物品的数量，T 表示背包的容量 // w[i] 表示第 i 个物品的重量，val[i] 表示第 i 个物品的价值 // i 和 j 为循环变量 int dp[101][1001],m,T,w[101],val[101],i,j; // 循环读取输入，直到输入结束 while(cin>>T>>m) { // 读取每个物品的重量和价值 for(i=1;i<=m;i++) { cin>>w[i]>>val[i]; } // 初始化 dp 数组，将所有元素置为 0 memset(dp,0,sizeof(dp)); // 遍历每个物品 for(i=1;i<=m;i++) { // 遍历背包的每个容量 for(j=0;j<=T;j++) { // 如果当前背包容量 j 大于等于第 i 个物品的重量 w[i] if(j>=w[i]) // 选择放入或不放入第 i 个物品，取价值较大的情况 dp[i][j]=max(dp[_1_][j],dp[i-1][j-w[i]]+_2_); else // 当前背包容量不足以放入第 i 个物品，只能不放入 dp[i][j]=dp[i-1][j]; } } // 输出前 m 个物品放入容量为 T 的背包中所能获得的最大价值 cout<<dp[m][T]<<endl; } return 0; }

最大字段和 #include <stdio.h> #include <math.h> #include <string.h> int _Max(int x,int y){return x>y?x:y;} int number[200001],sum[200001]; int main(){ // 定义循环变量 i 和 j，i 用于遍历数组，j 在此代码中未使用 int i,j; // n 表示输入序列的长度，maxx 用于存储最大字段和，初始化为 0 int n,maxx=0; // 从标准输入读取序列的长度 scanf("%d",&n); // 循环读取序列中的每个元素，并存储到 number 数组中 for(i=1;i<=n;i++) scanf("%d",&number[i]); // 初始化 sum 数组的第一个元素为序列的第一个元素 sum[1]=number[1]; // 初始化最大字段和为序列的第一个元素 maxx=sum[1]; // 从第二个元素开始遍历序列 for(i=_1_;i<=n;i++){ // 状态转移方程：当前位置的最大字段和为前一个位置的最大字段和加上当前元素 // 或者仅当前元素，取两者中的较大值 sum[i]=_Max(sum[_2_]+number[i],number[i]); // 更新最大字段和 maxx=_Max(sum[i],maxx); } // 输出最大字段和 printf("%d",maxx); }

深度优先搜索 #include <stdio.h> #include <queue> using namespace std; #define maxv 9999 int a[100][100]; int n,ne,v[100]={0};// 顶点一般用来记录改点是否已访问 int GetFirstVex(int x) { int i; for(i=1;i<=n;i++) if(a[x][i]>0&&a[x][i]<maxv) return i; return -1; } int GetNextVex(int x,int w) { int i; for(i=w+1;i<=n;i++) if(a[x][i]>0&&a[x][i]<maxv) return i; return -1; } void dfs(int x) { // 用于存储当前顶点的邻接顶点编号 int w; // 打印当前顶点对应的字母标签，假设顶点编号从 1 开始，通过加 64 转换为 ASCII 码对应的字母 printf("%c",x+64); // 标记当前顶点已被访问，v 数组用于记录顶点的访问状态 v[x]=1; // 获取当前顶点的第一个邻接顶点编号，如果不存在则返回 -1 w=GetFirstVex(x); // 当存在邻接顶点时进行循环 while(w!=-1) { // 检查邻接顶点是否未被访问 if(v[w]!=1)// 未访问 // 对未访问的邻接顶点递归调用 dfs 函数进行深度优先搜索 dfs(w); // 获取当前顶点的下一个邻接顶点编号，如果不存在则返回 -1 w=GetNextVex(_1_,_2_); } } void bfs(int x) { queue<int> my; int w,u; printf("%c",x+64); v[x]=1; my.push(x); while(!my.empty()) { u=my.front(); my.pop(); w=GetFirstVex(u); while(w!=-1) { if(!v[w]) { printf("%c",w+64); v[w]=1; my.push(w); } w=GetNextVex(u,w); } } } int main(int argc, char *argv[]) { int i,j,x,y,c; scanf("%d%d",&n,&ne); for(i=0;i<100;i++) for(j=0;j<100;j++) if(i!=j) a[i][j]=0; else a[i][j]=0; for(i=0;i<ne;i++) { scanf("%d%d%d",&x,&y,&c); a[x][y]=c; } dfs(1); return 0; }