PAT 解题报告 (数据结构学习与实验指导) 2-06. 数列求和

题目描述:

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

算法分析:

由于最后结果的位数可能很大, 所以不能用long long存结果, 应该是找规律算出最后结果的每一位上的数值digit, 结果应该存在一个vector或者干脆的string上. 每一位的digit的算法是这样的:  S = A + AA + AAA + … + AA…A(N个A) = \sum_{k=0}^{N-1} {A * 10^k * (N – k)}. 于是一个for i = 0 to N-1的for循环就可以算出结果的. 时间复杂度O(N).

注意点:

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on July 13, 2013