|
原帖由 chenzyyysl 于 2010-9-9 23:12 发表
这个算法学习了,那里有讲解(证明)?
设为三位数ABC(即100A+10B+C),多位数证法同
求A+B+C之和,若超过10请继续同样方法累加至个位数
情况一:A+B+C已为个位数,则其为所求
证:因100A+10B+C=9*(11A+B)+(A+B+C)
故求(A+B+C)之和,
等价于求100A+10B+C-9*(11A+B )之和
等价于MOD(100A+10B+C,9)之和(先假设A+B+C不被9整除)
情况二:A+B+C为十位数,设为10X+Y,则(X+Y)为所求
证:因100A+10B+C=9*(11A+B)+(A+B+C)=9*(11A+B)+10X+Y=9*(11A+B+X)+(X+Y)
故求(X+Y)之和,
同情况一等价于求100A+10B+C-9*(11A+B+X )之和
等价于MOD(100A+10B+C,9)之和(先假设A+B+C不被9整除)
显然A+B+C之最终解可能为1, 2, 3, 4, …, 9
故若需于MOD结合,则先行将A+B+C-1,求完余数再行加1即得
[ 本帖最后由 piny 于 2010-9-10 06:54 编辑 ] |
|