$D_0$, iki-harfli "Fa" harf dizisi olsun. $n\ge 1$ için, $D_n$ ifadesi $D_{n-1}$ ifadesinden aşağıdaki harf dönüşümleri kullanılarak yapılsın: $$"a"\rightarrow "aRbFR"$$ $$"b"\rightarrow "LFaLb".$$
Böylece $D_{0}="Fa"$, $D_{1}="FaRbFR"$, $D_{0}="FaRbFRRLFaLbFR"$, ... olur.
Bu diziler bir bilgisayar grafik programının yönergeleri olabilirler: Bir birim ileri çiz "F" ile, sola 90 derece dön "L" ile, sağa 90 derece dön "R" ile gösterilir ve "a" ve "b" boş geç demektir. Bilgisayar imlecinin başlangıç noktası (0,0) ve yönü (0,1) olsun.
Bu durumda $D_n$, n. sıradan Heighway Ejderhası olarak bilinen egzotik bir çizimdir. Örnek olarak $D_{10}$ aşağıda verildi; her "F" bir adım olarak sayılırsa 500 adım sonra varılan nokta işaretli olan (18,16) noktasıdır.
Cevap: 139776,963904
C++:
#include <stdio.h>
#include <string.h>
typedef long long LL;
LL X[64],Y[64],P[64];
int main(){
int i;
LL x,y,p,tar,ox,oy;
tar=1000000000000LL;
//scanf("%lld",&tar);
x=0; y=1; p=1; i=2;
X[1]=x; Y[1]=y; P[1]=1;
while (p<10000000000000LL){
ox=x; oy=y;
x=ox+oy;
y=oy-ox;
p=p+p;
X[i]=x; Y[i]=y; P[i]=p; i++;
printf(" %lld (%lld,%lld) %lld\n",p,x,y,P[i-1]);
}
LL tarx,tary;
tarx=0; tary=0; x=1; y=1; i--;
int dir=0;
while (tar>0){
if (tar>P[i]){
printf("[%lld %lld] %d %lld %lld\n",X[i+1]*x,Y[i+1]*y,i+1,x,y);
switch(dir){
case 0: x= X[i+1]; y= Y[i+1]; break;
case 1: x= Y[i+1]; y=-X[i+1]; break;
case 2: x=-X[i+1]; y=-Y[i+1]; break;
case 3: x=-Y[i+1]; y= X[i+1]; break;
}
tarx+=x; tary+=y;
tar=P[i+1]-tar;
dir=(dir+3)%4;
}
i--;
}
printf("<%lld,%lld>\n",tarx,tary);
return 0;
}Python:
from numpy import matrix
def p220(lim):
# matrices transform the vector [ x_pos ; y_pos; x_dir; y_dir ]
F = matrix([[1, 0, 1, 0], [0, 1, 0, 1], [ 0, 0, 1, 0], [0, 0, 0, 1]], dtype = 'object')
R = matrix([[1, 0, 0, 0], [0, 1, 0, 0], [ 0, 0, 0, 1], [0, 0, -1, 0]], dtype = 'object')
L = matrix([[1, 0, 0, 0], [0, 1, 0, 0], [ 0, 0, 0, -1], [0, 0, 1, 0]], dtype = 'object')
v = matrix([[0],[0],[0],[1]], dtype='object')
R1 = F*R*F
L1 = F*L*F
rules = [(0, R, L)]
lim -= 1
while x <= lim:
x, r, l = rules[-1]
x = 2*x + 2
rules.append((x, l*R1*r, l*L1*r))
rules.pop()
v = F*v
in_r = True
while lim > 1:
x, r, l = rules.pop()
if x > lim:
in_r = True
continue
v = r*v
lim -= x
if lim >= 2:
if in_r:
v = R1*v
else:
v = L1*v
lim -= 2
in_r = False
if lim == 1:
v = F*v
return v[0,0], v[1,0]Java:
public class Euler220 {
Euler220(){
long[] res = getDisplacement( 1000000000000L, 50 );
System.out.println(res[2]+","+res[3]);
}
// returns endpoint position of curve followed by position at given distance on curve
long[] getDisplacement( long distance, int generation ){
if( generation == 0 ){
if ( distance==0 ) return new long[]{0,1, 0,0};
else if( distance==1 ) return new long[]{0,1, 0,1};
else throw new RuntimeException("Travel past end");
}
long halflen = 1L<<(generation-1);
boolean secondHalf = distance>halflen;
if( secondHalf ) distance = halflen+halflen-distance;
long[] ret = getDisplacement( distance, generation-1 );
long ex = ret[0], ey = ret[1]; // end point
ret[0] = ex+ey;
ret[1] = ey-ex;
if( secondHalf ){
long px = ret[2], py = ret[3]; // current point
ret[2] = ex + ey - py;
ret[3] = ey - ex + px;
}
return ret;
}
}Mathematica:
a[k_]:=a[k]=a[k-1]+I(b[k-1]-1);
b[k_]:=b[k]=I(1+a[k-1]-I b[k-1]);
a[0]=b[0]=0;
L[n_]:=2^n-1;
A[k_,m_]:=If[m<=L[k-1],
A[k-1,m],
If[m<=2L[k-1],
a[k-1]+I B[k-1,m-L[k-1]],
a[k-1]+I(y[k-1]-1)]];
B[k_,m_]:=If[m==1,
I,
If[m<=L[k-1]+1,
I(1+A[k-1,m-1]),
I(1+a[k-1]-I B[k-1,m-L[k-1]-1])]];
I(1+A[50,10^12-1]) Haskell:
-- dragon' n = (dragon n, dragon (n+1))
dragon' 0 = ((0, 0), (0, 1))
dragon' n
| even n = ((x+y, y-x), (x+y, v-u))
| otherwise = ((x+y, v-u), (u+v, v-u))
where
((x, y), (u, v)) = dragon' (n `div` 2)
dragon :: Integer -> (Integer, Integer)
dragon n = fst (dragon' n) Delphi:
program Problem220;
{$APPTYPE CONSOLE}
uses
SysUtils,Windows;
const
steplimit=1000000000000;
var
starttime,endtime,countfreq:int64;
stepcount:int64;
i:integer;
pos:TPoint;
movecount,zerocount:integer;
directionDown:boolean;
inSequence,firstNonZeroBit:boolean;
function calcPos(n:integer;startDirDown:boolean;p:TPoint):TPoint;overload;
var
i:integer;
f:integer;
begin
if startDirDown then f:=-1 else f:=1;
Result.X:=0;
Result.Y:=1;
with Result do for i := 1 to n do
case i mod 4 of
0:
begin
x:=0; y:=2*y;
end;
1:x:=y;
2:
begin
x:=2*x; y:=0;
end;
3:y:=-x;
end;
Result.X := p.X+Result.X*f;
Result.Y := p.Y+Result.Y*f;
end;
begin
try
QueryPerformanceFrequency(countfreq);
QueryPerformanceCounter(starttime);
stepcount:=steplimit;
pos.X:=0; pos.Y:=0;
movecount:=0; zerocount:=0;
directionDown:=false;
firstNonZeroBit:=true; inSequence:=false;
for i := 63 downto 0 do begin
if (stepcount shr i) and 1 = 1 then begin
if moveCount=0 then directionDown:=false else //+
if (zeroCount > 0) and (firstNonZeroBit) then begin
directionDown:=true; //-
firstNonZeroBit:=false;
inSequence:=(((stepcount shr (i+1)) and 1) = 1);
end else
if moveCount=1 then begin
directionDown:=true;
end else //-
if (((stepcount shr (i+1)) and 1) = 1) then begin
if (((stepcount shr (i+2)) and 1) = 1) then begin
inSequence:=true;
end else begin
inSequence:=true;
directionDown:=not directionDown; //turn around
end;
end else begin
if not inSequence then begin
directionDown:=not directionDown; //turn around
end;
inSequence:=false;
end;
pos:=calcPos(i,directionDown,pos);
movecount:=movecount+1;
end else if movecount>0 then zerocount:=zerocount+1;
end;
QueryPerformanceCounter(endtime);
writeln(pos.X,',',pos.Y);
writeln((endtime-starttime),',',countfreq,',',(endtime-starttime)/countfreq);
{$IFDEF DEBUG}
readln;
{$ENDIF}
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
end.