数列求和-加强版(C语言)
题目详情
给定某数字A(1≤A≤9)以及非负整数N(0≤N≤100000),求数列之和S=A+AA+AAA+⋯+AA⋯A(N个A)。例如A=1, N=3时,S=1+11+111=123。
要求
时间限制: 200 ms
内存限制: 64 MB
代码长度限制: 16 KB
输入格式:
输入数字A与非负整数N。
输出格式:
输出其N项数列之和S的值
输入样例:
1 3
输出样例:
123
个人思路
这道题的局限是当输出其N项之和S的值时发现S太大了,
拿最大的来说:当A=9,N=100000时,
S肯定是>最后一项999…9(总共有10^5个9)>9.0e+99999
int(最大为2.0e+31 - 1)还是long long(最大为2.0e+63 - 1)还是long double(最大为1.1e+4932)都不可以满足大于9.0e+99999
所以我打算采用竖式加法计算,这样可以把很大的一个S这样的数分成各个位数的值来存储,可以用一个数组记录各个位数的数值,而十进制中各个位数上的值又不可能超过10,所以避免了越界问题。可以先从低位到高位如此分位计算和分别考虑前一位的进位问题,然后再用数组元素来记录下各个位数上的数值。
不用动态链表或者可变数组的话需要考虑一开始定义数组的大小,而决定数组大小的又是当其N项数列之和S的值的最大值(也就是当A=9,N=100000时),此时的最大的数S是可以估算出来的,可以用下面方法:
-
我们知道9,99,999 …999999 的通项公式为an=10^n-1,
则1,11,111 的通项公式为(10^n-1)/9 ,
所以m,mm,mmm 的通项公式为m*(10^n-1)/9 (1≤m≤9);
接下来用等比数列的求和方法Sn=a1(1-q^n)/(1-q)可以估算出最大的数S。
求出来大概是总共有100002-1=100001位(参考下图计算结果)
所以最高位是第100001位,所以数组大小只需定义为int s[100001]={0}即可。 -
下面代码有相应的注释
#include <stdio.h>
//int在正数的范围是1~2147483647
int main(int argc,char const *argv[])
{
int A,N;
int s[100001]={0}; //记录结果的各个位数,通过计算当A=9,N=100000时,最多为100001个位数
scanf("%d %d",&A,&N);
int jinwei=0,num=N,weishu=0; //num来辅助各个位数的计算 , weishu用来判断输出时的有效最高位
//接下来进行竖式加法计算
for(int i=0; i<N+1 ;i++)//i=0表示从个位开始相加 ,且最多到N+1位(i的值最多为N)
{
s[i]=num*A+jinwei; //这步的最大值为9*100000=900000<2147483647,往前面的位数只能比该数小,所以这步不会越界
jinwei=s[i]/10; //下一位需要进位多少
s[i]=s[i]%10; //该位数上最后是与10的余数
num--; //为更高位的计算做准备
}
for(int i=N; i>=0 ;i--)//用来判断输出时的有效最高位(筛选作用)
{
if(s[i]!=0)
{
weishu=i;
break;
}
}
for(int i=weishu; i>=0 ;i--)//从有效的最高位开始逐个输出
{
printf("%d",s[i]);
}
return 0;
}
下一篇: SQL例子