CompSci 100e 2.1 1 N-Body Simulation !! Applications to astrophysics. !! Orbits of solar system bodies. !! Stellar dynamics at the galactic center. !! Stellar dynamics in a globular cluster. !! Stellar dynamics during the collision of two galaxies. !! Formation of structure in the universe. !! Dynamics of galaxies during cluster formation. © Sedgewick & Wayne CompSci 100e 2.2 2 N-Body Simulation !! 1. Setup initial distribution of particles. !! Need accurate data and model of mass distribution. !! 2. Compute forces between particles. !! Direct sum: N2. !! Appel / Barnes-Hut" N log N. !! 3. Evolve particles using ODE solver. !! Leapfrog method balances efficiency and accuracy. !! 4. Display and analyze results. ! = softening parameter eliminates binary stars with r < ! hard binaries can be important source of energy © Sedgewick & Wayne CompSci 100e 2.3 3 If Statement Examples © Sedgewick & Wayne CompSci 100e 2.4 While Loop !! The while loop. A common repetition structure. !! Check a boolean expression. !! Execute a sequence of statements. !! Repeat. while (boolean expression) { statement 1; statement 2; } statement 1 true false boolean expression statement 2 loop body loop continuation condition © Sedgewick & WayneCompSci 100e 2.5 5 For Loops !! The for loop. Another common repetition structure. !! Execute initialization statement. !! Check boolean expression. !! Execute sequence of statements. !! Execute increment statement. !! Repeat. for (init; boolean expression; increment) { statement 1; statement 2; } statement 1 true false boolean expression statement 2 init increment body loop continuation condition © Sedgewick & Wayne CompSci 100e 2.6 6 Loop Examples © Sedgewick & Wayne CompSci 100e 2.7 Problem 1 !! Given n, calculate 2n !! What if you wanted to print all from 20 to 2n? !! What if you wanted to return the value? CompSci 100e 2.8 8 While Loops: Powers of Two !! Ex. Print first n powers of 2. !! Increment i from 1 to n. !! Double v each time. int i = 0; int v = 1; while (i <= N) { System.out.println(v); i = i + 1; v = 2 * v; } Console: 1 2 4 8 16 32 64 0 1 i v 1 2 2 4 3 8 true i <= N true true true 4 16 5 32 6 64 7 128 true true true false n = 6 © Sedgewick & WayneCompSci 100e 2.9 Problem 2 !! Square Root: !! Given a real number c and some error tolerance epsilon !! Estimate t, the square root of c CompSci 100e 2.10 10 While Loops: Square Root !! Q. How might we implement Math.sqrt() ? !! A. To compute the square root of c: !! Initialize t0 = c. !! Repeat until ti = c / ti, up to desired precision: set ti+1 to be the average of ti and c / ti. ! t0= 2.0t1=12( t0+2t0) = 1.5t2=12( t1+2t1) = 1.416666666666665t3=12( t2+2t2) = 1.4142156862745097t4=12( t3+2t3) = 1.4142135623746899t5=12( t4+2t4) = 1.414213562373095computing the square root of 2 © Sedgewick & Wayne CompSci 100e 2.11 Problem 3 !! Gambler's ruin. Gambler starts with $stake and places $1 fair bets until going broke or reaching $goal. !! What are the chances of winning? !! How many bets will it take? CompSci 100e 2.12 12 Gambler's Ruin !! One approach. Monte Carlo simulation. !! Flip digital coins and see what happens. •! Pseudorandom number generation •! java.util.Random !! Repeat and compute statistics. © Sedgewick &
View Full Document
Unlocking...