例23 數列求和
問題描述
已知某數列前兩項為2和3，其后繼項根據前面最后兩項的乘積，按下列規則生成：
① 若乘積為一位數，則該乘積即為數列的后繼項；
② 若乘積為二位數，則該乘積的十位上的數字和個位上的數字依次作為數列的兩個后繼項，
輸出該數列的前Ｎ項及它們的和，
輸入格式
一個整數N（2≤N≤1000），
輸出格式
第1行輸出該數列的前Ｎ項的和，
第2行輸出該數列的前N項，
輸入樣例
10
輸出樣例
sum(10)=44
2 3 6 1 8 8 6 4 2 4
（1）編程思路，
撰寫函式int sum(int *pa, int n)按數列的生成方法生成數列的前n項并保存在陣列pa中，同時將前n項的和作為函式值回傳，
（2）源程式，
#include <stdio.h>
#define MAXNUM 1001
int sum(int *pa, int n);
int main()
{
int n,num[MAXNUM];
scanf("%d",&n);
printf("sum(%d)=%d\n",n,sum(num,n));
for (int i=0;i<n;i++)
{
printf("%d ",num[i]);
}
printf("\n");
return 0;
}
int sum(int *pa, int n)
{
int count, total, temp;
*pa = 2;
*(++pa)=3;
total=5;
count=2;
while (count++<n)
{
temp = *(pa-1) * (*pa);
if (temp<10)
{
total+=temp;
*(++pa) = temp;
}
else
{
*(++pa)= temp/10;
total += *pa;
if (count++<n)
{
*(++pa) = temp%10;
total += *pa;
}
}
}
return total;
}
習題23
23-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 <stdio.h>
int main()
{
int a[2][300];
int x,y,n;
scanf("%d%d%d",&x,&y,&n);
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;j<k-1;j++)
{
a[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<k;i++)
s+=a[n%2][i];
printf("%d\n",s);
return 0;
}
（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 <stdio.h>
int main()
{
int x,y,n,s,i;
scanf("%d%d%d",&x,&y,&n);
s=x+y;
for (i=1;i<=n;i++)
{
s=3*s-(x+y);
}
printf("%d\n",s);
return 0;
}
23-2 序列
本題選自洛谷題庫 （https://www.luogu.org/problem/P1732）
題目描述
設有數列A={a1, a2, …, an}，根據數列A計算數列B={b1, b2, …, bn}，其中：
求數列B的前n項之和，
輸入格式
第一行是一個正整數t（0<t<=10），表示測驗資料的組數，接下來有t行，每行表示一組測驗資料，每行以一個正整數n（0<n<=100 000）開始，表示數列A中元素的個數；然后是n個非負整數，依次表示a1, a2, …, an的值（0<= ai<=65 536），
輸出格式
對于每組測驗資料，輸出數列B的所有的元素之和，
輸入樣例
2
5 1 2 3 4 5
7 2 9 7 4 6 2 6
輸出樣例
5
14
（1）編程思路1，
對每一個ai直接根據規則求bi，具體說就是用回圈求每一個ai 與它前面各個數的差的最小絕對值，
（2）源程式1，
#include <stdio.h>
#include <math.h>
int main()
{
int t;
scanf("%d",&t);
int a[100001];
while(t--)
{
int n;
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&a[i]);
int sum=a[0];
for (int i=1;i<n;i++)
{
int min=abs(a[i]-a[0]);
for (int j=1;j<=i-1;j++)
if (abs(a[i]-a[j])<min)
min=abs(a[i]-a[j]);
sum+=min;
}
printf("%d\n",sum);
}
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 <stdio.h>
#include <string.h>
int main()
{
int t;
scanf("%d",&t);
int hash[65537];
while(t--)
{
memset(hash,0,sizeof(hash));
int n,x;
scanf("%d%d",&n,&x);
hash[x]=1;
int sum=x;
for (int k=2;k<=n;k++)
{
scanf("%d",&x);
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",sum);
}
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后的結果，
輸入樣例
2
1
2
3
1 2 3
輸出樣例
2
20
（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 <stdio.h>
#define MOD 1000000007
int main()
{
int t,n;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
long long sum=0,x,ai;
for (int i=1;i<=n;i++)
{
scanf("%lld",&ai);
x=(i*ai)% MOD;
x=(x*(n+1-i)) % MOD;
sum=(sum+x) % MOD;
}
printf("%lld\n",sum);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/59764.html
標籤：C
上一篇：C語言筆記 03_常量&存盤類
下一篇：疑異步罕有