page473.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 64 行
HTML
64 行
<HTML><HEAD><TITLE>Example-Computing #tex2html_wrap_inline68687#</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6613" HREF="page474.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6611" HREF="page472.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6607" HREF="page472.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6615" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0014531000000000000000">Example-Computing <IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68687" SRC="img1938.gif" ></A></H3><P>This section presents a simple, Monte Carlo algorithmto compute the value of <IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68687" SRC="img1938.gif" > from a sequence of random numbers.Consider a square positioned in the <I>x</I>-<I>y</I> planewith its bottom left corner at the origin as shown in Figure <A HREF="page473.html#figmontecarlo"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The area of the square is <IMG WIDTH=14 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline68695" SRC="img1939.gif" >,where <I>r</I> is the length of its sides.A quarter circle is inscribed within the square.Its radius is <I>r</I> and its center is at the origin of <I>x</I>-<I>y</I> plane.The area of the quarter circle is <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline68705" SRC="img1940.gif" >.<P><P><A NAME="34123"> </A><A NAME="figmontecarlo"> </A> <IMG WIDTH=575 HEIGHT=193 ALIGN=BOTTOM ALT="figure33957" SRC="img1941.gif" ><BR><STRONG>Figure:</STRONG> Illustration of a Monte Carlo method for computing <IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68687" SRC="img1938.gif" >.<BR><P><P>Suppose we select a large number of points at random inside the square.Some fraction of these points will also lie inside the quarter circle.If the selected points are uniformly distributed,we expect the fraction of points in the quarter circle to be<P> <IMG WIDTH=305 HEIGHT=36 ALIGN=BOTTOM ALT="displaymath68685" SRC="img1942.gif" ><P>Therefore by measuring <I>f</I>, we can compute <IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68687" SRC="img1938.gif" >.Program <A HREF="page473.html#progexampleu"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows how this can be done.<P><P><A NAME="34134"> </A><A NAME="progexampleu"> </A> <IMG WIDTH=575 HEIGHT=162 ALIGN=BOTTOM ALT="program34131" SRC="img1943.gif" ><BR><STRONG>Program:</STRONG> Monte Carlo program to compute <IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68687" SRC="img1938.gif" >.<BR><P><P>The <tt>pi</tt> method uses the <tt>RandomNumberGenerator</tt> definedin Program <A HREF="page467.html#prograndomNumberGeneratora"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>to generate (<I>x</I>,<I>y</I>) pairs uniformly distributed on the unit square (<I>r</I>=1).Each point is tested to see if it falls inside the quarter circle.A given point is inside the circle when its distance from the origin, <IMG WIDTH=67 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline68729" SRC="img1944.gif" > is less than <I>r</I>.In this case since <I>r</I>=1,we simply test whether <IMG WIDTH=80 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline68735" SRC="img1945.gif" >.<P>How well does Program <A HREF="page473.html#progexampleu"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> work?When 1000 trials are conducted,792 points are found to lie inside the circle.This gives the value of 3.168 for <IMG WIDTH=9 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68687" SRC="img1938.gif" >,which is only 0.8% too large.When <IMG WIDTH=21 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline68739" SRC="img1946.gif" > trials are conducted,78535956 points are found to lie inside the circle.In this case, we get <IMG WIDTH=114 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline68741" SRC="img1947.gif" >which is within 0.005% of the correct value!<P><HR><A NAME="tex2html6613" HREF="page474.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6611" HREF="page472.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6607" HREF="page472.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6615" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?