Part-1: find the longest block (subsequence of elements with same value) in
an array.
Part-2: find all subsequences in an array of int that add up to a given sum.
*/
#include <iostream>
#include <cstdlib>
using namespace std;
void printSeq(int* a, int s, int e);
// -------------------------------------------- functions to be implemented by you
void longestBlock(const int* a, int n, int& s, int& e)
{
// s = start index of the block
// e = end index of the block (exclusive, i.e. the block contains elements
from a[s] to a[e-1])
s = e = 0; // empty block
// your codes
}
/*
Determine all subsequences in the array such that the sum
of each subsequence is equal to the targetSum
example: A[] = {5, 1, 4, 4, 2, 5, 3, 2, 4, 5}
if targetSum = 10
the function prints: subsequence : 5, 1, 4
subsequence : 4, 4, 2
subsequence : 2, 5, 3
subsequence : 5, 3, 2
if targetSum = 13
the function prints: no subsequence found
*/
void findAllSubSeq(int a[], int n, int targetSum)
{
cout << "Subsequence with sum = " << targetSum << endl;
// Your codes
}
// -------------------------------------------------- functions given to you
void printSeq(int* a, int s, int e)
{
for (int i = s; i < e; i++)
cout << a[i] << ", ";
cout << endl;
}
void part_1()
{
cout << "Part_1:\n\n";
int a[] = {1, 2, 3, 3, 1, 4, 4, 4, 5, 8, 6, 6, 5, 5, 5, 5, 2, 1, 7, 7};
int n = 20;
cout << "a[] : ";
printSeq(a, 0, n);
cout << endl;
int s, e;
longestBlock(a, n, s, e);
cout << "Longest block in the array:\n";
cout << "Data value = " << (e > s ? a[s] : 0) << ", start index = " << s;
cout << ", block length = " << e - s << endl << endl;
cout << "Test with empty array:\n";
longestBlock(a, 0, s, e);
cout << "Longest block in the array:\n";
cout << "Data value = " << (e > s ? a[s] : 0) << ", start index = " << s;
cout << ", block length = " << e - s << endl << endl;
}
void part_2()
{
cout << "\n------------------------------------------------------\n";
cout << "Part-2:\n\n";
int a[] = {5, 1, 4, -4, 2, 1, 5, 3, -2, 4, 5, -8, 7, 9, 1};
int n = 15;
cout << "a[] : ";
printSeq(a, 0, n);
cout << endl;
int targetSum = 16;
findAllSubSeq(a, n, targetSum);
cout << endl;
targetSum = 31;
findAllSubSeq(a, n, targetSum);
cout << "\nTest with empty array:\n";
targetSum = 16;
findAllSubSeq(a, 0, targetSum);
}
int main()
{
part_1();
part_2();
cout << endl;
system("pause");
return 0;
}
C++ code:
//=========================================================
#include <iostream>
#include <cstdlib>
using namespace std;
void printSeq(int* a, int s, int e);
// -------------------------------------------- functions to be
implemented by you
void longestBlock(const int* a, int n, int& s, int&
e)
{
// s = start index of the block
// e = end index of the block (exclusive, i.e. the
block contains elements
//from a[s] to a[e - 1])
s = e = 0; // empty block
int temp_s = 0; // starting point
int length = 0; // largest block length
for (int i = 1; i < n; i++)
{
// if 2 character does not
match
if (a[i-1] != a[i])
{
// check if new
block is larger than previous longest block
if ( i - temp_s
>length)
{
length = i - temp_s; //update length
s =
temp_s; //
update starting point
e =
i;
// update end point
}
temp_s = i; //
start finding new block
}
}
// check if last block is longest block or not
if (n - temp_s > length)
{
s = temp_s;
e = n - 1;
}
}
/*
Determine all subsequences in the array such that the sum
of each subsequence is equal to the targetSum
example: A[] = {5, 1, 4, 4, 2, 5, 3, 2, 4, 5}
if targetSum = 10
the function prints: subsequence : 5, 1, 4
subsequence : 4, 4, 2
subsequence : 2, 5, 3
subsequence : 5, 3, 2
if targetSum = 13
the function prints: no subsequence found
*/
void findAllSubSeq(int a[], int n, int targetSum)
{
cout << "Subsequence with sum = " <<
targetSum << endl;
int start = 0; //
starting index of subsequence
int sum =0;
// sum of sequence
bool flag = 0; // flag to
check found atleast one sequence
for (int i = 0; i < n; i++) // starting index of
array
{
sum = 0;
for (int j = i; j < n; j++) //
end index of array
{
sum +=
a[j];
if (sum ==
targetSum) // when array sum become required target sum
{
cout << "subsequence : ";
printSeq(a, i, j + 1); // print
subsequence
flag =
1;
// atlest found one sequence
}
}
}
// no sequence found
if (flag == 0) cout << "no subsequence found"
<< endl;
}
//added to test part 2 with more example
void part_2_1()
{
cout <<
"\n------------------------------------------------------\n";
cout << "Part-2 test2:\n\n";
int a[] = { 5, 1, 4, 4, 2, 5, 3, 2, 4, 5 };
int n = 10;
cout << "a[] : ";
printSeq(a, 0, n);
cout << endl;
int targetSum = 10;
findAllSubSeq(a, n, targetSum);
cout << endl;
targetSum = 13;
findAllSubSeq(a, n, targetSum);
cout << "\nTest with empty array:\n";
targetSum = 16;
findAllSubSeq(a, 0, targetSum);
}
// -------------------------------------------------- functions
given to you
void printSeq(int* a, int s, int e)
{
for (int i = s; i < e; i++)
cout << a[i] << ",
";
cout << endl;
}
void part_1()
{
cout << "Part_1:\n\n";
int a[] = { 1, 2, 3, 3, 1, 4, 4, 4, 5, 8, 6, 6, 5, 5,
5, 5, 2, 1, 7, 7 };
int n = 20;
cout << "a[] : ";
printSeq(a, 0, n);
cout << endl;
int s, e;
longestBlock(a, n, s, e);
cout << "Longest block in the array:\n";
cout << "Data value = " << (e > s ?
a[s] : 0) << ", start index = " << s;
cout << ", block length = " << e - s
<< endl << endl;
cout << "Test with empty array:\n";
longestBlock(a, 0, s, e);
cout << "Longest block in the array:\n";
cout << "Data value = " << (e > s ?
a[s] : 0) << ", start index = " << s;
cout << ", block length = " << e - s
<< endl << endl;
}
void part_2()
{
cout <<
"\n------------------------------------------------------\n";
cout << "Part-2:\n\n";
int a[] = { 5, 1, 4, -4, 2, 1, 5, 3, -2, 4, 5, -8, 7,
9, 1 };
int n = 15;
cout << "a[] : ";
printSeq(a, 0, n);
cout << endl;
int targetSum = 16;
findAllSubSeq(a, n, targetSum);
cout << endl;
targetSum = 31;
findAllSubSeq(a, n, targetSum);
cout << "\nTest with empty array:\n";
targetSum = 16;
findAllSubSeq(a, 0, targetSum);
}
int main()
{
part_1();
part_2();
part_2_1();
cout << endl;
system("pause");
return 0;
}
//=========================================================
sample output:
Explanation:
longestBlock : check if two continues index contain same number. if not than calculate largest block length by using temp_s and current index.
findAllSubSeq : choose one starting pointing of subsequence and iterate over remaining array to find target sum.
Comment: I have added one more test case for testing part 2( part_2_1) and part which I have added are in BOLD TEXT.
Part-1: find the longest block (subsequence of elements with same value) in an array. Part-2: find...
read in numbers into array , print out, sort - my program reads in and prints out but crashes before the sort - crashes after it prints out the scores - *important I have to use pointers!!!! c++ #include <iostream> using namespace std; void sortarray(int *tarray, int ); void displayarray(int *[], int); void averageshowarray(int *[], int); int main() { int Size; int count; cout << "enter the size: " << endl; cin >> Size; int...
Consider a non-empty int array ints. A contiguous subarray ints[ start .. start + len -1 ] (with starting index start and length len) is called a flat if all elements of that subarray are equal. Furthermore, such a subarray is called a plateau if it is flat and each of the elements ints[start -1] and ints[start + len] that immediately proceed/succeed the subarray are either nonexistent (i.e., out of array’s index range) or are strictly smaller than the elements...
please help with the operator overloading lab (intArray) in c++ will provide what it is being required and the code that was given from the book. the code that was provided is below ------------------------------------------------------------------------------------------------------------------------- // iadrv.h #ifndef _IADRV_H #define _IADRV_H #include "intarray.h" int main(); void test1(); void test2(); void test3(); void test4(); void test5(); void test6(); void test7(); void test8(); void test9(); void test10(); void test11(); void test12(); void test13(); void test14(); void test15(); void test16(); void test17(); void test18();...
I need help with this code: #include <iostream> #include <cstdlib> #include <string> using namespace std; void dump(int ar[], int size) { cout << "\nDUMP [ "; for (int i=0; i<=size; i++) { cout << ar[i] << " "; } cout << "]\n\n"; } void quicksort(int ar[], int start, int end) { cout << "TOP OF SORT ===========================" << endl; dump(ar, start, end); int pivot = ar[end]; int left = start; int right = end - 1; int tmp; cout <<...
Convert the TreeArray C++ source code(posted below) into a BinaryTree, using this TreeNode definition: class TreeNode<T> T data TreeNode<T> left TreeNode<T> right Since this TreeNode is a generic Template, use any data file we've used this quarter to store the data in the BinaryTree. To do this will likely require writing a compare function or operator. Hint: Think LEFT if the index is calculate (2n+1) and RIGHT if index is (2n+2). Source code: #include<iostream> using namespace std;...
How can i make a counter for the number of exchanges made in the linear algorithm?? The binary counter works but the linear doesn't. Here's my code. #include <iostream> using namespace std; void selectionSort(int[], int, int& ); void showSelection(int[], int); void sortArray(int[], int, int&); void showArray(const int[], int); int main() { int values[25] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24...
C++ problem where should I do overflow part? in this code do not write a new code for me please /////////////////// // this program read two number from the user // and display the sum of the number #include <iostream> #include <string> using namespace std; const int MAX_DIGITS = 10; //10 digits void input_number(char num[MAX_DIGITS]); void output_number(char num[MAX_DIGITS]); void add(char num1[MAX_DIGITS], char num2[MAX_DIGITS], char result[MAX_DIGITS], int &base); int main() { // declare the array = {'0'} char num1[MAX_DIGITS] ={'0'}; char...
C++ Programming - Design Process I need to create a flow chart based on the program I have created. I am very inexperienced with creating this design and your help will be much appreciated. My program takes a string of random letters and puts them them order. Our teacher gave us specific functions to use. Here is the code: //list of all the header files #include <iomanip> #include <iostream> #include <algorithm> #include <string> using namespace std; //Here are the Function...
I have to type and explain in class each code in every detail filled with // commentary. Explains how does work in every codes. 1) What does the below print #include <iostream> using namespace std ; int main() { int var1 = 20 ; int var2 = 30 ; int* ptr1 ; int* ptr2 ; int* temp ; ptr1 = &var1 ; ptr2 = &var2 ; cout << *ptr1 << endl ;...
I need help fixing my code: In C++ *************** 1) I want to sum the digits of an n*n matrix 2) find the average I have completed the rest ****Do not use C++ standard library. You must use pointers and pointer arithmetic to represent the matrix and to navigate through it. MY CODE: (I have indicated at which point I need help) #include <iostream> using namespace std; void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp;...