C语言程序设计100例之（23）：数列求和

例23 数列求和

问题描述

已知某数列前两项为2和3，其后继项根据前⾯最后两项的乘积，按下列规则⽣成：① 若乘积为⼀位数，则该乘积即为数列的后继项；

② 若乘积为⼆位数，则该乘积的⼗位上的数字和个位上的数字依次作为数列的两个后继项。输出该数列的前Ｎ项及它们的和。输⼊格式

⼀个整数N（2≤N≤1000）。输出格式

第1⾏输出该数列的前Ｎ项的和。第2⾏输出该数列的前N项。输⼊样例10输出样例sum(10)=442 3 6 1 8 8 6 4 2 4 （1）编程思路。 编写函数int sum(int *pa, int n)按数列的⽣成⽅法⽣成数列的前n项并保存在数组pa中，同时将前n项的和作为函数值返回。 （2）源程序。#include #define MAXNUM 1001int sum(int *pa, int n);int main(){

int n,num[MAXNUM]; scanf(\"%d\

printf(\"sum(%d)=%d\\n\ for (int i=0;iprintf(\"%d \ }

printf(\"\\n\"); return 0;}

int sum(int *pa, int n)

{

int count, total, temp; *pa = 2; *(++pa)=3; total=5; count=2;

while (count++temp = *(pa-1) * (*pa); if (temp<10) {

total+=temp; *(++pa) = temp; } else {

*(++pa)= temp/10; total += *pa; if (count++*(++pa) = temp%10; total += *pa; } } }

return total;}

习题2323-1 序列求和问题描述

有⼀个序列，初始时只有两个数x和y，之后每次操作时，在原序列的任意两个相邻数之间插⼊这两个数的和，得到新序列。举例说明：初始：1 2操作1次：1 3 2操作2次：1 4 3 5 2……

问操作n次之后，得到的序列的所有数之和是多少？输⼊格式

三个整数x，y，n，相邻两个数之间⽤单个空格隔开。0 <= x <= 5，0 <= y <= 5，1 < n <= 10。输出格式

⼀个整数，即最终序列中所有数之和。样例输⼊1 2 2样例输出15

（1）编程思路1。

像例23⼀样将操作n次之后的序列⽣成出来再求和。要⽣成操作n次之后的序列需要进⾏⼆重循环，外循环控制操作次数，内循环通过在前⼀序列相邻两数间插⼊和的⽅式⽣成新序列。这个序列是不断增长的，第1次操作后有3个数，第2次操作后有5个数，…，第10次操作后有288个数。

由于题⽬求最终序列中所有数之和，因此⽆需保留中间序列的情况，只需保留最终序列的结果。因此为了⽅便操作，定义⼀个⼆维数组a[2][300]，⽤滚动数组的⽅式进⾏操作。即初始时，a[0][0]=x，a[0][1]=y。然后进⾏

第1次操作，由a[0][0]~a[0][1]得到a[1][0]~a[1][2]；第2次操作，由a[1][0]~a[1][2]得到a[0][0]~a[0][4]；第3次操作，由a[0][0]~a[0][2]得到a[1][0]~a[1][8]；……

第n次操作，由a[(n-1)%2][0]~a[(n-1)%2][ k-1 ]得到 a[n%2][0]~a[n%2][ k-1+(n-1)*(n-1)]。（k表⽰上⼀次操作结束后的元素个数） （2）源程序1。

#include int main(){

int a[2][300]; int x,y,n;

scanf(\"%d%d%d\ int i,j,k; a[0][0]=x; a[0][1]=y; k=2;

for(i=1;i<=n;i++) {

int cnt=0; for (j=0;ja[i%2][cnt++]=a[(i-1)%2][j];

a[i%2][cnt++]=a[(i-1)%2][j]+a[(i-1)%2][j+1]; }

a[i%2][cnt++]=a[(i-1)%2][j]; k=cnt; }

int s=0; for (i=0;i（3）编程思路2。

由于题⽬求最终序列中所有数之和，因此我们可以通过找到各次操作后和之间的规律得到结果，⽽⽆需⽣成整个最终序列。 初始序列为 ： x y 和S[0]为 x+y 第1次操作后 ：x， x+y， y 和s[1]为2x+2y 第2次操作后 ：x， 2x+y，x+y，x+2y，y 和s[2]为5x+5y

第3次操作后 ：x，3x+y，2x+y，3x+2y，x+y，2x+3y，x+2y，x+3y，y，和s[3]为14x+14y ……

由上⾯可以推出，若第n次操作后序列和为S[n]，则第n+1次操作后的和S[n+1]⼀定为3*S[n]-(x+y)。因为在由第n次操作后序列⽣成第n+1次操作序列时，除⾸尾两个元素x和y外，中间每个元素会在新序列中产⽣3次作⽤（与前⼀个元素的和，⾃⾝，与后⼀个元素的和），⽽⾸尾两个元素x和y只作⽤两次，x没有前⼀个元素，y没有后⼀个元素。 （4）源程序2。

#include int main(){

int x,y,n,s,i;

scanf(\"%d%d%d\ s=x+y;

for (i=1;i<=n;i++) {

s=3*s-(x+y); }

printf(\"%d\\n\ return 0;}23-2 序列题⽬描述

设有数列A={a1, a2, …, an}，根据数列A计算数列B={b1, b2, …, bn}，其中：

求数列B的前n项之和。输⼊格式

第⼀⾏是⼀个正整数t（0对于每组测试数据，输出数列B的所有的元素之和。输⼊样例2

5 1 2 3 4 57 2 9 7 4 6 2 6输出样例514

（1）编程思路1。

对每⼀个ai直接根据规则求bi。具体说就是⽤循环求每⼀个ai 与它前⾯各个数的差的最⼩绝对值。 （2）源程序1。

#include #include int main(){ int t;

scanf(\"%d\ int a[100001]; while(t--) { int n;

scanf(\"%d\ for (int i=0;iint min=abs(a[i]-a[0]); for (int j=1;j<=i-1;j++) if (abs(a[i]-a[j])printf(\"%d\\n\ } return 0;}

（3）编程思路2。

按思路1编写程序后，提交给洛⾕OJ，只能得30分。10组测试数据中有7组数据显⽰“TLE”超时。因此需要想另外的办法。

题⽬中给定0≤ai≤65536，这意味着可以定义⼀个hash数组存储对应数字是否已经出现过，hash[i]=0，表⽰数i在序列中没出现，hash[i]=1表⽰数i在序列中出现过。这样，每1个a[i]转化成b[i]时，都在hash表中寻找距离它最近的、已经出现过的数。

即从当前数字x（表⽰ai）开始向前（x-i）或向后（x+i）遍历，找到对应hash[x-i]或hash[x+i]为1的值，也就是找到了最近已经出现过的的数字aj。

（4）源程序2。

#include #include int main(){ int t;

scanf(\"%d\ int hash[65537]; while(t--) {

memset(hash,0,sizeof(hash)); int n,x;

scanf(\"%d%d\ hash[x]=1; int sum=x;

for (int k=2;k<=n;k++) {

scanf(\"%d\ for(int i=0;;i++) {

if (x-i>=0) if (hash[x-i]) {

sum+=i; break; }

if (x+i<=65536) if (hash[x+i]) {

sum+=i; break; } }

hash[x]=1; }

printf(\"%d\\n\ } return 0;}

23-3 ⼦序列的和求和问题描述

给定⼀个正整数数列，求该数列中所有连续⼦序列和的和。例如，给定数列1,2,3，该数列中连续⼦序列有：[1], [2], [3], [1, 2], [2, 3]和[1, 2,3]，这些连续⼦序列和的和为：1 + 2 + 3 + 3 + 5 + 6 = 20。输⼊格式

第1⾏是⼀个正整数T，代表测试数据的组数。

每组测试数据包括两⾏，⾸⾏为⼀个正整数N，表⽰序列中元素的个数，接着⼀⾏给出序列的N个元素。输出格式

对每组测试⽤例，输出序列的和模1 000 000 007后的结果。输⼊样例21231 2 3输出样例220

（1）编程思路。

同样找规律，规律很明显，数列中每个数ai都被加了i*(N+1-i)次。

以数列1,2,3为例，第1个数1被加了1*（3+1-1）=3次，第2个数2被加了2*（3+1-2）=4次，第3个数3被加了3*（3+1-3）=3次。所以和=1*3+2*4+3*3=20。 （2）源程序。

#include #define MOD 1000000007int main(){ int t,n; scanf(\"%d\ while (t--) {

scanf(\"%d\ long long sum=0,x,ai; for (int i=1;i<=n;i++) {

scanf(\"%lld\ x=(i*ai)% MOD; x=(x*(n+1-i)) % MOD; sum=(sum+x) % MOD; }

printf(\"%lld\\n\ } return 0;}