QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2797|回复: 0
打印 上一主题 下一主题

[讨论]一道分治法的题目,仅供参考

[复制链接]
字体大小: 正常 放大
lllaaa        

2

主题

2

听众

27

积分

升级  23.16%

该用户从未签到

新人进步奖

跳转到指定楼层
1#
发表于 2005-9-29 19:02 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
< ><FONT face="Times New Roman">2-2</FONT>、下面的<FONT face="Times New Roman">7</FONT>个算法与本章中的二分搜索算法<FONT face="Times New Roman">binarySearch</FONT>略有不同。请判断这<FONT face="Times New Roman">7</FONT>个算法的正确性。如果算法不正确,请说明错误产生的原因。如果算法正确,请给出算法的正确性证明。</P>
2 r. ]. ]- C2 g5 x# E9 |; R< ><FONT face="Times New Roman">public static int binarySearch1(int[] a, int x, int n)</FONT></P>
; ?  f* t# N$ f3 I$ Q< ><FONT face="Times New Roman">{</FONT></P>1 X2 \0 O% P' M. v7 Z/ O1 C7 R
< ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P>
( J# U/ U% p; H0 o5 K3 p< ><FONT face="Times New Roman">              while(left &lt;= right)</FONT></P>9 N9 V" E1 }; W. K# r# A) z
< ><FONT face="Times New Roman">{</FONT></P>, T/ M, U6 @" d: c* J3 d% o  T/ [3 o
< ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>
4 L3 b9 J1 I& s3 ?) G< ><FONT face="Times New Roman">   if(x == a[middle]) return middle;</FONT></P>
, F$ ?/ w3 X' S1 s< ><FONT face="Times New Roman">   if(x &gt; a[middle]) left = middle;</FONT></P>1 f+ p( j+ a6 X# \, T
< ><FONT face="Times New Roman">   else right = middle;</FONT></P>
  p" ^/ l, o" |# k  ?9 V7 g< ><FONT face="Times New Roman">}//while</FONT></P>) j/ q" |0 N6 {7 f# J# \
< ><FONT face="Times New Roman">return –1;</FONT></P>/ p; _. x9 ~4 P  Q- i" N, K
< ><FONT face="Times New Roman">}</FONT></P>  D, A5 S4 t+ `& f
< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
; k, n+ `( \/ m2 r< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>8 G8 \& z/ z+ F( ^5 s
< ><FONT face="Times New Roman">public static int binarySearch2(int[] a, int x, int n)</FONT></P>
, g  _- b3 L9 |" |2 y, h+ r< ><FONT face="Times New Roman">{</FONT></P>" e5 v. d9 x" `  Y
< ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P>9 c, P/ @; {6 I
< ><FONT face="Times New Roman">              while(left &lt; right-1)</FONT></P>
! G  ]; d# i1 w$ F/ p8 T< ><FONT face="Times New Roman">{</FONT></P>
' M& t  D2 o" l3 U< ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>8 I/ W0 _8 j5 `* z% ]
< ><FONT face="Times New Roman">   if(x &lt; a[middle]) right = middle;</FONT></P>
* f& i; Y4 s# ^4 I7 Q4 p< ><FONT face="Times New Roman">   else left = middle;</FONT></P>- m" D5 f0 h) _0 ^  G
< ><FONT face="Times New Roman">}//while</FONT></P># i0 E9 c4 {6 m- h
< ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
, W% z' R, E: s4 Q, |" R$ n0 x< ><FONT face="Times New Roman">else return –1;</FONT></P>
4 D; e0 V. H, V5 @5 m  q3 S) t6 H+ p< ><FONT face="Times New Roman">}</FONT></P>
) b/ H1 h6 g+ _# e2 [0 ^< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
, v+ n; s: O3 a< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>1 N  i9 c2 H- ]5 v" f" C. U
< ><FONT face="Times New Roman">public static int binarySearch3(int[] a, int x, int n)</FONT></P>
( Q3 q+ q; q) B6 u0 F" H<P ><FONT face="Times New Roman">{</FONT></P>
7 b$ |2 s+ k: s) W<P ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P>- ~+ p& s4 j: W1 s
<P ><FONT face="Times New Roman">              while(left+1 != right)</FONT></P>
2 J0 V; d+ Y$ K  A2 ]<P ><FONT face="Times New Roman">{</FONT></P>
( D: t" G: w* S8 [5 B; K$ t<P ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>
+ m/ O3 O0 C& Q0 |<P ><FONT face="Times New Roman">   if(x &gt;= a[middle]) left = middle;</FONT></P>" K3 |) Y9 K( K
<P ><FONT face="Times New Roman">   else right = middle;</FONT></P>
6 D! Z; q5 ?2 U) l# L# J7 v<P ><FONT face="Times New Roman">}//while</FONT></P>9 O+ T9 d% p$ |4 c. p
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
( R- W( A% Y* A: V9 t% C/ I<P ><FONT face="Times New Roman">else return –1;</FONT></P>
3 I. u4 u! \3 k6 [<P ><FONT face="Times New Roman">}</FONT></P>; `+ j$ N3 G/ R3 z' Z9 W  Q5 _4 p1 Z
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>: M0 t) N. y" S0 s
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
; t" f$ E" B( D/ @7 b<P ><FONT face="Times New Roman">public static int binarySearch4(int[] a, int x, int n)</FONT></P>2 R- a2 B+ K6 w
<P ><FONT face="Times New Roman">{</FONT></P>1 m, |$ @. u  R7 r( _
<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>
& I$ r# b" z9 E  w0 }<P ><FONT face="Times New Roman">              {</FONT></P>
) a( n8 j6 s$ |5 Z0 x<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>* v6 W7 P3 N6 K2 H, {. h; E
<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>2 d" e6 i% d3 v/ W) q
<P ><FONT face="Times New Roman">              {</FONT></P>; W2 H9 y8 f4 ^5 m( Q) {/ p% _
<P ><FONT face="Times New Roman">          int middle = (left + right) / 2;</FONT></P>
( c9 n9 x8 {0 F' c<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P>
7 N! V0 ?# x5 g( L& l9 U<P ><FONT face="Times New Roman">else left = middle;</FONT></P>8 A- V7 b' I9 W& Y0 u! P
<P ><FONT face="Times New Roman">}//while</FONT></P>
9 Y4 c- ~5 d' s- g<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P># x9 b8 a/ V: h  T
<P ><FONT face="Times New Roman">}//if</FONT></P>" \) W/ H# R) \7 a) I
<P ><FONT face="Times New Roman">return –1;</FONT></P>
/ z0 J  Y- q6 G7 a% c9 X<P ><FONT face="Times New Roman">}</FONT></P>
6 n( M1 H4 s/ f' @- h- B# w0 I2 W. q<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
1 e/ v6 |& p% y  T# c: x$ D<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
. q3 A" u. d( `% p+ {<P ><FONT face="Times New Roman">public static int binarySearch5(int[] a, int x, int n)</FONT></P>! \. g: u  m5 k- V3 P
<P ><FONT face="Times New Roman">{</FONT></P>
# ?: w# |. o! r8 Y4 Q: l9 ~0 V" p<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>
, ^( a* [5 ]  l& v3 Q: E& M<P ><FONT face="Times New Roman">              {</FONT></P>
3 A: j7 C6 l4 S6 I" [' a& n<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>3 b) P4 n9 \+ k) ?" q2 E
<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>  @; [( {3 R8 b/ k1 L
<P ><FONT face="Times New Roman">              {</FONT></P>
/ {$ Y. D/ Z: p<P ><FONT face="Times New Roman">          int middle = (left + right + 1) / 2;</FONT></P>
0 O2 |" U8 t! i# C" Z0 J<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P>0 |7 p9 f; `- A+ K( h' g% f7 g
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>! ~% J5 o) p" _8 p! x7 Z* w
<P ><FONT face="Times New Roman">}//while</FONT></P>9 V3 E" W* {; B, A
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>5 [1 H7 u, M% _' u
<P ><FONT face="Times New Roman">}//if</FONT></P>) ]' Q- K3 @* F) y  T4 F9 d  b* k# }- |
<P ><FONT face="Times New Roman">return –1;</FONT></P>
& o. i4 R+ G6 l  K( P<P ><FONT face="Times New Roman">}</FONT></P>* f8 R" c. h1 z$ R# J% ~. e0 h
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>- D4 y" n- n0 W8 A7 v8 x; Z9 W
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
$ `% K3 j- ]6 P0 ^3 v<P ><FONT face="Times New Roman">public static int binarySearch6(int[] a, int x, int n)</FONT></P>8 E* Q) B4 }, q& k& R
<P ><FONT face="Times New Roman">{</FONT></P>! E# n, \  a1 E7 M# A1 c' O
<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>
3 U9 M' q; G+ c<P ><FONT face="Times New Roman">              {</FONT></P>8 H4 C/ `) Y& ^; ]* D- r
<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>
' p5 C: Q7 Z- U* Z& P# Q  `/ ?<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>0 z9 Z# u$ j! C1 R( o( s4 g
<P ><FONT face="Times New Roman">              {</FONT></P>8 n1 a& Y, Y7 ^3 N/ t
<P ><FONT face="Times New Roman">          int middle = (left + right + 1) / 2;</FONT></P>
# C. X5 t/ ?% H2 i<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P># _+ a4 n$ u  O
<P ><FONT face="Times New Roman">else left = middle + 1;</FONT></P>8 @& ?/ v" d7 p! ]7 H2 M
<P ><FONT face="Times New Roman">}//while</FONT></P>
, J  `- ?# ]8 m# R<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
  M, a( C& y: w8 T- [% l<P ><FONT face="Times New Roman">}//if</FONT></P>( ]1 z$ x+ L4 h4 `9 K0 j9 g% C6 w
<P ><FONT face="Times New Roman">return –1;</FONT></P>5 S: w+ d5 g' E6 L
<P ><FONT face="Times New Roman">}</FONT></P>
0 [4 `4 E7 p- u% P) Z: x- W; I/ D<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
4 r6 |" ?0 v$ c, ]- L& k- l<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>! {6 d* |# o7 E) _
<P ><FONT face="Times New Roman">public static int binarySearch7(int[] a, int x, int n)</FONT></P>
1 B* P( D- j9 k/ @3 t0 s3 E<P ><FONT face="Times New Roman">{</FONT></P>+ O2 n  {; `" X6 x% n4 W" R, C+ Z
<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>- C% a8 V8 }& K: b
<P ><FONT face="Times New Roman">              {</FONT></P>
9 C$ [0 c# [3 b, s' _<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>
, U, C, K# W: w<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>
' h  M. c  J0 z3 t, m8 ]<P ><FONT face="Times New Roman">              {</FONT></P>
: `! B" |) G1 _! E6 E9 s* _<P ><FONT face="Times New Roman">          int middle = (left + right +1) / 2;</FONT></P>
' N2 z2 M: e( B1 k0 g4 P1 A<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle;</FONT></P>6 c' r' @3 n4 o; h
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
: q7 A' I% d- |% V- ?6 z* p& e# F<P ><FONT face="Times New Roman">}//while</FONT></P>3 t# i8 S2 M0 U) }, \% W; F
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>" q  j. A  t5 m9 o
<P ><FONT face="Times New Roman">}//if</FONT></P>; @& j+ z5 H# l1 t1 }6 r; W- F; Y
<P ><FONT face="Times New Roman">return –1;</FONT></P>
- @' k) Z7 t, Z5 m<P ><FONT face="Times New Roman">}</FONT></P>
- i5 }/ o, G$ K5 s  G<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>2 V% e* g# }' p  b$ G* C) B: J9 _
<P >解:(<FONT face="Times New Roman">1</FONT>)算法<FONT face="Times New Roman">1</FONT>不正确。<o:p></o:p></P>$ y0 }% ^6 W  G& a9 j2 I$ W5 M
<P >当在数组<FONT face="Times New Roman">a</FONT>中找不到与<FONT face="Times New Roman">x</FONT>相等的元素时,算法将进入死循环状态。<o:p></o:p></P>* v; R( t/ Q# s. Y' e6 f2 R
<P >原因:每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改不正确。应修改如下:<o:p></o:p></P>
7 B% b- F; S5 `<P ><FONT face="Times New Roman">if(x &gt; a[middle]) left = middle + 1;<o:p></o:p></FONT></P>+ M6 f1 w9 _  q& L' \
<P ><FONT face="Times New Roman">       else right = middle - 1;<o:p></o:p></FONT></P>
8 ?) U% U! ^( d* f. i<P >(<FONT face="Times New Roman">2</FONT>)算法<FONT face="Times New Roman">2</FONT>不正确。<o:p></o:p></P>9 w6 V- e# Q$ \+ v$ B. N
<P >当<FONT face="Times New Roman">n</FONT>≥<FONT face="Times New Roman">2</FONT>时,如果条件<FONT face="Times New Roman">x = a[n-1] </FONT>且<FONT face="Times New Roman"> a[n-2] </FONT>≠<FONT face="Times New Roman"> a[n-1]</FONT>成立,则必将在某一步之后出现<FONT face="Times New Roman">x = a[left +1]</FONT>,导致永远不会出现<FONT face="Times New Roman">x = a[middle]</FONT>的情形,算法最终在<FONT face="Times New Roman">x = a
</FONT>时结束循环,导致错误地返回<FONT face="Times New Roman">-1</FONT>。<o:p></o:p></P>/ @( v2 N) b4 w/ O' J% \0 m7 q
<P >另外,当<FONT face="Times New Roman">n=0</FONT>时执行<FONT face="Times New Roman">if(x == a
)...</FONT>时将出现下标越界错误。<o:p></o:p></P>
' H, z3 l% I9 u( e1 Q$ o<P >原因:循环结束条件错误,应改为<FONT face="Times New Roman">left &lt;= right</FONT>。每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改也不正确。<o:p></o:p></P>
- Q, _6 w9 @8 I' E' q$ T<P >(<FONT face="Times New Roman">3</FONT>)算法<FONT face="Times New Roman">3</FONT>不正确。<o:p></o:p></P>) u3 S/ f. F4 k( u
<P >除了有与算法<FONT face="Times New Roman">2</FONT>相同的错误,另外当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,必然进入死循环。<o:p></o:p></P>( N- [$ H- C5 e' N; J& J
<P >原因:与算法<FONT face="Times New Roman">2</FONT>相同。<o:p></o:p></P>6 Z' B% h5 y; c- h
<P >(<FONT face="Times New Roman">4</FONT>)算法<FONT face="Times New Roman">4</FONT>不正确。<o:p></o:p></P>
6 K% D. v* c# R" \9 J4 Z<P >如果在循环过程中出现<FONT face="Times New Roman">left = right – 1</FONT>情况,算法即进入死循环。例如<FONT face="Times New Roman"> x</FONT>≥a[n-2]条件成立时,即必然进入死循环。<o:p></o:p></P>' v% v+ j; C6 l3 x5 t, v$ X
<P >原因:循环条件和对变量<FONT face="Times New Roman">left</FONT>值的修改有错误。<o:p></o:p></P>
/ n$ ?8 X& J5 H: y7 r<P >(<FONT face="Times New Roman">5</FONT>)此算法正确。<o:p></o:p></P>3 c$ e) K  E9 q4 K
<P >证明:当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,算法显然正确。<o:p></o:p></P>
7 m# \; U  c* {7 t. G) T5 L<P >当<FONT face="Times New Roman">n</FONT>≥<FONT face="Times New Roman">2</FONT>时,在循环结束前有<FONT face="Times New Roman">x</FONT>≥a[0]且left &lt; right,<o:p></o:p></P>4 O# O$ Y; B+ z' V/ p) x: Q' O
<P >∴<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [left + (right –1) + 1 +1] / 2 </FONT>≥ (2left + 2) / 2 = left + 1,<o:p></o:p></P>6 ^: ]" U# M- a2 V* L5 s* j
<P >即:middle &gt; left成立。<o:p></o:p></P>
+ N* l/ B" g$ z; Z<P >且<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [(left + 1) + right] / 2 </FONT>≤ 2right / 2 = right,<o:p></o:p></P>  p5 B& }+ [8 C  u) F* J
<P >∴left &lt; middle ≤ right恒成立。<o:p></o:p></P>5 r1 B7 v+ g) y
<P >因此,每次循环之后,right与left之差必然减小,在有限次循环后,必有left = right条件成立,从而循环结束。<o:p></o:p></P>% N4 v3 b8 p& f8 [& t. v7 \8 T
<P >如果x值与数组a的某个元素值相等,则在循环结束时显然有x = a
且x = a
成立,否则x ≠a
,即未找到x,<o:p></o:p></P>
, ]/ ]$ H5 Z9 m; `# ^+ P" M<P >∴返回结果正确。<o:p></o:p></P>6 I0 F& U! ?) ^3 v, p3 }) c
<P >(6)算法6是错误的。<o:p></o:p></P>& ~) a) e; i# x5 F9 b
<P >当执行到某次循环x = a[middle]成立时,再执行if 语句中的<o:p></o:p></P>, [# Z, j  A# p
<P >left = middle + 1;<o:p></o:p></P>, t# i% R4 e% R: ~3 Q+ \
<P >就把结果丢失了,导致错误。而且还可能会导致下标越界错误。例如:<o:p></o:p></P>0 c3 s6 [6 p# m& c' X4 W& d9 J1 j
<P >当n = 2且x = a[1]时即会出现这些情况。<o:p></o:p></P>9 @& G) ^2 R/ Y, b; q
<P >原因:if 语句中的left = middle + 1;应改为left = middle;<o:p></o:p></P>
0 `- L8 r( O+ {<P >(7)算法7是错误的。<o:p></o:p></P>
" R& @% ~# ^5 M- \# O* T% A<P >在循环过程中,一旦出现<o:p></o:p></P>
; Z% O4 L5 ~7 c0 s<P >a
≤ x &lt; a[left + 1],则必进入死循环。<o:p></o:p></P>
* y6 `/ m" k. `  M- P6 h/ l<P >原因:right值的修改不正确。<o:p></o:p></P>
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-4-21 01:34 , Processed in 0.381485 second(s), 52 queries .

回顶部