QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2839|回复: 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>
) a# X  i" S) K7 \< ><FONT face="Times New Roman">public static int binarySearch1(int[] a, int x, int n)</FONT></P>
  I9 `( ?7 q5 Q< ><FONT face="Times New Roman">{</FONT></P># A9 r4 _, l1 G4 ?
< ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P>2 D4 }2 S: K- g- ?
< ><FONT face="Times New Roman">              while(left &lt;= right)</FONT></P>6 |9 h6 H; B& }, h2 v* l( g" \
< ><FONT face="Times New Roman">{</FONT></P>5 j5 O1 S' d& D5 u$ k- U
< ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>
7 ]: b) E* L8 m< ><FONT face="Times New Roman">   if(x == a[middle]) return middle;</FONT></P>( k) {! W6 {3 Q% ~& H
< ><FONT face="Times New Roman">   if(x &gt; a[middle]) left = middle;</FONT></P>* d- K! F) t  I8 S( t
< ><FONT face="Times New Roman">   else right = middle;</FONT></P>% w2 P( z: X. U
< ><FONT face="Times New Roman">}//while</FONT></P>" ^+ W# r$ G1 d( B4 b3 u  I: L6 C
< ><FONT face="Times New Roman">return –1;</FONT></P>/ X6 [% B7 \5 `+ j* H' i+ \. c& T
< ><FONT face="Times New Roman">}</FONT></P>
" X2 \/ e: V3 V< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>. W2 i! [6 q4 X, n* ]
< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
1 a' I" z2 A9 b& t8 j< ><FONT face="Times New Roman">public static int binarySearch2(int[] a, int x, int n)</FONT></P>. o' C5 @0 m! C
< ><FONT face="Times New Roman">{</FONT></P>: _7 P! `5 t) ?9 m3 F  e- X; ^
< ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P>" }5 r; ]' D, Q9 ~3 ^; [3 q
< ><FONT face="Times New Roman">              while(left &lt; right-1)</FONT></P>( J4 N2 f  v! W# P5 _  R9 P  R
< ><FONT face="Times New Roman">{</FONT></P>! ]& x' H" z- }( K# P4 x
< ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>
5 o7 D/ ]! ?! U  N' V! E9 ^* e< ><FONT face="Times New Roman">   if(x &lt; a[middle]) right = middle;</FONT></P>! e! f% q" k+ H( k3 S) p! c+ k9 I
< ><FONT face="Times New Roman">   else left = middle;</FONT></P>2 N1 |% P" I9 m
< ><FONT face="Times New Roman">}//while</FONT></P>4 {1 I3 R# m/ R, x5 D
< ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>% p" [  b# G) r8 q. V- F( s7 [3 U
< ><FONT face="Times New Roman">else return –1;</FONT></P>
) t+ s% d: e: S+ Y6 x+ }' n6 r< ><FONT face="Times New Roman">}</FONT></P>
/ a- v8 Q8 G6 ~$ s< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
0 j" n( |: A( U8 r& T< ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>2 @4 W4 `8 J  G. M4 |
< ><FONT face="Times New Roman">public static int binarySearch3(int[] a, int x, int n)</FONT></P>
; p& {/ a3 w: i  T+ Q' p8 l) L<P ><FONT face="Times New Roman">{</FONT></P>& P# D' D$ w9 \! u  Z
<P ><FONT face="Times New Roman">              int left = 0, right = n-1;</FONT></P># @* Y; q( G* {0 ]/ ]- |& [
<P ><FONT face="Times New Roman">              while(left+1 != right)</FONT></P>$ Z: y: m) s2 Y- z! K' p# T3 u; T' G
<P ><FONT face="Times New Roman">{</FONT></P>
7 Y5 }9 h& B* B; ^<P ><FONT face="Times New Roman">   int middle = (left + right) / 2;</FONT></P>4 B% h+ {, f5 }$ `* v6 z4 Q/ N( t3 K+ X
<P ><FONT face="Times New Roman">   if(x &gt;= a[middle]) left = middle;</FONT></P>+ X6 r* r4 e* ]  I: W
<P ><FONT face="Times New Roman">   else right = middle;</FONT></P>
* A! U5 ^9 h4 M9 U<P ><FONT face="Times New Roman">}//while</FONT></P>% Q& h  ]3 t- }6 Y
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>  a; R# d" ]: m6 C/ O
<P ><FONT face="Times New Roman">else return –1;</FONT></P>: Q. H- A) n  G5 u/ o. S9 N6 }
<P ><FONT face="Times New Roman">}</FONT></P>
. h4 P/ H7 t' m( j! d8 x4 ?<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>- E0 O: w4 f: d0 E* b- m2 t
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
5 \: b) o9 V  J8 t. |<P ><FONT face="Times New Roman">public static int binarySearch4(int[] a, int x, int n)</FONT></P>0 Z3 G( P, l: [- T% Y/ I. h& h
<P ><FONT face="Times New Roman">{</FONT></P>/ ~3 U) I" W+ m: Z
<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>
6 y' ]8 Z6 i& R8 Q: @  \3 M<P ><FONT face="Times New Roman">              {</FONT></P>+ t1 }/ N( x1 p
<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>
. E. e& P  y- L8 E<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>+ y( Q8 Q# f& Y/ C9 E
<P ><FONT face="Times New Roman">              {</FONT></P>
1 [' n0 N* e- m6 x9 |; m<P ><FONT face="Times New Roman">          int middle = (left + right) / 2;</FONT></P>! F% _; }! P9 h4 v
<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P>' F/ }' P4 D. B) ]6 A
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>
7 u7 {4 X' N. _' W9 {0 ^<P ><FONT face="Times New Roman">}//while</FONT></P>" M4 @2 L, k' g& Q- ^- e8 p
<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>$ S9 b- w' k3 }/ Y: J. \. C; {
<P ><FONT face="Times New Roman">}//if</FONT></P>
( Y# I4 S6 u* j7 k* u1 F<P ><FONT face="Times New Roman">return –1;</FONT></P>1 T; r$ I6 b3 h* o; p/ \4 P; r+ X
<P ><FONT face="Times New Roman">}</FONT></P>6 W* `/ ^- h& D
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
2 d; @. r; o6 Z. [' m+ }- W<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
0 ^, `1 @3 j" f, n<P ><FONT face="Times New Roman">public static int binarySearch5(int[] a, int x, int n)</FONT></P># J0 _  b5 K# Z
<P ><FONT face="Times New Roman">{</FONT></P>
7 s6 u& u( h7 T8 N4 c' G+ Y% H<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>+ ]/ s, |/ r" v; P
<P ><FONT face="Times New Roman">              {</FONT></P>
3 K! B) g4 ^0 O<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>
# [, y) y0 ?/ W. W<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>, T6 b; p3 A& q$ F+ m3 [
<P ><FONT face="Times New Roman">              {</FONT></P>, f) [5 g- I- S  K0 f2 I* h$ {+ X; P
<P ><FONT face="Times New Roman">          int middle = (left + right + 1) / 2;</FONT></P>
' W& e4 E% K7 X: r- x<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P>) m- e5 A, v( Q2 r) \
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>! ~3 B) Q, N6 p. |+ {7 b, B) }
<P ><FONT face="Times New Roman">}//while</FONT></P>
. I7 G$ Z; P" u8 {, m% A3 _5 {$ D; ?<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>: f6 {4 C7 J1 O& Z- x7 y
<P ><FONT face="Times New Roman">}//if</FONT></P>: z# v# P$ |) h2 n4 S1 t
<P ><FONT face="Times New Roman">return –1;</FONT></P>+ K9 C/ d' f5 r2 E0 P
<P ><FONT face="Times New Roman">}</FONT></P>9 G: p0 u9 v+ D' H& T. I
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>1 o  W7 Q7 J0 R% d; V
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
9 x! U- y" h8 c" K, p<P ><FONT face="Times New Roman">public static int binarySearch6(int[] a, int x, int n)</FONT></P>
( l. M! C  K% `( A9 Z9 j1 G# t<P ><FONT face="Times New Roman">{</FONT></P>5 p! V4 c. p3 ^% X) C
<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>5 E9 _4 l8 M5 |
<P ><FONT face="Times New Roman">              {</FONT></P>2 g( A/ j9 V; l
<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>$ d8 L. i' n9 D8 j; j$ m
<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>
( g6 B, G# [  v: F) A4 x<P ><FONT face="Times New Roman">              {</FONT></P>
" @5 O- ]2 i. B$ z, q8 \) Y; ^<P ><FONT face="Times New Roman">          int middle = (left + right + 1) / 2;</FONT></P>
6 j; H+ q8 U. S, `1 e0 Q* S0 [9 q& U* a<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle - 1;</FONT></P>' D1 |$ k8 q. [  O+ }6 u
<P ><FONT face="Times New Roman">else left = middle + 1;</FONT></P>
/ q$ G7 `9 a- O<P ><FONT face="Times New Roman">}//while</FONT></P>
% z% N+ M1 N! O" e1 y7 @<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>' D$ z! D) O$ _( D, {
<P ><FONT face="Times New Roman">}//if</FONT></P>' F9 V$ q2 u) y! ?* L
<P ><FONT face="Times New Roman">return –1;</FONT></P>
' j% Z8 M: h) c+ U<P ><FONT face="Times New Roman">}</FONT></P>8 w, a- w3 d: k1 c* n% I
<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
8 `- b0 Z# b( Y<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
0 X8 L( n- R" r4 F<P ><FONT face="Times New Roman">public static int binarySearch7(int[] a, int x, int n)</FONT></P>
0 O' \) l, u7 B) h/ V+ n: X<P ><FONT face="Times New Roman">{</FONT></P>" D! ~* ]* `4 e- D
<P ><FONT face="Times New Roman">              if(n &gt; 0 &amp;&amp; x &gt;= a[0])</FONT></P>) t( N8 e  ~$ Q
<P ><FONT face="Times New Roman">              {</FONT></P>
  h1 m- M! l# p8 D3 G! U<P ><FONT face="Times New Roman">                     int left = 0, right = n-1;</FONT></P>
! y8 i" {6 E. l1 g5 ]4 y; z<P ><FONT face="Times New Roman">              while(left &lt; right)</FONT></P>
/ L/ A; J7 u, b& |6 t) V<P ><FONT face="Times New Roman">              {</FONT></P>! a2 Y6 g) x# h' x
<P ><FONT face="Times New Roman">          int middle = (left + right +1) / 2;</FONT></P>! v6 ^) b0 R/ I7 l( X# f
<P ><FONT face="Times New Roman">if(x &lt; a[middle]) right = middle;</FONT></P>: K2 O" z& ]& L
<P ><FONT face="Times New Roman">else left = middle;</FONT></P>2 ~* `& Z8 X3 T) B1 a
<P ><FONT face="Times New Roman">}//while</FONT></P>
$ Q, b& Q2 s* l0 S* }* U- e<P ><FONT face="Times New Roman">if(x == a
) return left;</FONT></P>, L4 n, [* b% {. y: L
<P ><FONT face="Times New Roman">}//if</FONT></P>
! I1 U+ G8 C# M2 Y' E<P ><FONT face="Times New Roman">return –1;</FONT></P>
7 |4 r8 Y+ b9 \/ j, r. `<P ><FONT face="Times New Roman">}</FONT></P>
+ z: n! c2 ?2 n<P ><FONT face="Times New Roman"> <o:p></o:p></FONT></P>
4 E# Z- E5 \' i<P >解:(<FONT face="Times New Roman">1</FONT>)算法<FONT face="Times New Roman">1</FONT>不正确。<o:p></o:p></P>$ u/ O) ~3 _0 Q4 o
<P >当在数组<FONT face="Times New Roman">a</FONT>中找不到与<FONT face="Times New Roman">x</FONT>相等的元素时,算法将进入死循环状态。<o:p></o:p></P>
# E# y$ g* t' {) `: _5 q2 W. J0 H. i<P >原因:每次循环时,变量<FONT face="Times New Roman">left</FONT>和<FONT face="Times New Roman">right</FONT>的值修改不正确。应修改如下:<o:p></o:p></P>
; H8 R2 G; @$ j* @<P ><FONT face="Times New Roman">if(x &gt; a[middle]) left = middle + 1;<o:p></o:p></FONT></P>( \. M* f* o) L# i9 t' F7 x
<P ><FONT face="Times New Roman">       else right = middle - 1;<o:p></o:p></FONT></P>
# r/ v( r5 U5 B0 B6 J0 w$ ^<P >(<FONT face="Times New Roman">2</FONT>)算法<FONT face="Times New Roman">2</FONT>不正确。<o:p></o:p></P>
! f1 f  i1 t& y$ a<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>5 K4 k& I& g9 G4 \% w& F
<P >另外,当<FONT face="Times New Roman">n=0</FONT>时执行<FONT face="Times New Roman">if(x == a
)...</FONT>时将出现下标越界错误。<o:p></o:p></P>
( V! n5 k/ @# F# U* P$ \! i<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>
$ F! B" A! ^, X: b+ [  d' \<P >(<FONT face="Times New Roman">3</FONT>)算法<FONT face="Times New Roman">3</FONT>不正确。<o:p></o:p></P>
% h6 m7 q, M! C* w" ]9 H/ S0 M<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>
2 V3 H* ^' u$ C9 s3 Q<P >原因:与算法<FONT face="Times New Roman">2</FONT>相同。<o:p></o:p></P>
# l) }# }9 z( ]1 i$ L2 O. W& F<P >(<FONT face="Times New Roman">4</FONT>)算法<FONT face="Times New Roman">4</FONT>不正确。<o:p></o:p></P>9 l  d5 Q1 h) w, 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>
7 _4 I+ d6 R" x' o" }. b5 l4 z<P >原因:循环条件和对变量<FONT face="Times New Roman">left</FONT>值的修改有错误。<o:p></o:p></P>
5 U- p. R* O' P# V- P9 k- I<P >(<FONT face="Times New Roman">5</FONT>)此算法正确。<o:p></o:p></P>% [8 z+ ], g: d. P4 }% X' h
<P >证明:当<FONT face="Times New Roman">n=0</FONT>或<FONT face="Times New Roman">n=1</FONT>时,算法显然正确。<o:p></o:p></P>: S/ G3 T$ `- I/ \" s
<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>
1 S2 g7 b. T6 {3 i3 z<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 q& Y, {) q  v6 R- s5 Z. p
<P >即:middle &gt; left成立。<o:p></o:p></P>
# C. H& A3 S% w1 {' r<P >且<FONT face="Times New Roman">middle = (left + right + 1) / 2 = [(left + 1) + right] / 2 </FONT>≤ 2right / 2 = right,<o:p></o:p></P>; B9 |& u) c- _, W0 y  I
<P >∴left &lt; middle ≤ right恒成立。<o:p></o:p></P>
6 I2 {. S6 E. z2 n# }2 A, D0 d" o<P >因此,每次循环之后,right与left之差必然减小,在有限次循环后,必有left = right条件成立,从而循环结束。<o:p></o:p></P>- R& f5 B& M: H; Q3 A1 b# }) i
<P >如果x值与数组a的某个元素值相等,则在循环结束时显然有x = a
且x = a
成立,否则x ≠a
,即未找到x,<o:p></o:p></P>
8 @- v  V+ y7 J0 z2 U<P >∴返回结果正确。<o:p></o:p></P>
2 l/ Z, k# _. }% k4 Q# Q<P >(6)算法6是错误的。<o:p></o:p></P># R0 x2 n. W9 \/ ]  s' o
<P >当执行到某次循环x = a[middle]成立时,再执行if 语句中的<o:p></o:p></P>$ `" B8 k; c! N, |' s$ q# Q2 i
<P >left = middle + 1;<o:p></o:p></P>9 q: z, H1 z  x  g8 c' p8 F) w
<P >就把结果丢失了,导致错误。而且还可能会导致下标越界错误。例如:<o:p></o:p></P>& N% W0 E9 F" W- q) ?8 [  W5 X: [6 b
<P >当n = 2且x = a[1]时即会出现这些情况。<o:p></o:p></P>
0 F5 i% R; G# a( b% d( P5 X: F<P >原因:if 语句中的left = middle + 1;应改为left = middle;<o:p></o:p></P>
% k* A4 p5 \* |- R<P >(7)算法7是错误的。<o:p></o:p></P>
" m( ]. @; [, J( v5 j, {  @+ Z<P >在循环过程中,一旦出现<o:p></o:p></P>
3 U. X# h' |- `6 Y<P >a
≤ x &lt; a[left + 1],则必进入死循环。<o:p></o:p></P>1 f9 n& A3 u& K/ ^% E" U: O- U' c
<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 19:27 , Processed in 0.450623 second(s), 52 queries .

回顶部