s08.ps

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

%!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
(Algorithm Design Techniques)2 2620 1 1570 960 t
(An Example)1 1082 1 1080 1620 t
(The Problem)1 1148 1 1580 1860 t
(Algorithm 1: Cubic Time)3 2138 1 1580 2100 t
(Algorithm 2: Quadratic Time)3 2496 1 1580 2340 t
(Algorithm 3:)1 1070 1 1580 2580 t
20 HI f
(O)2706 2580 w
20 H f
(\()2878 2580 w
20 HI f
(n)2960 2580 w
20 H f
(log)3160 2580 w
20 HI f
(n)3516 2580 w
20 H f
(\) Time)1 566 1 3644 2580 t
(Algorithm 4: Linear Time)3 2184 1 1580 2820 t
(Comparison of Algorithms)2 2306 1 1580 3060 t
(Principles)1080 3300 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-8-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
20 HI f
(Definition.)720 1560 w
20 H f
(Given the real vector)3 1852 1 1724 1560 t
20 HI f
(x)3632 1560 w
20 H f
([)3748 1560 w
20 HI f
(n)3820 1560 w
20 H f
(], compute the)2 1274 1 3948 1560 t
(maximum sum found in any contiguous subvector.)6 4462 1 720 1800 t
20 HI f
(An Example.)1 1138 1 720 2520 t
20 H f
(If the input vector is)4 1742 1 1970 2520 t
1260 2844 1260 3204 Dl
1620 2844 1260 2844 Dl
1620 3204 1620 2844 Dl
1260 3204 1620 3204 Dl
(31)1328 3064 w
1620 2844 1620 3204 Dl
1980 2844 1620 2844 Dl
1980 3204 1980 2844 Dl
1620 3204 1980 3204 Dl
(-41)1655 3064 w
1980 2844 1980 3204 Dl
2340 2844 1980 2844 Dl
2340 3204 2340 2844 Dl
1980 3204 2340 3204 Dl
(59)2048 3064 w
2340 2844 2340 3204 Dl
2700 2844 2340 2844 Dl
2700 3204 2700 2844 Dl
2340 3204 2700 3204 Dl
(26)2408 3064 w
2700 2844 2700 3204 Dl
3060 2844 2700 2844 Dl
3060 3204 3060 2844 Dl
2700 3204 3060 3204 Dl
(-53)2735 3064 w
3060 2844 3060 3204 Dl
3420 2844 3060 2844 Dl
3420 3204 3420 2844 Dl
3060 3204 3420 3204 Dl
(58)3128 3064 w
3420 2844 3420 3204 Dl
3780 2844 3420 2844 Dl
3780 3204 3780 2844 Dl
3420 3204 3780 3204 Dl
(97)3488 3064 w
3780 2844 3780 3204 Dl
4140 2844 3780 2844 Dl
4140 3204 4140 2844 Dl
3780 3204 4140 3204 Dl
(-93)3815 3064 w
4140 2844 4140 3204 Dl
4500 2844 4140 2844 Dl
4500 3204 4500 2844 Dl
4140 3204 4500 3204 Dl
(-23)4175 3064 w
4500 2844 4500 3204 Dl
4860 2844 4500 2844 Dl
4860 3204 4860 2844 Dl
4500 3204 4860 3204 Dl
(84)4568 3064 w
2160 3204 2178 3276 Dl
2160 3204 2142 3276 Dl
2160 3348 2160 3204 Dl
(2)2104 3532 w
3600 3204 3618 3276 Dl
3600 3204 3582 3276 Dl
3600 3348 3600 3204 Dl
(6)3544 3532 w
(then the program returns the sum of)6 3204 1 720 3888 t
20 HI f
(x)3980 3888 w
20 H f
([2..6], or 187.)2 1186 1 4080 3888 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-8-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 Cubic Algorithm)2 1604 1 2258 960 t
20 HI f
(Idea.)720 1560 w
20 H f
(For all pairs of integers)4 2040 1 1280 1560 t
20 HI f
(i)3376 1560 w
20 H f
(and)3476 1560 w
20 HI f
(j)3868 1560 w
20 H f
(satisfying)3968 1560 w
(0)720 1800 w
20 S f
(\243)848 1800 w
20 HI f
(i)974 1800 w
20 S f
(\243)1034 1800 w
20 HI f
(j)1177 1800 w
20 S f
(<)1254 1800 w
20 HI f
(n)1397 1800 w
20 H f
(, check whether the sum of)5 2400 1 1509 1800 t
20 HI f
(x)3965 1800 w
20 H f
([)4081 1800 w
20 HI f
(i.)4153 1800 w
20 H f
(.)4253 1800 w
20 HI f
(j)4342 1800 w
20 H f
(] is greater)2 948 1 4402 1800 t
(than the maximum sum so far.)5 2698 1 720 2040 t
20 HI f
(Code.)720 2760 w
20 CW f
(maxsofar = 0)2 1440 1 720 3055 t
(for i = [0, n\))4 1680 1 720 3290 t
(for j = [i, n\))4 1680 1 1200 3525 t
(sum = 0)2 840 1 1680 3760 t
(for k = [i, j])4 1680 1 1680 3995 t
(sum += x[k])2 1320 1 2160 4230 t
(/* sum is sum of x[i..j] */)6 3240 1 1680 4465 t
(maxsofar = max\(maxsofar, sum\))3 3480 1 1680 4700 t
20 HI f
( O)1 268(Run Time.)1 924 2 720 5480 t
20 H f
(\()1928 5480 w
20 HI f
(n)2010 5480 w
17 H f
(3)2150 5400 w
20 H f
(\).)2277 5480 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-8-3)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 3 3