C++ 函数二分法
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了C++ 函数二分法,现在分享给大家,供学习和参考。文章包含838字,纯文字阅读大概需要3分钟。
教程信息
学习目标
理解二分法的算法和实现
场景说明:
二分法猜数游戏规则说明:
一个 [1, 100] 内的数字,只需猜 7 次: >50? 是。[1, 100] 二分,中位数 50,下一步猜 [51, 100] >75? 否。[51, 100] 二分,中位数 75,下一步猜 [51, 75] >63? 否。[51, 75] 二分,... >56? 否。[51, 63] 二分, >53? 是。 >54? 否。 =54? 是。 这个数是 54
尝试用代码实现这个逻辑。
实现代码:
// 二分法 搜索函数 /* 例子 56 (1+100)-2=50.5-50 小 (51+100)-2=75.5-75大 (51+74):2=62.5-62大 (51+61) -2=56 */ int search(int b[],int len,int key) { int high,low; high=len-1; low=0; int mid=len/2; while(high>=low) { mid=(high+low)/2; cout<<b[mid]<<endl; if(b[mid]==key) // 如果想等,则是找到对应的数值 return mid; else if(b[mid]>key) /* 如果中间元素大于目标值, 说明最目标值小于中间元素, 则最大值需要调整为中间元素-1,继续搜索。 */ high=mid-1; else /* 如果中间元素小于目标值, 说明最目标值大于中间元素, 则最小值需要调整为中间元素+1,继续搜索。 */ low=mid+1; } return 0; } // 主函数 main() { const int max=100; int a[max],n; for(int i=0; i<max; i++) a[i]=i+1; do { cin>>n; } while(n<1||n>100); if(search(a,max,n)) cout<<"成功!"; else cout<<"失败!"; return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供C++ 函数二分法的全部内容,希望教程文章能够帮你了解学习C++ 函数二分法,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaocpp-87.html
发布时间:2023-11-21
更新时间:2024-01-08