Rolling division, Young's matrix and three-step flip

Catalog

introduction

division

  Young's matrix

  Three step flipping

---

introduction

This article is about learning C Three classic problems in language process , Elaborate , Understand the details of the three solutions from the perspective of logic and code .

division

Euclid algorithm also called division , Is used to calculate two nonnegative integers a,b Of greatest common divisor . There are two fields of application: Mathematics and computer .

Next, let's take a look at its implementation principle ：

#include <stdio.h>

int main()
{
    int n = 0;
    int m = 0;
    scanf("%d%d", &n, &m);
    // set up max Is the greatest common divisor 
    int max = n>m?m:n;
    // set up min It's the least common multiple 
    int min = n>m?n:m;
    while(1)
    {
        if(m%max==0 && n%max ==0)
        {
            break;
        }
        max--;
    }
    while(1)
    {
        if(min%m == 0 && min%n==0)
        {
            break;
        }
        min++;
    }
    printf("%d\n", max+min);
    
    return 0;
}

  Young's matrix

Young's matrix is a numerical matrix , Each row of the matrix is incremented from left to right , The matrix is increasing from top to bottom , Please write a program to find out whether a number exists in such a matrix .

Let's observe from the picture ：

#include <stdio.h>
 
int findnum(int a[][3], int x, int y, int f) // The type of the first parameter needs to be adjusted 
{
	int i = 0, j = x - 1; // Start from the top right corner and traverse 
 
	while (j >= 0 && i < y)
	{
		if (a[i][j] < f) // Older than me, down 
		{
			i++;
		}
		else if (a[i][j] > f) // He left when he was younger than me 
		{
			j--;
		}
		else
		{
			return 1;
		}
	}
	return 0;
}
 
int main()
{
	int a[][3] = { {1, 3, 5},
				  {3, 5, 7}, 
				  {5, 7, 9} }; // An example 
 
	if (findnum(a, 3, 3, 2))
	{
		printf(" eureka \n");
	}
	else
	{
		printf(", I didn't find it \n");
	}
 
	return 0;
}

  Three step flipping

The three-step inversion method is used to solve the problem of multiple left rotation of strings .

Implement a function , You can rotate left in a string k Characters .

for example ：

void reverse_part(char *str, int start, int end) // String from start To end This paragraph is in reverse order 
{
	int i, j;
	char tmp;
 
	for (i = start, j = end; i < j; i++, j--)
	{
		tmp = str[i];
		str[i] = str[j];
		str[j] = tmp;
	}
}
 
void leftRound(char * src, int time)
{
	int len = strlen(src);
	int pos = time % len;
	reverse_part(src, 0, pos - 1); // The preceding paragraph in reverse order 
	reverse_part(src, pos, len - 1); // Backward segment 
	reverse_part(src, 0, len - 1); // The whole is in reverse order 
}