Bingbing learning notes: find the greatest common divisor and the least common multiple. Complex version reverse string

One 、 greatest common divisor

Ideas 1：（ Exhaustive method ）

The greatest common divisor of two numbers must be less than the smaller of the two numbers , The greatest common divisor is the smallest 1.

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d",&a,&b);
	int min = a < b ? a : b;
	int i = 1;
	int s = min;
	for (i = 1;i <= min;i++)
	{
		if (a % i == 0 && b % i == 0)
		{
			s = i;
		}
	}
	printf("%d\n", s);
	return 0;
}

Ideas 2： division

Take the remainder of two numbers , If 0; Divisor is the greatest common divisor , If not for 0, Make the dividend equal to the divisor , Divisor becomes remainder , Continue to fetch remainder , Until the remainder of the two numbers is 0; Then the divisor is the greatest common divisor .

int main()
{

	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	while (a%b)
	{
		int tmp = a %b;
		a = b;
		b = tmp;
	}
	printf("%d\n", b);

	return 0;
}

Ideas 3： More impairment surgery （ Reference blog ：http://t.csdn.cn/DlDcv, The original text is more wonderful ）

Subtract the smaller number from the larger number , And then continue to subtract from the difference to get a new difference ( When the difference is negative , It's the reverse ), Keep cycling until the subtraction and difference are equal , At this point, the equal number is the greatest common divisor .

int main()
{
	int a = 0;
		int b = 0;
		scanf("%d %d", &a, &b);
	while (a != b)
	{
		if (a > b)
		{
			a = a - b;
		}
		else
		{
			b = b - a;
		}
	}
	printf("%d\n", a);
	return 0;
}

Two 、 Minimum common multiple

Ideas 1：（ Exhaustive method ）

The smallest common multiple of two numbers is the larger number itself , Then incrementally perform trial operation , Until we find a number that can take the remainder of two numbers at the same time 0 until . This number is the least common multiple .

int main()
{
		int a = 0;
		int b = 0;
		scanf("%d %d", &a, &b);
		int max = a > b ? a : b;
		int i = 0;
		//1
		for (i = max;i <= a * b;i++)
		{
			if (i % a == 0 && i % b == 0)
			{
				printf("%d\n", i);
				break;
			}
		
		}
		//2
		/*for (i = 1;i <= max;i++)
		{
			if ((a * i) % b == 0)
			{
				printf("%d\n", a*i);
					break;
			}
		}
	*/

	return 0;
}

Ideas 2： Calculation by rolling Division a,b greatest common divisor m, Reuse the formula a*b/m Find the least common multiple

int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    int x = a;
    int y = b;
    while (a % b)
    {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    printf("%d\n", x * y / b);


return 0;
}

  3、 ... and 、 Reverse order of strings in complex cases

Input I like beijing.

Output beijing. like I

This question is not a simple string in reverse order , Instead, reverse the word order , The words themselves are not in reverse order .

We found that through analysis

#include<assert.h>
void reverse(char* left, char* right)
{
	assert(left && right);
	while (left < right)
	{
		char tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}
int main()
{
	char arr[101] = { 0 };
	gets(arr);
	int len = strlen(arr);
	//1、 The whole is in reverse order 
	reverse(arr, arr + len - 1);
    //2、 The reverse order of each word 
	char* s = arr;
	char* e = s;
	while (*s!='\0')
	{
		while (*e != ' ' && *e != '\0')
		{
			e++;
		}
		reverse(s, e-1);
		s = e + 1;
		if (*e == ' ')
		{
			e++;
		}
		
	}
	printf("%s\n", arr);

	return 0;
}

Be careful ：

When getting a string , Not used scanf, It uses gers function , The reason lies in ,scanf The function does not read spaces

such as , Input abc def, He will only accept adc

however scanf It is not that there is no way to accept spaces , If used, it can be written like this scanf("%[^\n]",arr)