Arrays, Functions, and Memory
In this new module, we examine a new important data type that
operates much like the vector of Scheme. In C, these
linear data structures are called arrays. We also give more
concrete examples on how to decompose your programs into
functions. With both of these come the need to understand
more closely how data is represented in computer memory.
In class we will examine several of the following programs.
follower
/* Program to find a object, and follow it if it moves
* (e.g. paper used as "wall")
*
* This uses the Scribbler 2 IR sensors.
*
* Authors: April O'Neill & Erik Opavsky
* Date: 7/8/11
*/
#include <MyroC.h>
#include <stdio.h>
int
main()
{
rConnect("/dev/rfcomm0");
rSetForwardnessTxt ("scribbler-forward");
int IRs[2];
while (1)
{
rGetIRAll (IRs);
if (!IRs[0] && !IRs[1] ) // if both sensors don't sense obstacles
rForward (1,1); // move forward for 1 second
else if (IRs[0] && !IRs[1] ) // if right senses obstacle and left doesn't
rTurnRight (1, .2); // turn right for 1 second
else if (!IRs[0] && IRs[1] ) // if left senses obstacle and right doesn't
rTurnLeft (1, .2); // turn left for one second
else if (IRs[0] && IRs[1] ) // if both sense obstacle
sleep (1); // wait for one second
} // while
rDisconnect();
return 0;
} // main
wall
/* * * * *
* wall.c
*
* Scribbler moves until it sees a wall, then turns right, and stops at
* the next obstacle seen.
*
* The program uses 800 as a threshold for obstacle being seen using
* getObstacle.
*
* Authors: April O'Neill, Dilan Ustek
*
* Date: 7 July 2011
*/
#include <MyroC.h>
/* if batteries are fresh, then the obstacle sensors typically identify
an object at a level of about 800. If batteries weaken, use a lower
value
*/
const int obstacleLimit = 800;
int
main()
{
rConnect("/dev/rfcomm0");
int i = 0;
// loop to stop at the second obstacle seen
while(i<2)
{
rForward(1.0,1.0);
if (rGetObstacleTxt("center", 3)>obstacleLimit)//fixme
{
rTurnRight(1.0,1.0);
i++;
}
}
rDisconnect();
return 0;
} // main
max-min
/* A program to store several numbers and
compute their maximum, minimum, and average.
This code illustrates built-in C-style arrays.
*/
#include <stdio.h>
#define LENGTH 10 /* number of elements to be processed in array */
int main (void)
{
int j;
double max, min, sum;
double numbers[LENGTH] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
printf("Program to process real numbers.\n");
sum = max = min = numbers[0]; /* right to left assignment operator */
for (j = 1; j < LENGTH; j++)
{
if (numbers[j] > max)
max = numbers[j];
if (numbers[j] < min)
min = numbers[j];
sum += numbers[j];
}
printf("Maximum: %5.2f\n", max);
printf("Minimum: %5.2f\n", min);
printf("Average: %5.2f\n\n", sum/LENGTH);
printf("printing specific array elements\n");
for (j = -2; j < LENGTH+2; j++)
printf ("numbers[%d] = %5.1lf\n", j, numbers[j]);
return 0;
}
trap-1
/* A program for approximating the area under a function y = f(x) *
* between a and b using the Trapezoidal Rule. *
* The Trapezoidal Rule divides [a, b] into n evenly spaced intervals *
* of width W = (b-a)/n. The approximate area is *
* W*(f(a)/2+f(a+W)+f(a+2W)+ ... +f(a+(n-2)W)+f(a+(n-1)W)+f(b)/2) *
* Version 1: Approximating area under sqrt(4-x^2) on [0, 2]. *
* As this is 1/4 of circle of radius 2, result should be Pi. */
#include <stdio.h>
#include <math.h>
const float a = 0.0; /* limits for the area under y = f(x) */
const float b = 2.0; /* area will be computed under f(x) on [a,b] */
const int n = 100; /* number of subintervals to be used */
/* function to be used in the area approximation
* Preconditions: x*x does not underflow or overflow
* Postconditions: f(x) = sqrt(4-x^2)
*/
double f(double x)
{
return sqrt(4.0 - x*x);
}
/* main: runs trapezoid approximation for semicircle of radius 2 centered at
* origin over [0,2]
*
* Preconditions: f(x) is defined
* Postconditions:
* Prints the area to terminal
* returns 0
*/
int main (void)
{
double width, sum, xvalue, area;
printf ("Program approximates the area under a function using the ");
printf ("Trapezoidal Rule, based on %d intervals.\n", n);
width = (b - a) / n;
/* compute the sum in the area approximation */
sum = (f(a) + f(b)) / 2.0; /* first and last terms in sum */
for (xvalue = a + width; xvalue < b; xvalue += width)
sum += f(xvalue);
area = sum * width;
printf ("The approximate area is %7.4f\n", area);
return 0;
}
trap-2
/* Approximating area under sqrt(4-x^2) on [0, 2] using the Trapezoidal Rule.*
* Version 2: A function performs the area computation. */
#include <stdio.h>
#include <math.h>
const int n = 50; /* number of subintervals to be used */
/* function to be used in the area approximation
* Preconditions: x*x does not underflow or overflow
* Postconditions: f(x) = sqrt(4-x^2)
*/
double f(double x);
/* Approximation of area under f(x) on [a, b] using the Trapezoidal Rule
*
* Preconditions:
* b > a
* numInt > 0
*
* Postconditions:
* Returns area under f(x) over range [a,b] by the trapezoid rule
*/
double area(double a, double b, int numInt);
/* main: runs trapezoid approximation for semicircle of radius 2 centered at
* origin over [0,2]
*
* Preconditions:
* f(x) is defined
* area(a,b,n) is defined
*
* Postconditions:
* Prints the area to terminal
* returns 0
*/
int main (void)
{
printf ("Program approximates the area under a function using the ");
printf ("Trapezoidal Rule, based on %d intervals.\n", n);
printf ("The approximate area is %7.4f\n", area (0.0, 2.0, n));
return 0;
}
/* function to be used in the area approximation
* Preconditions: x*x does not underflow or overflow
* Postconditions: f(x) = sqrt(4-x^2)
*/
double f(double x)
{
return sqrt(4.0 - x*x);
}
/* Approximation of area under f(x) on [a, b] using the Trapezoidal Rule
*
* Preconditions:
* b > a
* numInt > 0
*
* Postconditions:
* Returns area under f(x) over range [a,b] by the trapezoid rule
*/
double area (double a, double b, int numInt)
{
double width = (b - a) / numInt;
double sum = (f(a) + f(b)) / 2.0; /* first and last terms in sum */
double xvalue;
for (xvalue = a + width; xvalue < b; xvalue += width)
sum += f(xvalue);
return sum * width;
}
trap-3
/* Approximating the area under sqrt(4-x^2) on [0, 2] *
* using the Trapezoidal Rule. *
* Version 3: A procedure performs the area computation. */
#include <stdio.h>
#include <math.h>
const int n = 50; /* number of subintervals to be used */
/* function to be used in the area approximation
* Preconditions: x*x does not underflow or overflow
* Postconditions: f(x) = sqrt(4-x^2)
*/
double f(double x);
/* Approximation of area under f(x) on [a, b] using the Trapezoidal Rule
*
* Preconditions:
* b > a
* numInt > 0
*
* Postconditions:
* *area modified to contain the calculated area
*/
void compute_area(double a, double b, int numInt, double *area);
/* main: runs trapezoid approximation for semicircle of radius 2 centered at
* origin over [0,2]
*
* Preconditions:
* f(x) is defined
* compute_area is defined
*
* Postconditions:
* Prints the area to terminal
* returns 0
*/
int main (void)
{ double new_area;
printf ("Program approximates the area under a function using the ");
printf ("Trapezoidal Rule, based on %d intervals.\n", n);
compute_area(0.0, 2.0, n, &new_area);
printf ("The approximate area is %7.4f\n", new_area);
return 0;
}
/* function to be used in the area approximation
* Preconditions: x*x does not underflow or overflow
* Postconditions: f(x) = sqrt(4-x^2)
*/
double f(double x)
{
return sqrt(4.0 - x*x);
}
/* Approximation of area under f(x) on [a, b] using the Trapezoidal Rule
*
* Preconditions:
* b > a
* numInt > 0
*
* Postconditions:
* *area modified to contain the calculated area
*/
void compute_area (double a, double b, int numInt, double *area)
{
double width = (b - a) / (double) numInt;
double sum = (f(a) + f(b)) / 2.0; /* first and last terms in sum */
double xvalue;
for (xvalue = a + width; xvalue < b; xvalue += width)
sum += f(xvalue);
*area = sum * width;
}
trap-4
/* Approximating area under y = f(x) on [a, b] using the Trapezoidal Rule. *
* Version 4: Approximating area under sqrt(4-x^2) on [0, 2]. *
* Here sqrt is computed via Newton's Method, rather than through math.h. */
#include <stdio.h>
const double a = 0.0; /* alternative constant definitions */
const double b = 2.0; /* [a, b] gives interval for area */
const double root_accuracy = 0.00005; /* sqrt computes to this accuracy */
const int n = 50; /* number of subintervals to be used */
/* Compute square root using Newton's Method
*
* Preconditions:
* r >= 0
*
* Postconditions:
* sqrt(r)*sqrt(r) = r
*/
double sqrt(double r)
{
double change = 1.0;
double x; /* current approximation for sqrt(r) */
if (r == 0.0)
return 0.0; /* the square root of 0.0 is a special case */
x = r; /* r is used as a first approximation to sqrt(r) */
while ( (change > root_accuracy) || (change < - root_accuracy) )
{
change = (x*x - r) / (2*x);
x -= change;
}
return x;
}
/* function to be used in the area approximation
* Preconditions: x*x does not underflow or overflow
* Postconditions: f(x) = sqrt(4-x^2)
*/
double f(double x)
{
return sqrt(4.0 - x*x);
}
/* main: runs trapezoid approximation for semicircle of radius 2 centered at
* origin over [0,2]
*
* Preconditions:
* f(x) is defined
*
* Postconditions:
* Prints the area to terminal
* returns 0
*/
int main (void)
{
double width, sum, xvalue, area;
printf ("Program approximates the area under a function using the ");
printf ("Trapezoidal Rule, based on %d intervals.\n", n);
width = (b - a) / n;
/* compute the sum in the area approximation */
sum = (f(a) + f(b)) / 2.0; /* first and last terms in sum */
for (xvalue = a + width; xvalue < b; xvalue += width)
sum += f(xvalue);
area = sum * width;
printf ("The approximate area is %7.4f\n", area);
return 0;
}
trap-5
/* Approximating the area under several functions *
* using the Trapezoidal Rule. *
* Version 5: An area function has numeric and functional parameters. */
#include <stdio.h>
#include <math.h>
const int n = 50; /* number of subintervals to be used */
/* function for a circle of radius 2, centered at the origin */
double circle(double x);
/* function for the standard parabola y = x^2 */
double parabola(double x);
/* Approximation of area under f(x) on [a, b] using the Trapezoidal Rule */
double area(double a, double b, int numInt, double f (double));
/* main: runs trapezoid approximation for circle and parabola
*
* Preconditions:
* f(x) is defined
* area is defined
*
* Postconditions:
* Prints the area to terminal
* returns 0
*/
int main (void)
{ int number;
printf ("Program approximates the area under a function using the ");
printf ("Trapezoidal Rule, based on %d intervals.\n", n);
printf ("\n");;
printf ("Approximation of 1/4 area of circle of radius 2 is %7.5f .\n\n",
area (0.0, 2.0, n, circle));
printf ("Approximation of area under y = x^2 between 1 and 3 is%8.5f .\n\n",
area (1.0, 3.0, n, parabola));
return 0;
}
/* function for a circle of radius 2, centered at the origin */
double circle(double x)
{
return sqrt(4.0 - x*x);
}
/* function for the standard parabola y = x^2 */
double parabola(double x)
{
return x*x;
}
/* Finding area via the Trapezoidal Rule */
double area (double a, double b, int numInt, double f (double))
{
double width = (b - a) / numInt;
double sum = (f(a) + f(b)) / 2.0; /* first and last terms in sum */
double xvalue;
for (xvalue = a + width; xvalue < b; xvalue += width)
sum += f(xvalue);
return sum * width;
}
darts
/* This program approximates Pi by picking a points in a sqaure and *
* and determining how often they are also in an appropriate circle. */
#include <stdio.h>
/* libraries for the random number generator */
#include <stdlib.h>
#include <time.h>
/* Within the stdlib.h library,
* time returns a value based upon the time of day
* on some machines, rand returns a random integer between 0 and 2^31 - 1
* although on some machines rand gives values between 0 and 2^32 - 1
* and on other machines rand gives values between 0 and 2^15 - 1
* MaxRandInt is this maximum integer minus 1
* (Note: 2^32 = 2147483648, 2^31 = 1073741824 and 2^15 = 32768)
* Use 2^32-1 for SparkStations
* Use RAND_MAX for Linux machines,
* Use 2^15-1 for IBM Xstation 140s and HP 712/60s
*/
const int MaxRandInt = RAND_MAX; /* declaration of program constants*/
const int NumberOfTrials = 5000;
int main (void)
{ int i;
int counter = 0; /* declare and initialize counter */
double x, y;
double MaxRandReal = (double) MaxRandInt; /* make MaxRandInt a real */
printf ("This program approximates Pi by picking %d points in a square\n",
NumberOfTrials);
printf ("and counting the number in an appropriate circle.\n\n");
// initialize random number generator
// change the seed to the random number generator, based on the time of day
srand (time ((time_t *) 0) );
// pick points in first quadrant with coordinates between 0 and 1
// determine how many are in the circle of radius 1
for (i = 1; i <= NumberOfTrials; i++) {
x = rand() / MaxRandReal;
y = rand() / MaxRandReal;
if (x*x + y*y <= 1) counter++;
}
printf ("%d points were inside the circle, and\n", counter);
printf ("the approximate value of Pi is %.5f .\n",
4.0 * counter / NumberOfTrials);
return 0;
}
