首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2281字,纯文字阅读大概需要4分钟。
内容图文
实践报告任选一题进行分析。内容包括:
- 实践题目;
- 问题描述;
- 算法描述;
- 算法时间及空间复杂度分析(要有分析过程);
- 心得体会(对本次实践收获及疑惑进行总结)。
1.实践题目:
7-2 改写二分搜索算法
2.问题描述:
设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。
3.算法描述:
void search(int a[] , int left , int right ,int x, int N){ int i , j , mid, k = 0; //k为标志位,标志是否查找到 while(left < right && k == 0){ mid = (left + right)/2 ; //中间数等于左右之和除以二 if(a[mid] == x) { //若中间数的值等于x(x在数组中) i = j = mid ; cout<<i<<" "<<j ; k = 1 ; } else{ //若中间数的值不等于x(x不在数组中) if(x < a[mid]) right = mid - 1 ; if(x > a[mid]) left = mid + 1 ; } } if(left >= right) { //若左边大于等于右边 if(a[left] == x) cout << left <<" "<<left ; //若左边的值等于x else { if(a[0] > x) { //若第一个数的值大于x i=-1,j=0; cout<<i<<" "<<j ; } if(a[N-1] < x) cout << N-1 <<" " << N ; for(int i = 0 ; i < N-1 ; i++){ if(a[i] < x && x < a[i+1]) cout<<i<<" "<<i+1 ; } } } } int main(){ int n , a[1001] , x , sum; cin >> n ; cin >> x ; for(int i = 0 ;i < n; i++){ cin >> a[i] ; } search(a , 0 ,n-1, x, n) ; //返回下标 }
此算法在二分搜索算法的基础上改写而成,首先定义变量,判断x是否在数组中(若在数组中则k=1,标志能够查找到x)。当x不在数组中时,用变量i和j分别保存小于x的最大元素的最大下标i和大于x的最小元素的最小下标j,跳出while循环只有满足条件“当left比right大”,数组中比x大的数为left所指向的数,比x小的数为right所指向的数,故返回i和j,并通过最后输出来达到题目要求。
4.算法时间及空间复杂度分析(要有分析过程)
时间复杂度:考虑最坏情况下,第一次循环 n/2,以此类推, 每一次循环时间复杂度减少一半,将搜索1*T(n/2)+O(1)次,即时间复杂度为O(logn)。
空间复杂度:常数级别,为O(1).
5.心得体会(对本次实践收获及疑惑进行总结)
①认真审题!不要把眼光局限在某一个地方。我们实验课编译运行第二题的时候,很长一段时间内一直处于编译没有错误,但是输出的结果却是1和2而非正确的输出4、5。我们俩以为是出了问题,结果想来想去改了的结果都不对。最后发现原来是cout要输出的值不是i和j而是n和n-1……
②编程题应该在一开始就想好整体的框架和布局,不然容易思路混乱。我们在一开始没有添加k为标志位,导致x小于所有数的时候一直不能跳出循环,PTA显示“部分正确”,后来添加k就所有情况完全正确了。
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。