算法第二题
星期二, 十月 9th, 2007这次比较顺利，1个小时，呵呵，虽然时间仍然算长，不过很长时间没摸过了已经。
题目：
Problem Statement
????
***Note: Please keep programs under 7000 characters in length. Thank you
Class Name: SquareDigits
Method Name: smallestResult
Parameters: int
Returns: int
Define the function S(x) as the sum of the squares of the digits of x. �
For example: S(3)=3*3=9 and S(230)=2*2+3*3+0*0=13.
Define the set T(x) to be the set of unique numbers that are produced by
repeatedly applying S to x. That is: S(x), S(S(x)), S(S(S(x))), etc…
For example, repeatedly applying S to 37:
S(37)=3*3+7*7=58.�
S(58)=5*5+8*8=89.
S(89)=145.
S(145)=42.
S(42)=20.
S(20)=4.
S(4)=16.
S(16)=37.
Note this sequence will repeat so we can stop calculating now and:
T(37)={58,89,145,42,20,4,16,37}.
However, note T(x) may not necessarily contain x.
Implement a class SquareDigits, which contains a method smallestResult. The
method takes an int, n, as a parameter and returns the smallest int, x, such
that T(x) contains n.
The method signature is (be sure your method is public):
int smallestResult(int n);
TopCoder will ensure n is non-negative and is between 0 and 199 inclusive.
Examples:
If n=0: S(0) = 0, so T(0)={0}, so the method should return 0.
If n=2: T(0) through T(10) do not contain the value 2. If x=11, however:
S(11)=1*1+1*1=2, so T(11) contains 2, and the method should return 11.
If n=10: T(0) through T(6) do not contain 10. If x=7:
S(7)=49.
S(49)=97.
S(97)=130.
S(130)=10.
S(10)=1.
and it starts to repeat…
so T(7) is {49,97,130,10,1}, which contains 10, and the method should return 7.
n=1 -> x=1
n=19 -> x=133
n=85 -> x=5
n=112 -> x=2666
Definition
????
Class:
SquareDigits
Method:
smallestResult
Parameters:
int
Returns:
int
Method signature:
int smallestResult(int param0)
(be sure your method is public)
????
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
解答：
#include<iostream>
using namespace std;
const int MAXLENGTH = 1000;
class SquareDigits
{
public:
SquareDigits()
{
sresult = 0;
smallResult = 0;
ti = 0;
lengthoftresult = 0;
xinput = 0;
number = 0;
for(int i=0;i<MAXLENGTH; i++)
tresult[i]=”;
}
int s(int x)
{
if(x<10)
sresult += x*x;
else
{
int mod = x%10;
sresult += mod*mod;
s(x/10);
}
return sresult;
}
int* t(int x)
{
xinput = x;
lengthoftresult = 0;
return t1(x);
}
int* t1(int x)
{
sresult = 0;
if(x == 0 || x==1)
{
tresult[ti]=x;
lengthoftresult++;
}
else
{
int temp = s(x);
if(xinput != temp && ti<MAXLENGTH)
{
for(int i = 0; i<lengthoftresult-1;i++)
{
if(temp == tresult[i])
return tresult;
}
tresult[ti] = temp;
ti++;
lengthoftresult++;
t1(temp);
}
ti = 0;
}
return tresult;
}
int smallestResult(int n)
{
number = n;
int i=0;
do
{
t(i);
i++;
}while(comparetsmall()!=true);
smallResult = i -1 ;
return smallResult;
}
bool comparetsmall()
{
for(int i=0; i<lengthoftresult; i++)
{
�
if(tresult[i] == number)
return true;
}
return false;
}
private:
int sresult;
int tresult[MAXLENGTH];
int xinput;
int lengthoftresult;
int ti;
int smallResult;
int number;
};
void main()
{
SquareDigits sd;
int x = 0;
cout<<”Input the param of n:”<<endl;
cin>>x;
//cout<<”x is:”<<x<<endl;
int smallresult = sd.smallestResult(x);
cout<<”smallestresult is:”<<smallresult<<endl;
//sd.t(x);
}