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

• 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