【c++百日刷题计划】 ———— DAY3，带你轻松学习算法

文章目录

第一题【深基7.例3】闰年展示
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
- 提示
- 解题思路
- 参考代码
第二题 A+B Problem（高精）
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
- 样例 #2
- - 样例输入 #2
  - 样例输出 #2
- 解题思路
- 参考代码
第三题 A*B Problem
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
- 提示
- 解题思路
- 参考代码
第四题 [NOIP1998 普及组] 阶乘之和
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
- 提示
- 解题思路
- 参考代码

第一题【深基7.例3】闰年展示题目描述

输入 x , y x,y x,y，输出 [ x , y ] [x,y] [x,y] 区间中闰年个数，并在下一行输出所有闰年年份数字，使用空格隔开。

输入格式

输入两个正整数 x , y x,y x,y，以空格隔开。

输出格式

第一行输出一个正整数，表示 [ x , y ] [x,y] [x,y] 区间中闰年个数。

第二行输出若干个正整数，按照年份单调递增的顺序输出所有闰年年份数字。

样例 #1 样例输入 #1

1989 2001

样例输出 #1

3
1992 1996 2000

提示

数据保证， 1582 ≤ x < y ≤ 3000 1582le x < y le 3000 1582≤x 解题思路

1）简单的判断闰年问题，判断是闰年记录下次数，记下年份，然后输出。

参考代码

#include
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<
		cout< 
第二题 A+B Problem（高精） 
题目描述 
高精度加法，相当于 a+b problem，不用考虑负数。 
输入格式 
分两行输入。
    
     
      
       
        a
       
       
        ,
       
       
        b
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         500
        
       
      
      
       a,b leq 10^{500}
      
     
    a,b≤10500。 
输出格式 
输出只有一行，代表 
    
     
      
       
        a
       
       
        +
       
       
        b
       
      
      
       a+b
      
     
    a+b 的值。 
样例 #1 
样例输入 #1 
1
1
 
样例输出 #1 
2
 
样例 #2 
样例输入 #2 
1001
9099
 
样例输出 #2 
10100
 
解题思路 
 
 1）注意数据范围，不能用简单的加法，要使用高精度算法。
2）用数组分别存储高精度数的每一位，计算同一位的结果。
3）或结果大于10，向前一项进一，若结果小于10，保持不变。
4）继续计算下一位，直到运算结束. 
 
参考代码 
#include
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*B Problem 
题目描述 
给出两个非负整数，求它们的乘积。 
输入格式 
输入共两行，每行一个非负整数。 
输出格式 
输出一个非负整数表示乘积。 
样例 #1 
样例输入 #1 
1 
2
 
样例输出 #1 
2
 
提示 
每个非负整数不超过 
    
     
      
       
        1
       
       
        
         0
        
        
         2000
        
       
      
      
       10^{2000}
      
     
    102000。 
解题思路 
 
 1）注意数据范围，不能用简单的乘法，要使用高精度算法。
2）用数组分别存储高精度数的每一位，计算同一位的结果。
3）或结果大于10，向前一项进一，若结果小于10，保持不变。
4）继续计算下一位，直到运算结束. 
 
参考代码 
#include
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< 
第四题 [NOIP1998 普及组] 阶乘之和 
题目描述 
用高精度计算出 
    
     
      
       
        S
       
       
        =
       
       
        1
       
       
        !
       
       
        +
       
       
        2
       
       
        !
       
       
        +
       
       
        3
       
       
        !
       
       
        +
       
       
        ⋯
       
       
        +
       
       
        n
       
       
        !
       
      
      
       S = 1! + 2! + 3! + cdots + n!
      
     
    S=1!+2!+3!+⋯+n!（
    
     
      
       
        n
       
       
        ≤
       
       
        50
       
      
      
       n le 50
      
     
    n≤50）。 
其中 ! 表示阶乘，定义为 
    
     
      
       
        n
       
       
        !
       
       
        =
       
       
        n
       
       
        ×
       
       
        (
       
       
        n
       
       
        −
       
       
        1
       
       
        )
       
       
        ×
       
       
        (
       
       
        n
       
       
        −
       
       
        2
       
       
        )
       
       
        ×
       
       
        ⋯
       
       
        ×
       
       
        1
       
      
      
       n!=ntimes (n-1)times (n-2)times cdots times 1
      
     
    n!=n×(n−1)×(n−2)×⋯×1。例如，
    
     
      
       
        5
       
       
        !
       
       
        =
       
       
        5
       
       
        ×
       
       
        4
       
       
        ×
       
       
        3
       
       
        ×
       
       
        2
       
       
        ×
       
       
        1
       
       
        =
       
       
        120
       
      
      
       5! = 5 times 4 times 3 times 2 times 1=120
      
     
    5!=5×4×3×2×1=120。 
输入格式 
一个正整数 
    
     
      
       
        n
       
      
      
       n
      
     
    n。 
输出格式 
一个正整数 
    
     
      
       
        S
       
      
      
       S
      
     
    S，表示计算结果。 
样例 #1 
样例输入 #1 
3
 
样例输出 #1 
9
 
提示 
【数据范围】 
对于 
    
     
      
       
        100
       
       
        %
       
      
      
       100 %
      
     
    100% 的数据，
    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        50
       
      
      
       1 le n le 50
      
     
    1≤n≤50。 
解题思路 
 
 1）这道题目融合了前面两道题目，同时使用了高精度加法和乘法。 
 
参考代码 
#include
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<

【c++百日刷题计划】 ———— DAY3，带你轻松学习算法

Java相关栏目本月热门文章