A Finite State Machine (FSM) is a popular tool that is widely used in computer s
ID: 3761798 • Letter: A
Question
A Finite State Machine (FSM) is a popular tool that is widely used in computer science. Why it is so popular? Because it is simple, and easy to understand and implement. Here is a brief introduction: Finite State Machine Tutorial Your task is to implement a FSM that can recognize if the number of times that ‘3’ appeared in the input string is ‘odd’ or ‘even’. Here are couple of examples a1234567890 => even a3balc2;034 => even 23423432 => odd 54 => even The FSM that can recognize this pattern is simple and only has two states as follows: 3 Here is procedure that you need to implement: - First you need to create an array of char and get the user’s input. To do so, you can see the string sample file of the project (proj2-sample.c). Even Odd Start from ‘even’ State 3 CSE 220 Fall 2015 - You should define a variable (probably integer or char) to keep track of the states. This variable can only hold two values, one indicating the state ‘even’ and another value for ‘odd’. For example, if you have it as an integer, 0 can indicate the state even and 1 can indicate odd state. (Or if it is char, ‘e’ can be for even and ‘o’ for odd). - Initially, you can assume that we have even number of ‘3’s (due to having zero number of ‘3’ will be considered as even). - Then you should go over all the input characters one by one and when ever you detect a ‘3’, just switch your state. Hence, if you are in state ‘odd’ and see a new ‘3’, you should switch to state ‘even’ and vice versa. - Whenever you see a new character which is not ‘3’, you should not change the states and simply ignore it and go to the next char till you get to the end of chars. - When you are done with all characters, you should simply print state which you are in. Show your work to your TA. Program 2: Sorting Sorting a list of data is a very common task that we use computer to do. Here we need to write a C program to sort a given one-dimensional array of integers, namely, to re-arrange the elements in an array in ascending order based on their values. For example, if we are given an array as int a[5] = {6,12,5,97,1}; After sorting, it will become {1, 5, 6, 12, 97} Complete the following program to sort an array. You need to implement the following steps: ² First, find the smallest element in the array and swap the smallest element with the element at position 0 (i.e, put the smallest element at position 0 and the element that was at position 0 in place of the smallest element). ² Second, find the second smallest element and swap it with the element at position 1 (Note that the smallest element is now at position 0, so the second smallest element is the smallest of elements at positions 1 to 4). ² Repeat by swapping the third smallest element with the element at position 2, swapping the fourth smallest element with the element at position 3, ... ... ² Finally, the array should have been already sorted. To tackle this problem, a good strategy is to start with a pseudo-code “recipe” of the solution. We try to write a clear, concise, and formal description of how our program should work first. Here we already have a given description in natural language about how the program should CSE 220 Fall 2015 work, we can translate it into a pseudo-code kind of description which will be more helpful for writing our program: Step 1: Find the smallest value from a[0] to a[4]. Suppose the smallest value we find is a[min], swap a[0] and a[min]. Step 2: Find the smallest value from a[1] to a[4]. (Again) suppose the smallest value we find is a[min], swap a[1] and a[min]. Step 3: Find the smallest value from a[2] to a[4]. Suppose the smallest value we find is a[min], swap a[2] and a[min]. Step 4: Find the smallest value from a[3] to a[4]. Suppose the smallest value we find is a[min], swap a[3] and a[min]. Step 5: We are done! (think about why we just stop here and don’t need to keep going?) Again, what we have just done is to translate the natural language description of a procedure into a more concise and formal pseudo-code description. It should be easy to see there is actually a repetitive pattern in our pseudo-code description (what is the repetitive pattern?). If you see that pattern, we can further modify our pseudo-code into an even more concise version, which is also getting closer to a real program: for i from 0 to 3: Find the smallest value from a[i] to a[4]. Suppose it is a[min]. swap a[i] and a[min]. From this version of pseudo-code, you should see that our program need to contain a loop (i.e., for i from 0 to 3), and in the loop body we just need to do two things: “Find the smallest value from a[i] to a[4] (a[min])” and “swap a[i] and a[min]”. Now let’s write our real program. Create an empty program file lab8.c in your folder. Open the file, and copy the following function definition into the file: This function does one thing for you: given an array (a), its size (size), and a starting index (start), the function finds (returns) the index of the smallest value in the array from the given CSE 220 Fall 2015 start index to the last index. For example, if we have: int a[5] = {6,12,1,97,5}; int minIdx = findMin(a, 5, 1); minIdx will be 2, because it finds the index of the smallest value in the array from a[1] to a[4], which is 2 (i.e., a[2] is the smallest value, which is 1). In your lab8.c, below the function you just copied into the file, write a main function that uses the findMin function to sort a given array, i.e., your code should be looked like the following: Print out the array after it has been sorted. It would be even better if you can print out the intermediate results (i.e., the current array after each iteration of the loop). ***Written in C
Explanation / Answer
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
long a,s=0,s1=0;
int b,n=0,n1=0,k=0;
int d[10],nl[10];
int c=0;
int i=0,j=0;
for (i=0; i<10; i++)
{
d[i]=0;
nl[i]=0;
}
cout<<"Write a number: "<<endl;
cin>>a;
i=0;
while(a!=0) {
b=a%10;
a=a/10;
if(b%2!=0) {
d[i]=b;
i++;
}
else {
nl[k]=b;
k++;
}
}
n=i;
n1=k;
cout<<n1<<" even numbers "<<n<<" odd numbers "<<endl;
cout<<" Odd numbers not ranged array"<<endl;
for(i=0; i<n; i++)
cout<<d[i]<<" ";
cout<<endl;
cout<<" Even numbers not ranged array"<<endl;
for(i=0; i<n1; i++)
cout<<nl[i]<<" ";
cout<<endl;
c=0;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(d[i]>d[j])
{
c=d[i];
d[i]=d[j];
d[j]=c;
}
}
}
cout<<" Odd numbers ranged array"<<endl;
for(i=0; i<n; i++)
cout<<d[i]<<" ";
cout<<endl;
cout<<"Min odd number "<<d[n-1]<<endl;
c=0;
for(i=0; i<n1; i++)
{
for(j=0; j<n1; j++)
{
if(nl[i]<nl[j])
{
c=nl[i];
nl[i]=nl[j];
nl[j]=c;
}
}
}
cout<<" Even numbers ranged array"<<endl;
for(i=0; i<n1; i++)
cout<<nl[i]<<" ";
cout<<endl;
cout<<"Max even number "<<nl[k-1]<<endl;
for(i=0; i<n; i++)
{
s=s*10+d[i];
}
for(i=0; i<n1; i++)
s1=s1*10+nl[i];
cout<<"Max odd digits' number "<<s<<endl;
cout<<"Min odd digits' number "<<s1<<endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.