CPP   73

get brief step limit

Guest on 30th June 2022 02:52:51 AM

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib>
  4. #include <climits>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8.  
  9.  
  10.  
  11.  
  12. int  acute_count[10000];
  13.  
  14.  
  15.  
  16.  
  17. int  get_brief_step_limit(int number);
  18. void find_addition_chain_ids(vector<int> &, int);
  19. void find_addition_chain(vector<int> &, vector<int> &, int, int);
  20.  
  21.  
  22.  
  23.  
  24.  
  25. int
  26. main()
  27. {
  28.     int num = 0;
  29.  
  30.     while (cin >> num)
  31.     {
  32.         if (num == 0)
  33.         {
  34.             break;
  35.         }
  36.  
  37.  
  38.         vector<int> result;
  39.         find_addition_chain_ids(result, num);
  40.  
  41.         for (int i = 0; i < result.size(); ++i)
  42.         {
  43.             if (i > 0)
  44.             {
  45.                 cout << ' ';
  46.             }
  47.  
  48.             cout << result[i];
  49.         }
  50.  
  51.         cout << endl;
  52.     }
  53.  
  54.     return EXIT_SUCCESS;
  55. }
  56.  
  57.  
  58.  
  59.  
  60.  
  61. int
  62. get_brief_step_limit(int num)
  63. {
  64.     if (num == 1)
  65.     {
  66.         return 1;
  67.     }
  68.     else
  69.     {
  70.         if (num & 0x1)
  71.         {
  72.             return get_brief_step_limit(num >> 1) + 2;
  73.         }
  74.         else
  75.         {
  76.             return get_brief_step_limit(num >> 1) + 1;
  77.         }
  78.     }
  79. }
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86. void
  87. find_addition_chain_ids(vector<int> &result, int target)
  88. {
  89.     int limit = get_brief_step_limit(target);
  90.  
  91.     for (int i = 1; i <= limit; ++i)
  92.     {
  93.         vector<int> S;
  94.         find_addition_chain(result, S, target, i);
  95.  
  96.         if (result.size() != 0)
  97.         {
  98.             return;
  99.         }
  100.     }
  101. }
  102.  
  103.  
  104.  
  105. void
  106. find_addition_chain(vector<int> &result,
  107.                     vector<int> &S,
  108.                     int target,
  109.                     int limit)
  110. {
  111.     if (S.size() >= limit)
  112.     {
  113.         return;
  114.     }
  115.  
  116.     if (S.size() == 0)
  117.     {
  118.         S.push_back(1);
  119.  
  120.         if (target == 1)
  121.         {
  122.             result = S;
  123.             return;
  124.         }
  125.         else
  126.         {
  127.             find_addition_chain(result, S, target, limit);
  128.         }
  129.     }
  130.     else
  131.     {
  132.         for (int i = 0; i < S.size(); ++i)
  133.         {
  134.             for (int j = 0; j < S.size(); ++j)
  135.             {
  136.                 int next_num = S[i] + S[j];
  137.  
  138.                 if (next_num == target)
  139.                 {
  140.                     result = S;
  141.                     result.push_back(next_num);
  142.                     return;
  143.                 }
  144.                 else if (next_num > target)
  145.                 {
  146.                     continue;
  147.                 }
  148.                 else
  149.                 {
  150.                     S.push_back(next_num);
  151.  
  152.                     int promissing_max =
  153.                         ((INT_MAX >> (limit - S.size())) > next_num)?
  154.                             (next_num << (limit - S.size())):
  155.                             (INT_MAX);
  156.  
  157.                     if (promissing_max >= target)
  158.                     {
  159.                         find_addition_chain(result, S, target, limit);
  160.                     }
  161.  
  162.                     S.pop_back();
  163.                 }
  164.             }
  165.         }
  166.     }
  167. }
  168.  
  169.  
  170.  
  171.  
  172.  
  173. // -- eof --------

Raw Paste


Login or Register to edit or fork this paste. It's free.