The goal of this lab is to develop a C++ program to simulate a virus spread model using recursion and iteration. The simulation will take the input value of the number of days and calculate the total number of infected individuals based on predefined recurrence relations. Students will learn how to apply both recursive problem-solving and iterative approaches to model real-world scenarios, analyze growth patterns, and compare the efficiency of recursion and iteration in computational modeling.
A virus spreads in a community based on a defined pattern. The number of newly infected individuals each day follows a predictable recurrence relation. The total number of infected individuals can be determined based on the number of days:
Recurrence Relation for new infected individuals on day \(n\):
\[ I(n) = \begin{cases} 1, & \text{if } n = 1 \\ 2, & \text{if } n = 2 \\ I(n-1) + 2\times I(n-2), & \text{if } n \geq 3 \end{cases} \]
Recurrence Relation for total infected Individuals on day \(n\):
\[ T(n) = \begin{cases} 1, & \text{if } n = 1 \\ 3, & \text{if } n = 2 \\ T(n-1) + I(n), & \text{if } n \geq 3 \end{cases} \]
The recursive approach follows the defined recurrence relation by calling the function recursively for smaller values until reaching the base cases. This method directly translates the recurrence relation into a program but may lead to inefficiency due to redundant computations.
// Recursive function to compute new infections on day n
Function newInfectionsRecursive(n):
If n == 1:
Return 1 // Base case: Day 1 has 1 new infection
Else if n == 2:
Return 2 // Base case: Day 2 has 2 new infections
Else:
Return newInfectionsRecursive(n - 1) + 2 * newInfectionsRecursive(n - 2)
// Apply recurrence relation for new infections
// Recursive function to compute total infected individuals up to day n
Function totalInfectedRecursive(n):
If n == 1:
Return 1 // Base case: Total infected on Day 1 is 1
Else if n == 2:
Return 3 // Base case: Total infected on Day 2 is 1 + 2 = 3
Else:
Return totalInfectedRecursive(n - 1) + newInfectionsRecursive(n)
//Accumulate total infections using the new infections from the current day and the total from the previous day
Instead of recursion, an iterative approach will reduce memory overhead and improve performance. This method iterates over values from 1 to \( n \), keeping track of previous results to avoid redundant calculations.
// Iterative function to compute total infected individuals up to day n
Function totalInfectedIterative(n):
If n == 1:
Return 1 // Base case: Total infected on Day 1 is 1
Else if n == 2:
Return 3 // Base case: Total infected on Day 2 is 1 + 2 = 3
// Initialize values for iteration
prev1 = 1 // I(1)
prev2 = 2 // I(2)
total = 3 // T(2) = 3
currentNewInfections = 0
// Loop to compute total infected individuals up to day n
For i from 3 to n:
currentNewInfections = prev2 + 2 * prev1 // Apply recurrence relation for new infections
total = total + currentNewInfections // Accumulate total infections
prev1 = prev2 // Update previous values
prev2 = currentNewInfections
Return total // Return the total infected individuals up to day n
Virus Spread Simulation
-------------------------------------------------------------
Enter the number of days (n ≥ 1): 1
Recursive Approach: Total infected individuals on Day 1: 1
Iterative Approach: Total infected individuals on Day 1: 1
Do you want to simulate again? (y/n): y
Enter the number of days (n ≥ 1): 2
Recursive Approach: Total infected individuals on Day 2: 3
Iterative Approach: Total infected individuals on Day 2: 3
Do you want to simulate again? (y/n): y
Enter the number of days (n ≥ 1): 5
Recursive Approach: Total infected individuals on Day 5: 31
Iterative Approach: Total infected individuals on Day 5: 31
Do you want to simulate again? (y/n): y
Enter the number of days (n ≥ 1): 7
Recursive Approach: Total infected individuals on Day 7: 127
Iterative Approach: Total infected individuals on Day 7: 127
Do you want to simulate it again? (y/n): n
Simulation ended. Stay safe!
-------------------------------------------------------------
| n | Recursive Execution Time | Iterative Execution Time |
|---|---|---|
| 5 | Fast | Fast |
| 40 | Noticeable delay | Still fast |
| 50 | Very slow | Fast |
| 60 | Likely crashes | Runs efficiently |
| Category | Criteria | Points |
|---|---|---|
| Variable Declarations (14 points) |
Integer variables:
|
6 |
Character variable:
|
2 | |
Function prototypes are correctly declared before the main() function.
|
6 | |
| User Inputs (4 points) |
Reads inputs from standard input and stores them in the variables correctly. | 4 |
| newInfectionsRecursive Function (12 points) |
Function Implementation is accurately implemented after the main() function:
\[ I(n) = \begin{cases} 1, & \text{if } n = 1 \\ 2, & \text{if } n = 2 \\ I(n-1) + 2\times I(n-2), & \text{if } n \geq 3 \end{cases} \] |
10 |
| Function Activation: The function is called correctly in the totalInfectedRecursive function. | 2 | |
| totalInfectedRecursive Function (12 points) |
Function Implementation is accurately implemented after the main() function:
\[ T(n) = \begin{cases} 1, & \text{if } n = 1 \\ 3, & \text{if } n = 2 \\ T(n-1) + I(n), & \text{if } n \geq 3 \end{cases} \] |
10 |
| Function Activation: The function is called correctly in the main function. | 2 | |
| totalInfectedIterative Function (20 points) |
Function Implementation is accurately implemented after the main() function: ensuring that it correctly follows the iterative approach to compute the total number of infected individuals. The function must use loops to compute values iteratively instead of recursion. | 18 |
| Function Activation: The function is called correctly in the main function. | 2 | |
| Main Function Implementation (20 points) |
Prompt the user to enter input in a clear and correct format. | 5 |
| Proper formatting of program output for readability and clarity. | 5 | |
| do-while loop is implemented correctly. | 10 | |
| Code Readability & Comments (10 points) |
Maintain consistent indentation and spacing throughout the code. | 5 |
| Include comments that explain the purpose of key sections and logic. | 5 | |
| Test Cases & Output Accuracy (5 points) |
The output for different test cases is correct and consistent. | 5 |
| AI disclaimer (3 points) |
Please put an AI disclaimer at the top of your source code as comments. | 3 |
| Errors |
Your program has syntax errors, compiling errors, running errors, or infinite loops. | -50 points |
/*
Author: Your Name
Date: Month/Day/Year
Lab Purpose: Virus Spread Simulation Using Recursion and Iteration
A.I. Disclaimer: please put your A.I. disclaimer here
*/
Please submit your Lab 2 source code file: lab2.cpp in D2L!