Background:
In PC1 you had a good deal of specific preparation for the problem you were asked to solve. The purpose of this final check is to verify that you can handle a wider variety of problems without requiring such specific preparation.
For the final programming check I will give you a problem similar to one of those described below, but requiring different data and probably a different combination of basic operations. But the basic operations required will be drawn from this list.
Be SURE you can write, compile and run ALL of the following kinds of programs. To do this you should not only do all of the examples shown, but you should also devise and solve another example of each kind (a good way to do this would be to trade problems with members of your team or other classmates.)
I've included solutions at the end of the notes.
If you have trouble with ANY of this material, it's critically important that you (1) ask about the material in class (2) work with your team mates on it (3) come and see Clayton (4) work with the TA.
Note that knowledge, speed and skill are interrelated. You need to be sure you can solve problems of this kind reliably and fast, not just be able to do them "eventually". So just "knowing the concepts" is not enough. As with any skill, which is what programming largely is, practice makes perfect, practice makes reliable, and practice makes fast.
Being able to solve these problems fast is not an artificial requirement arising from the time constraints of the Programming Check. Look ahead to next semester's course: your work there and in later courses will assume that you will need little time to deal with issues at this level, so you can concentrate on the new material without being distracted by wrestling with the basics.
Do not spend time committing this material to memory, since you will have access to these notes during the Programming Check. Concentrate on understanding the material and (most important) being able to write programs that work.
Passing this Programming Check is MORE IMPORTANT than contributing to your team project. Take the time you need to master this material as the semester nears its end!
You should be able to define a struct that contains an array of elements, which could themselves be structs, and a count, and perform the following operations on it. In the examples I use the following structs:
struct student_record
{
int student_no;
int grade;
};
struct grade_book
{
struct student_record records[MAX];
int count;
};
Be sure to check that the subscript is in range!
Remember that all of the "good" elements of a collection have to be packed into the slots 0...count-1, with no gaps. Also remember that you can't remove something from an empty collection, and that you can't remove something from a position (subscript) out of range.
Ex: increase all the grades in the gradebook by calling a function that adds 1 to a grade
Find the sum or product or ... of the elements or parts of elements in the collection... use the Running Total Plan (or a variant)
Ex: Find the overall average grade in a grade book...find the sum and divide by the count
Ex: (minimum student no, give position)
Ex: (maximum grade, give the student record)
Ex: Find value of a student record that has a given student number
Ex: read a student record
Ex: Read a student record; user types -1 instead of student number to quit
Ex: Print a student record.
The above operations can be combined to do all kinds of things, and you should be able to handle combinations like the following:
Ex: Read in a bunch of student records and then increase each grade.
Ex: sort the elements in a grade book by student number
Note: Next semester you'll learn better ways of sorting. The point here is that you can sort by combining basic operations that you know how to do.
Ex: prompt for a student record, and indicate whether of not it is already in a grade book
Ask the user to type in the value of
part of an element, and print the values of the other parts on any elements
that contain that part that is in a collection (if any)
Ex: ask for student number, print grades for that student
Ask the user to type in the value of
part of an element, and print the minimum or maximum value of some part of any
elements in the collection that contain the value typed in (or indicate if
there are none)
Ex: ask for student number, print highest grade (if any)
plan: prompt for student no, add all matching student records to collection temp, find max grade in temp, print it
For any of the above kinds of work, you have to be able to create a complete program that can be executed and tested.
Ex: read in a bunch of student records. Then ask for student number, print highest grade (if any).
Note: You do not have to solve these problems exactly as shown. I've constructed all the solutions to emphasize the building block character of these ideas: you can learn standard ways of doing the basic operations, so that you can write functions that do these things; then you can combine these basic functions to do more complex things, and so on.
In some cases there are simpler ways of doing some of the combinations that involve modifying the building blocks. If these are clear to you, great; if not, stick with the building block ideas.
Note: Part of my personal building block style is heavy use of return codes that functions use to tell me whether they worked or not. Doing this often comes in handy by allowing me to control functions using while(), and it's also useful in detecting errors.
You should be able to define a struct that contains an array of elements, which could themselves be structs, and a count, and perform the following operations on it. In these examples I use the following structs:
struct student_record
{
int student_no;
int grade;
};
struct grade_book
{
struct student_record
records[MAX];
int count;
};
Ex:
void make_empty(struct grade_book *pg)
{
pg->count=0;
}
Ex:
int get_value(int index, struct grade_book gb, struct student_record
*psr)
{
if
((index<0) || (index>gb.count))
return
0;
*psr=gb.records[index];
return
1;
}
int add(struct grade_book *pgb, struct student_record sr)
{
if (pgb->count >=MAX)
return 0;
pgb->records[pgb->count]=sr;
pgb->count++;
return 1;
}
int rem(int index, struct grade_book *pgb)
{
if (pgb->count<=0)
return 0;
if ((index<0)||(index>pgb->count-1))
return 0;
pgb->records[index]=pgb->records[pgb->count -1];
//that copies the last element into the space vacated by the element removed
pgb->count--;
return 1;
}
Ex: increase all the grades in the gradebook by calling a function that adds 1 to a grade
void bump(struct student_record *psr)
{
psr->grade=psr->grade+1;
}
void bump_grades(struct grade_book *pgb)
{
int i;
for(i=0;i<pgb->count;i++)
bump(&pgb->records[i]);
}
Find the sum or product or ... of the elements or parts of elements in the collection... use the Running Total Plan (or a variant)
Ex: Find the overall average grade in a grade book...find the sum and divide by the count
float average(struct grade_book gb)
{
int runningtotal;
int i;
if (gb.count==0)
{
printf("average of empty collection not defined\n");
exit(1);
}
runningtotal=0;
for(i=0;i<gb.count;i++)
runningtotal=runningtotal+gb.records[i].grade;
return ((float) runningtotal)/gb.count;
//the (float) forces a conversion of runningtotal to float. If you do not convert either runningtotal or
//gb.count to a float here, you will get integer division, which throws away fractions
}
Ex: (minimum student no, gives position)
int min(struct grade_book gb, int *pos)
{
int i;
int min_so_far;
int pos_min_so_far;
if (gb.count<=0)
return 0;
min_so_far=gb.records[0].student_no;
pos_min_so_far=0;
for(i=0;i<gb.count;i++)
if (gb.records[i].student_no<min_so_far)
{
min_so_far=gb.records[i].student_no;
pos_min_so_far=i;
}
*pos=pos_min_so_far;
return 1;
}
Ex: (maximum grade, gives the student record)
int max(struct grade_book gb, struct student_record *psr)
{
int i;
struct student_record max_so_far;
if (gb.count<=0)
return 0;
max_so_far=gb.records[0];
for(i=0;i<gb.count;i++)
if (gb.records[i].grade>max_so_far.grade)
max_so_far=gb.records[i];
*psr=max_so_far;
return 1;
}
Ex: Find value of a student record that has a given student number
int find(struct grade_book gb, int student_no, struct student_record *psr)
{
int i;
if (gb.count<=0)
return 0;
for(i=0;i<gb.count;i++)
if (gb.records[i].student_no==student_no)
{
*psr=gb.records[i];
return 1;
}
return 0;
}
Ex:
int read_student_record(FILE *fp, struct student_record *sr)
{
int items_read;
items_read=fscanf(fp,"%d%d",&sr->student_no,&sr->grade);
if (items_read!=2)
return 0;
return 1;
}
Ex: Read a student record
int read_student_record_from_kb(struct student_record *psr)
{
int user_input;
printf("Type student number or -1 to quit: ");
scanf("%d", &user_input);
if (user_input==-1)
return 0;
psr->student_no=user_input;
printf("Type a grade: ");
scanf("%d", &psr->grade);
return 1;
}
Note: this function is not very robust... what if the user types in garbage, such as a letter? Can you do better?
Ex: Print a student record.
void print_sr(struct student_record sr)
{
printf("Student no: %d Grade: %d\n", sr.student_no, sr.grade);
}
The above operations can be combined to do all kinds of things, and you should be able to handle combinations like the following:
Note: For this kind of job I use a plan I call PUF, for "Process Until Finished". The idea is that we want to carry out a process consisting of two steps, read an element and store an element, until one of the steps fails. The read step will fail if we come to the end of the file, and the store step will fail if the collection fills up. If we write a function for each process step in the PUF plan, and we make each of these functions return a 1 when it works and 0 when it fails, we can use this outline:
while (step1(...) )
{
ok=step2(...);
if (!ok)
break;
}
The test in the while just looks at the number step1() returns: it keeps going as long as that number is 1, that is, as long as step1() succeeds. The body of the loop checks the number step2() returns and terminates the loop as soon as it is 0, that is, as soon as step2() fails.
C offers a shorter way to write the PUF plan. This may be a little hard to understand at first, but once you get used to it it will be not only shorter but also clearer:
while (step1(...) &&
step2(...));
Yes, this is a while loop with no body! All the work we want to do is done in the test, which calls the functions step1() and step2(). The symbol && is an and operator: it combines two tests and gives true if the first test and the second test are both true. So here, if either step, step1() or step2(), fails, that step returns 0, which make the test false and ends the loop. The test is evaluated over and over again until one of the steps fails.
You might worry that if step1() fails, then step2() will still be called as part of evaluating the test, and that that might cause trouble. But in fact C stops evaluating the parts of a test as soon as the overall result is known. In this case, if step1() returns 0 it is obvious that the test will be false, and no further evaluation is done.
Notice that the PUF plan is easy to extend to processes with more than two steps. As long as you write functions to carry out each step, and each function returns 1 if it succeeds and 0 if it fails, you can write a statement like this:
while(step1(...) &&
step2(...) && step3(...)&&...&&step27(...));
This is a PUF for a process with 27 steps.
Ex: Read in a bunch of student records and then increase each grade.
void read_and_bump()
{
struct grade_book gb;
struct student_record sr;
make_empty(&gb);
while (read_student_record_from_kb(&sr)&&add(&gb,sr)); //PUF plan
bump_grades(&gb);
}
Ex: sort the elements in a grade book by student number
int remove_min(struct grade_book *pgb, struct student_record *psr)
{
int return_code;
int pos;
return_code=min(*pgb,&pos);
if (return_code==0)
return 0; //collection is empty
return_code=get_value(pos,*pgb,psr);
if(return_code==0)
{
printf("bad subscript from min\n");
exit(1);
}
return_code=rem(pos,pgb);
if(return_code==0)
{
printf("something badly wrong in remove_min()\n");
exit(1);
}
return 1;
}
void sort(struct grade_book *pgb)
{
struct student_record sr;
struct grade_book temp;
make_empty(&temp);
while(remove_min(pgb,&sr)&&add(&temp, sr));//PUF plan
*pgb=temp;
}
Ex: prompt for a student record, and indicate whether of not it is already in a grade book
int matching_record(struct student_record r1, struct student_record r2)
{
if ((r1.student_no==r2.student_no)&&(r1.grade==r2.grade))
return 1;
return 0;
}
int is_there_matching_record(struct grade_book gb, struct student_record sr)
{
int i;
for (i=0;i<gb.count;i++)
if (matching_record(sr, gb.records[i]))
return 1;
return 0;
}
void is_in(struct grade_book gb)
{
struct student_record sr;
int return_code;
return_code=read_student_record_from_kb(&sr);
if (return_code==0)
return;
if (is_there_matching_record(gb, sr))
printf("It's there.\n");
else printf("It's not there.");
}
Ex: ask for student number, print grades for that student
void print_grade_if_match(struct student_record sr, int student_no)
{
if (sr.student_no==student_no)
printf("Grade: %d\n",sr.grade);
}
void print_grades_for_sno(struct grade_book gb, int student_no)
{
int i;
for (i=0;i<gb.count;i++)
print_grade_if_match(gb.records[i],student_no);
}
void prompt_for_sno_print_grades(struct grade_book gb)
{
int sno;
printf("Enter a student number: ");
scanf("%d", &sno);
print_grades_for_sno(gb,sno);
}
Ex: ask for student number, print highest grade (if any)
plan: prompt for student no, add all matching student records to collection temp, find max grade in temp, print it
void add_grade_if_match(struct student_record sr, int student_no, struct grade_book *pgb)
{
int return_code;
if (sr.student_no==student_no)
{
return_code=add(pgb, sr);
if (return_code==0)
{
printf("error in add\n");
exit(1);
}
}
}
void add_grades_for_sno(struct grade_book gb, int student_no, struct grade_book *pnewgb)
{
int i;
for (i=0;i<gb.count;i++)
add_grade_if_match(gb.records[i],student_no, pnewgb);
}
void prompt_for_sno_print_max_grade(struct grade_book gb)
{
int sno;
int return_code;
struct student_record sr;
struct grade_book temp;
make_empty(&temp);
printf("Enter a student number: ");
scanf("%d", &sno);
add_grades_for_sno(gb, sno, &temp);
return_code=max(temp, &sr);
if (return_code==0)
printf("No grades for this student.\n");
else printf("Max grade for this student is: %d\n", sr.grade);
}
Note: There's a good alternative plan for this one, that involves modifying the knockout plan slightly: when you run through the collection doing the knockout, DON'T allow any record with wrong student number to beat the champion:
int max_for_this_sno(int sno, struct grade_book gb, struct student_record *psr)
{
int i;
struct student_record max_so_far;
if (gb.count<=0)
return 0;
max_so_far=gb.records[0];
for(i=0;i<gb.count;i++)
if ((gb.records[i].student_no==sno)&&(gb.records[i].grade>max_so_far.grade))
max_so_far=gb.records[i];
*psr=max_so_far;
return 1;
}
Using this you can get rid of temp and the calls that empty it and add grades to it, and replace max() by max_for_this_sno().
For any of the above kinds of work, you have to be able to create a complete program that can be executed and tested.
Ex:
Ex: read in a bunch of student records. Then ask for student number, print highest grade (if any).
Note: This example is longer than I can ask you to write in a 50 min Programming Check. But it is a good illustration of the building block idea: the only new function I had to write for this was main().
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
struct student_record
{
int student_no;
int grade;
};
struct grade_book
{
struct student_record records[MAX];
int count;
};
void add_grade_if_match(struct student_record sr, int student_no, struct grade_book *pgb);
void add_grades_for_sno(struct grade_book gb, int student_no, struct grade_book *pnewgb);
void prompt_for_sno_print_max_grade(struct grade_book gb);
int read_student_record_from_kb(struct student_record *psr);
int add(struct grade_book *pgb, struct student_record sr);
int max(struct grade_book gb, struct student_record *psr);
void make_empty(struct grade_book *pg);
int main()
{
struct grade_book gb;
struct student_record sr;
make_empty(&gb);
while (read_student_record_from_kb(&sr)&&add(&gb,sr));//PUF
prompt_for_sno_print_max_grade(gb);
return 0;
}
void add_grade_if_match(struct student_record sr, int student_no, struct grade_book *pgb)
{
int return_code;
if (sr.student_no==student_no)
{
return_code=add(pgb, sr);
if (return_code==0)
{
printf("error in add\n");
exit(1);
}
}
}
void add_grades_for_sno(struct grade_book gb, int student_no, struct grade_book *pnewgb)
{
int i;
for (i=0;i<gb.count;i++)
add_grade_if_match(gb.records[i],student_no, pnewgb);
}
void prompt_for_sno_print_max_grade(struct grade_book gb)
{
int sno;
int return_code;
struct student_record sr;
struct grade_book temp;
make_empty(&temp);
printf("Enter a student number: ");
scanf("%d", &sno);
add_grades_for_sno(gb, sno, &temp);
return_code=max(temp, &sr);
if (return_code==0)
printf("No grades for this student.\n");
else printf("Max grade for this student is: %d\n", sr.grade);
}
int read_student_record_from_kb(struct student_record *psr)
{
int user_input;
printf("Type student number or -1 to quit: ");
scanf("%d", &user_input);
if (user_input==-1)
return 0;
psr->student_no=user_input;
printf("Type a grade: ");
scanf("%d", &psr->grade);
return 1;
}
int add(struct grade_book *pgb, struct student_record sr)
{
if (pgb->count >=MAX)
return 0;
pgb->records[pgb->count]=sr;
pgb->count++;
return 1;
}
int max(struct grade_book gb, struct student_record *psr)
{
int i;
struct student_record max_so_far;
if (gb.count<=0)
return 0;
max_so_far=gb.records[0];
for(i=0;i<gb.count;i++)
if (gb.records[i].grade>max_so_far.grade)
max_so_far=gb.records[i];
*psr=max_so_far;
return 1;
}
void make_empty(struct grade_book *pg)
{
pg->count=0;
}
Practice Problems and Further Suggestions
I cannot urge
you too strongly to solve at least SOME of the following practice problems
before the Programming Check.
If you get help in working any of the examples, fine, but then create a similar example and try to solve that without help. Continue until you can solve them without help. You may create notes to assist you.
Practice Problems
Use the following function as needed in the practice problems below. Be sure to put #include <stdlib.h> in your program when you use this function:
int random() //returns a random int between 0 and 99.
{
return (100.*rand())/RAND_MAX;
}
An important tip: Don’t try to write the whole program before compiling and testing. This is a bad idea, except for material you have down cold. Instead, you should write the program in stages, compiling and testing as you go. For example, first do the prompt and read a number, and print the number. Compile and test that before going on. Then create a collection (if that's what comes next) and print the collection. Get that working before continuing, and so on.
Prompt the user for a positive number and create a collection containing that many random ints. Print the minimum and maximum.
Prompt the user for a positive number and create a collection containing that many random ints. Sort it in increasing order. Print the numbers.
Prompt the user for a positive number and create a collection containing that many random ints. Remove all those greater than 50. Print the remaining numbers.
Prompt the user for a positive number and create a collection containing that many random ints. Create a new collection containing the numbers less than 25. Print the new collection.
Prompt the user for a positive number and create a collection containing that many random ints. Using a function, multiply each number in the collection by 3. Print.
Prompt the user for a positive number and create a collection of that many random dots. Each dot has an x and y coordinate, each a random int. Print the coordinates of all dots whose x coordinate is greater than 50.
Prompt the user for a positive number and create a collection of that many random dots. Remove all dots whose x coordinate is greater than 50 and print the coordinates of the remaining dots.
Prompt the user for a positive number and create a collection of that many random dots. Print the subscript of the first dot in the collection whose x coordinate is greater than 50, or print a message saying that there are no such dots in the collection.