Article From:https://www.cnblogs.com/sunrisepeak/p/9652968.html

Main contents:

  • An example is given to illustrate the process of algorithm design and the techniques and ideas used in design and analysis (c / C + +)

 

Example: finding the greatest common divisor of two positive integers.

  1. Mathematical model: an integer of a, B & gt; 0, finding that c, C can divide a, B and a / C and B / C are mutually prime (no common number).
  2. Problem analysis:
    • Decomposition factor method: the greatest divisor of a and B.
    • Decomposition quality factor method: multiplication of a and B divisibility
    • Short division: all common divisors are multiplied.
    • Rotary phase division:
  3. Algorithm description:

Decomposition factor method:

    1. Decomposition factor method: ☛source code
      int a, b, flag;
      input(a,b)
      if(a>b)
          a,bExchange valuefor(Decreasing from a cycle to searching the greatest common factor.if(Can divide a at the same time, B is the common factor.Jump out of circulation;Print (flag);
    2. Algorithm description:
      • Define flag for marking common factor (or a loop), easy to understand and define flag variables.
      • Compare the size of a and B, ensure that a is the smallest number, and facilitate the following loop (s-code provides one.Two variable exchange valueMethods)
      • The greatest common factor is required.Reverse searchReduce search times (from big to small).
      • If you want to type A, b value (that is, multiple sets of data) and a or B equal to 0, end the input.while(cin >> a >> b && a && b)Input mode: any conditional condition in while is false stop cycle (0 is false, non 0 is true).
    3. Algorithmic analysis: It is best to cycle once, the worst cycle a, then T (n) = 1/n (1 +…. + n) = (1/n) * n * (n + 1) / 2 = 1/2 * n + 1 / 2 time complexity is O (n).

 Decomposition mass factor method:

    1. Decomposition mass factor method:
      #include<iostream>
      #include<cmath> 
      using namespace std;
      bool pNumber(int n)            //Quality of judgment
      {
          for(int i = 2; i <= sqrt(n); i++)
              if(n%i == 0)
                  return false;
          return true;
      }
      void exchange(int &x, int &y)    //Swap the value of X, y
      {
          int temp = x;
          x = y;
          y = temp;
      }
      int main()
      {
          int a, b;    
          while(cin >> a >> b && a != 0 && b != 0){
              int flag = 1;
              if(a > b)
                  exchange(a, b);
              for(int i = 2; i <= a; i++)
                  if(a%i == 0 && b%i == 0 && pNumber(i)){
                      flag *= i;
          //        cout << "this is debug!----" <<i << endl;    
                  }
              cout << flag << endl;
          }
          return 0;
      }
    2. Algorithm description:
      • The modularization idea is used to modularize some general functions of main function (judging prime number and exchanging variable value), and subdivide them step by step from top to bottom.
      • Reduce the number of cycles by virtue of the advantages of short circuit and (& &).:pNumber()The number of cycles caused by different functions is different.if(a%i == 0 && b%i == 0 && pNumber(i)<   if(pNumber(i) &&a%i == 0 && b%i == 0 )
    3. Algorithm analysis: suppose that I can divide a at the same time, and the probability of B is p.:O(n) = n^(5/2).

 

Short division:

    1. Short division:
      #include<iostream>
      #include<cmath> 
      using namespace std;
      int main()
      {
              int a, b, t, i;
              cin >> a >> b;
              t = 1;
              for(i = 2; i <= a && i <= b; i++)
                  while(a%i == 0 && b%i == 0)
                  {
                      t = t*i;
                      a = a/i;
                      b = b/i;
                  }
              cout << t << endl;
              return 0;
      }

       

 

Rotary phase division:

    1. Rotary phase division:
      #include<iostream>
      #include<cmath> 
      using namespace std;
      int main()
      {
              int a, b, c;
              cin >> a >> b;
              if(b == 0 || a == 0)
              {
                  cout << "data error!" << endl;
                  return 0;
              }
              else
              {
                  c = a % b;
                  while(c != 0)
                  {
                      a = b;
                      b = c;
                      c = a %b;
                  }
              }
              cout << b;
              return 0;
      }

       

 ☛source code——For reference only

Link of this Article: Algorithm learning (1)

Leave a Reply

Your email address will not be published. Required fields are marked *