s02b.ps

来自「c programming pearls answer」· PS 代码 · 共 1,191 行 · 第 1/2 页

%!PS-Adobe-2.0
%%Copyright: Copyright (c) 1993 AT&T, All Rights Reserved
%%Version: 3.4
%%DocumentFonts: (atend)
%%Pages: (atend)
%%BoundingBox: (atend)
%%EndComments
/DpostDict 200 dict def
DpostDict begin
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 prologue for troff files.
%

/#copies 1 store
/Prologue (dpost.ps) def
/aspectratio 1 def
/formsperpage 1 def
/landscape false def
/linewidth .3 def
/magnification 1 def
/margin 0 def
/orientation 0 def
/resolution 720 def
/rotation 1 def
/xoffset 0 def
/yoffset 0 def

/roundpage true def
/useclippath true def
/pagebbox [0 0 612 792] def

/R  /Times-Roman def
/I  /Times-Italic def
/B  /Times-Bold def
/BI /Times-BoldItalic def
/H  /Helvetica def
/HI /Helvetica-Oblique def
/HB /Helvetica-Bold def
/HX /Helvetica-BoldOblique def
/CW /Courier def
/CO /Courier def
/CI /Courier-Oblique def
/CB /Courier-Bold def
/CX /Courier-BoldOblique def
/PA /Palatino-Roman def
/PI /Palatino-Italic def
/PB /Palatino-Bold def
/PX /Palatino-BoldItalic def
/Hr /Helvetica-Narrow def
/Hi /Helvetica-Narrow-Oblique def
/Hb /Helvetica-Narrow-Bold def
/Hx /Helvetica-Narrow-BoldOblique def
/KR /Bookman-Light def
/KI /Bookman-LightItalic def
/KB /Bookman-Demi def
/KX /Bookman-DemiItalic def
/AR /AvantGarde-Book def
/AI /AvantGarde-BookOblique def
/AB /AvantGarde-Demi def
/AX /AvantGarde-DemiOblique def
/NR /NewCenturySchlbk-Roman def
/NI /NewCenturySchlbk-Italic def
/NB /NewCenturySchlbk-Bold def
/NX /NewCenturySchlbk-BoldItalic def
/ZD /ZapfDingbats def
/ZI /ZapfChancery-MediumItalic def
/S  /S def
/S1 /S1 def
/GR /Symbol def

/inch {72 mul} bind def
/min {2 copy gt {exch} if pop} bind def

/setup {
	counttomark 2 idiv {def} repeat pop

	landscape {/orientation 90 orientation add def} if
	/scaling 72 resolution div def
	linewidth setlinewidth
	1 setlinecap

	pagedimensions
	xcenter ycenter translate
	orientation rotation mul rotate
	width 2 div neg height 2 div translate
	xoffset inch yoffset inch neg translate
	margin 2 div dup neg translate
	magnification dup aspectratio mul scale
	scaling scaling scale

	addmetrics
	0 0 moveto
} def

/pagedimensions {
	useclippath userdict /gotpagebbox known not and {
		/pagebbox [clippath pathbbox newpath] def
		roundpage currentdict /roundpagebbox known and {roundpagebbox} if
	} if
	pagebbox aload pop
	4 -1 roll exch 4 1 roll 4 copy
	landscape {4 2 roll} if
	sub /width exch def
	sub /height exch def
	add 2 div /xcenter exch def
	add 2 div /ycenter exch def
	userdict /gotpagebbox true put
} def

/landscapepage {
	landscape not {
		0 height scaling div neg translate	% not quite
		90 rotate
	} if
} bind def

/portraitpage {
	landscape {
		width scaling div 0 translate	% not quite
		-90 rotate
	} if
} bind def

/addmetrics {
	/Symbol /S null Sdefs cf
	/Times-Roman /S1 StandardEncoding dup length array copy S1defs cf
} def

/pagesetup {
	/page exch def
	currentdict /pagedict known currentdict page known and {
		page load pagedict exch get cvx exec
	} if
} def

/decodingdefs [
	{counttomark 2 idiv {y moveto show} repeat}
	{neg /y exch def counttomark 2 idiv {y moveto show} repeat}
	{neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat}
	{neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat}
	{counttomark 2 idiv {y moveto show} repeat}
	{neg setfunnytext}
] def

/setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def

/w {neg moveto show} bind def
/m {neg dup /y exch def moveto} bind def
/done {/lastpage where {pop lastpage} if} def

/f {
	dup /font exch def findfont exch
	dup /ptsize exch def scaling div dup /size exch def scalefont setfont
	linewidth ptsize mul scaling 10 mul div setlinewidth
	/spacewidth ( ) stringwidth pop def
} bind def

/changefont {
	/fontheight exch def
	/fontslant exch def
	currentfont [
		1 0
		fontheight ptsize div fontslant sin mul fontslant cos div
		fontheight ptsize div
		0 0
	] makefont setfont
} bind def

/sf {f} bind def

