Problem4.cpp (998B)
1 // Problem 1: Bucket Sort 2 // Description: Sort a vector using a modified version of bucket sort. 3 // Course: IT405G - Datastructures and Algorithms 4 // Authors: William Lindholm, Lili Tran, Victor Adamson 5 // Date: 29-11-2023 6 // 7 8 #include <iostream> 9 #include <cmath> 10 #include <unordered_map> 11 12 using namespace std; 13 14 // A map to store already calculated results 15 unordered_map<int, int> storage; 16 17 int T(int n) { 18 // Check if the result for n is already computed 19 if (storage.find(n) != storage.end()) { 20 return storage[n]; 21 } 22 23 // Base case 24 if (n == 1) { 25 return 1; 26 } 27 28 // Calculate T(n-1) and T(ceil(n/2)) if not already done 29 int result = T(n - 1) + T(std::ceil(n / 2.0)) + n; 30 31 // Store the result in the map before returning 32 storage[n] = result; 33 34 return result; 35 } 36 37 int main() { 38 int n; 39 cout << "Enter the value of n: "; 40 cin >> n; 41 42 // Compute and print the result 43 cout << "T(" << n << ") = " << T(n) << std::endl; 44 45 return 0; 46 }