HW 07 Solution

For Submission and/or Questions about the HomeWork #2 see Ar. Gör. Betül Türkkol (Room 108-Computer Vision Lab)




Do not use global and/or static variables. Do not change given prototypes of functions.




A) You will write a recursive function that finds and returns size of a string. int find_size(const char *string)

Using the function above write a new function that finds how many times a given string is used in a given string.
int char_number(const char *string, const char *wish_to_find)




Assume every Friday, you have to climb n stairs for C lab on the first floor. You can take your steps as follow: One stair at a time or two stairs at a time. You will write a complete C program to calculate in how many distinct ways you can climb to the top and to print it on the screen.



For example: n=4 you can climb in 5 different ways as




1 stair+1 stair+1stair+1stair

OR




1 stair+1 stair+2 stairs

OR




1 stair+2 stairs+1 stair

OR




2 stairs+1 stair+1 stair

OR




2 stairs+2 stairs




To calculate ways you will use the sum of combinations of choice “2 stairs” in total steps. For example C(4,0)+C(3,1)+C(2,2) will be calculated for the case above.




Your program will include at least two functions as following :

int combination (int n , int k) : a recursive function to calculate combination “n choose k” and returns the result.



int ways (int n) : write a recursive function to calculate and return total number of ways.



Hint : Use following properties of combination




C(n, k) = C(n, n-k)
C(n, 0) = C(n, n) = 1
C(n, k) = C(n-1, k-1) + C(n-1, k)






You will write a complete C program to find a path on a grid maze with the following rules:

You must stay in the grid
You can follow available's and right_down's on your path
You cannot use notavailable's on your path
When you are on an available position, you can go to either right or down if it is also available.
A notavailable position means that coordinate is not available. You can not move to that position.
When you are on a right_down position, you must go to right-down coordinate if it is available or it is a dead-end.



Your program should have at least 3 functions.

void read_table(FILE *input_file, Grid_t table[][COL_SIZE]); void print_path(char path[][COL_SIZE], int n);




Bool find_path(Grid_t table[][COL_SIZE], char path[][COL_SIZE], int size, int location_x, int location_y);




Some More Information About Program:




Grid Generation: An NxN table will be read from a file called table.txt.

Into an NxN array of enumerated type called Grid_t.

enum Grid_t{notavailable,available,right_down};




You are expected to write a recursive function to draw a path from first coordinate of the grid to the last coordinate.




Bool find_path(Grid table[][COL_SIZE], char path[][COL_SIZE], int size, int location_x, int location_y)




Inputs of the function:

Grid table[][] : given NxN Grid array that you are asked to find a way on.

Char path[][] : an NxN char you will draw the path on this char array using “*”'s as shown in the example

int ROW_SIZE : row size of the input array

int location_x : x coordinate of your current location initially 0.

int location_y : y coordinate of your current location initially 0.




The function returns whether a path is found or not.

Example : Assume I am given the My_table below where 0 = notavailable; 1=available; 2=right_down. My path array would be as shown.

My_table




1
0


0
0
0












1
1


1
0
0












1
0


2
0
0












0
0


1
1
0












0
0


2
1
1
















My_path


*






















*
*


*






















*
























*






















*
*















General:




Obey honor code principles.
Read your homework carefully and follow the directives about the I/O format (data file names, file formats, etc.) and submission format strictly. Violating any of these directives will be penalized.



Obey coding convention.
Your submission should include the following files and NOTHING MORE (no data files, object files, etc):
HW07_<student_name_<studentSurname_<student number_part1.c HW07_<student_name_<studentSurname_<student number_part2.c HW07_<student_name_<studentSurname_<student number_part3.c




Do not use non-English characters in any part of your homework (in body, file name, etc.).



Deliver the printout of your work until the last submission date.