Transcript Document

Week 10 - Programming III
• So far:
– Branches/condition testing
– Loops
• Today:
– Problem solving methodology
– Examples
• Textbook chapter 7
Problem Solving Methodology
1. Define the problem and your goals
2. Identify information (inputs) and desired
results (outputs)
3. Select mathematical approach
(assumptions, scientific principles,
solution method)
4. Write a program (use array operations)
5. Test your program (with a simple case)
Example 1: line fitting
Given N pairs of values (xi,yi), find the best
straight line fit
y=mx+b
m ≡ slope of line, b ≡ y intercept
Problem solving methodology:
1. State the problem: find best line to fit data
2. Identify inputs and outputs:
(xi,yi)  (m,b)
3. Describe algorithm: least squares
4. Write program
5. Test program
• method of least squares:
 N
 1  N  N

  x j y j     x j   y j 

 N


j 1

 j 1  j 1 
m
2
N
N


1
2
 xj    xj 

 N

j

1
j

1




1 N
b    y j
N  j 1
 m N 
   xj 
 N

j

1



Method of least squares
•
Fit line, y = mx + b, to points
•
Find m and b to Minimize the error,
•
Solve for m and b
• Program flow:
1. Read in data:
• How many data points
• Get paired data
2. Compute best fit for m and b
3. Provide output to user:
• Numerical values of both m and b
• Graphical presentation
% Comments on the program
…
% Get number of pairs, n_points
n_points = input('How many (x,y) pairs? ');
% Read in the input data x, y
for ii = 1:n_points
temp = input('Enter [x y]: ');
x(ii) = temp(1);
y(ii) = temp(2);
end
typical use of a loop,
but could have user
just enter vectors!
 N
 1  N  N

  x j y j     x j   y j 

 N


j 1
j 1
j 1






m
2
N
N

 1

 xj2    xj 

 N

j

1
j

1




1 N
b    y j
N  j 1
 m N 
   xj 
 N

j

1



% Calculate m and b
m = ( sum(x.*y) – sum(x)*sum(y)/n_points )/( …
sum(x.^2) – sum(x)^2/n_points );
b = ( sum(y) – m*sum(x) )/n_points;
% Plot the data
plot(x,y,'bo')
hold on
twopts = [ min(x), max(x) ];
plot( twopts, m*twopts+b ,'r-','Linewidth',2)
hold off
% Add labels, etc.
gtext([' y = ',num2str(m), ' x + ',num2str(b)])
xlabel('x data'), ylabel('y data'), title('line fit')
Typical result:
Simple check to
see if it works
Example 2: sorting
Given N numbers (x1,…xN), sort them into
increasing order
3 1 4 5 2 7 1
0 1 2 3 4 5 7
Algorithm:
• Given N numbers, x1…xN:
– Search through x1…xN for the smallest, swap
with x1
– Search through x2…xN for the smallest, swap
with x2
– Continue a total of N-1 times
start
3
1
4
5
2
7
0
0
1
4
5
2
7
3
0
1
4
5
2
7
3
0
1
2
5
4
7
3
0
1
2
3
4
7
5
0
1
2
3
4
7
5
0
1
2
3
4
5
7
done
Program employs nested loops:
function array = simpsort(array)
% function to sort from smallest to largest
for k = 1:length(array)-1
loc = k;
for k2 = k:length(array)
locate the index (loc)
if array(k2)<array(loc) of the smallest value
loc = k2;
end
end
if loc ~= k
swap values,
array([k,loc ]) = array([loc,k]); if necessary
end
end
Another sort
function y = upsort(x)
% UPSORT sorts a vector x of any length.
% UPSORTs output y is the vector x with elements arranged
% in ascending order
z = x;
% Put x in a temporary vector z.
for n=1:length(x)
[y(n),k]=min(z);
% y(n) is the smallest element of z.
z(k)=[];
% Erase the smallest element of z.
end
Example 3: equation solving
•
•
•
3 x + 7 y = 0 and 2 x – 5 y = 4
(simultaneous linear equations)
x2 + 4 x + 7 = 0
(rooting polynomials)
x – sin x – 0.0236 = 0
(transcendental equations ?? )
Newton-Raphson method:
• Assuming an equation of form f(x) = 0
• From the Taylor series expansion
f(x) = f(x1) + ( x – x1 ) f ’(x1) + …
keep only the first 2 terms
f(x)  f(x1) + ( x – x1 ) f ’(x1) = 0
and solve for x
x = x1 – f(x1) / f ’(x1)
• Thinking of x1 as a first guess, then
x = x1 – f (x1) / f ’(x1)
yields a better estimate of the root
• Repeating is the NR iteration:
xk+1 = xk – f (xk) / f ’(xk)
Back to the example f(x) = x – sin x – 0.0236
• NR iteration is xk+1 = xk – f(xk) / f ’(xk) or
xk  sin xk  0.0236
xk 1  xk 
1  cos xk
implement this
recursion; compare
different values for
first guess
compute until
x = -1
it converges
diff = 1;
while diff > 0.001
xnew = x - ( x - sin(x) - 0.0236 )/( 1 - cos(x) );
diff = abs(xnew-x);
x = xnew
end
abs to detect
size of difference
Comparison of starting points:
x – sin x – 0.0236 = 0
Start at x0= 0.1
value
Start at x0= – 1.0
iteration
Homework: tic-tac-toe analysis
•
Find the winner in a 3-by-3 tic-tac-toe
board. Assume representations:
–
–
–
Empty cell = 0
X = +1
O=–1
Problem solving methodology:
1. State the problem: look for occurrences of
+1 or – 1 in 3 adjacent cells
2. Identify inputs and outputs:
board array  winner or not
3. Describe algorithm:
4. Write program
5. Test program
1 1 1
0 1 1
1 1 0
win for X, column
of 1’s sums to 3
1 1 1
1 1 1
1 1 1
draw – no empty cells,
and no winner
Sum(board) and trace(board) are useful,
where board is the 3x3 array representing the game.