close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Subroutines
Harder Problems
Examples so far: sum, sum between, minimum
– straightforward computation
– small number of intermediate variables
– single control structure
 How do we design algorithms for more
complicated problems?
– complex computation
– many intermediate variables
– multiple control structures

Solving Complex Problems
Often it is difficult visualize all the details of a
complete solution to a problem
 Top-down design
– original problem is divided into simpler
independent subproblems
– successive refinement: these subproblems
may require further division into smaller
subproblems
– continue until all subproblems can be
easily solved

Subroutines
Set of instructions to perform a particular
computation
– subproblems of more complex problems
– repeated computation (e.g. different inputs)
– may be used in solving other problems
 Also called subprograms, methods, functions,
and procedures
 Subroutines are named
– referred to by name inside another program

Declaring subroutines

Adding two integers
return value
type (output)
subroutine
name
parameters
(input)
int sum_two_numbers(int x, int y)
{
return x+y;
}
return
statement
output
value
Subroutine: Minimum of two integers
int minimum(int x, int y)
{
if(x < y)
return x;
else
return y;
}
Minimum of three numbers

Problem: Design an algorithm to compute the
minimum of three integers x, y, and z
Top-down design
Compute minimum of x,y,z
Get input
values x,y,z
Perform
computations
Compute min_tmp =
minimum of x and y
Return output
value
Compute minimum
of min_tmp and z
Calling subroutines

Use subroutines for repeated tasks
– We can call the minimum subroutine
twice to compute the minimum of three
integers:
int min3(int x, int y, int z)
{
min_temp = minimum(x,y);
return minimum(min_temp,z);
}
Example: Computing combinations

A combination C(n,k) is the number of ways to
select a group of k objects from a population of
n distinct objects
n!
C(n,k) =
k! (n-k)!

n! is the factorial function
n! = n(n –1)(n -2) … 321

Problem: Compute C(n,k)
Top-down design
n!
Compute C(n,k) =
k! (n-k)!
Get input
values n,k
Compute n!
Perform
computations
Compute k!
Return output
value C(n,k)
Compute (n-k)!
Analysis

Computing C(n,k) can be divided into three
factorial computations
– Compute n!
– Compute k!
– Compute (n-k)!

Use subroutines for repeated tasks
– we can write a factorial subroutine rather
than computing C(n,k) directly
Algorithm to compute C(n,k)
Inputs: n, k
 Output: combination

1. Get input values for n and k
2. Perform computation:
factorial(n)
combination =
factorial(k)  factorial(n-k)
3. Return combination
Algorithm to compute C(n,k)
int combination(int n, int k)
{
return factorial(n)/
(factorial(k)*factorial(n-k));
}
Exercises
You can use any of the subroutines we
discussed in class without declaring them

Design an algorithm to compute n!

Suppose we have a subroutine sum_n that
computes the sum of the first n integers
int sum_n(int n)
Use the subroutine sum_n to compute the
inclusive sum between two integers
Exercises

Design an algorithm to compute the minimum
of four numbers

Design an algorithm to compute the inclusive
product between two numbers
– for example, the product between 3 and 6
is
3456 = 360
1/--страниц
Пожаловаться на содержимое документа