Advanced Search

《The 3n + 1 problem》

/ Published in: C++
Save to your folder(s)

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <ctime>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. int three_n_plus_one(unsigned int n)
  10. {
  11. 	int times(1);
  12. 	//cout << n << " ";
  13. 	if(n == 1)
  14. 		return times;
  15.  
  16. 	if((n%2) == 1)
  17. 		times += three_n_plus_one( ((n*3)+1) );
  18. 	else
  19. 		times += three_n_plus_one( (n/2) );
  20.  
  21. 	return times;
  22. }
  23.  
  24. int find_max_times(unsigned int begin, unsigned int end)
  25. {
  26. 	int max(0);
  27. 	int temp_result(0);
  28. 	int temp_begin_end(0);
  29. 	if(begin > end)
  30. 	{
  31. 		temp_begin_end = end;
  32. 		end            = begin;
  33. 		begin          = temp_begin_end;
  34. 	}
  35. 	for(unsigned int i=begin; i<=end; ++i)
  36. 	{
  37. 		temp_result = three_n_plus_one(i);
  38. 		if(temp_result > max)
  39. 			max = temp_result;
  40. 	}
  41. 	return max;
  42. }
  43.  
  44. int main(int argv, char* argc[])
  45. {
  46. 	clock_t start = clock();
  47. 	string out_file_name(argc[1]);
  48. 	out_file_name.replace(5, 2, "out");
  49.  
  50. 	ifstream fin(argc[1], ios::in);
  51. 	ofstream fout(out_file_name, ios::out);
  52.  
  53. 	unsigned int begin(0), end(0);
  54.  
  55. 	while(!fin.eof())
  56. 	{
  57. 		fin >> begin;
  58. 		fin >> end;
  59. 		if(!begin || !end)
  60. 		{
  61. 			cout << "read invalid value" << endl;
  62. 			exit(1);
  63. 		}
  64.  
  65. 		fout << begin << " " << end << " " << find_max_times(begin, end) << " ";
  66. 	}
  67.  
  68. 	fin.close();
  69. 	fout.close();
  70.  
  71. 	cout << "cost :" << clock()-start << "ms" << endl;
  72. 	return 0;
  73. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.