第一题【深基7.例3】闰年展示
题目描述
输入 x , y ，输出 [ x , y ] 区间中闰年个数，并在下一行输出所有闰年年份数字，使用空格隔开。
输入格式
输入两个正整数 x , y ，以空格隔开。
输出格式
第一行输出一个正整数，表示 [ x , y ] 区间中闰年个数。
第二行输出若干个正整数，按照年份单调递增的顺序输出所有闰年年份数字。
样例 #1
样例输入 #1
1989 2001
样例输出 #1
3 1992 1996 2000
提示
数据保证，1582 ≤ x < y ≤ 3000 。
解题思路
1）简单的判断闰年问题，判断是闰年记录下次数，记下年份，然后输出。
参考代码
#include<bits/stdc++.h> using namespace std; int ans[1500]; bool year(int n) { if(n%4==0&&n%100!=0) return 1; if(n%400==0)return 1; return 0; } int main() { int begin,end; cin>>begin>>end; int cnt=0; for(int i=begin;i<=end;i++) { if(year(i)) { ans[cnt++] = i; } } cout<<cnt<<endl; for(int i=0;i<cnt;i++) { cout<<ans[i]<< " "; } return 0; }
第二题 A+B Problem（高精）
题目描述
高精度加法，相当于 a+b problem，不用考虑负数。
输入格式
输出格式
输出只有一行，代表 a + b 的值。
样例 #1
样例输入 #1
1 1
样例输出 #1
2
样例 #2
样例输入 #2
1001 9099
样例输出 #2
10100
解题思路
1）注意数据范围，不能用简单的加法，要使用高精度算法。
2）用数组分别存储高精度数的每一位，计算同一位的结果。
3）或结果大于10，向前一项进一，若结果小于10，保持不变。
4）继续计算下一位，直到运算结束.
参考代码
#include<bits/stdc++.h> using namespace std; int a[250],b[250]; int main() { string str1,str2; int len1,len2,len; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cin>>str1>>str2; len1=str1.size(); len2=str2.size(); for(int i=0;i<=len1;i++) { a[i]=str1[len1-i]-'0'; } for(int i=0;i<=len2;i++) { b[i]=str2[len2-i]-'0'; } len=max(len1,len2); for(int i=1;i<=len;i++) { a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; } len++; while((a[len]==0)&&(len>1)) len--; for(int i=len;i>=1;i--) cout<<a[i]; return 0; }
第三题 A*B Problem
题目描述
给出两个非负整数，求它们的乘积。
输入格式
输入共两行，每行一个非负整数。
输出格式
输出一个非负整数表示乘积。
样例 #1
样例输入 #1
1 2
样例输出 #1
2
提示
每个非负整数不超过
。
解题思路
1）注意数据范围，不能用简单的乘法，要使用高精度算法。
2）用数组分别存储高精度数的每一位，计算同一位的结果。
3）或结果大于10，向前一项进一，若结果小于10，保持不变。
4）继续计算下一位，直到运算结束.
参考代码
#include<bits/stdc++.h> using namespace std; int a[50001],b[50001],c[50001]; int main() { string str1,str2; int len1,len2,len; cin>>str1>>str2; len1=str1.size(); len2=str2.size(); for(int i=0;i<=len1;i++) { a[i]=str1[len1-i]-'0'; } for(int i=0;i<=len2;i++) { b[i]=str2[len2-i]-'0'; } for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { c[i+j-1]+=a[i]*b[j]; c[i+j]+=c[i+j-1]/10; c[i+j-1]%=10; } } len=len1+len2+1; while((c[len]==0)&&(len>1)) len--; for(int i=len;i>=1;i--) cout<<c[i]; return 0; }
第四题 [NOIP1998 普及组] 阶乘之和
题目描述
输入格式
一个正整数 n 。
输出格式
一个正整数 S ，表示计算结果。
样例 #1
样例输入 #1
3
样例输出 #1
9
提示
【数据范围】
解题思路
- 1）这道题目融合了前面两道题目，同时使用了高精度加法和乘法。
参考代码
#include<bits/stdc++.h> using namespace std; int A[1005],B[1005]; int main() { int n; cin>>n; A[0]=B[0]=1; for (int i=2;i<=n;i++) { for (int j=0;j<100;j++) B[j]*=i; for (int j=0;j<100;j++) if (B[j]>9) { B[j+1] += B[j]/10; B[j]%=10; } for (int j=0;j<100;j++) { A[j]+=B[j]; if (A[j]>9) { A[j+1] += A[j]/10; A[j]%=10; } } } int k; for(k=100;k>=0&&A[k]==0;k--); for(int j=k;j>=0;j--) cout<<A[j]; return 0; }