/cf {
	dup length 2 idiv
	/entries exch def
	/chtab exch def
	/newencoding exch def
	/newfont exch def

	findfont dup length 1 add dict
	/newdict exch def
	{1 index /FID ne {newdict 3 1 roll put}{pop pop} ifelse} forall

	newencoding type /arraytype eq {newdict /Encoding newencoding put} if

	newdict /Metrics entries dict put
	newdict /Metrics get
	begin
		chtab aload pop
		1 1 entries {pop def} for
		newfont newdict definefont pop
	end
} bind def

%
% A few arrays used to adjust reference points and character widths in some
% of the printer resident fonts. If square roots are too high try changing
% the lines describing /radical and /radicalex to,
%
%	/radical	[0 -75 550 0]
%	/radicalex	[-50 -75 500 0]
%
% Move braceleftbt a bit - default PostScript character is off a bit.
%

/Sdefs [
	/bracketlefttp		[201 500]
	/bracketleftbt		[201 500]
	/bracketrighttp		[-81 380]
	/bracketrightbt		[-83 380]
	/braceleftbt		[203 490]
	/bracketrightex		[220 -125 500 0]
	/radical		[0 0 550 0]
	/radicalex		[-50 0 500 0]
	/parenleftex		[-20 -170 0 0]
	/integral		[100 -50 500 0]
	/infinity		[10 -75 730 0]
] def

/S1defs [
	/underscore		[0 80 500 0]
	/endash			[7 90 650 0]
] def
end
%%EndProlog
%%BeginSetup
DpostDict begin
mark
/rotation 1 def
/gotpagebbox true def
/linewidth 0.5 def
/xoffset 0 def
/yoffset 0 def
/#copies 1 store
/magnification 1 def
%%FormsPerPage: 1
/formsperpage 1 def
%%Patch from lp
%%EndPatch from lp
/landscape false def
/resolution 720 def
setup
2 setdecoding
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 drawing procedures for dpost. Automatically pulled in when
% needed.
%

/inpath false def
/savematrix matrix def

/Dl {
	inpath
		{pop pop neg lineto}
		{newpath neg moveto neg lineto stroke}
	ifelse
} bind def

/De {
	/y1 exch 2 div def
	/x1 exch 2 div def
	/savematrix savematrix currentmatrix def
	neg exch x1 add exch translate
	x1 y1 scale
	0 0 1 0 360
	inpath
		{1 0 moveto arc savematrix setmatrix}
		{newpath arc savematrix setmatrix stroke}
	ifelse
} bind def

/Da {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arc}
		{newpath arc stroke}
	ifelse
} bind def

/DA {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arcn}
		{newpath arcn stroke}
	ifelse
} bind def

