夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

SRM152 Div.2 Easy FixedPointTheorem

あ゛〜〜〜〜〜〜!!!!!

寝オチしてしまった。
しかも寝てたのが大会開始30分前から大会終了75分後・・・
でたかったよ〜(泣

イライラしたので過去問ときました。結構。嘘。

英語の読解

PROBLEM STATEMENT
The fixed-point theorem is one of those cornerstones of 
mathematics that reaches towards all disciplines, and 
oddly enough it is also closely related to the ability of 
any program to Quine itself (or to print out its own 
source code). Put simply, the fixed-point theorem states 
that with certain restrictions on a real-valued function 
F, there is always a point such that X=F(X). Taking the 
fixed-point theorem further, you can show that any 
function that meets certain restrictions will start to 
cycle through values if you keep on feeding it its own 
output (doing this with programs and their output is one 
way of producing programs that Quine themselves).
 One simple function that does this is the logistic 
function F(X)=R*X*(1-X) in the interval [0,1] for certain 
values of R. For example, if you start with the value X=.
25 and feed it into F to get a new X, then feed that value 
into F to get yet another X, and so on, the values of X 
that are produced will converge to a small set of values 
that will eventually repeat forever, called a cycle. 

Your program will be given a double R between 0.1 and 
3.569 inclusive. Starting with X=.25, generate the first 
200,000 iterations of F using the given value of R, which 
will stabilize values of X. Then generate 1000 more 
values, and return the range of these values (highest 
value - lowest value).  In other words, you will be 
finding the range of the values produced between 
iterations 200,001 and 201,000 inclusive.

DEFINITION
Class:FixedPointTheorem
Method:cycleRange
Parameters:double
Returns:double
Method signature:double cycleRange(double R)


NOTES
 -Don't worry about overflow. With the given values it'll 
never happen.


CONSTRAINTS
 -R will be a value between 0.1 and 3.569 inclusive.
 -R will always be a value such that the process stated 
above will produce a result accurate to 1e-9 (absolute or 
relative).

今回こんな問題ですが、もはや読解力が要求される。

時間も時間だし、気持ちがふらついてたので自分では理解できずそこらへんでググル。
ココに『X0=0.25,Xi+1=R*Xi*(1-Xi)として、X200001〜X201000の範囲の最大値と最小値の差を求める問題。』ってあったのでその通りにやった。

class FixedPointTheorem {
   public:
   double cycleRange(double R)
  {
	double X = 0.25;
	double max_x=0, min_x=1, res;
	for (int i=0; i<200000; i++) {
		X = R*X*(1-X);
	}
	for (int i=0; i<1000; i++) {
		X = R*X*(1-X);
		max_x = max(max_x, X);
		min_x = min(min_x, X);
	}
	res = max_x - min_x;
	return res;
  }
};
広告を非表示にする