Tags:
create new tag
view all tags

Lab 5 - Pattern Matching

Due: March 22, 11:55pm

Moodle Link

good-versus-bad-patterns.jpg

Instructions

  • Turn in the code (a cpp file or ideone.com link), and the run outputs as requested below.
  • Remember to format the code as described and the book and text, and to include comments including complete commetns at the beginning of the program.
  • You will need to use arrays

Grading Table

Requirement Grading Comments Points Score
Easy to use user interface   10  
C++ code includes comments, with project information at top, pre and post conditions for each functions and other cmments as needed.   10  
The C++ code has good formatting, indentation, and organization.   10  
Good variable and function names, appropriate use of constants rather then literal numbers.   10  
Functions: Logic divided up into cohesive functions with a single purpose   20  
Runs: Run examples from trials with correct output   40  
Total   100  

Problem

Pattern Matching: Write a program that looks for a pattern of integers in an array of integers. The program first asks the user to input up to 100 numbers greater than or equal to zero. The user terminates the input with a negative number or sentinel. The program automatically moves to the next step after 100 numbers has been entered.

The program then enters a loop, and asks the users to enter a sequence of up to 10 numbers. As before, they enter numbers until either a negative number is entered, or they have entered 10 numbers. This array will be called the pattern.

The program then searches the larger array for a sub-sequence of numbers that matches the pattern. It will continue to search until it finds all instances of that pattern, counting the matches. (Note that for this exercise patterns cannot overlap, e.g. when you find a pattern, start searching for then next only AFTER the previous pattern.

The program will then report the number of matching, and then ask for another pattern to be entered.

If the user enters a negative number when as the first number in a pattern, the pattern is empty, and the program terminates.

If the number list or pattern is longer than 100 or 10, respectively, ignore the extra, using the first 100 or 10.

If the user enters a pattern that is longer then the search array, give the user an error.

Example:

Enter up to 100 integers (-1 to end): 1 4 3 6 8 5 12 5 6 8 5 2 9 3 1 4 3 6 6 8 5 -1

Enter a pattern (Up to 10, -1 to end): 6 -1
Array: 1 4 3 6 8 5 12 5 6 8 5 2 9 3 1 4 3 6 6 8 5 
Pattern: 6 
Matches: 4
Enter 'C' to continue:C

Enter a pattern (Up to 10, -1 to end): 6 8 5 -1
Array: 1 4 3 6 8 5 12 5 6 8 5 2 9 3 1 4 3 6 6 8 5 
Pattern: 6 8 5 
Matches: 3
Enter 'C' to continue:C

Enter a pattern (Up to 10, -1 to end): 6 5 2 -1
Array: 1 4 3 6 8 5 12 5 6 8 5 2 9 3 1 4 3 6 6 8 5 
Pattern: 6 5 2 
Matches: 0
Enter 'C' to continue:C

Enter a pattern (Up to 10, -1 to end): 1 3 2 4 3 4 2 4 3 4 2 1 3 1 3 4 -1
Array: 1 4 3 6 8 5 12 5 6 8 5 2 9 3 1 4 3 6 6 8 5 
Pattern: 1 3 2 4 3 4 2 4 3 4 
Matches: 0
Enter 'C' to continue:
RUN FINISHED; exit value 0; real time: 1m 3s; user: 0ms; system: 0ms
Solution Strategy

You should create the following functions as part of your solution:

void getArray(int a[], int max, int& count);
// Precondition: a[] is a array, MAX is the size of a[];
// Postcondition: a[] contains up tp MAX numbers entered by user, and count is the number of number entered

void displayArray(int a[], int n) ;
// Precondition: a[] is an array of n integers.
// Postcondition: the n integers in a[] are displayed separated by spaces.

bool checkMatch(int a[], int as, int ao, int p[], int ps);
// Check to see if the pattern p[] matches in a[] at the location ao
// Precondition: a[] has as integers, p[] has ps integers, ao is an index in A[].
// Postcontition: return false if ps is less then as-ao (pattern is longer then elemts left in a[]
// Postcontition: return true if the ints in p[] match the ints in a[] starting from ao, else false.
// Postcondition: (formally) return ps <= as-ao && a[ao] == p[0] && a[ao+1] == p[1] && .. && a[ao+ps-1] == p[ps-1]


int countMatches(int a[], int as, int p[], int ps);
// Precondition: a[] has as integers, p[] has ps integers
// Postcondition: The number of occurrences of the pattern in p[] in a[] is returned

Turn in:

1. A search in array "3 6 6 6 4 7 8 8 4 6 2 4 10 4 8 6 6 4 2 6 6 6 4 7 8 6 5 6 4 6 4 2 6 5 6 5 6 5 5 1 2 1 3 6 4 7 8 6 8 6 6 4 2"

  • Search for 6
  • Search for 6 4 2
  • Search for 6 6 4 7 8
  • Search for 5 4 3 2 1
  • Search for 10 4 8 6 6 4 2 6 6 6
2. A search in array "1 2 3 4 5 6 7 8"

  • Search for 8 9 10
  • Search for 1 2 3 4 5 6 7 8 9 10
  • Search for 12
  • Search for 5 6 7

Solution

  • good-versus-bad-patterns.jpg:
Edit | Attach | Watch | Print version | History: r21 < r20 < r19 < r18 < r17 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r21 - 2018-03-01 - JimSkon
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback