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

Doctor_ Chen. 2022-01-15 02:32:37


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 .


thank
Similar articles

2022-01-15

2022-01-15

2022-01-15

2022-01-15