fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. struct OperationCounter
  7. {
  8.     int eqTest, ltTest, gtTest;
  9.     int mul, div, mod, add, inc;
  10.     int assign, deref;
  11.     int memAlloc, memFree;
  12.  
  13.     OperationCounter() { reset(); }
  14.  
  15.     void reset() { memset(this, 0, sizeof(*this)); }
  16.  
  17.     void print()
  18.     {
  19.         cout << "=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=" << endl;
  20.         cout << "    equality tests : " << eqTest   << endl;
  21.         cout << "   less than tests : " << ltTest   << endl;
  22.         cout << "greater than tests : " << gtTest   << endl;
  23.         cout << "   multiplications : " << mul      << endl;
  24.         cout << "         divisions : " << div      << endl;
  25.         cout << "        modulo ops : " << mod      << endl;
  26.         cout << "         additions : " << add      << endl;
  27.         cout << "        increments : " << inc      << endl;
  28.         cout << "       assignments : " << assign   << endl;
  29.         cout << "      dereferences : " << deref    << endl;
  30.         cout << "       allocations : " << memAlloc << endl;
  31.         cout << "     deallocations : " << memFree  << endl;
  32.         cout << "=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=" << endl;
  33.     }
  34.  
  35. } opc1, opc2;
  36.  
  37. int gcd(int a, int b)
  38. {
  39.     opc1.assign += 2;
  40.     opc1.eqTest++;
  41.  
  42.     if (b == 0)
  43.         return a;
  44.     else
  45.     {
  46.         opc1.mod++;
  47.  
  48.         return gcd(b, a % b);
  49.     }
  50. }
  51.  
  52. int lcm(int a, int b)
  53. {
  54.     opc1.assign += 2;
  55.  
  56.     opc1.mul++;
  57.     opc1.div++;
  58.  
  59.     return a * b / gcd(a, b);
  60. }
  61.  
  62. int lcmOfList1(const int * list, int size)
  63. {
  64.     opc1.assign ++;
  65.     opc1.deref ++;
  66.  
  67.     int ret = list[0];
  68.  
  69.     opc1.assign ++;
  70.  
  71.     for (int i = 1; i < size; ++ i)
  72.     {
  73.         opc1.ltTest ++;
  74.         opc1.inc ++;
  75.  
  76.         opc1.assign ++;
  77.         opc1.deref ++;
  78.  
  79.         ret = lcm(ret, list[i]);
  80.     }
  81.  
  82.     return ret;
  83. }
  84.  
  85. int lcmOfList2(const int * list, int size)
  86. {
  87.     opc2.memAlloc ++;
  88.  
  89.     int * newList = new int[size];
  90.  
  91.     opc2.assign ++;
  92.  
  93.     for (int i = 0; i < size; ++ i)
  94.     {
  95.         opc2.ltTest ++;
  96.         opc2.inc ++;
  97.  
  98.         opc2.deref += 2;
  99.         opc2.assign ++;
  100.  
  101.         newList[i] = list[i];
  102.     }
  103.  
  104.     int min, max, imin, cur;
  105.  
  106.     while (true)
  107.     {
  108.         opc2.assign += 3;
  109.         opc2.deref ++;
  110.  
  111.         min = max = newList[0];
  112.         imin = 0;
  113.  
  114.         opc2.assign ++;
  115.  
  116.         for (int i = 1; i < size; ++ i)
  117.         {
  118.             opc2.ltTest ++;
  119.             opc2.inc ++;
  120.  
  121.             opc2.assign ++;
  122.             opc2.deref ++;
  123.  
  124.             cur = newList[i];
  125.  
  126.             opc2.gtTest ++;
  127.  
  128.             if (min > cur)
  129.             {
  130.                 opc2.assign += 2;
  131.  
  132.                 min = cur;
  133.                 imin = i;
  134.             }
  135.  
  136.             opc2.ltTest ++;
  137.  
  138.             if (max < cur)
  139.             {
  140.                 opc2.assign ++;
  141.  
  142.                 max = cur;
  143.             }
  144.         }
  145.  
  146.         opc2.eqTest ++;
  147.  
  148.         if (min == max) break;
  149.  
  150.         opc2.deref +=2 ;
  151.         opc2.add ++;
  152.         opc2.assign ++;
  153.  
  154.         newList[imin] += list[imin];
  155.     }
  156.  
  157.     opc2.deref ++;
  158.     opc2.assign ++;
  159.  
  160.     int ret = newList[0];
  161.  
  162.     opc2.memFree ++;
  163.  
  164.     delete[] newList;
  165.  
  166.     return ret;
  167. }
  168.  
  169. int main()
  170. {
  171.     enum { size = 5 };
  172.  
  173.     int nList[size] = { 2, 3, 5, 7, 11 };
  174.  
  175.     cout << "method 1 result : " << lcmOfList1(nList, size) << endl;
  176.     cout << "method 1 stats  : " << endl;
  177.     opc1.print();
  178.  
  179.     cout << endl;
  180.  
  181.     cout << "method 2 result : " << lcmOfList2(nList, size) << endl;
  182.     cout << "method 2 stats  : " << endl;
  183.     opc2.print();
  184. }
Success #stdin #stdout 0.02s 2816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
method 1 result : 2310
method 1 stats  : 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
    equality tests : 14
   less than tests : 4
greater than tests : 0
   multiplications : 4
         divisions : 4
        modulo ops : 10
         additions : 0
        increments : 4
       assignments : 42
      dereferences : 5
       allocations : 0
     deallocations : 0
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

method 2 result : 2310
method 2 stats  : 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
    equality tests : 2923
   less than tests : 23389
greater than tests : 11692
   multiplications : 0
         divisions : 0
        modulo ops : 0
         additions : 2922
        increments : 11697
       assignments : 35882
      dereferences : 20470
       allocations : 1
     deallocations : 1
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
https://ideone.com/fcBoU
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

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!