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 day 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) {...

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;...

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; }

*MUST ONLY USE** #include <iostream> #include <fstream> #include <string.h> #include <stdio.h> Description The word bank system...

*****MUST ONLY USE****** #include <iostream> #include <fstream> #include <string.h> #include <stdio.h> Description The word bank system maintains all words in a text file named words.txt. Each line in the text file stores a word while all words are kept in an ascending order. You may assume that the word length is less than 20. The system should support the following three functions: Word lookup: to check whether a given word exists in the word bank. Word insertion: to insert a...

Take the following program and translate it into PEP/9 assembly language: #include <iostream> using namespace std;...

Take the following program and translate it into PEP/9 assembly language: #include <iostream> using namespace std; int theArray[] = { 5, 11, -29, 45, 9, -1}; void sumPos(int ary[], int len, int &sum) { sum = 0; for (int i = 0; i < len; i++) if (ary[i] > 0) sum = sum + ary[i]; } int main() { int total; sumPos(theArray, 6, total); for (int k=0; k < 6; k++) cout...