# Treasure Map and Saddle Points

edited Mar 31, 2018

Part 2: Code

1) Follow your instructions and implement your algorithm for problem 1 as a function in c. Call this

function from your main verifying that it works. I have provided some sample inputs that you

can use to test it with in the file “all.h”. The easiest way to include this into your code is to use

an include statement in your c file.

a. Example: #include “all.h”

b. When including custom .h files that you made, you should use “” instead of <>

2) Follow your instructions and implement your algorithm for problem 2 as a function in c. Call this

function from your main verifying that it works. I have provided some sample inputs that you

can use to test it with in the file “all.h”. The easiest way to include this into your code is to use

an include statement in your c file.

a. Example: #include “all.h”

b. When including custom .h files that you made, you should use “” instead of <>

c. If you decide to create both of these functions in the same file (then call both of them

from main), you only need to include all.h once.

3) Below is an algorithm for sorting numbers in a list. If you follow the algorithm, you should end

up with a list sorted in ascending order. Implement the algorithm below as a C function. I have

provided some sample inputs that you can use to test it with in the file “all.h”.

Sorting Algorithm:

1) function sort_numbers (A: array[1..n] of numbers)

2) for i from 1 to n-1

3)for j from 1 to n-1

4)if A[j] > A[j+1]

4a)temp = A[j]

4b)A[j] = A[j+1]

4c)A[j+1] = temp

5) for i from 1 to n

6)print: A[i] + “ “

Algorithms

Treasure Map:

Precondition: N < 10

1. Function find_treasure (map:N x N of whole numbers)

2. clue = map[1][1]

3. col = clue % 10

4. row = (clue – col) / 10 (whole number division)

5. print “first clue is: “ + row + “, ” col

6. while map[row][col] != clue

6a.clue = map[row][col]

6b.col = clue % 10

6c. row = (clue – col) / 10 (whole number division)

6d. print “next clue is: “ + row + “, “ + col

7. print “Found the treasure at coordinate “ + row + “, “ + col

1. function find_sp (A: N x N array of whole numbers)

2. row = true, col = true

4. for i from 1 to N

5. for j from 1 to N

6.for k from 1 to N

7.if A[i][j] < A[i][k]

8.row = false

9.break

10.if A[i][j] > A[k][j]

11.col = false

12.break

13.if row == true and col == true

15.print “Saddle Point at “ + i “, “ + j

16.row = true

17.col = true

/*

* all.h

*

* Created on: Mar 18, 2018

* Author: rsardinas

*/

#ifndef ALL_H_

#define ALL_H_

int treasure_map1 [5][5] = { {34,21,32,41,25},

{14,42,43,14,31},

{54,45,52,42,23},

{33,15,51,31,35},

{21,52,33,13,23} };

int saddle_points1 [5][5] = { {1,2,5,4,5},

{2,3,1,4,6},

{1,2,3,4,5},

{2,4,6,8,10},

{1,3,5,7,9} };

int saddle_points2 [5][5] = { {1,2,3,4,5},

{1,2,3,4,5},

{1,2,3,4,5},

{1,2,3,4,5},

{1,2,3,4,5} };

int saddle_points3 [5][5] = { {5,4,3,2,1},

{5,4,3,2,1},

{5,4,3,2,1},

{5,4,3,2,1},

{5,4,3,2,1} };

int saddle_points4 [5][5] = { {1,2,3,4,5},

{0,2,3,4,6},

{1,2,3,4,7},

{10,10,10,10,10},

{1,5,7,9,2} };

int unsorted_numbers1 [10] = {1,5,3,4,6,7,10,2,8,4};

int unsorted_numbers2 [5] = {5,4,3,2,1};

#endif /* ALL_H_ */