小学英语教师做应用相关网站,网站做跳转教程,wordpress 开发,企业官网手机版本专栏为c语言练习专栏#xff0c;适合刚刚学完c语言的初学者。本专栏每天会不定时更新#xff0c;通过每天练习#xff0c;进一步对c语言的重难点知识进行更深入的学习。 今日练习题关键字#xff1a;记负均正 旋转数组的最小数字 二分查找 #x1f493;博主… 本专栏为c语言练习专栏适合刚刚学完c语言的初学者。本专栏每天会不定时更新通过每天练习进一步对c语言的重难点知识进行更深入的学习。 今日练习题关键字记负均正 旋转数组的最小数字 二分查找 博主csdn个人主页小小unicorn ⏩专栏分类C语言天天练 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 Day1 题目一题目描述解题思路代码实现结果情况 题目二题目描述解题思路1.为什么想到二分查找2.如何解决分段单调的问题3.上面的写法发生错误,为什么呢4.如何解决重复的问题? 代码实现结果情况 总结 题目一
题目描述 题目来源记负均正 首先输入要输入的整数个数n然后输入n个整数。输出为n个整数中负数的个数和所有正整数的平均值结果保留一位小数。 0既不是正整数也不是负数不计入计算。如果没有正数则平均值为0。 数据范围 1≤n ≤2000 输入的整数都满足 ∣val∣≤1000 输入描述 首先输入一个正整数n 然后输入n个整数。 输出描述 输出负数的个数和所有正整数的平均值。 解题思路
1.边输入边统计负数个数
2.边输入边统计正整数个数注意0既不是正整数也不是负整数否则求平均会出问题
3.求平均时特殊处理除数为0的情况
代码实现
#includestdio.hint main()
{int cnt;int num[2000];int avr 0;int negtive 0;float sum 0;scanf(%d, cnt);for (int i 0; i cnt; i) {scanf(%d, num[i]);if (num[i] 0) {negtive;}if (num[i] 0) {avr;sum num[i];}}//输出负数个数|所有正数平均值结果保留一位小数if (avr 0) {//考虑除数为0的情况printf(%d 0.0\n, negtive);}else {printf(%d %0.1f\n, negtive, sum / avr);}return 0;
}
结果情况 符合题目要求问题解决。
题目二
题目描述 题目来源旋转数组的最小数字 有一个长度为 n 的非降序数组比如[1,2,3,4,5]将它进行旋转即把一个数组最开始的若干个元素搬到数组的末尾变成一个旋转数组比如变成了[3,4,5,1,2]或者[4,5,1,2,3]这样的。请问给定这样一个旋转数组求数组中的最小值。 解题思路
这道题目,我们可以采用一个方法:二分查找.
1.为什么想到二分查找
二分查找的本质的本质是二段性只要满足二段性的问题都可以使用二分查找求解。 在本题中二分查找的二段性体现在最小值左边的单调增最小值右边的单调增。且左边的元素都大于右边的元素。 2.如何解决分段单调的问题
很简单我们只需要比对arr[mid]与arr[0]和arr[numsSize - 1]的大小关系就可以
1.arr[mid] arr[0],说明mid此时落在最小值左边 2.arr[mid] arr[numsSize - 1]说明此时mid落在最小值的右边。
根据这一特性我们利用左闭右开型的二分查找就可以压缩出最小值所在的地方。
到此我们可以写下这样的一段代码
int minNumberInRotateArray(int* arr, int arrSize)
{int left 0;int right arrSize - 1;while(left right){int mid (left right) / 2;if(arr[mid] arr[0]){left mid 1;}else{right mid;}}return arr[left];
}
3.上面的写法发生错误,为什么呢
因为题目只是说到非降序所以不能排除出现重复的情况
4.如何解决重复的问题?
我们重点对数据的右边进行去重 1.如果发生arr[mid] arr[right],则和上面一样使得right mid。 2.如果发生arr[mid] arr[right],则和上面一样使得left mid 1。 3.如果发生arr[mid] arr[right],则说明发生重复对于重复我们将right–因为既然有重复那删掉其中一个可以保证至少还有1个。 这样不断删之后可以排除重复的影响最终的代码如下:
代码实现
int minNumberInRotateArray(int* arr, int arrSize)
{int left 0;int right arrSize - 1;while(left right){int mid (left right) / 2;if(arr[mid] arr[right])right mid;else if(arr[mid] arr[right])left mid 1;elseright - 1;}return arr[left];
}
结果情况 调整过后的代码符合题目要求,题目得到解决.
总结
今天的两道编程题整体来说难度不大。只不过有个新颖的点在于第二道题用到了二分查找。通过不断改进我们的思路一步一步完善最后将问题解决。 文章到这里就要告一段落了有更好的想法或问题欢迎评论区留言。 希望今天的练习能对您有所收获咱们下期见
