CSC231 Optional Homework 9 2017

--D. Thiebaut (talk) 11:10, 22 April 2017 (EDT)

---

Page under construction!

Problem 1: C Functions

Write a C program called funcs.c that contains only C functions. You will need to write an additional file called funcs.h, and the information about what it contains is the section on testing. The functions will be called by an external main program. This is very similar to the the last homework assignment, except then it was done in assembly.

Functions

Your funcs.c program should contain 3 functions: getMin(), zap() and merge().

getMin()

Receives 3 ints as parameters and returns the smallest.

Example

  printf( "Min of -10, 1, 10 = %d\n", getMin( -10, 1, 10 ) );
  printf( "Min of -10, 1, 10, -20, 2 = %d\n", getMin( getMin( -10, 1, 10 ), -20, 2 ) );
  // output:
  //  Min of -10, 1, 10 = -10
  //  Min of -10, 1, 10, -20, 2 = -20

zap()

Receives two strings as parameters and modifies the first one by finding the first

string in it, and replacing it with dashes.

Example

  char s1[] = "Mississippi Burning";
  char s2[] = "Mississippi Burning";

  //--- test zap ---
  printf( "s1 = %s\n", s1 );
  zap( s1, "ss" );
  printf( "zap(s1) = %s\n", s1 );

  printf( "s2 = %s\n", s2 );
  zap( s2, "tt" );
  printf( "zap(s2) = %s\n", s2 );
 
  // output:
  // s1 = Mississippi Burning
  // zap(s1) = Mi--issippi Burning 
  // s2 = Mississippi Burning
  // zap(s2) = Mississippi Burning

merge()

receives 3 arrays of ints. The first two have dimension 5, each, and are sorted. The third one is of dimension 10, and contains random information, i.e. it is not initialized. Merge() takes the ints from both arrays of dimension 5 and merges them into the third array, keeping the ints sorted. You may assume that the first two arrays will always have dimension 5, and the third one will always have dimension 10.

Example

  int A[] = { 1, 2, 3, 10, 11 };
  int B[] = { 4, 5, 12, 13, 15 };
  int C[10];

  merge( A, B, C );
  for ( i=0; i<10 && A[i]!=-1; i++ )
    printf( "%d, ", C[i] );
  printf( "\n" );
  // output:
  // 1, 2, 3, 4, 5, 10, 11, 12, 13, 15,

Merging in Python

For reference, here is how merge would work in Python:

from __future__ import print_function

def merge( A, B, C ):
    """
    merges 2 arrays into a 3rd one.  The dimensions of the arrays can be 
    any valid integer.  C must be a mutable list.
    """
    i = 0
    j = 0
    k = 0
    while i<len(A) and j<len(B):
        if A[i] < B[j]:
            C.append( A[i] )
            i += 1
        else:
            C.append( B[j] )
            j += 1
        if i >= len( A) or j >= len( B ):
            break
    while i < len( A ):
        C.append( A[i] )
        i += 1
    while j < len( B ):
        C.append( B[j] )
        j += 1
 
def main():   
    A = [1, 3, 10, 20, 30 ]
    B = [2, 3, 4, 5, 100 ]
    C = []
    merge( A, B, C )
    print( "A = ", A )
    print( "B = ", B )
    print( "C = ", C )

main()

# output
# A =  [1, 3, 10, 20, 30, 31]
# B =  [2, 3, 4, 5, 100]
# C =  [1, 2, 3, 3, 4, 5, 10, 20, 30, 31, 100]

Testing Your Program

Here is a simple example showing how to write two C programs, one containing functions, and one containing a main program, and link them together.

funcDemo.c

// funcDemo.c
// D. Thiebaut
// demonstration code for illustrating how to link
// several C programs.
// This program contains only 1 function.


// sum()
// returns the sum of the 2 ints it gets as parameters.
int sum( int a, int b ) {
  return a + b;
}

mainDemo.c

// mainDemo.c
// D. Thiebaut
// main program that calls the sum()
// function from funcDemo.c
#include <stdio.h>
#include "funcDemo.h"

void main() {
  int a=3, b=10;
  int c;

  c = sum( -1, 2000000000 );
  printf( "sum( %d, %d ) = %d\n", -1, 2000000000, sum(-1, 2000000000 ) );
  printf( "sum( %d, %d ) = %d\n", a, b, sum(a, b) );
  printf( "sum( %d, sum( %d, %d ) ) = %d\n", a, 2, b, sum(a, sum( 2, b ) ) );
  printf( "sum( %d, %d ) = %d\n", -1, 1, sum(-1, 1) );
}

funcDemo.h

