[ACM training I] time complexity, recursion and enumeration

Time complexity

Easy to understand explanation: https://blog.csdn.net/qq_41523096/article/details/82142747#commentsedit

Common time complexity (Big O representation)
(1) O(1): constant order, running time is constant
(2) O(logn): logarithmic order, such as binary search algorithm
(3) O(n): linear order, such as finding the maximum value within n numbers
(4) O(nlogn): logarithmic order, such as fast sorting algorithm
(5) O(n^2): square order, if sorting is selected, bubble sorting
(6) O(n^3): cubic order, such as multiplication of two n-order matrices
(7) O(2^n): algorithm of exponential order, such as all subsets of N element sets
(8) O(n!): factorial order, such as the algorithm for arranging all n elements

Enumeration and recursion

No explanation for the definition
Example
1. Enumeration improvement
Input a number n (0 < n < 8) and a number k (0 < K < = 5). Requirements: select any k numbers from the N numbers of 1~N (numbers can be selected repeatedly). Please output all schemes according to the size.

#include <stdio.h>
int n,k;
int tt[9];
void di(int pt)
{
	int i;
	if(pt>k)
	{
		for(i=1;i<=k;i++)
		printf("%d",tt[i]);
		printf("\n");
	}
	else
	{
		for(i=1;i<=n;i++)
		{
		tt[pt]=i;
		di(pt+1);
	    }
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	di(1);
	return 0;
}

2. Full arrangement
Input a number n (0 < n < 8), and output a total arrangement of N numbers from 1 to N in order of small to large.

#include<stdio.h>
#include<math.h>
int main(){
	int used[10];
	int N,i,j,k,s,t;
	int min=0,max=0;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
    {
	min=min+i*pow(10,N-i);
	max=max+(N-i+1)*pow(10,N-i);
	}
	for(i=min;i<=max;i++)
	{
			used[1]=0;
			used[2]=0;
			used[3]=0;
			used[4]=0;
			used[5]=0;
			used[6]=0;
			used[7]=0;
			used[8]=0;
		for(j=1,k=i;j<=N;j++)
		{
		s=k/pow(10,N-j);
		k=k-(s*pow(10,N-j));
			switch(s)
				{
					case 0:used[0]=used[0]+1;break;
					case 1:used[1]=used[1]+1;break;
					case 2:used[2]=used[2]+1;break;
					case 3:used[3]=used[3]+1;break;
					case 4:used[4]=used[4]+1;break;
					case 5:used[5]=used[5]+1;break;
					case 6:used[6]=used[6]+1;break;
					case 7:used[7]=used[7]+1;break;
					case 8:used[8]=used[8]+1;break;
					case 9:used[9]=used[9]+1;break;
				}
		}
    for(j=1,k=0;j<=N;j++)
        {
            if(used[j]!=1)
            break;
            else 
            k=k+1;
        }
			if(k==N)
            printf("%d\n",i);
	}
}

3, Queen N
N queens are placed on the checkerboard of N*N, so that they do not attack each other (that is, any two queens are not allowed to be in the same row, the same column, or on the diagonal line with a 45 angle to the board frame).
Your task is to find out how many legal placement methods are available for a given N.

#include <stdio.h>
#define NUMS 10
int N;
int chessboard[11][11];
int cal;
int dfs_check(int row,int column,int k)
{
    if(row>k)
    {
        cal++;
        return 1;
    }
    int i=0;
    int j=0;
    for( i = 1; i < row; i++)
       
    if(chessboard[i][column] == 1)
    return 0;

    /* Check whether the upper left and right 45 degree angle is OK*/
    /* Upper left*/
    for( i=row-1,j=column-1;i>0&&j>0;i--,j--)
    if(chessboard[i][j] == 1)
    return 0;
    /* Upper right*/
    for( i=row-1,j=column+1;i>0&&j<=k;i--,j++)
    if(chessboard[i][j] == 1)
    return 0;
    /*Mark this position successfully*/
    chessboard[row][column] = 1;

    /*Next line search*/
    for( i=1;i<=k;i++)
    if(dfs_check(row+1,i,k)==1)
    break;

    chessboard[row][column] = 0;
    return 0;
}
int main()
{
    int i,j,k;
    int count[11];
    /*charge by the meter*/
    for(k=1;k<=NUMS;k++)
    {
        count[k] = 0;
        cal = 0;
        /*First, set all chessboard initialization to 0*/
        for(i=0;i<=NUMS;i++)
        for(j=0;j<=NUMS;j++)
        chessboard[i][j]=0;
        for(i=1;i<=k;i++)
        dfs_check(1,i,k);
        count[k] = cal;
    }

    while(scanf("%d",&N)!=EOF&&N!=0)
    printf("%d\n",count[N]);
    return 0;
}

To be continued

Posted on Sun, 03 Nov 2019 01:57:16 -0700 by jimdelong