fork download
copy 
  1. #include <cmath>
  2. #include <stack>
  3. #include <tuple>
  4.  
  5. int M1(int H, int T){
  6. 	if (H == 0) return T;
  7. 	if (H + 1 >= T) return pow(2, T) - 1;
  8. 	return M1(H - 1, T - 1) + M1(H, T - 1) + 1;
  9. }
  10.  
  11. 	struct Data
  12. 	{
  13. 	public:
  14. 		Data(int newH, int newT)
  15. 			: T(newT), H(newH)
  16. 		{
  17.  
  18. 		}
  19.  
  20. 		int H;
  21. 		int T;
  22. 	};
  23.  
  24. 	int M(int H, int T)
  25. 	{
  26. 		std::stack<Data> st;
  27.  
  28. 		st.push(Data(H, T));
  29.  
  30. 		int sum = 0;
  31.  
  32. 		while (st.size() > 0)
  33. 		{
  34. 			Data top = st.top();
  35. 			st.pop();
  36.  
  37. 			if (top.T + 1 >= top.T)
  38. 				sum += pow(2, top.T) - 1;
  39. 			else
  40. 			{
  41. 				st.push(Data(top.H - 1, top.T - 1));
  42. 				st.push(Data(top.H, top.T - 1));
  43. 				sum += 1;
  44. 			}
  45. 		}
  46.  
  47. 		return sum;
  48. 	}
  49.  
  50. int main(int argc, char * argv[])
  51. {
  52. 	printf("Original: %d Iterative: %d\n", M1(5, 2), M(5, 2));
  53. 	getchar();
  54. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original: 3 Iterative: 3
https://ideone.com/k5BED3
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!