In order to link together funcDemo.c and mainDemo.c, we need a third file, called a header file, that will list all the functions in funcDemo.c, but just the name of the functions and what kind of parameters they take, along with the type of value they return. We'll include this file in mainDemo.c, so that it knows what functions are available "on the outside." For funcDemo.c, the header file funcDemo.h looks like this:

// funcDemo.h
// D. Thiebaut
// header file for funcDemo.c
//

int sum( int a, int b );

Compiling Steps

 gcc -c funcDemo.c
 gcc -o funcMain funcMain.c funcDemo.o

• the first execution of the gcc command instructs it to generate an object file (with a .o extension) for funcDemo.c
• the second execution of gcc instructs it to compile funcMain.c, link it with the object file funcDemo.o and output the resulting executable in funcMain.

• to run the program, we simply type:

./funcMain

and we get the following output:

sum( -1, 2000000000 ) = 1999999999
sum( 3, 10 ) = 13
sum( 3, sum( 2, 10 ) ) = 15
sum( -1, 1 ) = 0

A Test Program for funcs.c

In case this could be useful, here is a test main program to test your functions with, and its output when linked with the solution program containing the functions.

// main.c
// D. Thiebaut
// Test program for functions of Homework 9.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "funcs.h"

void main(){
  char s1[] = "Mississippi Burning";
  char s2[] = "Mississippi Burning";
  int i;

  //--- test getMin ---
  printf( "Min of -10, 1, 10 = %d\n", getMin( -10, 1, 10 ) );
  printf( "Min of -10, 1, 10, -20, 2 = %d\n", getMin( getMin( -10, 1, 10 ), -20, 2 ) );

  //--- test zap ---
  printf( "s1 = %s\n", s1 );
  zap( s1, "ss" );
  printf( "zap(s1) = %s\n", s1 );

  printf( "s2 = %s\n", s2 );
  zap( s2, "tt" );
  printf( "zap(s2) = %s\n", s2 );

  strcpy( s1, "Mississippi less" );
  printf( "s1 = %s\n", s1 );
  while ( zap( s1, "ss" ) )
    ;
  printf( "zap(zap(...(s1))) = %s\n", s1 );

  //--- test merge ---
  int A[] = { 1, 2, 3, 10, 11 };
  int B[] = { 4, 5, 12, 13, 15 };
  int C[10];

  merge( A, B, C );
  for ( i=0; i<10 && A[i]!=-1; i++ )
    printf( "%d, ", C[i] );
  printf( "\n" );
  
}

output

Min of -10, 1, 10 = -10
Min of -10, 1, 10, -20, 2 = -20
s1 = Mississippi Burning
zap(s1) = Mi--issippi Burning
s2 = Mississippi Burning
zap(s2) = Mississippi Burning
s1 = Mississippi less
zap(zap(...(s1))) = Mi--i--ippi le--
1, 2, 3, 4, 5, 10, 11, 12, 13, 15,

Submission

Submit your program in the Homework 9 section, on Moodle.

Problem 2

Your assignment is to implement a recursive version of the Towers of Hanoi in assembly.

You can use this Python version for inspiration:

# hanoi.py
# D. Thiebaut
# implements the game of hanoi in python.
# uses recursion.
#
# to run, type 
#        python hanoi.py 
# at the command line, or run in Idle
from __future__ import print_function

def moveDisk( source, dest, extra, n ):
    if n==1:
        print( "move disk from %s to %s" % ( source, dest ) )
        return
    
    # more than 1 disk...
    moveDisk( source, extra, dest, n-1)
    print( "move disk from %s to %s" % ( source, dest ) )
    moveDisk( extra, dest, source, n-1)

def main():
        moveDisk( "A", "B", "C", 5 )

main()

The output of the program is shown below:

move disk from A to B
move disk from A to C
move disk from B to C
move disk from A to B
move disk from C to A
move disk from C to B
move disk from A to B
move disk from A to C
move disk from B to C
move disk from B to A
move disk from C to A
move disk from B to C
move disk from A to B
move disk from A to C
move disk from B to C
move disk from A to B
move disk from C to A
move disk from C to B
move disk from A to B
move disk from C to A
move disk from B to C
move disk from B to A
move disk from C to A
move disk from C to B
move disk from A to B
move disk from A to C
move disk from B to C
move disk from A to B
move disk from C to A
move disk from C to B
move disk from A to B

Requirements

• Your program will call the recursive function moveDisk and pass it the characters 'A', 'B', 'C' and the number 5, and will display an output similar to the one shown above.
• You may not pass the parameters via registers. Instead you must pass all four parameters through the stack.
• Your program will also output at the end of the output the number of moves that were performed. You may not use a global variable to keep track of the count. If you are not sure how to do this in assembly, modify the python program to make it display the number of moves, then translate the python program in assembly.