DSA-Assignments

commit 72a9aba8ce40730fa7d93e2944b95a939b6d235b
parent d62ad0cdb7ba40dd000c99f7144421b152f93e4f
Author: TranLili <tranlili96@gmail.com>
Date:   Thu, 30 Nov 2023 14:37:44 +0100

Implementation using dynamic programming principles.

Diffstat:
M
Problem4/Problem4.cpp
 | 
30
+++++++++++++++++++++---------

1 file changed, 21 insertions(+), 9 deletions(-)
diff --git a/Problem4/Problem4.cpp b/Problem4/Problem4.cpp
@@ -10,24 +10,36 @@
 
 using namespace std;
 
-// Temp
-// Från labbanvisningarna
-// T(n) = T(n-1)+T([n/2])+n
-// T(1) = 1
-// Recursive function to calculate T(n)
+// A map to store already calculated results
+unordered_map<int, int> storage;
+
 int T(int n) {
-    if (n == 1)
+    // Check if the result for n is already computed
+    if (storage.find(n) != storage.end()) {
+        return storage[n];
+    }
+
+    // Base case
+    if (n == 1) {
         return 1;
+    }
+
+    // Recursive case: calculate T(n-1) and T(ceil(n/2)) if not already done
+    int result = T(n - 1) + T(std::ceil(n / 2.0)) + n;
 
-    int result = T(n - 1) + T(ceil(n / 2.0)) + n;
+    // Store the result in the map before returning
+    storage[n] = result;
 
     return result;
 }
 
 int main() {
     int n;
-    cout << "Enter a value for n: ";
+    cout << "Enter the value of n: ";
     cin >> n;
-    cout << "T(" << n << ") = " << T(n) << endl;
+
+    // Compute and print the result
+    cout << "T(" << n << ") = " << T(n) << std::endl;
+
     return 0;
 }