题目--找鞍点 及 选择排序和冒泡排序

2019/03/19 19:23
阅读数 93

 

2019年春季学期第四周作业:

 

作业课程 C语言程序设计II
作业要求 2019年春季学期第四周作业
课程目标 背熟栈,队列,向量函数
从作业中得到的帮助 更加熟练两种基本排序算法(冒泡排序和选择排序)
参考文献 挑战程序设计

 

第一题:

7-1 找鞍点 (20 分)

一个矩阵元素的“鞍点”是指该位置上的元素值在该行上最大、在该列上最小。

本题要求编写程序,求一个给定的n阶方阵的鞍点。

输入格式:

输入第一行给出一个正整数n(1n6)。随后n行,每行给出n个整数,其间以空格分隔。

输出格式:

输出在一行中按照“行下标 列下标”(下标从0开始)的格式输出鞍点的位置。如果鞍点不存在,则输出“NONE”。题目保证给出的矩阵至多存在一个鞍点。

输入样例1:

4
1 7 4 1
4 8 3 6
1 6 1 2
0 7 8 9

输出样例1:

2 1

输入样例2:

2
1 7
4 1

输出样例2:

NONE

 

此题是一道简单的搜索题,也就是先确认一个点,然后沿4个方向搜索到不满足条件的数(不越界的情况下),然后返回需要的值。由于题目给的条件非常非常非常小,所以不需要考虑复杂度,逻辑通了随便写。

 

AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int arr[10][10];//n<6,直接定义一个全局变量
 5 bool solve(int n,int x,int y){
 6    for(int i = 0; i < n ; i++)
 7    if(arr[x][y]<arr[x][i])return false;//搜索行,找到一个大于确认的点的值直接返回
 8    for(int j = 0; j < n ; j++)
 9    if(arr[x][y]>arr[j][y])return false;//搜索列,找到一个小于确认的点的值直接返回
10    
11    return true;
12 }
13 
14 int main ( int argc , const char * argv[])
15 {
16     int n,flag;
17     cin>>n;
18     for(int i=0;i<n;i++)for(int j=0;j<n;j++){cin>>arr[i][j];}//给数组赋值
19     
20      for(int i=0;i<n;i++)
21      for(int j=0;j<n;j++)
22      if(solve(n,i,j)){cout<<i<<" "<<j;flag++;}//找到满足条件的鞍点就输出(虽然题目说给的矩阵至多一个鞍点,但懒得弄就直接判断所有的点是否为鞍点吧)
23      if(!flag)cout<<"NONE";//没有鞍点则输出NONE
24     return 0;
25 }

 

设计思路

 

 

 

 

 

本题调试过程中遇到的问题及解决方法

由于是一遍AC的,暂无任何疑问。

 

运行结果截图

 

 

第二题

7-2 选择法排序 (20 分)

本题要求将给定的n个整数从大到小排序后输出。

输入格式:

输入第一行给出一个不超过10的正整数n。第二行给出n个整数,其间以空格分隔。

输出格式:

在一行中输出从大到小有序的数列,相邻数字间有一个空格,行末不得有多余空格。

输入样例:

4
5 1 7 6

输出样例:

7 6 5 1

首先提一下,三种基本排序方法(冒泡,选择,插入)在N久之前就写了很多遍的东西..这次写也没花多久直接一遍过了,只能说这周问题比较面向初次了解排序算法的人,我接下来会把选择排序和“挑战题”冒泡排序(挑战题有加分吧?手动滑稽)稍微写详细点,因为自己也很久没写过了,帮助记忆一下。

AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 void solve(int arr[],int n){
 5     for(int i=0;i<n-1;i++){   //首先理所当然solve里面第一个要做的事情就是做一个内外循环,外循环要少一次,防止最后两个元素重复。
 6         int maxs=arr[i];  //重置maxs的值,maxs就是各轮循环处理中,第i号到第N-1号元素中的最大值
 7         int sz_zb=i;      //重置sz_zb的值,sz_zb就是各轮循环处理中,第i号到第N-1号元素中最大值的下标
 8     for(int j=i;j<n;j++){if(maxs<arr[j]){maxs=arr[j] ; sz_zb=j;} }    //找出第i号到第N-1号中的最大值及其下标    
 9           int tmp = arr[i] ;
10              arr[i] = maxs;     //交换第i号和对应的最大值的元素的位置
11              arr[sz_zb] = tmp;             
12      }
13      for(int i=0;i<n;i++)
14      if(i<n-1)
15      cout<<arr[i]<<" ";
16      else cout<<arr[i];  //从大到小输出数组
17 
18 }
19 
20 int main ( int argc , const char * argv[])
21 {
22     int n,num[12];
23     cin>>n;
24     for(int i=0;i<n;i++)
25     cin>>num[i];
26     
27     solve(num,n);
28     return 0;
29 }

 

