QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2838|回复: 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>
$ Y  u7 q+ R6 P0 h4 ~! S  x# v< ><FONT face="Times New Roman">public static int binarySearch1(int[] a, int x, int n)</FONT></P>
) ~5 F% I9 f! Y' x< ><FONT face="Times New Roman">{</FONT></P>
  ~4 I" [+ f5 n1 o: m4 _< ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P>
; m" L7 D$ l% M/ G- _- x< ><FONT face="Times New Roman">              while(left &lt;= right)</FONT></P>. }6 C- [  v" P* S  z  b
< ><FONT face="Times New Roman">{</FONT></P>
( p+ r- J6 C) K< ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>( q9 Q2 H6 {  R6 h- b, O5 N
< ><FONT face="Times New Roman">   if(x == a[middle]) return middle;</FONT></P>- T& n0 N& B8 i8 L& x5 U& b6 ^- d$ B
< ><FONT face="Times New Roman">   if(x &gt; a[middle]) left = middle;</FONT></P>& U/ v3 B2 n7 Z3 y# }
< ><FONT face="Times New Roman">   else right = middle;</FONT></P>$ e7 s1 Z% O0 ~9 K: T8 f
< ><FONT face="Times New Roman">}//while</FONT></P>
) [( e) D2 f8 Y  c. \# z6 s$ z< ><FONT face="Times New Roman">return –1;</FONT></P>
$ f- H0 H$ [+ `4 L5 A< ><FONT face="Times New Roman">}</FONT></P>
1 i6 @" [0 W9 D< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
+ g4 j- k/ u$ @, U; j+ s< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>. q* W8 @& ?! M. m
< ><FONT face="Times New Roman">public static int binarySearch2(int[] a, int x, int n)</FONT></P>* o; M0 G) x. U* ^8 ^, J- P! V
< ><FONT face="Times New Roman">{</FONT></P>
5 Y/ M/ I) t& s% v< ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P>* Y" \" k* J0 D& s1 @$ K. \
< ><FONT face="Times New Roman">              while(left &lt; right-1)</FONT></P>
+ Y  @% b$ O# M/ P# Y< ><FONT face="Times New Roman">{</FONT></P>
1 K  c8 m+ \$ t4 D) u7 \< ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>0 x* A; g( H. x" n) B9 E( g' r- r
< ><FONT face="Times New Roman">   if(x &lt; a[middle]) right = middle;</FONT></P>
+ e) U# E6 X& _- V* ], f: t. w: ^< ><FONT face="Times New Roman">   else left = middle;</FONT></P>
) h1 L; L. ^4 o. }< ><FONT face="Times New Roman">}//while</FONT></P>
2 @) A: |. `7 E1 c) s< ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>) f' ?( P# `9 d' D2 R% m; z! X& w( [
< ><FONT face="Times New Roman">else return –1;</FONT></P>
: d3 ~3 Z* `  M: X( M" t$ {< ><FONT face="Times New Roman">}</FONT></P>
$ `* N- \6 t) @5 w0 E. ^< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
' Y) N) y% z  Z< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>8 N! y4 a8 `9 l7 X) O
< ><FONT face="Times New Roman">public static int binarySearch3(int[] a, int x, int n)</FONT></P>; {" E3 I( ~- S0 z
<P ><FONT face="Times New Roman">{</FONT></P>
# D6 _% y9 w4 N: Z+ A6 }1 {  p0 p<P ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P>0 }0 T, G- f8 U& S8 `
<P ><FONT face="Times New Roman">              while(left+1 != right)</FONT></P>" j3 u4 f! o0 g' P
<P ><FONT face="Times New Roman">{</FONT></P>+ F8 ]5 H* ~2 e3 ^5 O$ ]9 v
<P ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>  b- |' r9 x% n& P8 H0 Q
<P ><FONT face="Times New Roman">   if(x &gt;= a[middle]) left = middle;</FONT></P>6 m0 F2 E1 l3 ^! W! _, F" J
<P ><FONT face="Times New Roman">   else right = middle;</FONT></P>
! `7 A) I  l8 K/ k/ z6 g7 O<P ><FONT face="Times New Roman">}//while</FONT></P>
$ R$ z& u4 T: X& S9 P) k<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
$ x% h( q7 F; W" c& W<P ><FONT face="Times New Roman">else return –1;</FONT></P>" |2 r& k- o- X( P9 T' o% r
<P ><FONT face="Times New Roman">}</FONT></P>
# Y7 N% a, t( x9 l& T<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>6 g3 k: I6 v5 v; s
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P># K4 D, g3 l& G* B& F' v
<P ><FONT face="Times New Roman">public static int binarySearch4(int[] a, int x, int n)</FONT></P>
7 e6 z  j2 q" n: q<P ><FONT face="Times New Roman">{</FONT></P>
0 R8 C- u8 l9 T) v) E2 Z3 y9 F+ }<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>* J0 x, v' A& Z) x- B
<P ><FONT face="Times New Roman">              {</FONT></P>
) g2 d% R5 |1 [& d. j<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>
, B  [% k% ]: m: i! |! F" Z- C8 B<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>
1 V/ D+ \. }( }: p<P ><FONT face="Times New Roman">              {</FONT></P>( \) k! l; T  u5 L9 _
<P ><FONT face="Times New Roman">          int middle = (left + right) / 2;</FONT></P>4 I; G8 h+ ^9 n$ |3 m
<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P>' q  B* O- k: x$ A$ t* I  g# c3 s
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
( \+ I. ]) [3 i& a% d<P ><FONT face="Times New Roman">}//while</FONT></P>
6 N- a; F( F/ s, c1 \3 l4 D<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
' g. N  n3 @; [7 k, n4 t<P ><FONT face="Times New Roman">}//if</FONT></P>* f) \+ Z% U6 e$ R6 p2 [. O9 D+ {8 P0 N
<P ><FONT face="Times New Roman">return –1;</FONT></P>
% ?1 C1 A. M: f( d7 W8 Q<P ><FONT face="Times New Roman">}</FONT></P>0 ~+ c9 t0 e5 d
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
. Y( D$ @. [+ P# @<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>6 H5 j6 ^3 o' R
<P ><FONT face="Times New Roman">public static int binarySearch5(int[] a, int x, int n)</FONT></P>: k/ I" v- v# |: |+ M" s: n
<P ><FONT face="Times New Roman">{</FONT></P>
; @+ A5 `7 U% b- n8 D<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>5 b, d% w/ ^6 Q6 g. r9 n: J
<P ><FONT face="Times New Roman">              {</FONT></P>1 k& ]. Q  G8 ~; R0 y) X! J  d1 W1 l
<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>
* n; i9 y4 v5 j& F3 T<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>) F+ V- R& c% _& }0 G1 I: I1 M, }
<P ><FONT face="Times New Roman">              {</FONT></P>" F: q6 E" S, T/ S0 t' k, `
<P ><FONT face="Times New Roman">          int middle = (left + right + 1) / 2;</FONT></P>* s) J7 M: b. t% F4 j" ^
<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P>+ F$ L! M) O6 e; g. L; d
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
  b* N: Z; r% x3 R( D$ e! \, L<P ><FONT face="Times New Roman">}//while</FONT></P>0 I+ R, B5 Y/ L1 M7 s
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
$ l. t1 `  F3 G. e2 q<P ><FONT face="Times New Roman">}//if</FONT></P>
: M' V# e+ R7 {<P ><FONT face="Times New Roman">return –1;</FONT></P>+ E6 A& i$ @3 C1 Y+ h# H  K
<P ><FONT face="Times New Roman">}</FONT></P>, c, U4 G' b  B' }8 t( ]) H
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>( J& B7 @7 y' _, `. c' ~
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
) T/ A8 @; S0 k) Z, y, q<P ><FONT face="Times New Roman">public static int binarySearch6(int[] a, int x, int n)</FONT></P>
7 O; M; i: ]9 }2 @2 G+ r$ [& z" K$ n<P ><FONT face="Times New Roman">{</FONT></P>$ }, y5 L2 @5 j: }, I4 d
<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>  ]  o' O3 B1 d  S4 Y; K+ W- x: G! Q
<P ><FONT face="Times New Roman">              {</FONT></P>! U5 z+ h& h9 f) k
<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>( U  D# k& _2 _* P
<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>7 u8 V( ], a; h! o& g
<P ><FONT face="Times New Roman">              {</FONT></P>
, m5 j* n$ j# r" c<P ><FONT face="Times New Roman">          int middle = (left + right + 1) / 2;</FONT></P>) C0 Y' R& p: M- b
<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P>
8 p. m/ J# Y7 X3 \0 T2 a! J<P ><FONT face="Times New Roman">else left = middle + 1;</FONT></P>
( t1 y/ o4 ]  H1 T) \+ x" X% [0 c4 U5 ^5 p<P ><FONT face="Times New Roman">}//while</FONT></P>
* L! x1 B7 e9 w5 s; |/ b<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>* l: E( W( F0 R5 U6 D# w
<P ><FONT face="Times New Roman">}//if</FONT></P>
7 D, e' z8 l: S1 C' y* E<P ><FONT face="Times New Roman">return –1;</FONT></P>
+ W! P+ m, V* Y, k0 j<P ><FONT face="Times New Roman">}</FONT></P>
: b( g! }6 a3 N<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>, v& V0 z4 y7 Y( w  l: X, v5 s
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
, G% P" p+ {+ J$ W" L4 U<P ><FONT face="Times New Roman">public static int binarySearch7(int[] a, int x, int n)</FONT></P>6 L/ U" ?+ b3 H8 w+ g" U( A" R
<P ><FONT face="Times New Roman">{</FONT></P>1 W; g& p0 a% I
<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>
9 D; ^, L) ~0 @- _& z8 B<P ><FONT face="Times New Roman">              {</FONT></P>
- H8 Q" p/ m) k$ H5 j<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>
& a% f# d/ M( [, b7 P( {<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>
# H. k+ B) m6 D<P ><FONT face="Times New Roman">              {</FONT></P>
8 f/ m" H, Q! v. \& W6 g5 X' @<P ><FONT face="Times New Roman">          int middle = (left + right +1) / 2;</FONT></P>8 G# c  v4 U7 H  I$ x$ A7 t9 W/ V. l
<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle;</FONT></P>% w  W6 H& |. M( v* x4 F/ F
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>; L; w, k7 }1 m1 t8 I
<P ><FONT face="Times New Roman">}//while</FONT></P>
4 O5 f0 v# x& c- u1 U<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>
! R; o" J( A' V# p4 }( ?" D+ m<P ><FONT face="Times New Roman">}//if</FONT></P>2 V3 T* w2 ^% q0 x% Q
<P ><FONT face="Times New Roman">return –1;</FONT></P>
. M+ R+ r# R6 \5 {! m4 O( _/ S8 S  i<P ><FONT face="Times New Roman">}</FONT></P>" e" d( l; T; w/ U0 Q
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
! ]) Q- t( k2 S/ U8 C<P >解:(<FONT face="Times New Roman">1</FONT>)算法<FONT face="Times New Roman">1</FONT>不正确。<o:p></o:p></P>) C) {: j* {' {" j) v3 ^4 R- r
<P >当在数组<FONT face="Times New Roman">a</FONT>中找不到与<FONT face="Times New Roman">x</FONT>相等的元素时,算法将进入死循环状态。<o:p></o:p></P>
+ D3 C: i/ K& S, b! F6 r<P >原因:每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改不正确。应修改如下:<o:p></o:p></P>
- ?3 p! Z0 n  Z<P ><FONT face="Times New Roman">if(x &gt; a[middle]) left = middle + 1;<o:p></o:p></FONT></P>0 T" G& _! J& }1 q! o  p+ }( G
<P ><FONT face="Times New Roman">       else right = middle - 1;<o:p></o:p></FONT></P>: f" I/ u7 J+ N- |9 U
<P >(<FONT face="Times New Roman">2</FONT>)算法<FONT face="Times New Roman">2</FONT>不正确。<o:p></o:p></P>
! c- E+ X0 _' u2 L, K<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>& U5 L# S; a1 h4 }
<P >另外,当<FONT face="Times New Roman">n=0</FONT>时执行<FONT face="Times New Roman">if(x == a
)...</FONT>时将出现下标越界错误。<o:p></o:p></P>3 E% t+ F+ Z) S$ `5 p) V
<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>
9 n0 g. e& v) x<P >(<FONT face="Times New Roman">3</FONT>)算法<FONT face="Times New Roman">3</FONT>不正确。<o:p></o:p></P>
& f" [6 _' Y7 v$ \$ z<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>- W. P0 F6 {% c# R" I: f4 I9 N2 ]
<P >原因:与算法<FONT face="Times New Roman">2</FONT>相同。<o:p></o:p></P>& `) e8 }/ p( y# r
<P >(<FONT face="Times New Roman">4</FONT>)算法<FONT face="Times New Roman">4</FONT>不正确。<o:p></o:p></P>
% t1 ~( \  r/ \<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>& x2 I" K" W: @7 z# i
<P >原因:循环条件和对变量<FONT face="Times New Roman">left</FONT>值的修改有错误。<o:p></o:p></P>
& }% l8 A" |& {9 I<P >(<FONT face="Times New Roman">5</FONT>)此算法正确。<o:p></o:p></P>6 {4 R3 S+ I, y( W- {( G) k
<P >证明:当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,算法显然正确。<o:p></o:p></P>
; {: r7 H$ a3 T<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>
( c7 m, U1 G$ S' |<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>
3 O; X. ]# X' W- `# x6 V# ~* ^) ]<P >即:middle &gt; left成立。<o:p></o:p></P>, b8 H+ O1 O/ L. `9 h
<P >且<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [(left + 1) + right] / 2 </FONT>≤ 2right / 2 = right,<o:p></o:p></P>
. d' z  y. P$ j  V" A# K! m<P >∴left &lt; middle ≤ right恒成立。<o:p></o:p></P>
" W$ t( x* I9 ^! A8 B" K: }/ p0 n<P >因此,每次循环之后,right与left之差必然减小,在有限次循环后,必有left = right条件成立,从而循环结束。<o:p></o:p></P>
) \" B% Z' R# K5 q& A<P >如果x值与数组a的某个元素值相等,则在循环结束时显然有x = a
且x = a
成立,否则x ≠a
,即未找到x,<o:p></o:p></P>, |) M9 m7 s0 ^( q  ?! d
<P >∴返回结果正确。<o:p></o:p></P>5 a/ k2 z& d: m; r' N
<P >(6)算法6是错误的。<o:p></o:p></P>+ v5 j1 d* d6 g3 P8 n/ I  ^7 s
<P >当执行到某次循环x = a[middle]成立时,再执行if 语句中的<o:p></o:p></P>
0 z/ N- y6 L4 R& j! G5 ~<P >left = middle + 1;<o:p></o:p></P>( Z  u& p4 t6 I% H3 ?! P. ?
<P >就把结果丢失了,导致错误。而且还可能会导致下标越界错误。例如:<o:p></o:p></P>/ G* a8 X$ W/ _( Q0 z& B
<P >当n = 2且x = a[1]时即会出现这些情况。<o:p></o:p></P>5 C5 Z1 q% u6 l+ A
<P >原因:if 语句中的left = middle + 1;应改为left = middle;<o:p></o:p></P>+ y8 v# X1 t) ^9 r6 g
<P >(7)算法7是错误的。<o:p></o:p></P>3 S# u+ s: ?9 [
<P >在循环过程中,一旦出现<o:p></o:p></P>
" A$ @/ x( V" H3 X) ]1 H1 H/ f<P >a
≤ x &lt; a[left + 1],则必进入死循环。<o:p></o:p></P>
3 w2 m% X7 i1 G! m<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-7-21 18:13 , Processed in 0.400825 second(s), 52 queries .

回顶部