算法题实验笔记-使用递归

做算法实验课作业,感觉又回到了当初学C语言刷POJ的年代,不过很久没用C写程序,好多东西都忘记了,比如C里面布尔型是怎么声明的你造吗?其实C里面没有布尔型,话说我真忘记了。做完了几道题,这里先记下

导航目录

  1. 归并排序
  2. 快速排序
  3. 走迷宫
  4. 穷举n位二进制数
  5. 循环赛日程表

  1. 归并排序

    描述

     给定一个数列,用归并排序算法把它排成升序。
    

    输入

     第一行是一个整数n(n不大于10000),表示要排序的数的个数;
     下面一行是用空格隔开的n个整数。
    

    输出

     输出排序后的数列,每个数字占一行。
    

    输入样例

     5
     3 2 1 4 5
    

    输出样例

     1
     2
     3
     4
     5
    

    我的程序:

     #include <stdio.h>
     #include <stdlib.h>
    
     int * combin(int *arr1,int *arr2,int b1,int e1,int b2,int e2){
         int i;
         int *tmp = (int *)malloc(sizeof(int)*(e1-b1+e2-b2));
         for(i = 0;b1<e1||b2<e2;i++){
             if(b2>=e2||(b1<e1&&arr1[b1] <= arr2[b2])){
                 tmp[i] = arr1[b1];
                 b1++;
             }
             else{
                 tmp[i] = arr2[b2];
                 b2++;
             }
         }
         free(arr1);
         free(arr2);
         return tmp;
     }
    
     int* quickSort(int * arr,int n){
         int* arra;
         int* arrb;
         if(n==1){
             int *tmp = malloc(sizeof(int));
             tmp[0] = arr[0];
             return tmp;
         }
         arra = quickSort(arr,n/2);
         arrb = quickSort(arr+(n/2),n-(n/2));
         return combin(arra,arrb,0,n/2,0,n-(n/2));
     }
    
     int main()
     {
         int i,n;
         int *input;
         int *output;
         scanf("%d",&n);
         input = (int*)malloc(sizeof(int)*n);
         for(i=0;i<n;i++){
             scanf("%d",input+i);
         }
         output = quickSort(input,n);
         for(i = 0;i<n;i++){
             printf("%d\n",output[i]);
         }
         //system("pause");
         return 0;
     }
    

  1. 快速排序

    描述

     给定一个数列,用快速排序算法把它排成升序。
    

    输入

     第一行是一个整数n,表示要排序的数的个数;下面一行是用空格隔开的n个整数。
    

    输出

     输出排序后的数列,每个数字占一行。
    

    输入样例

     5
     3 2 1 4 5
    

    输出样例

     1
     2
     3
     4
     5
     
    

    我的程序:

     #include <stdio.h>
     #include <stdlib.h>
    
     int quickSort(int arr[],int begin_index,int end_index){
         int i,j,tmp_num,tmp_index;
         i = begin_index;
         j = end_index;
         tmp_num = arr[begin_index];
         tmp_index = begin_index;
         for(;i<j;){
             if(tmp_index==i){
                 if(arr[j]<tmp_num){
                     arr[tmp_index] = arr[j];
                     i++;
                     tmp_index = j;
                 }else{
                     j--;
                 }
             }
             else if(tmp_index==j){
                 if(arr[i]>tmp_num){
                     arr[tmp_index] = arr[i];
                     j--;
                     tmp_index = i;
                 }else{
                     i++;
                 }
             }
         }
         arr[tmp_index] = tmp_num;
         if(tmp_index-1>begin_index)
             quickSort(arr,begin_index,tmp_index-1);
         if(tmp_index+1<end_index)
             quickSort(arr,tmp_index+1,end_index);
         return 0;
     }
    
     int main()
     {
         int i,n;
         int *input;
         scanf("%d",&n);
         input = (int*)malloc(sizeof(int)*n);
         for(i=0;i<n;i++){
             scanf("%d",input+i);
         }
         quickSort(input,0,n-1);
         for(i = 0;i<n;i++)
             printf("%d\n",input[i]);
         return 0;
     }
    

  1. 走迷宫

    描述

     判断是否能从迷宫的入口到达出口
    

    输入

     先输入两个整数表示迷宫的行数m和列数n,再输入口和出口的坐标,最后分m行输入迷宫,其中1表示墙,0表示空格每个数字之间都有空格。
    

    输出

     若能到达,则输出"Yes",否则输出"No",结果占一行。
    

    输入样例

     3 3
     0 0
     2 2
     0 0 0
     1 1 0
     0 1 0
    

    输出样例

     Yes
    

    我的程序,这里使用了一个链表来模拟队列并进行广度搜索:

     #include <stdio.h>
     #include <stdlib.h>
    
     typedef struct MNode{
         int row;
         int col;
         struct MNode * next;
     } Node,* PNode;
    
     int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
     int maxRow ,maxCol ;
     int i,j,inrow ,incol ,outrow ,outcol ;
     int **mmap;
    
     PNode head = NULL,tail = NULL;
    
     void addItem(int row,int col){
         PNode newPoint = (PNode)malloc(sizeof(Node));
         newPoint->row = row;
         newPoint->col = col;
         newPoint->next = NULL;
         tail->next = newPoint;
         tail = newPoint;
     }
    
     void removeItem(){
         PNode tmp = head;
         head = head->next;
         free(tmp);
     }
    
     int haveItem(){
         if(head==NULL) return 0;
         return 1;
     }
    
     int isCan(row,col){
         if(row<0||col<0||row>=maxRow||col>=maxCol) return 0;
         if(mmap[row][col]!=0) return 0;
         return 1;
     }
    
     int main()
     {
         scanf("%d%d%d%d%d%d",&maxRow,&maxCol,&inrow,&incol,&outrow,&outcol);
         mmap = (int **)malloc(sizeof(int*)*maxRow);
         for(i = 0;i<maxRow;i++){
             mmap[i] = (int*)malloc(sizeof(int)*maxCol);
         }
    
         for(i = 0;i<maxRow;i++)
             for(j = 0;j<maxCol;j++){
                 scanf("%d",&mmap[i][j]);
             }
    
         head = (PNode)malloc(sizeof(Node));
         head->row = inrow;
         head->col = incol;
         head->next = NULL;
         tail = head;
         for(;haveItem();){
             if(head->row==outrow&&head->col == outcol){
                 printf("Yes\n");
                 for(;haveItem();){
                     removeItem();//free more
                 }
                 return 0;
             }
             for(i = 0;i<4;i++){
                 if(isCan(head->row+dir[i][0],head->col+dir[i][1])){
                     addItem(head->row+dir[i][0],head->col+dir[i][1]);
                 }
             }
             mmap[head->row][head->col] = 2;
             removeItem();
         }
         printf("No\n");
         return 0;
     }
    

  1. 穷尽N位二进制

    描述

     输入一个小于20的正整数n,要求按从小到大的顺序输出所有的n位二进制数,每个数占一行。
    

    输入

     输入一个小于20的正整数n。
    

    输出

     按从小到大的顺序输出所有的n位二进制数,每个数占一行。
    

    输入样例

     3
    

    输出样例

     000
     001
     010
     011
     100
     101
     110
     111
     
    

    我的程序,这个简单直接贪心算法:

     #include <stdio.h>
     #include <stdlib.h>
    
     int input,* arr;
    
     int mPrint(int n,int num){
         int i;
         arr[input-n] = num;
         if(n<=1){
             for(i = 0;i<input;i++){
                 printf("%d",arr[i]);
             }
             printf("\n");
             return 0;
         }
         mPrint(n-1,0);
         mPrint(n-1,1);
         return 0;
     }
    
     int main()
     {
         scanf("%d",&input);
         arr = (int *)malloc(sizeof(int)*input);
         mPrint(input,0);
         mPrint(input,1);
         return 0;
     }
    

  1. 循环赛日程表

    描述

     用分治算法生成循环赛日程表(1到2的n次方个人)
    

    输入

     一个整数n
    

    输出

     循环赛日程表(1到2的n次方个人)
    

    输入样例

     3
    

    输出样例

     1 2 3 4 5 6 7 8
     2 1 4 3 6 5 8 7
     3 4 1 2 7 8 5 6
     4 3 2 1 8 7 6 5
     5 6 7 8 1 2 3 4
     6 5 8 7 2 1 4 3
     7 8 5 6 3 4 1 2
     8 7 6 5 4 3 2 1
     
    

    我的程序,由样例看出,每个正方形块中,右上角和左下角、左上角和右下角是一样的,所以主要使用分治算法:

     #include <stdio.h>
     #include <stdlib.h>
    
     int change(int **arr,int row,int n){
         int i,j;
         if(n==1){
             return 0;
         }
         change(arr,row,n/2);
         change(arr,row+n/2,n/2);
         //方格转换
         for(i = 0;i<n/2;i++){
             for(j = 0;j<n/2;j++){
                 arr[row+i][n/2+j] = arr[row+n/2+i][j];
                 arr[row+n/2+i][n/2+j] = arr[row+i][j];
             }
         }
         return 0;
     }
    
     int main()
     {
         int i,j,input,n = 1,**arr;
         scanf("%d",&input);
         for(i = 0;i<input;i++){
             n *= 2;
         }
         arr = (int**)malloc(sizeof(int*)*n);
         for(i = 0;i<n;i++){
             arr[i] = (int*)malloc(sizeof(int)*n);
             arr[i][0] = i+1;
         }
    
         change(arr,0,n);
         for(i = 0;i<n;i++){
             for(j = 0;j<n;j++){
                 if(j==n-1) printf("%d\n",arr[i][j]);
                 else printf("%d ",arr[i][j]);
             }
         }
         return 0;
     }
    

标签: C/C++, 算法, 递归

添加新评论