| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 591 人关注过本帖
标题:求指点:用C++取值的算法!
只看楼主 加入收藏
ysh198877
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2013-9-25
结帖率:0
收藏
已结贴  问题点数:10 回复次数:7 
求指点:用C++取值的算法!
问题:
     假如我有一组数,例{1,2,3,4,5,6……},我想输入一个数,假如是2.3,然后输出是是数组里与它最靠近的那个数即“2”。

想法:用输入数2.3与每一个数做减法得到最小差值的绝对值,然后在检测那一个数与最小绝对差值的和或差等于输入值,最后输出这个值!这个想法太复杂了有没有更优化的算法,求指点!
搜索更多相关主题的帖子: 绝对值 检测 
2013-09-26 16:40
西安郑鑫
Rank: 7Rank: 7Rank: 7
来 自:陕西
等 级:黑侠
帖 子:163
专家分:624
注 册:2013-9-26
收藏
得分:4 
你给的那组数是排好了顺序的,所以可以利用二分法,把2.3插入,然后 a=2.3 - 直接前驱;b=直接后继 - 2.3; 然后比较a和b的大小得到最靠近的那个数。
根据提示你自己先研究下,动动脑筋。

Hello World!------鑫花璐放
2013-09-26 17:22
303770957
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:6
帖 子:838
专家分:2125
注 册:2005-9-10
收藏
得分:4 
楼上的思路不错,要是没有排好序可以先排序然后寻找。

♂ 死后定当长眠,生前何须久睡。♀
2013-09-26 17:27
西安郑鑫
Rank: 7Rank: 7Rank: 7
来 自:陕西
等 级:黑侠
帖 子:163
专家分:624
注 册:2013-9-26
收藏
得分:0 
回复 3楼 303770957
我也是新手一枚,望以后多多指教。

Hello World!------鑫花璐放
2013-09-26 17:34
ysh198877
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2013-9-25
收藏
得分:0 
回复 2楼 西安郑鑫
太抽象了说……
2013-09-26 17:38
西安郑鑫
Rank: 7Rank: 7Rank: 7
来 自:陕西
等 级:黑侠
帖 子:163
专家分:624
注 册:2013-9-26
收藏
得分:0 
回复 5楼 ysh198877
我的数据结构已经够烂了,目前只会写个冒泡排序,你貌似也不咋地
你的目标就是快速定位,用二分法第一次缩小查找范围为二分之一,第二次缩小查找范围为四分之一,第三次缩小查找范围为八分之一。。。。。。这个算法效率是指数倍的了。
给你举个例子
 1 2 3 4 5 6 7 8 9 10  取中间数5,和2.3比较,得在这个数列的左半边
 1 2 3 4 5             取中间数3,和2.3比较,得在这个数列的左半边
 1 2 3                 取中间数2,和2.3比较,得在这个数列的右半边
 2 3                   这个数列的元素为2个,直接插他俩中间就排好了
2就是2.3的直接前驱,3就是2.3的直接后继
程序代码:
a = 2.3 - 2;
b = 3 - 2.3;
if(a > b)
    cout << b << endl;
else cout << a << endl;


[ 本帖最后由 西安郑鑫 于 2013-9-26 17:57 编辑 ]

Hello World!------鑫花璐放
2013-09-26 17:55
ysh198877
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2013-9-25
收藏
得分:0 
回复 6楼 西安郑鑫
你说的我想过,问题是如何在最后到2和3之间的时候停止查值,输出来在做比较?
程序代码:
#include <iostream> 
double binsch( double k);
using  namespace std;
int main()
{
    cout<<"enter you number:"<<endl;
    double value_p;
    cin>>value_p;
    binsch(value_p);
    cout<<binsch(value_p)<<endl;

}
#define SIZE 10
int g_x[SIZE] = {1 ,2 ,3 ,4 ,5, 6 ,7 ,8, 9, 10};
double binsch( double k)
{
    int low=0,high=SIZE-1;
    while (low<=high)
    {
        int mid=(low+high)/2;      
        if (k==g_x[mid]  )        
            return g_x[mid];     
        else if(k<g_x[mid] )    
            high=mid-1;
        else low=mid+1;
    }
    return -1;                   //  返回-1
}
2013-09-26 19:15
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:4 
回复 7楼 ysh198877
如果你用C++,不要写二分查找,应当用std::lower_bound;

另外,题目中并没有说序列有序,因此只搜索一两次的话,先排序再二分是浪费时间。应该直接遍历:
最小差值 = fabs(a[0]-2.3);
最小差值索引 = 0;
for( int i=1; i<n; ++i )
{
    本次差值 = fabs(a[i]-2.3);
    if( 本次差值 < 最小差值 )
    {
        最小差值 = 本次差值;
        最小差值索引 = i;
    }
}
cout << a[最小差值索引] << endl;
2013-09-27 09:01
快速回复:求指点:用C++取值的算法!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.012923 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved