This is the 31st day of my participation in the August Text Challenge.More challenges in August
preface
Hello! Friend!!!
Thank you very much for reading haihong’s article, if there are any mistakes in the article, please point out ~
Self-introduction ଘ(੭, ᵕ)੭
Nickname: Haihong
Tag: programmer monkey | C++ contestant | student
Introduction: because of the C language acquaintance programming, then transferred to the computer major, had the honor to win the national award, provincial award and so on, has guaranteed graduate school. Currently learning C++/Linux (really really hard ~)
Learning experience: solid foundation + more notes + more code + more thinking + learn English well!
[Animation Xiao Xiao Le] Usually study life is rather boring, inadvertently in some web pages, applications transition/loading animation developed a strong interest, want to know how to achieve the specific? Then in the free time to learn how to use CSS to achieve some simple animation effects, the article is only for their own learning notes, record learning life, strive to understand the principle of animation, a lot of “eliminate” animation!
concept
Greatest common divisor: refers to the largest least common multiple of the divisor shared by two or more integers. The common multiple of two or more integers is called their common multiple. The smallest common multiple other than 0 is called the least common multiple of these integers.
this
Note: Take the greatest common factor of two positive integers as an example
Method 1 [Enumeration method]
Ideas:
- Find smaller values in A and B
- Starting from the value, determine whether the number is divisible by both a and B
- Returns the value if divisible
- If not, decrease by 1
#include <iostream>
using namespace std;
// Find the greatest common divisor
int gcd(int a, int b)
{
int temp = a > b ? b : a;
while (temp)
{
if (a % temp == 0 && b % temp == 0)
{
break;
}
--temp;
}
return temp;
}
int main(a)
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
Copy the codeMethod two [Toss and Turn division]
Division by toss and turn uses the following property to determine the greatest common factor of two positive integers A and B:
- If r is the remainder of a ÷ b, and r is not 0, then GCD (a,b) = GCD (b,r)
Note: GCD represents the greatest common factor, and GCD (a,b) represents the greatest common factor of a and B
The idea of program design is:
- Let r be the remainder of a/b (0<=r)
- If r= 0, the algorithm ends; B.
- Swap: set A ← B, B ←r, and return to the first step.
#include <iostream>
using namespace std;
// Find the greatest common divisor
int gcd(int a, int b)
{
int r;
// When a is not divisible by B
/ / make a = b = a % b b
// repeat until a%b==0
// return b, which is the greatest common factor
while(a % b ! =0)
{
r = a % b;
a = b;
b = r;
}
return b;
}
int main(a)
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
Copy the codeSame idea, using recursion:
Core:
- If r is the remainder of a ÷ b, and r is not 0, then GCD (a,b) = GCD (b,r)
#include <iostream>
using namespace std;
// Find the greatest common divisor
int gcd(int a, int b)
{
if (a % b == 0)
{
return b;
}
else
{
return gcd(b, a % b); }}int main(a)
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
Copy the codeMethod 3 [More phase reduction method]
Procedure design steps:
- Step 1: Arbitrarily given two positive integers; See if they’re all even. If so, use 2 to reduce; If not, go to step 2.
- Step 2: Subtract the smaller number from the larger number, then compare the difference with the smaller number, and reduce the number by the larger number. Continue until the resulting subtraction and difference are equal.
- The product of the number of 2’s in the first step and the intermediate number in the second step is the greatest common divisor.
#include <iostream>
#include <math.h>
using namespace std;
// Find the greatest common divisor
int gcd(int a, int b)
{
// Check whether both numbers are even
// Divide both by 2
// Until one of the numbers is odd
int count = 0;// Count the number of 2
while (a % 2= =0 && b % 2= =0)
{
a /= 2;
b /= 2;
++count;
}
/ / when a! When = b
// Subtract smaller numbers from larger numbers in a and b
// Loop until a==b
while(a ! = b) {if (a > b)
{
a -= b;
}
else{ b -= a; }}// Notice that we need to multiply by count by 2
return a * pow(2, count);
}
int main(a)
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
Copy the codeRecursive:
#include <iostream>
#include <math.h>
using namespace std;
// Find the greatest common divisor
int gcd(int a, int b)
{
// There is no simultaneous operation of 2 on a and b
if (a == b)
{
return a;
}
else if (a > b)
{
a -= b;
}
else
{
b -= a;
}
return gcd(a, b);
}
int main(a)
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
Copy the codeMethod 4 [Stein algorithm]
The greatest common factor is Cn
Algorithm steps:
1, set up An = | A |, Bn = | | B, Cn = 1 and n = 1
2, If An=Bn, then An(or Bn)*Cn is the greatest common divisor, end of algorithm
3. If An=0, Bn is the greatest common divisor, end of algorithm
4. If Bn=0 and An is the greatest common divisor, end of algorithm
If n and Bn are both even, then n+1=An/2, Bn+1=Bn/2, and Cn+1=Cn*2.
If An is even and Bn is not even, then An+1=An/2, Bn+1=Bn, and Cn+1=Cn.
If Bn is even, and An is not even, then Bn+1=Bn/2, An+1=An, and Cn+1=Cn.
8, if An and Bn are not even, the An + 1 = | An – Bn | / 2 + 1 = | (or An An – Bn | also line), Bn + 1 = min (An, Bn), Cn + 1 = Cn
9, n=n+1, turn 2
Non-recursive:
#include <iostream>
#include <math.h>
using namespace std;
// Find the greatest common divisor
int gcd(int a, int b)
{
int count = 0;
if (a == b)
return a;
if (a == 0)
return b;
if (b == 0)
return a;
while(a ! = b) {// if a&1==1, a is odd, and a%2==1
// whether a is odd or even
if (a & 1)
{
if (b & 1)
{
// if both a and b are odd
// Store a ahead of time because a changes later
int temp = a;
a = abs(a - b) >> 1;
b = min(temp, b);
}
else
{
//a is odd and b is even
b >>= 1; }}else
{
if (b & 1)
{
// A is even and b is odd
a >>= 1;
}
else
{
//a and b are both even numbers
a >>= 1;
b >>= 1; ++count; }}}return a << count;
}
int main(a)
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
Copy the codeRecursive implementation:
#include <iostream>
#include <math.h>
using namespace std;
// Find the greatest common divisor
int gcd(int a, int b)
{
// Return B if A=0 and B is the greatest common factor
if (a == 0)
return b;
// Return A if B=0 and A is the greatest common factor
if (b == 0)
return a;
// If A and B are both even
// Divide by factor 2
// Until both cannot be even
if (a % 2= =0 && b % 2= =0)
return 2 * gcd(a >> 1, b >> 1);
// If a is even b is not even
// If 2 is not in the common factor, it can be removed directly
else if (a % 2= =0)
return gcd(a >> 1, b);
If b is even, a is not even
// If 2 is not in the common factor, it can be removed directly
else if (b % 2= =0)
return gcd(a, b >> 1);
// if both a and b are odd
/ / An + 1 = | the An - Bn |, Bn + 1 = min (An, Bn)
else
/ / abs (a - b) / 2 is right
// return gcd(abs(a - b)/2, min(a, b));
return gcd(abs(a - b), min(a, b));
}
int main(a)
{
int a, b;
cin >> a >> b;
cout << "gcd(a,b)=" << gcd(a, b) << endl;
return 0;
}
Copy the codeThe least common multiple method is relatively simple, to find the largest common factor, between a*b/ GCD (a,b) can be
conclusion
The essay is just a study note, recording a process from 0 to 1
Hope to help you, if there is a mistake welcome small partners to correct ~
