Question

In: Computer Science

Need a description what does this program does and how does it work. #include <iostream> using...

Need a description what does this program does and how does it work.

#include <iostream>

using namespace std;

double function(int num, double* memorize);

int main()

{

int num=5;

char cont;

double* memorize = new double[num + 1];

do {

cout << "Enter n ";

cin >> num;

memorize[1] = 1;

memorize[2] = 1;

memorize[3] = 1;

memorize[4] = 3;

memorize[5] = 5;

for (int i = 6; i <= num; i++)

memorize[i] = -1; // -1 means that the value is not in the array

cout << num << "th number: " << function(num, memorize) << endl;

cout << "Continue?";

cin >> cont;

cout << endl;

} while (cont == 'y' || cont == 'Y');

delete[] memorize;

return 0;

}

double function(int num, double* memorize)

{

// checks if value was calculated before

if (memorize[num] == -1)

{

// recursively calculates said value and stores it in

memorize[num] = function(num - 1, memorize) + (3 * function(num - 5, memorize));

}

return memorize[num];

}

Expert Solution

This question basically solves a equation which is below:

T(N) = T(N-1) + 3 * T(N-5)
with base conditions as:
T(N) = 1 for 1 <= N <= 3
T(N) = 3 for N=4
T(N) = 5 for N=5
================================================

This code basically sees that to solve the above problem using recursion, we would get overlapping subproblems, which will be unnecessary work..

So like if we need to solve T(10), then:
T(10) = T(9) + 3 * T(5)
T(9) will be broken as T(8) + 3*T(4)..
T(8) will be broken as T(7) + 3*T(3)..
T(7) will be broken as T(6) + 3*T(2)..
T(6) will be broken as T(5) + 3*T(1)..

So we again, got to solve T(5), which we already did in the above bolded part.. Hence it is repeated subproblem.. So To avoid this problem, we just memorize the values which we solve.. using the memorize double array.. and when need arises, we check whether we already solved the problem beforehand.

Let me know if any doubt.. please upvote if it helps.

venereology answered 1 month ago

Writing a squareroot program in C++ using only: #include <iostream> using namespace std; The program must...

Writing a squareroot program in C++ using only: #include <iostream> using namespace std; The program must be very basic. Please don't use math sqrt. Assume that the user does not input anything less than 0. For example: the integer square root of 16 is 4 because 4 squared is 16. The integer square root of 18 is 5 because 4 squared is 16 and 5 squared is 25, so 18 is bigger than 16 but less than 25.

How do i make this program accept strings? #include <iostream> #include <algorithm> using namespace std; int...

How do i make this program accept strings? #include <iostream> #include <algorithm> using namespace std; int binaryToOctal(char digits[], int a) { int number; if (digits[0] == '0') { if (digits[1] == '1') if (digits[2] == '0') return 2; //found "010" else return 3; //found "011" else if (digits[1] == '0') if (digits[2] == '1') return 1; // found "001" else return 0; //found "000" } else { if (digits[0] == '1') if (digits[1] == '1') if (digits[2] == '0') return...

Modify the program to double each number in the vector. #include <iostream> #include <vector> using namespace...

Modify the program to double each number in the vector. #include <iostream> #include <vector> using namespace std; int main() { const int N=8; vector<int> nums(N); // User numbers int i=0; // Loop index cout << "\nEnter " << N << " numbers...\n"; for (i = 0; i < N; ++i) { cout << i+1 << ": "; cin >> nums.at(i); } // Convert negatives to 0 for (i = 0; i < N; ++i) { if (nums.at(i) < 0) {...

Read Ch. 3. Using the C++ editor, type the following program: #include <iostream> #include <string> using...

Read Ch. 3. Using the C++ editor, type the following program: #include <iostream> #include <string> using namespace std; int main () { //declarations string name; //input cout <<"Enter your first name" << endl; cin >> name; //output cout << "Hello " << name << "! " << endl; return 0; } Compile and run. What does the cin statement do? What does the cout statement do? Is name a variable or a constant? What...

Question 1 Given the program below, what are the errors. #include <iostream> using namespace std; int...

Question 1 Given the program below, what are the errors. #include <iostream> using namespace std; int main() { int ind_square(int &); int x, *p; x=15; p = &x; ind_square(*p); } int ind_square(int &p) { *p = *p **p; } Question 1 options: C. No return for non-void function A. Indirection for the variables in ind_square requires pointer operand A and B B. Invalided use of address (&) symbol as a parameter for ind_squared A and C Question 2 Which statement...

What is the output of the following program? #include <iostream> using namespace std; void showDouble(int); //Function...

What is the output of the following program? #include <iostream> using namespace std; void showDouble(int); //Function prototype int main() { int num; for (num = 0; num < 10; num++) showDouble(num); return 0; } // Definition of function showDouble void showDouble(int value) { cout << value << ‘\t’ << (value * 2) << endl; } Please do the following Program and hand in the code and sample runs. Write a program using the following function prototypes: double getLength(); double getWidth();...

A C++ question: I want to indent the code of this C++ program: #include<iostream> #include<cstring> using...

A C++ question: I want to indent the code of this C++ program: #include<iostream> #include<cstring> using namespace std; int lastIndexOf(char *s, char target) { int n=strlen(s); for(int i=n-1;i>=0;i--) { if(s[i]==target) { return i; } } return -1; } void reverse(char *s) { int n=strlen(s); int i=0,j=n-1; while(i<=j) { char temp=s[i]; s[i]=s[j]; s[j]=temp; i++; j--; } return; } int replace(char *s, char target, char replacementChar) { int len=strlen(s); int total=0; for(int i=0;i<len;i++) { if(s[i]==target) { s[i]=replacementChar; total+=1; } } return total;...

Complete the following program #include<iostream> #include<iomanip> #include<fstream> using namespace std; int main() { // I -...

Complete the following program #include<iostream> #include<iomanip> #include<fstream> using namespace std; int main() { // I - Declaring a five by five array /* II - Read data from data.txt and use them to create the matrix in the previous step*/ // III - Count and print the number of even integers in the matrix. /* IV - Calculate and print the sum of all integers in the columns with an even index value. Please note the column index begins...

Write a C++ program that prints a calendar for a given year. ONLY USING "#include<iostream>" and...

Write a C++ program that prints a calendar for a given year. ONLY USING "#include<iostream>" and "#include<cmath>" The program prompts the user for two inputs: 1) The year for which you are generating the calendar. 2) The day of the week that January first is on, you will use the following notation to set the day of the week: 0 Sunday 1 Monday 2 Tuesday 3 Wednesday 4 Thursday 5 Friday 6 Saturday Your program should...

What would the following program output? #include <iostream> using namespace std; int main() { char alpha...

What would the following program output? #include <iostream> using namespace std; int main() { char alpha = 'A'; for(int i = 0; i < 13; i++){ for(int j = 0; j < 2; j++){ cout << alpha; alpha++; } } cout << endl; return 0; }