百度推广网站备案,进货渠道网,网络营销软件,湖南网络营销#xff08;请先看置顶博文#xff09;本博打开方式#xff0c;请详读_liO_Oil的博客-CSDN博客_怎么把androidstudio卸载干净
一、题目大意
查找最接近的元素#xff08;分治法/二分查找#xff09;#xff1a;在一个非降序列中#xff0c;查找与给定值最接近的元素。…请先看置顶博文本博打开方式请详读_liO_Oil的博客-CSDN博客_怎么把androidstudio卸载干净
一、题目大意
查找最接近的元素分治法/二分查找在一个非降序列中查找与给定值最接近的元素。
[输入]
第一行包含一个整数n为非降序列长度。
第二行包含n个整数为非降序列各元素。
第三行包含一个整数m为要询问的给定值个数。1 m 10000。
接下来m行每行一个整数为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间
[输出]
m行每行一个整数为最接近相应给定值的元素值保持输入顺序。若有多个值满足条件输出最小的一个
input
3
2 5 8
2
10
5
output
8
5
二、主要思想 我认为这道题考察的知识点有两个一个是递归另一个是二分查找。这个二分查找和通常的二分查找不一样题目要求查找最接近的所以这就给题目求解带来了很大的难度。我在写程序时先在纸上模拟用到了很多的if和else判断语句对可能出现的各种情况进行细分最后实现了一个finder函数用于在递增数列中查找与要查找的数字最近的数字。 关于二分
在写代码的时候遇到一个问题就是关于long long的使用问题
1、long long定义时如果还用scanf()函数输入编译器不报错但是输入的数字完全改变。
针对这个问题我也找到了相应的解决办法请看这篇文章C语言CED与long long相关的知识_liO_Oil的博客-CSDN博客
三、具体实现
#includestdio.h
#includestdlib.h
int a[1000];//存放升序排列的一列数字
int b[1000];//存放要找的数字
int m;//输入要查找的数的个数
long long finder(int mx, int mn, int mid, int j)//
{//第一步区分查找的这个数是否在开区间内if (b[j] a[mn] || b[j] a[mx])//不在{//对内部进行细分到底是比最小的还小还是比最大的还大if (b[j] a[mn]) //比最小的还小printf(%d\n, a[mn]);else//比最大的还大printf(%d\n, a[mx]);}else//位于最小的数字和最大的数字之间{//根据mid来分比mid大还是比mid小还是和mid相等if (a[mn]b[j] b[j]a[mid])//比mid小{if (mid - mn ! 1){mx mid - 1;//将mx替换为midmid (mn mx) / 2;//重新计算mid下标finder(mx, mn, mid, j);}else{if (a[mid] - b[j]b[j] - a[mn])//比较距离printf(%d\n, a[mn]);else if (a[mid] - b[j]b[j] - a[mn])printf(%d\n, a[mid]);elseprintf(%d %d\n, a[mn], a[mid]);}}else if (a[mid]b[j] b[j]a[mx])//比mid大{if (mx - mid ! 1){mn mid;//重新计算mnmid (mn mx) / 2;//重新计算mid下标finder(mx, mn, mid, j);}else{if (b[j] - a[mid]a[mx] - b[j])printf(%d\n, a[mx]);else if (b[j] - a[mid]a[mx] - b[j])printf(%d\n, a[mid]);elseprintf(%d %d\n, a[mid], a[mx]);}}else//和mid相等printf(%d\n, b[j]);}return 0;
}
int main()
{int j 0;//用作函数循环的int n;//输入非降序序列的长度scanf(%d, n);for (int i 0; in; i) //循环输入n个数字scanf(%d, a[i]);scanf(%d, m); //输入要查询的数字个数for (int i 0; im; i) //循环输入要查找的数存在b[i]中scanf(%d, b[i]);int mx n - 1, mn 0;int mid (mx mn) / 2;for (j 0; jm; j)//循环调用函数把b[j]中存储的所有要找的数字找完finder(mx, mn, mid, j);system(pause);return 0;}在写完这个程序后我用大量的数据科学的测试方法边缘测试进行测试结果是没有发现问题如果大家在测试过程中发现问题请及时留言欢迎
