s08.ps

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

%%Page: 4 4
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
4 pagesetup
20 H f
(A Quadratic Algorithm)2 1962 1 2079 960 t
20 HI f
(Idea.)720 1560 w
20 H f
(The sum of)2 1004 1 1280 1560 t
20 HI f
(x)2340 1560 w
20 H f
([)2456 1560 w
20 HI f
(i.)2528 1560 w
20 H f
(.)2628 1560 w
20 HI f
(j)2717 1560 w
20 H f
(] is close to the previous)5 2154 1 2777 1560 t
(sum,)720 1800 w
20 HI f
(x)1210 1800 w
20 H f
([)1326 1800 w
20 HI f
(i.)1398 1800 w
20 H f
(.)1498 1800 w
20 HI f
(j)1587 1800 w
20 S f
(-)1664 1800 w
20 H f
(1 ].)1 240 1 1807 1800 t
20 HI f
(Code.)720 2520 w
20 CW f
(maxsofar = 0)2 1440 1 720 2815 t
(for i = [0, n\))4 1680 1 720 3050 t
(sum = 0)2 840 1 1200 3285 t
(for j = [i, n\))4 1680 1 1200 3520 t
(sum += x[j])2 1320 1 1680 3755 t
(/* sum is sum of x[i..j] */)6 3240 1 1680 3990 t
(maxsofar = max\(maxsofar, sum\))3 3480 1 1680 4225 t
20 HI f
( O)1 268(Run Time.)1 924 2 720 5005 t
20 H f
(\()1928 5005 w
20 HI f
(n)2010 5005 w
17 H f
(2)2150 4925 w
20 H f
(\).)2277 5005 w
20 HI f
(Other Quadratic Algorithms?)2 2542 1 720 5725 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-4)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 4 4
%%Page: 5 5
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
5 pagesetup
20 H f
(Another Quadratic Algorithm)2 2532 1 1794 960 t
20 HI f
(Idea.)720 1560 w
20 H f
(A ``cumulative array'' allows sums to be com-)7 3986 1 1280 1560 t
( If)1 224(puted quickly.)1 1228 2 720 1800 t
20 HI f
(ytd)2228 1800 w
20 H f
([)2512 1800 w
20 HI f
(i)2584 1800 w
20 H f
(] contains year-to-date sales)3 2522 1 2644 1800 t
(through month)1 1296 1 720 2040 t
20 HI f
(i)2072 2040 w
20 H f
(, then sales from March through)5 2834 1 2116 2040 t
(September are given by)3 2132 1 720 2280 t
20 HI f
(ytd)2908 2280 w
20 H f
([)3192 2280 w
20 HI f
(sep)3264 2280 w
20 H f
(])3604 2280 w
20 S f
(-)3782 2280 w
20 HI f
(ytd)3997 2280 w
20 H f
([)4281 2280 w
20 HI f
(feb)4386 2280 w
20 H f
(].)4682 2280 w
20 HI f
(Implementation.)720 3000 w
20 H f
(Use the cumulative array)3 2218 1 2260 3000 t
20 HI f
(cumarr)4534 3000 w
20 H f
(.)5156 3000 w
(Initialize)720 3240 w
20 HI f
(cumarr)1500 3240 w
20 H f
([)2138 3240 w
20 HI f
(i)2210 3240 w
20 H f
(])2270 3240 w
20 S f
(=)2448 3240 w
20 HI f
(x)2663 3240 w
20 H f
([ 0 ])2 256 1 2779 3240 t
20 S f
(+)3068 3240 w
20 H f
(. . .)2 280 1 3267 3190 t
20 S f
(+)3636 3240 w
20 HI f
(x)3779 3240 w
20 H f
([)3895 3240 w
20 HI f
(i)3967 3240 w
20 H f
( sum of)2 658(]. The)1 570 2 4027 3240 t
(the values in)2 1128 1 720 3480 t
20 HI f
(x)1904 3480 w
20 H f
([)2020 3480 w
20 HI f
(i.)2092 3480 w
20 H f
(.)2192 3480 w
20 HI f
(j)2281 3480 w
20 H f
(] is)1 312 1 2341 3480 t
20 HI f
(cumarr)2709 3480 w
20 H f
([)3347 3480 w
20 HI f
(j)3452 3480 w
20 H f
(])3512 3480 w
20 S f
(-)3601 3480 w
20 HI f
(cumarr)3744 3480 w
20 H f
([)4382 3480 w
20 HI f
(i)4454 3480 w
20 S f
(-)4547 3480 w
20 H f
(1 ].)1 240 1 4690 3480 t
20 HI f
(Code for Algorithm 2b.)3 2008 1 720 4200 t
20 CW f
(cumarr[-1] = 0)2 1680 1 720 4495 t
(for i = [0, n\))4 1680 1 720 4730 t
(cumarr[i] = cumarr[i-1] + x[i])4 3600 1 1200 4965 t
(maxsofar = 0)2 1440 1 720 5200 t
(for i = [0, n\))4 1680 1 720 5435 t
(for j = [i, n\))4 1680 1 1200 5670 t
(sum = cumarr[j] - cumarr[i-1])4 3480 1 1680 5905 t
(/* sum is sum of x[i..j] */)6 3240 1 1680 6140 t
(maxsofar = max\(maxsofar, sum\))3 3480 1 1680 6375 t
20 HI f
( O)1 268(Run Time.)1 924 2 720 7155 t
20 H f
(\()1928 7155 w
20 HI f
(n)2010 7155 w
17 H f
(2)2150 7075 w
20 H f
(\).)2277 7155 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-5)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 5 5
%%Page: 6 6
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
6 pagesetup
20 H f
(An)1956 960 w
20 HI f
(O)2258 960 w
20 H f
(\()2430 960 w
20 HI f
(n)2512 960 w
20 H f
(log)2712 960 w
20 HI f
(n)3068 960 w
20 H f
(\) Algorithm)1 968 1 3196 960 t
20 HI f
(The Divide-and-Conquer Schema.)2 3044 1 720 1800 t
20 H f
(To solve a prob-)3 1450 1 3876 1800 t
(lem of size)2 958 1 720 2040 t
20 HI f
(n)1734 2040 w
20 H f
(, recursively solve two subproblems of)5 3388 1 1846 2040 t
(size)720 2280 w
20 HI f
(n /)1 184 1 1132 2280 t
20 H f
(2 and combine their solutions.)4 2668 1 1332 2280 t
20 HI f
(The Idea.)1 850 1 720 3000 t
20 H f
(Divide into two subproblems.)3 2564 1 1682 3000 t
1260 3324 1260 3612 Dl
3060 3324 1260 3324 Dl
3060 3612 3060 3324 Dl
1260 3612 3060 3612 Dl
20 HI f
(a)2104 3508 w
3060 3324 3060 3612 Dl
4860 3324 3060 3324 Dl
4860 3612 4860 3324 Dl
3060 3612 4860 3612 Dl
(b)3904 3508 w
20 H f
(Recursively \256nd maximum in subvectors.)4 3630 1 720 4008 t
1260 4332 1260 4620 Dl
1548 4332 1260 4332 Dl
1548 4620 1548 4332 Dl
1260 4620 1548 4620 Dl
1548 4332 1548 4620 Dl
2340 4332 1548 4332 Dl
2340 4620 2340 4332 Dl
1548 4620 2340 4620 Dl
20 HI f
(m)1792 4516 w
17 HI f
(a)1986 4556 w
20 H f
2340 4332 2340 4620 Dl
3060 4332 2340 4332 Dl
3060 4620 3060 4332 Dl
2340 4620 3060 4620 Dl
3060 4332 3060 4620 Dl
3276 4332 3060 4332 Dl
3276 4620 3276 4332 Dl
3060 4620 3276 4620 Dl
3276 4332 3276 4620 Dl
3924 4332 3276 4332 Dl
3924 4620 3924 4332 Dl
3276 4620 3924 4620 Dl
20 HI f
(m)3448 4516 w
17 HI f
(b)3642 4556 w
20 H f
3924 4332 3924 4620 Dl
4860 4332 3924 4332 Dl
4860 4620 4860 4332 Dl
3924 4620 4860 4620 Dl
(Find maximum crossing subvector.)3 3096 1 720 5016 t
1260 5340 1260 5628 Dl
2628 5340 1260 5340 Dl
2628 5628 2628 5340 Dl
1260 5628 2628 5628 Dl
2628 5340 2628 5628 Dl
3276 5340 2628 5340 Dl
3276 5628 3276 5340 Dl
2628 5628 3276 5628 Dl
20 HI f
(m)2805 5524 w
17 HI f
(c)2999 5564 w
20 H f
3276 5340 3276 5628 Dl
4860 5340 3276 5340 Dl
4860 5628 4860 5340 Dl
3276 5628 4860 5628 Dl
(Return max of)2 1260 1 720 6024 t
20 HI f
(m)2036 6024 w
17 HI f
(a)2230 6064 w
20 H f
(,)2341 6024 w
20 HI f
(m)2453 6024 w
17 HI f
(b)2647 6064 w
20 H f
(and)2814 6024 w
20 HI f
(m)3206 6024 w
17 HI f
(c)3400 6064 w
20 H f
(.)3501 6024 w
20 HI f
( O)1 268(Run Time.)1 924 2 720 6744 t
20 H f
(\()1928 6744 w
20 HI f
(n)2010 6744 w
20 H f
(log)2210 6744 w
20 HI f
(n)2566 6744 w
20 H f
(\).)2694 6744 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-6)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 6 6
%%Page: 7 7
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
7 pagesetup
20 H f
(Code for the)2 1106 1 1494 960 t
20 HI f
(O)2656 960 w
20 H f
(\()2828 960 w
20 HI f
(N)2910 960 w
20 H f
(log)3142 960 w
20 HI f
(N)3498 960 w
20 H f
(\) Algorithm)1 968 1 3658 960 t
20 CW f
(float maxsum3\(l, u\))2 2280 1 720 1615 t
( zero elements */)3 2040( /*)1 480(if \(l > u\))3 1200 3 1200 1850 t
(return 0)1 960 1 1680 2085 t
( one element */)3 1800( /*)1 480(if \(l == u\))3 1320 3 1200 2320 t
(return max\(0, x[l]\))2 2280 1 1680 2555 t
(m = \(l + u\) / 2)6 1800 1 1200 2907 t
(/* find max crossing to left */)6 3720 1 1200 3142 t
(lmax = sum = 0)4 1680 1 1200 3377 t
(for \(i = m; i >= l; i--\))7 2880 1 1200 3612 t
(sum += x[i])2 1320 1 1680 3847 t
(lmax = max\(lmax, sum\))3 2520 1 1680 4082 t
(/* find max crossing to right */)6 3840 1 1200 4317 t
(rmax = sum = 0)4 1680 1 1200 4552 t
(for i = \(m, u])4 1680 1 1200 4787 t
(sum += x[i])2 1320 1 1680 5022 t
(rmax = max\(rmax, sum\))3 2520 1 1680 5257 t
(return max\(lmax+rmax,)1 2520 1 1200 5609 t
(maxsum3\(l, m\),)1 1680 1 2520 5844 t
(maxsum3\(m+1, u\)\))1 1920 1 2520 6079 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-7)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 7 7
%%Page: 8 8
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
8 pagesetup
20 H f
(A Linear Algorithm)2 1650 1 2235 960 t
20 HI f
(Idea.)720 1560 w
20 H f
(How can we extend a solution for)6 2958 1 1280 1560 t
20 HI f
(x)4294 1560 w
20 H f
([ 0)1 184 1 4410 1560 t
20 HI f
(.)4610 1560 w
20 H f
(.)4666 1560 w
20 HI f
(i)4738 1560 w
20 S f
(-)4831 1560 w
20 H f
(1 ])1 184 1 4974 1560 t
(into a solution for)3 1530 1 720 1800 t
20 HI f
(x)2306 1800 w
20 H f
([ 0)1 184 1 2422 1800 t
20 HI f
(.)2622 1800 w
20 H f
(.)2678 1800 w
20 HI f
(i)2750 1800 w
20 H f
( variables:)1 914(]? Key)1 626 2 2810 1800 t
1260 2124 1260 2412 Dl
1620 2124 1260 2124 Dl
1620 2412 1620 2124 Dl
1260 2412 1620 2412 Dl
1620 2124 1620 2412 Dl
2700 2124 1620 2124 Dl
2700 2412 2700 2124 Dl
1620 2412 2700 2412 Dl
20 HI f
(maxsofar)1748 2308 w
2700 2124 2700 2412 Dl
3276 2124 2700 2124 Dl
3276 2412 3276 2124 Dl
2700 2412 3276 2412 Dl
3276 2124 3276 2412 Dl
4860 2124 3276 2124 Dl
4860 2412 4860 2124 Dl
3276 2412 4860 2412 Dl
(maxhere)3678 2308 w
(I)4776 2586 w
(Code.)720 3302 w
20 CW f
(maxsofar = 0)2 1440 1 720 3597 t
(maxhere = 0)2 1320 1 720 3832 t
(for i = [0, n\))4 1680 1 720 4067 t
(/* invariant: maxhere and maxsofar)4 4080 1 1200 4302 t
(are accurate for x[0..i-1] */)4 3480 1 1560 4537 t
(maxhere = max\(maxhere + x[i], 0\))5 3840 1 1200 4772 t
(maxsofar = max\(maxsofar, maxhere\))3 3960 1 1200 5007 t
20 HI f
( O)1 268(Run Time.)1 924 2 720 5787 t
20 H f
(\()1928 5787 w
20 HI f
(n)2010 5787 w
20 H f
(\).)2138 5787 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-8)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 8 8
%%Page: 9 9
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
9 pagesetup
20 H f
(Summary of the Algorithms)3 2418 1 1851 960 t
16 S f
(_ ___________________________________________________________________)1 5390 1 504 1450 t
(_ ___________________________________________________________________)1 5390 1 504 1470 t
16 HB f
(A)785 1660 w
14 HB f
(LGORITHM)900 1660 w
16 HB f
( 4)1 1015( 3)1 993(1 2)1 1058 3 2506 1660 t
16 S f
(_ ___________________________________________________________________)1 5390 1 504 1700 t
16 H f
(Run time in)2 813 1 504 1900 t
(nanoseconds)504 2100 w
(1. 3)1 238 1 2327 2000 t
16 HI f
(n)2578 2000 w
13 H f
(3)2689 1936 w
16 H f