树根与模9运算

Description

我们通过把一个正数N的所有数字求和S来计算这个数的“数根”,如果累加的和为个位数,则这个数S即为N的“数根”;如果是两位和两位以上的数,那么重复这种累加求和的步骤,直到结果是个位数为止。
举例来说,对于正数N=24,将数字2和4相加得到6,因为6是个位数,所以6就是24的“数根”。再考虑N=39,将数字3和9相加得到12,因为12不是个位数,重复上面的计算,将数字1和2相加得到3,则3是个位数也就是39的“数根”了。

Input

输入数据中包含了若干个正数,一行一个,输入以“0”结束。

Output

对于每一个输入的正数,分行输出其“数根”。

[translated by B2L]

Sample Input

24
39
0

Sample Output

6
3

Hint

输入的正数很长,有可能大大超过了长整型能表示的范围。

Source

Greater New York 2000

=============================================================================
我的一种解决方法
数字9是废物
 
 
 
无所不在的9

如果把一个大数的各位数字相加得到一个和,再把这个和的各位数字相加又得一个和,再继续作数字和,直到最后的数字和是个位数为止,这最后的数称为最初那个数的“数字根”。这个数字根等于原数除以9的余数,因此这个计算过程常常称为“合九法”。

求一个数的数字根最快的方法是在加原数的数字时把9舍去。例如,最初两个数宇是68,二者相加成14,再将14,结果是5。换言之,舍去9以后的数字和若多于—位数则把两个数字再加起来,计算这个和。最后的数就是要求的数字根。可说数字根等价于原数对9的模,简称模9。由于9除以9余零,所以在模9算法中,90是等价的。

在发明计算机之前,会计员常常用模9算法来检查很大数目的和、差、积和商。譬如,假若我们用AB得到C,这个结果可以作下面检查:把A的数字根减去B的数字根,看看差是否对得上C的数字权。如果原来算的差是对的,那么数字根的差也对得上。这并不能证明原来的计算正确,可是如果数字根的差不等,则会计员就知道他算错了。如果数字根能对得上,则他计算正确的可能性是8/9。这种数字根检验方法可同样应用于数字的加、乘和除上。

现在我们就可以弄懂上述生日算法的奥妙在哪里了。假定一个数N由很多个数字组成。我们把N的数字打乱就得到—个新的数N’。显然NN’有着同样的数字根。因此,如果我们把二者相减就会得0,这和9是一回事(在模9算法中)。这个数,0或者9,必然是NN’之差的数字根。简言之,取任意一个数,把它的数字打乱重排得另一数,将二者相减,所得的差的数字根就是09

结果为0只是在NN’相等时。因此,应当提醒学生,在他们用自己生日进行计算时,要保证重排的数可以得到一个差数。只要两个数不等,其差的数字根就是9

用这个无所不在的9可以玩出很多数字魔术来。例如,一个学生在老师背转身去时写下一个数,所以老师看不见学生写的是什么。然后学生把那个数的数字打乱排成另一个数,计算这个数与原来那个数的差(大数减小数)。然后老师就让学生把差数中一个非零的数字划掉。这时,学生把余下的数字按任意顺序高声读出。老师仍然背转着身子,却能说出划掉的数字是几。

这个魔术的技巧很明显。那两个数之差应该有数字根9。当学生划掉一个数字后,并高声读出其他数字时,老师只要去掉9把其他数字心算加出来。学生念完时,老师用9减去最后的数字,结果就是学生划掉的那个数字(如果最后算得9,学生划掉的就是9)。

上述魔术和生日之谜将大大激发学生学习模算系统的兴趣。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s