This is the process I have written very early, regardless of a watering article
A idea of full-aligned programs
A number of all-alone, such as 2 full-ranked 12, 21; a total of 2; 3 full-ranked 123, 132, 213, 231, 312, 321; a total of 6 ... All arrangements have important applications in many places, but it is necessary to produce but a number of full alignment, but it is not as simple as we think, (Do not believe you can never look at the program in the article, write a generating algorithm yourself), This article uses a chessboard idea to prepare a full-aligned program.
We know that a number of Natural numbers are all sorted from 1 to n, and after being arranged, it cannot be repeated in the later row. We can use the following method to simply understand.
It is idea that there is a chess, the chessboard is n × n, and the chess pieces total N, which requires two or more chess pieces per row and each column, requiring its own possible layout. The picture below shows a layout of 4 × 4 chessboard.
●
●
●
●
In fact, think about the following, this is a number of N full arranging equivalents. Because each row and each column cannot have a repetitive chess piece, and the board is square, and the all possible layout of its chess pieces is equivalent to a number of Number N.
You can use the following ideas to place a chess piece at the 1st column of Chain 1, then start on the second line, because the first column has already placed the chess, so it can only be placed on the second column, then put the first 3 columns ... .. Also put it until the Nth line. This is completed, the second arrangement is completed, pay attention: At this time, the state is not changed, and the chess pieces on the N-1 line began moving to the right from the first grid on the left, see if it is The front N-2 row of chess pieces (do not manage the chess pieces of the nth row), if the conflict will move the chess pieces to the right, then see if there is a conflict, until there is no conflict, if you can't find this location Regardless of the Nth and N-1 row, the same experiment is made with the N-2 chess pieces until a location is found, otherwise, the chess pieces used will be reduced by 1, and do the same experiment until I find one The position is later. Use the same way to discharge a row of chess pieces, and complete a arrangement when row to Nth. When the row of chess pieces in the first row, the row will not be row, and complete the full layout of the chessboard, at this time, the full routing ends.
Below is the program, written in C languages.
#include
#include
INT row [15]; // Used to simulate the board, where the array subscript is the line number, the value is the list where the value is located.
INT I;
INT canSet (INT K) / Judging whether the chess pieces on the row can be placed on the current list
{
Int J;
J = 1;
While (j IF (row [j] == row [k]) return 0; /// Usually, as long as there is a conflict with the chess pieces on the front of the line, it is unsuccessful. J ; } Return 1; } Void Quanpailie (int N) // full-railing implementation function { INT K; Row [1] = 0; the first time, the first line did not place chess pieces K = 1; / Start to place the first line While (k> 0) { Row [k] = row [k] 1; move the chess pieces to the right While (row [k] <= N && (canSet (k) <1)) { Row [k] = row [k] 1; can not be returned to the right moving } IF (row [k] <= n) {We found a position, then you can put down the chess pieces IF (k == n) { For (i = 1; i <= n; i ) Printf ("% d", row [i]); have been completed in one of the N rows, Print them out Printf ("/ n"); / change line } else { K = K 1; if it is not yet finished, continue Row [k] = 0; start from the left } } else { K = k-1; / up, see if there is any other } } } void main () { Int n; Printf ("Enter Your Num to Pailie:"); CIN >> N; Quanpailie (n); } This program is commissioned on TC 3.0 and VC5.0. 1997/6/10 Hefei Electronic Engineering College #####Finish##
