fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int ar[100010];
  5.  
  6. int max1_c=0,max2_c=0,min1_c=0,min2_c=0;
  7.  
  8. /*clock_t start1;
  9. clock_t start2;
  10. clock_t start3;
  11. clock_t start4;
  12. clock_t end1;
  13. clock_t end2;
  14. clock_t end3;
  15. clock_t end4;*/
  16. int max_for_one_base_case ( int low, int high)
  17. {
  18.     //start1=clock();
  19.  
  20.     if (low == high)
  21.         {
  22.              max1_c++;
  23.             return ar[low];
  24.  
  25.         }
  26.  
  27.     else
  28.     {
  29.         int mid;
  30.  
  31.         if (high >= low)
  32.             mid = ceil((low + high) / 2);
  33.         max1_c++;
  34.  
  35.         int p, q;
  36.  
  37.         p = max_for_one_base_case( low, mid);
  38.         q = max_for_one_base_case( mid+1, high);
  39.  
  40.         return max(p, q);
  41.         //cout<<"Time for max 1 :"<<(double)(end1-start1)/CLOCKS_PER_SEC<<endl;
  42.  
  43.     }
  44.   //end1 =clock();
  45.     //cout<<"Time for max 1 :"<<(double)(end1-start1)/CLOCKS_PER_SEC <<endl;
  46.  
  47. }
  48.  
  49. int max_for_two_base_case ( int low, int high)
  50. {
  51.  //start2=clock();
  52.     if (low == high)
  53.        {
  54.            max2_c++;
  55.          return ar[low];
  56.  
  57.        }
  58.     else if (high == low + 1)
  59.         {
  60.              max2_c++;
  61.             return max(ar[low], ar[high]);
  62.  
  63.         }
  64.     else
  65.     {
  66.         int mid;
  67.  
  68.         if (high >= low)
  69.             mid = ceil((low + high) / 2);
  70.  
  71.         max2_c++;
  72.  
  73.         int p, q;
  74.  
  75.         p = max_for_two_base_case( low, mid);
  76.         q = max_for_two_base_case( mid+1, high);
  77.  
  78.         return max(p, q);
  79.  
  80.     }
  81.  //end2 =clock();
  82. }
  83.  
  84.  
  85. int min_for_one_base_case ( int low, int high)
  86. {
  87.  //start3=clock();
  88.     if (low == high)
  89.         {
  90.              min1_c++;
  91.             return ar[low];
  92.  
  93.         }
  94.     else
  95.     {
  96.         int mid;
  97.  
  98.         if (high >= low)
  99.             mid = ceil((low + high) / 2);
  100.         min1_c++;
  101.  
  102.         int p, q;
  103.  
  104.         p = min_for_one_base_case( low, mid);
  105.         q = min_for_one_base_case( mid+1, high);
  106.  
  107.         return min(p, q);
  108.  
  109.     }
  110.      //end3 =clock();
  111. }
  112.  
  113. int min_for_two_base_case ( int low, int high)
  114. {
  115.  
  116.  //start4=clock();
  117.     if (low == high)
  118.         {
  119.              min2_c++;
  120.             return ar[low];
  121.  
  122.         }
  123.     else if (high == low + 1)
  124.         {
  125.             min2_c++;
  126.             return min(ar[low], ar[high]);
  127.  
  128.         }
  129.     else
  130.     {
  131.         int mid;
  132.  
  133.         if (high >= low)
  134.             mid = ceil((low + high) / 2);
  135.  
  136.         min2_c++;
  137.  
  138.         int p, q;
  139.  
  140.         p = min_for_two_base_case( low, mid);
  141.         q = min_for_two_base_case( mid+1, high);
  142.  
  143.         return min(p, q);
  144.  
  145.     }
  146.  
  147.   //end4 =clock();
  148. }
  149.  
  150. int main()
  151. {
  152.     ofstream out;
  153.     ifstream in;
  154.     out.open("dc.txt");
  155.     //out<<  "tamima";
  156.     int a;
  157.     for(int i=1; i<=100000; i++)
  158.     {
  159.         a=rand()%10;
  160.         out<<a<<endl;
  161.  
  162.     }
  163.  
  164.     int k;
  165.     cout<<"Enter the value of k :";
  166.     cin>>k;
  167.     in.open("dc.txt");
  168.     int d;
  169.      for(int i=0; i<k; i++)
  170.     {
  171.         in>>d;
  172.         ar[i]=d;
  173.  
  174.     }
  175.     clock_t start1=clock();
  176.     int max1=max_for_one_base_case(0,k-1);
  177.     clock_t end1=clock();
  178.  
  179.      clock_t start2=clock();
  180.     int max2=max_for_two_base_case(0,k-1);
  181.     clock_t end2=clock();
  182.  
  183.      clock_t start3=clock();
  184.     int min1=min_for_one_base_case(0,k-1);
  185.     clock_t end3=clock();
  186.  
  187.      clock_t start4=clock();
  188.     int min2=min_for_two_base_case(0,k-1);
  189.     clock_t end4=clock();
  190.  
  191.    cout<<"max1 : "<<max1<<"  max2 : "<<max2<<"  min1: "<<min1<<"  min2: "<<min2<<endl;
  192.     cout<<"max1 counter : "<<max1_c<<"\nmax2 counter : "<<max2_c<<"\nmin1 counter :  "<<min1_c<<"\nmin2 counter :  "<<min2_c<<endl;
  193.  
  194.     //cout<<"Time for max 1 :"<<fabs((double)(end-start)/CLOCKS_PER_SEC) <<endl;
  195.     cout<<"Time for max 1 :"<<fabs((double)(end1-start1)/CLOCKS_PER_SEC) <<endl;
  196.     cout<<"Time for max 2 :"<<fabs((double)(end2-start2)/CLOCKS_PER_SEC) <<endl;
  197.     cout<<"Time for min 1 :"<<fabs((double)(end3-start3)/CLOCKS_PER_SEC) <<endl;
  198.     cout<<"Time for min 2 :"<<fabs((double)(end4-start4)/CLOCKS_PER_SEC) <<endl;
  199.    // cout<<"Time for max 1 :"<<(double)(end1-start1)/CLOCKS_PER_SEC <<endl;
  200.  
  201.  
  202.  
  203. }
  204.  
Success #stdin #stdout 0s 4284KB
comments (?)
stdin
copy 
5
64
32
97
2
12345
stdout
copy 
Enter the value of k :max1 : 32764  max2 : 32764  min1: 32764  min2: 32764
max1 counter : 9
max2 counter : 5
min1 counter :  9
min2 counter :  5
Time for max 1 :1e-06
Time for max 2 :0
Time for min 1 :0
Time for min 2 :0
https://ideone.com/1lEEqa
language:
C++ (gcc 8.3)
created:
4 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!