基础编程题目集 —— 7-38 数列求和-加强版***

1 题目要求

给定某数字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。

输入格式：
输入数字A与非负整数N。

输出格式：
输出其N项数列之和S的值。

2 样例

输入样例：
1 3

输出样例：
123

3 分析

（1）本人想法：每个数的各为都是A，共N个数。使用变量item保存当前遍历的第i个数的第j位（j属于[0,i]），该数值使用循环计算。而数列和result 使用外循环表示.

（2）
参考 123-wqy的 PTA基础编程题目集-7-38 数列求和-加强版-C语言试解.，写出方式2 的代码
该方法的数据结构为整型数组，数组的每一位元素最终存放的是结果的每一位数值。这样就不会超过整型的范围。而核心问题也变成了如何使数组的每一位存放结果的每一位。
1）参考我只有一件白T恤的 7-38 数列求和-加强版.

可以发现这样的规律，——
单考虑每一位，先假设每一位都不进位，由于每一位都是A，则N个数相加的结果为A*N。比如N=100000，则该位暂存 100000*A，由于A属于[0,9]，所以每一位不会超过整型范围。

之后计算进位问题
当前位的进位=1）中的结果/10
下一位的数值（暂时）=下一位的数值（ 1）中计算）+当前位的进位。
当前位的最终值=当前为数值%10

还有一个规律，任意一个四位数+任意一个三位数+任意一个两位数+任意一个一位数，结果要么是四位数，要么是五位数。 所以一个最大为100000位的数相加，最终结果最大为100000+1 位

4 代码

方式1

#include <stdio.h>
#include <math.h>
int sequenceSum(int a,int n)
{
  int result=0;
  int item=0;
 // printf("%d\n",result);
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<=i;j++)
    {
      item=a*(int)(pow(10,j)+0.5);
      result+=item;
    }
  }
  printf("%d",result);
  return 0;
}

但该方式在提交后，在A和N取最大值时，超过整型范围——原因是最大位数为100000（十万）位。这远远超过了整型数的长度。

方式2：

#include <stdio.h>
#define MAX 100000+1
int sequenceSum2(int a,int n)
{
    if (n==0)
    {
        printf("0");
        return 0;
    }
    //举例：四位数+三位数+两位数+一位数，最多为五位数
    int result[MAX]={0};
    //     1
    //    11
    //   111
    //+ 1111
    //------
    //  1234
    // 还没有进位的基础数据
    // result[3]=1*1
    // result[2]=1*2;
    // result[1]=1*3;
    // result[0]=1*4;
    for(int i=0;i<n;i++)
        result[i]=a*(n-i);
    for(int i=0;i<n+1-1;i++)
    {
        if(result[i]>=10)
        {
            //进位计算
            result[i+1]+=result[i]/10;
            //保留当前位的个位数
            result[i]=result[i]%10;
        }
    }
    int length=n+1;
    if(result[n]==0)
        length=n;
    for(int i=length-1;i>=0;i--)
        printf("%d",result[i]);
    return 0;
}

int main()
{
  int a,n;
  scanf("%d %d",&a,&n);
  sequenceSum(a,n);
  return 0;
}

5 总结

超过整型范围的问题处理方式——通过数组存放各位数值。