首页 > ACM题库 > HDU-杭电 > HDU 1163 Eddy’s digital Roots-高精度-[解题报告] C++
2013
12-03

HDU 1163 Eddy’s digital Roots-高精度-[解题报告] C++

Eddy’s digital Roots

问题描述 :

The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.

For example, consider the positive integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 yeilds 3, a single digit and also the digital root of 39.

The Eddy’s easy problem is that : give you the n,want you to find the n^n’s digital Roots.

输入:

The input file will contain a list of positive integers n, one per line. The end of the input will be indicated by an integer value of zero. Notice:For each integer in the input n(n<10000).

输出:

Output n^n’s digital root on a separate line of the output.

样例输入:

2
4
0

样例输出:

4
4

 

如果把一个大数的各位数字相加得到一个和,再把这个和的各位数字相加又得一个和,再继续作数字和,直到最后的数字和是个位数为止,
这最后的数称为最初那个数的“数字根”。这个数字根等于原数除以9的余数,因此这个计算过程常常称为“合九法”。
此题用“合九法”和同余定理,同于定理为:
如果两个乘积除以m的余数等于这两个数分别除以m的余数积。
例如:7%3=1   5%3=2  7*5/3=2=1*2
代码如下:
#include<iostream>
using namespace std;
int main()
{
	int n,i,s;

	while(scanf("%d",&n),n)
	{
		s=1;
		for(i=0;i<n;i++)
		{
			s=(s*n)%9;
			if(s==0)
			{
				printf("9/n");
				break;
			}
		}
		if(s!=0)printf("%d/n",s);
	}
	return 0;
}

 


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。