设计思路

 

 

本题调试过程中遇到的问题及解决方法

虽然是一遍AC的,但还是提醒一下,一定要理解内外循环的概念及作用,不然排序会出错

 

运行结果截图

 

 

 

注意一下,选择排序的复杂度,假设数据总数为N,那么无论在哪一种情况下,选择排序都要进行(N-1)+(N-2)+.....+1=(N^2-N)/2次比较运算,用于搜索未排序部分的最小值,因此该算法的复杂度与N^2基本成正比,及复杂度数量级为O(N^2).使用时要看题目条件范围是否过大,如果过大建议选择其他排序算法。

挑战题

 

7-1 冒泡法排序 (10 分)

 

输入1个正整数n(1<=n<=10),然后输入n个整数并存放在数组中,将这n个整数从大到小排序后输出,相邻数字间有一个空格,行末不得有多余空格。

输入格式:

输入第一行给出一个不超过10的正整数n。第二行给出n个整数,其间以空格分隔。

输出格式:

在一行中输出从大到小有序的数列,相邻数字间有一个空格,行末不得有多余空格。

输入样例:

4 
75 71 77 76

输出样例:

77 76 75 71

 

冒泡排序算法的时间复杂度与选择排序的时间复杂度是基本一样的,也是要做(N^2-N)/2次比较,所以复杂度也为O(N^2).只是排序的过程略有不同,选择排序是每次遍历,找出未排序的数中最大的一个,然后将它放在最前面,而冒泡排序则是从第一个数(未排序好的数)开始,一个一个往后比较,遇到比自己大的则交换位置,直到无法交换为止,最后排完所有的数后一定是从大到小的顺序。

 

AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 void solve(int arr[],int n)
 5 {
 6     for(int i = n - 1 ; i > 0 ; i--)
 7       for(int j = 0 ; j < i ; j++)
 8         {
 9             if( arr[j] < arr[j+1] ){int tmp = arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;}
10         }
11     
12             for(int i = 0 ; i < n ; i++)
13                if(i<n-1)cout<<arr[i]<<" ";
14                 else cout<<arr[i];
15 }
16 int main ( int argc , const char * argv[] )
17 {
18     int n;
19     cin>>n;
20     int arr[12]; 
21     for( int i = 0 ; i < n ; i++)cin>>arr[i];
22     solve(arr,n);
23     return 0;
24 }

 

设计思路

 

本题调试过程中遇到的问题及解决方法

此题是一道较为简单的基础排序题,未遇到任何问题。

 

运行结果截图

 

 

写到这里为了能更加区别冒泡和选择排序的区别,我改一下代码将每一次排序的过程运行图发出来。

冒泡排序:

 

 选择排序:

 

稍微注意观察一下,排序过程的差异很明显。

最后还是分享一下利用partition进行快排的算法,是一个很经典及实用的排序算法,博客地址:https://www.cnblogs.com/xiangqi/p/10485379.html

 

学习总结: 存在的问题 心得 完成作业消耗时间 本周学习内容
第一周 对文件读取数据的运用不是很熟练 多去看关于刷题的书籍,有助于提高自己写题能力,实在不会的可以参考大佬的代码,加以自己理解之后去默写几遍 半个小时左右 文件输入,BFS,DFS,PARTITION算法及简单的贪心算法
第二周 对单纯用数组完成双向链表的操作还是太生疏了,说明对双向链表的运作原理不熟 推荐两本比较好的书《挑战程序设计》《算法竞赛》 半个小时左右 vector数组及list双向链表操作

 

 

再分享本周预习题的解法,写到了另外一篇博客,这里是地址:https://www.cnblogs.com/xiangqi/p/10573623.html

------------------------不用看了,这里没了-----------------------

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部