/Ds {
	/y2 exch def
	/x2 exch def
	/y1 exch def
	/x1 exch def
	/y0 exch def
	/x0 exch def
	x0 5 x1 mul add 6 div
	y0 5 y1 mul add -6 div
	x2 5 x1 mul add 6 div
	y2 5 y1 mul add -6 div
	x1 x2 add 2 div
	y1 y2 add -2 div
	inpath
		{curveto}
		{newpath x0 x1 add 2 div y0 y1 add -2 div moveto curveto stroke}
	ifelse
} bind def
end
%%EndSetup
%%Page: 1 1
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
1 pagesetup
20 H f
(Vector Rotation)1 1384 1 2188 960 t
(The Problem)1 1148 1 1080 1620 t
(Three Algorithms)1 1526 1 1080 1860 t
(Implementations)1080 2100 w
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-2-1)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 1 1
%%Page: 2 2
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
2 pagesetup
20 H f
(The Problem)1 1148 1 2486 960 t
(The Problem)1 1148 1 720 1560 t
(Rotate vector)1 1194 1 1008 2040 t
20 HI f
(x)2258 2040 w
20 H f
([)2374 2040 w
20 HI f
(n)2446 2040 w
20 H f
(] left by)2 648 1 2574 2040 t
20 HI f
(d)3278 2040 w
20 H f
(positions.)3446 2040 w
(For)1008 2520 w
20 HI f
(n)1364 2520 w
20 H f
(=8 and)1 620 1 1476 2520 t
20 HI f
(d)2152 2520 w
20 H f
(=3, change)1 1000 1 2264 2520 t
20 HI f
(abcdefgh)3320 2520 w
20 H f
(to)4204 2520 w
20 HI f
(defghabc)4428 2520 w
20 H f
(.)5256 2520 w
(Constraints:)1008 3000 w
20 HI f
(O)2134 3000 w
20 H f
(\()2306 3000 w
20 HI f
(n)2388 3000 w
20 H f
(\) time,)1 556 1 2516 3000 t
20 HI f
(O)3128 3000 w
20 H f
( extra space.)2 1150(\( 1 \))2 276 2 3300 3000 t
(Pricey Solutions)1 1438 1 720 3480 t
(Store)1008 3960 w
20 HI f
(d)1544 3960 w
20 H f
(in intermediate vector, shift the rest, store)6 3682 1 1712 3960 t
(back. [)1 648 1 1008 4200 t
20 HI f
(O)1656 4200 w
20 H f
(\()1828 4200 w
20 HI f
(n)1910 4200 w
20 H f
(\) extra space.])2 1272 1 2038 4200 t
(Rotate by 1)2 1028 1 1008 4680 t
20 HI f
(d)2092 4680 w
20 H f
(times. [)1 702 1 2260 4680 t
20 HI f
(O)2962 4680 w
20 H f
(\()3134 4680 w
20 HI f
(n)3216 4680 w
20 H f
(\) time.])1 612 1 3344 4680 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-2-2)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 2 2
%%Page: 3 3
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
3 pagesetup
20 H f
(A Juggling Algorithm)2 1840 1 2284 960 t
(The Idea \()2 916 1 720 1560 t
20 HI f
(n)1636 1560 w
20 S f
(=)1797 1560 w
20 H f
(12,)1940 1560 w
20 HI f
(d)2276 1560 w
20 S f
(=)2437 1560 w
20 H f
(3\))2580 1560 w
16 H f
1260 2484 1260 2784 Dl
1560 2483 1260 2483 Dl
1560 2783 1560 2483 Dl
1260 2784 1560 2784 Dl
(1)1364 2666 w
1560 2484 1560 2784 Dl
1860 2483 1560 2483 Dl
1859 2783 1859 2483 Dl
1559 2784 1859 2784 Dl
1859 2484 1859 2784 Dl
2159 2483 1859 2483 Dl
2160 2783 2160 2483 Dl
1860 2784 2160 2784 Dl
2160 2484 2160 2784 Dl
2460 2483 2160 2483 Dl
2460 2783 2460 2483 Dl
2160 2784 2460 2784 Dl
(2)2264 2666 w
2460 2484 2460 2784 Dl
2760 2483 2460 2483 Dl
2759 2783 2759 2483 Dl
2459 2784 2759 2784 Dl
2759 2484 2759 2784 Dl
3059 2483 2759 2483 Dl
3060 2783 3060 2483 Dl
2760 2784 3060 2784 Dl
3060 2484 3060 2784 Dl
3360 2483 3060 2483 Dl
3360 2783 3360 2483 Dl
3060 2784 3360 2784 Dl
(3)3164 2666 w
3360 2484 3360 2784 Dl
3660 2483 3360 2483 Dl
3659 2783 3659 2483 Dl
3359 2784 3659 2784 Dl
3659 2484 3659 2784 Dl
3959 2483 3659 2483 Dl
3960 2783 3960 2483 Dl
3660 2784 3960 2784 Dl
3960 2484 3960 2784 Dl
4260 2483 3960 2483 Dl
4260 2783 4260 2483 Dl
3960 2784 4260 2784 Dl
(4)4064 2666 w
4260 2484 4260 2784 Dl
4560 2483 4260 2483 Dl
4559 2783 4559 2483 Dl
4259 2784 4559 2784 Dl
4559 2484 4559 2784 Dl
4859 2483 4559 2483 Dl
4860 2783 4860 2483 Dl
4560 2784 4860 2784 Dl
2610 1884 2610 2184 Dl
2910 1884 2610 1884 Dl
2910 2184 2910 1884 Dl
2610 2184 2910 2184 Dl
16 HI f
(t)2737 2065 w
2160 2483 -300 360 -300 -360 Da
1560 2483 1702 2353 Dl
1560 2483 1747 2436 Dl
3060 2483 -300 360 -300 -360 Da
2460 2483 2602 2353 Dl
2460 2483 2647 2436 Dl
3960 2483 -300 360 -300 -360 Da
3360 2483 3502 2353 Dl
3360 2483 3547 2436 Dl
2609 2033 2420 1996 Dl
2609 2034 2460 1912 Dl
2610 2033 -481 804 -868 -354 Da
4258 2484 4130 2340 Dl
4259 2483 4213 2296 Dl
4260 2483 -868 354 -481 -804 Da
20 H f
(The Code)1 882 1 720 3420 t
20 CW f
(for i = [0, gcd\(d, n\)\))5 2640 1 1296 3715 t
(/* move i-th values of blocks */)6 3840 1 1776 3950 t
(t = x[i])2 960 1 1776 4185 t
(j = i)2 600 1 1776 4420 t
(loop)1776 4655 w
(k = j + d)4 1080 1 2256 4890 t
(if k >= n)3 1080 1 2256 5125 t
(k -= n)2 720 1 2736 5360 t
(if k == i)3 1080 1 2256 5595 t
(break)2736 5830 w
(x[j] = x[k])2 1320 1 2256 6065 t
(j = k)2 600 1 2256 6300 t
(x[j] = t)2 960 1 1776 6535 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-2-3)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 572 726
%%EndPage: 3 3
%%Page: 4 4
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
4 pagesetup
20 H f
(The Block-Swap Algorithm)2 2362 1 1879 960 t
(The Idea: Change)2 1610 1 720 1560 t
20 HI f
(ab)2386 1560 w
20 H f
(to)2666 1560 w
20 HI f
(ba)2890 1560 w
20 H f
(If)1008 2040 w
20 HI f
(a)1176 2040 w
20 H f
(is shorter, divide)2 1460 1 1344 2040 t
20 HI f
(b)2860 2040 w