contributed by dekrt,2021-11-18

第一次作业：

hanoi问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>

#define re register
#define il inline 

int n ;

inline void move( int n , char a , char b , char c )
//将a上的n块借助b移动到c上去
{
    static int cnt = 1 ;
    if ( n == 1 ) 
    {
        printf("step %3d : move %c to %c\n", cnt++ , a , c ) ;
        return ;
    }
    move ( n-1 , a , c , b ) ;
    printf("step %3d : move %c to %c\n", cnt++ , a , c ) ;
    move ( n-1 , b , a , c ) ;
}

int main()
{
    printf("Input the number of diskes you want to move:") ;
    scanf("%d",&n) ;
    move ( n , 'a' , 'b' , 'c' ) ;
    return 0 ;
}

上楼梯问题：

递归解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

#define re register
#define il inline 

int n ;

inline int move( int n )
{
    if ( n == 1 ) return 1 ;
    if ( n == 2 ) return 2 ;
    if ( n >= 3 ) return move(n - 1) + move(n - 2) ;
}

int main()
{
    scanf("%d",&n) ;
    printf("%d",move(n)) ;
    return 0 ;
}

递推解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>

#define re register
#define il inline 

int n , tmp1 , tmp2 , ans ;  

int main()
{
    tmp1 = 1 ; tmp2 = 2 ;
    scanf("%d",&n) ;
    if( n == 1 )
    {
        printf("1") ;
        return 0;
    }
    else if( n == 2 )
    {
        printf("2") ;
        return 0 ;
    }
    else
    {
        for ( re int i = 3 ; i <= n ; i++ )
        {
            ans = tmp1 + tmp2 ;
            tmp1 = tmp2 ;
            tmp2 = ans ;
        }
    }
    printf("%d",ans) ;
    return 0 ;
}

第二次作业：

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>

#define re register
#define maxn 10005

int a[] = { 49 , 38 , 65 , 97 , 76 , 13 , 27 } ;
int cnt = sizeof (a) / sizeof(a[0]) ;

void quicksort( int b[] , int l , int r ) 
{
    re int i = l , j = r , key ;
    if ( l == r ) return ;
    else key = b[i] ;
    while ( i < j )
    {
        while ( ( i < j ) && b[j] >  key ) j-- ;
        if( i < j ) b[i++] = b[j] ; 
        while ( ( i < j ) && b[i] <= key ) i++ ;
        if( i < j ) b[j--] = b[i] ;
    }
    b[i] = key ;
    sort( b , l , i-1 ) ;
    sort( b , i+1 , r ) ;
}

int main()
{
    quicksort( a , 0 , cnt - 1 ) ;
    for ( re int i = 0 ; i < cnt ; i++ )
        printf("%d " , a[i]) ;
    return 0 ;
}
// code by dekrt , 2021 - 11 - 20

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>

#define re register
#define maxn 10005

int a[] = { 49 , 38 , 65 , 97 , 76 , 13 , 27 } ;
int cnt = sizeof (a) / sizeof(a[0]) ;

int search ( int b[] , int l , int r , int key ) 
{
    if( l == r ) return l ;
    re int mid = l + ( ( r - l ) >> 1 ) ;
    if( b[mid] <= key ) return search( b , mid + 1 , r , key ) ;
    else return search ( b , l , mid - 1 , key ) ;
}

void binary_insertsort ( int b[] , int n ) 
{
    for ( re int i = 1 ; i < n ; i++ )
    {
        re int tmp = b[i] , l = 0 , r = i - 1 , mid ;
        while ( l <= r ) 
        {
            mid = ( l + r) >> 1 ;
            if( b[mid] <= tmp ) l = mid + 1 ;
            else r = mid - 1 ;
        }
        re int j ;
        for ( re int j = i - 1 ; j >= mid ; j-- )
            b[j+1] = b[j] ;
        b[l] = tmp ;
    }
}

int main()
{
    for ( re int i = 1 ; i < cnt ; i++ )
    {
        int tmp = search ( a , 0 , i - 1 , a[i] ) ;
        for ( re int j = i - 1 ; j >= tmp ; j-- )
            a[j+1] = a[j] ;
        a[tmp] = a[i] ;
    }
    for ( re int i = 0 ; i < cnt ; i++ )
        printf("%d " , a[i]) ;
    return 0 ;
}
// code by dekrt , 2021 - 11 - 20

罗伯法构建奇阶幻方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>

#define re register
#define maxn 10005

int n ;
int a[maxn][maxn] ;

void dfs( int cnt , int x , int y )
{
    if ( cnt > n * n ) return ;
    a[x][y] = cnt ;
    int xx = x + 1 , yy = y + 1 ;
    if( xx > n ) xx -= n ;
    if( yy > n ) yy -= n ;
    if( a[xx][yy] == 0 ) dfs ( cnt + 1 , xx , yy ) ;
    else dfs( cnt + 1 , x , y - 1 ) ;
}

int main()
{
    printf("Please input 'n' to start the program:\n") ;
    scanf ("%d" , &n ) ;
    dfs( 1 , ( n + 1 ) >> 1 , n ) ;
    for ( re int i = n ; i >= 1 ; i-- , putchar('\n') ) 
        for( re int j = 1 ; j <= n ; j++ )
            printf("%3d " , a[j][i] ) ;
    return 0 ;
}
// code by dekrt , 2021 - 11 - 20