编程知识 cdmana.com

Divide and conquer -- Digital rotating square matrix (c + +)


Preface

Divide and conquer method -- Digital rotating square matrix
The knowledge points involved are divided and treated 、 Array dynamic allocation and two-dimensional array parameter transfer .

One 、 Divide and conquer method

Divide and conquer decomposes a large problem that is difficult to solve directly into some smaller subproblems , Solve each sub problem separately , Then the solutions of the subproblem are combined to obtain the solution of the original problem . There are three main steps , Namely division , Solving subproblems , Merge . The partition is mainly based on the equilibrium subproblem , And preferably independent of each other .
Here we take the digital rotating square matrix as an example , See the source code for the specific process .

Two 、 Digital rotating square array source code (C++)

// Digital rotating square matrix 
#include <iostream>
using namespace std;

void Full(int number,int begin,int size,int **d)
{
    
	int i, j, k;
	// Recursive boundary , If size==0, There is no need to fill in .
	if (size == 0)
	{
    
		return;
	}
	// Recursive boundary , If size==1, Then just fill in number Just go in .
	if (size == 1)
	{
    
		d[begin][begin] = number;
		return;
	}
	// Initialize the upper left coordinate .
	i = begin;j = begin;
	// Fill in A Area , Fill in size-1 Time .
	for (k = 0; k < size - 1; k++)
	{
    
		d[i][j] = number;
		number++;
		i++;
	}
	// Fill in B Area , Fill in size-1 Time .
	for (k = 0; k < size - 1; k++)
	{
    
		d[i][j] = number;
		number++;
		j++;
	}
	// Fill in C Area , Fill in size-1 Time .
	for (k = 0; k < size - 1; k++)
	{
    
		d[i][j] = number;
		number++;
		i--;
	}
	// Fill in D Area , Fill in size-1 Time .
	for (k = 0; k < size - 1; k++)
	{
    
		d[i][j] = number;
		number++;
		j--;
	}
	Full(number, begin + 1, size - 2, d);

}

int main()
{
    
	// Confirm the order of the square matrix .
	int number = 1, begin = 0, size;
	cout << " Please enter the order of the square matrix :";
	cin >> size;
	// Assign arrays dynamically , Second order array .
	int** d = new int*[size];
	for (int i = 0; i < size; i++)
	{
    
		d[i] = new int[size];
	}
	// Second order array assignment 
	for (int i = 0; i < size; i++)
	{
    
		for (int j = 0; j < size; j++)
		{
    
			d[i][j] = 0;
		}
	}
	// Call the digital rotation matrix .
	Full(number, begin, size,d);
	// Output digital rotation matrix 
	cout << " Digital rotating square matrix :" << endl;
	for (int i = 0; i < size; i++)
	{
    
		for (int j = 0; j < size; j++)
		{
    
			cout<<d[i][j]<<" ";
		}
		cout << endl;
	}
	return 0;
}

result :
 Insert picture description here

3、 ... and 、 Assign arrays dynamically

One dimensional array

void oneDimensionalArray()
{
    
    // Define a length of 10 Array of 
	int* array = new int[10];
    // assignment 
	for(int i = 0; i < 10; i++)
	{
    
		array[i] = i*2;
	}
	// Output 
	for(int i = 0; i < 10; i++)
	{
    
		cout << i << " : " << array[i] << endl;
	}
	// Free memory 
	delete[] array;
}

Two dimensional array

void twoDimensionalArray()
{
    
	// Define a 2*10 Two dimensional array of 
	int** array = new int*[2];
	for(int i = 0; i < 2; i++)
	{
    
		array[i] = new int[10];
	}
	// assignment 
	for(int i = 0; i < 2; i++)
	{
    
		for(int j = 0; j < 10; j++)
		{
    
			array[i][j] = i*10 + j;
		}
	}
	// Output 
	for(int i = 0; i < 2; i++)
	{
    
		for(int j = 0; j < 10; j++)
		{
    
			cout << "(" << i << ", " << j << ")" << array[i][j] << endl;
		}
	}
	// Free memory 
	for(int i = 0; i < 2; i++)
	{
    
		delete[] array[i];
	}
	
	delete[] array;
}

And so on

Four 、 A two-dimensional array is passed as a function parameter

In the above example, I use a secondary pointer as a function parameter to pass , For detailed explanation, see

https://blog.csdn.net/kangxidagege/article/details/79475537

I don't have much time to organize and write recently , I hope I can come back and fill the pit later .

summary

Always write something to record and share , I hope it can help you , And this is my greatest happiness and happiness .

版权声明
本文为[Doctor_ Chen.]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/12/202112122246169230.html

Scroll to Top