CMPSC 121 Introduction to Programming Techniques Fall 2011 Penn State University
ID: 3631276 • Letter: C
Question
CMPSC 121 Introduction to Programming Techniques Fall 2011Penn State University Assignment 8 Due: October 27
The purpose of this assignment is to reinforce the concepts of functions, 2D arrays, searching and sorted
arrays. Be sure to submit your source le (the one with the cpp extension) as an attachment to the
Angel Drop Box by midnight of the due date.
Microsoft interview question! For this assignment, we will work with a Microsoft interview question.
For a 2D array, we can say that both its rows and columns are sorted if Ai;j < Ai+1;j and Ai;j < Ai;j+1.
Here is an example of a 2D array where its rows and columns are sorted.
1 2 4 7
2 3 6 8
4 5 7 10
5 7 8 12
You will write a program that can test whether a given 2D array is sorted in this way and also can
generate a new array that is sorted. Your program should prompt the user for a le name which should
be a plain text le in the following format:
m n
A11 A12 A13 A14 A15 ... A1n
A21 A22 ...
...
Am1 Am2 Am3 ... ... ... Amn
The rst two numbers give the number of rows m and the number of columns n. The remaining
numbers are the values for the mn 2D array. Your program must read in this data, display it as rows
and columns and inform the user whether the 2D array is sorted or not. (You can assume that no le
will contain an array with more than 100 rows or 100 columns.)
Next your program should prompt the user for a number and your program should report how many
times that number occurs in the 2D array. You must use the fact that each row (or column) is sorted
by using binary search to search each row (or column) for the number. (You will need to modify the
binary search algorithm to operate on a particular row of a 2D array.)
Finally your program should prompt the user for two numbers, both between 2 and 50 inclusive, repre-
senting the number of rows and columns of a new 2D array. It should then generate a sorted 2D array
with those dimensions, lled with what appear to be random numbers. (They can't truly be random
because we want the 2D array sorted.)
Here is a hint on how to generate these numbers. To generate a andom" number greater the n use
n + rand()%k for k=10. The rst row and rst column can be generated this way starting with some
initial random number. For the remaining array entries each must be greater than the numbers that
occur immediately above it and to its left. Find the greater of these two numbers and use the same
idea to create a random number greater than both of them. Your program should display the resulting
2D array.
Here is a sample output of how your program should interact with the user.
Enter a file to be checked: hw8.txt
The array:
1 3 9 15 21
4 5 11 21 28
8 15 19 27 35
11 21 23 29 39
is sorted.
Enter a number: 21
21 was found 3 times.
Enter new array dimensions: 3 5
The generated array is:
6 14 17 26 33
12 20 21 28 36
21 27 30 32 40
Your program must not produce any other output!
Part of this assignment involves following a top-down design philosophy and deciding what functions
you should write. Think carefully about how to decompose this problem into well-dened tasks that can
be implemented as functions. For each function be clear about what input the function requires and
about what value the function returns.
Be sure to follow the Coding Style Guidelines. Include pre- and post- conditions for all functions,
comment your loops with descriptions of what/why you are doing, and use descriptive variable names.
Be sure your loops are well designed. Do not use any magic numbers.
Don't forget to start early, and make sure you understand what you are doing before you start coding!
Explanation / Answer
please rate - thanks
I don't see how this can work with a binary search since by definition it doesn't look at every element in an array, and it only works on sorted arrays, and all arrays may not be sorted, so I used a linear
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
void input(int[][100],int&,int&);
void output(int[][100],int,int,string);
bool sorted(int[][100],int,int);
int binary(int[][100],int,int,int);
void generate(int[][100],int,int);
int main()
{int a[100][100],n,m,key;
input(a,m,n);
output(a,m,n,"The array ");
if(sorted(a,m,n))
cout<<"is sorted ";
else
cout<<"not sorted ";
cout<<"Enter a number: ";
cin>>key;
cout<<key<<" was found "<<binary(a,m,n,key)<<" times ";
cout<<"Enter new array dimensions: ";
cin>>m>>n;
generate(a,m,n);
output(a,m,n,"The generated array is: ");
system("pause");
return 0;
}
void generate(int a[][100],int m,int n)
{srand(time(0));
int i,j,max=100,min;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{if(i+j>0)
{if(j==0)
min=a[i-1][0];
else if(i==0)
min=a[0][j-1];
else
{if(a[i-1][j]>a[i][j-1])
min=a[i-1][j];
else
min=a[i][j-1];
}
a[i][j]=rand()%max+min+1;
}
else
a[i][j]=rand()%max+1;
}
}
int binary(int a[][100],int m,int n,int key)
{int i,j,count=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(a[i][j]==key)
count++;
return count;
}
bool sorted(int a[][100],int m,int n)
{int i,j;
for(i=0;i<m-1;i++)
for(j=0;j<n-1;j++)
if(a[i][j]>a[i+1][j]||a[i][j]>a[i][j+1])
return false;
return true;
}
void output(int a[][100],int m,int n,string mess)
{int i,j;
cout<<mess;
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
cout<<setw(4)<<a[i][j]<<" ";
cout<<endl;
}
}
void input(int a[][100],int& m,int& n)
{char filename[30];
int i,j;
cout<<"Enter a file to be checked: ";
cin>>filename;
ifstream in;
in.open(filename); //open file
if(in.fail()) //is it ok?
{ cout<<"file did not open please check it ";
system("pause");
system("exit");
}
in>>m;
in>>n;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
in>>a[i][j];
in.close();
}