2019年春季学期第四周作业:
作业课程 | C语言程序设计II |
作业要求 | 2019年春季学期第四周作业 |
课程目标 | 背熟栈,队列,向量函数 |
从作业中得到的帮助 | 更加熟练两种基本排序算法(冒泡排序和选择排序) |
参考文献 | 挑战程序设计 |
第一题:
7-1 找鞍点 (20 分)
一个矩阵元素的“鞍点”是指该位置上的元素值在该行上最大、在该列上最小。
本题要求编写程序,求一个给定的n阶方阵的鞍点。
输入格式:
输入第一行给出一个正整数n(1≤n≤6)。随后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
------------------------不用看了,这里没了-----------------------