第一题【深基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; }