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.。

- 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).
- 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:
**☜**

- Algorithm description:

**Decomposition factor method:**

- 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);

- 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).

- 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:**

- 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; }

- 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 )**

- 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:**

- 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; }

- Short division:

**Rotary phase division:**

- 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; }

- Rotary phase division:

* ☛source code——For reference only*

Link of this Article: Algorithm learning (1)