双重比较 [英] comparison between double
问题描述
嗨
我最近不得不在比赛中写一个小代码，但是我的代码被拒绝了因为它在一个测试用例中失败了。
问题是......我们给出了字符串向量....每个字符串
由1或2组成（12122 ; 0r" 2121" so ......）...我必须找到
该字符串，其中''1'的百分比最小。现在问题和
解决方案都是微不足道的，但我被告知将双倍与<
或>进行比较标志并不总是确保一个正确的解决方案，即它失败了
数字相差很小的值。
如果两个字符串有一个很小的百分比''1然后返回
最小的索引字符串（即
向量中的索引0的字符串与索引4相同，然后返回0。）
代码就是这样......
#include< iostream>
#include< ; string>
#include< sstream>
#include< vector>
using namespace std;
类选举{
public：
int visit（vector< string> like）;
};
int Elections :: visit（vector< string> like）
{
double min = 1000，temp = 0;
int index = 0;
for（int i = 0; i< like.size（）; i ++）
{
temp = 0;
for（int j = 0; j< like.size（）; j ++）
i f（如[i] [j] ==''1''）
temp ++;
temp = temp / like [i] .size（ ）;
if（min> temp）
{
min = temp;
index = i;
}
}
返回索引;
}
我的解决方案失败的测试用例是
{" 11122211222111111112121"，" 11122211222111111112121"，
" 11122211222111111112121"，" 11122211222111111112121" ;,
" 11122211222111111112121"，" 11122211222111111112121" ;,
" 11122211222111111112121"，" 11122211222111111112121" ;,
" 11122211222111111112121" ;，" 11122211222111111112121"}
根据系统测试他们返回9（索引而不是
0）上面的情况都是相同的字符串执行了。
我尝试在不同的编译器中运行上面的代码，并且我的答案是
得到的是正确的。 （即0）
我不确定，除了浮点比较模糊之外什么
其他原因可能导致两种不同的结果不同
编译器。
提前感谢
Somesh
Hi
I recently had to write a small code in a competition ,but my code was
rejected cause it failed in 1 of test cases.
The problm was .....we are given vector of strings....each string
consists of either 1 or 2("12122" 0r "2121" so on..)...i had to find
the that string where percentage of ''1'' is minimum.Now the problem and
solution both are trivial but i was told that comparing double with <
or > sign doesn''t ensure a correct solution always ie it fails for
number differing by a very small value.
Also if two string have indentical small percentage of ''1 then the
smallest indexed string is to be returned(ie string of index 0 in
vector is identical with index 4 then 0 is to be returned.)
The code goes something like this.....
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
using namespace std;
class Elections{
public:
int visit(vector<string> like);
};
int Elections::visit(vector<string>like)
{
double min=1000,temp=0;
int index=0;
for(int i=0;i<like.size();i++)
{
temp=0;
for(int j=0;j<like.size();j++)
if(like[i][j]==''1'')
temp++;
temp=temp/like[i].size();
if(min>temp)
{
min=temp;
index=i;
}
}
return index;
}
The test case for which my solution fails is
{"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121"}
The above case has all equal string yet it returned 9(index instead of
0) according to the system test they carried out.
I tried running the above code in a different compiler and the answer i
got was correct.(ie 0)
I am not sure , besides the floating point comparison ambiguity what
other reason could have led to different results in two different
compilers.
thanks in advance
Somesh
推荐答案
ch ************ @ gmail.com 写道：
嗨
我最近不得不在比赛中写一个小代码，但我的代码被拒绝因为它失败了在1个测试用例中。
问题是.....我们给出了字符串的向量....每个字符串
由1或2（12122组成） 0r2121所以...）...我必须找到那个字符串，其中''1'的百分比是最小的。现在问题和解决方案都是微不足道但我被告知比较双<
或>标志并不总是确保一个正确的解决方案，即它的数量不同，因为它的数值相差很小。
如果两个字符串有一个非常小的百分比''1那么
返回最小的索引字符串（即
向量中的索引0的字符串与索引4相同，然后返回0。）
代码就像这样...... ......
＃include< iostream>
#include< string>
＃include< sstream>
＃include< vector>
使用命名空间std;
类选举{
公开：
int visit（vector< string> like）;
};
int Elections :: visit（vector< string> like）
{min / = double min = 1000，temp = 0;
int index = 0;
for（int i = 0; i< like.size（）; i ++）
{
temp = 0;
for（int j = 0; j< like.size（）; j ++）
if（如[i] [j] ==''1''）
temp ++;
temp = temp / like [i] .size（）;
if（min&g t; temp）
{
min = temp;
index = i;
}
}
返回索引;
}
我的解决方案失败的测试用例是
{" 11122211222111111112121"，" 11122211222111111112121"，
" 11122211222111111112121"，" 11122211222111111112121" ，
" 11122211222111111112121"，" 11122211222111111112121"，" 11122211222111111112121"，" 11122211222111111112121"，
" 11122211222111111112121"，" 11122211222111111112121"}
上面的情况都是相同的字符串，但它根据他们执行的系统测试返回9（索引而不是
0）。
我尝试在不同的编译器中运行上面的代码，答案我<得到的是正确的。（即0）
我不确定，除了浮点比较模糊之外，其他原因可能导致两种不同的结果不同
编译器。
提前感谢
Somesh
Hi
I recently had to write a small code in a competition ,but my code was
rejected cause it failed in 1 of test cases.
The problm was .....we are given vector of strings....each string
consists of either 1 or 2("12122" 0r "2121" so on..)...i had to find
the that string where percentage of ''1'' is minimum.Now the problem and
solution both are trivial but i was told that comparing double with <
or > sign doesn''t ensure a correct solution always ie it fails for
number differing by a very small value.
Also if two string have indentical small percentage of ''1 then the
smallest indexed string is to be returned(ie string of index 0 in
vector is identical with index 4 then 0 is to be returned.)
The code goes something like this.....
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
using namespace std;
class Elections{
public:
int visit(vector<string> like);
};
int Elections::visit(vector<string>like)
{
double min=1000,temp=0;
int index=0;
for(int i=0;i<like.size();i++)
{
temp=0;
for(int j=0;j<like.size();j++)
if(like[i][j]==''1'')
temp++;
temp=temp/like[i].size();
if(min>temp)
{
min=temp;
index=i;
}
}
return index;
}
The test case for which my solution fails is
{"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121",
"11122211222111111112121", "11122211222111111112121"}
The above case has all equal string yet it returned 9(index instead of
0) according to the system test they carried out.
I tried running the above code in a different compiler and the answer i
got was correct.(ie 0)
I am not sure , besides the floating point comparison ambiguity what
other reason could have led to different results in two different
compilers.
thanks in advance
Somesh
试试这个
#define SMALL_NON_ZERO 1e-16D / *或其他小的东西* / b $ b #define DBL_EQ（X，Y）（（X） - （Y）< SMALL_NON_ZERO）/ * X == Y * /
#define DBL_LT（X，Y）（（X） - （Y）> SMALL_NON_ZERO）/ * X> Y * /
#define DBL_GT（X，Y）（（Y） - （X）> SMALL_NON_ZERO）/ * Y> X * /
只是一个想法，
我只将它用于DBL_EQ，但假设它应该扩展到>和<还有。
try this
#define SMALL_NON_ZERO 1e-16D /* or something else small */
#define DBL_EQ(X,Y) ( (X) - (Y) < SMALL_NON_ZERO ) /* X == Y */
#define DBL_LT(X,Y) ( (X) - (Y) > SMALL_NON_ZERO ) /* X > Y */
#define DBL_GT(X,Y) ( (Y) - (X) > SMALL_NON_ZERO ) /* Y > X */
just an idea,
I''ve used this only for DBL_EQ, but assume it should extend to > and < also.
Aaron Gage写道：
Aaron Gage wrote:
＃定义SMALL_NON_ZERO 1e-16D / *或其他小* *
#define DBL_EQ（X，Y）（（X） - （Y）< SMALL_NON_ZERO）/ * X == Y * /
＃定义DBL_LT（X，Y）（（X） - （Y）> SMALL_NON_ZERO）/ * X> Y * /
#define DBL_GT（X，Y）（（Y） - （X）> SMALL_NON_ZERO）/ * Y> X * /
只是一个想法，
我只将它用于DBL_EQ，但假设它应该扩展到>和<还有。
#define SMALL_NON_ZERO 1e-16D /* or something else small */
#define DBL_EQ(X,Y) ( (X) - (Y) < SMALL_NON_ZERO ) /* X == Y */
#define DBL_LT(X,Y) ( (X) - (Y) > SMALL_NON_ZERO ) /* X > Y */
#define DBL_GT(X,Y) ( (Y) - (X) > SMALL_NON_ZERO ) /* Y > X */
just an idea,
I''ve used this only for DBL_EQ, but assume it should extend to > and < also.
感谢您的回复
还有一件事......您认为SMALL_NON_ZERO应该有多小
是....并且这对代码的可移植性有任何影响，即
是编译器还是平台依赖。
还有一种方法可以避免这些近似值吗？
是否有运算符允许按位操作双倍??也许
那些可以避免需要近似值。
问候
Somesh
Thanks for the reply
just one more thing.....how small do u think SMALL_NON_ZERO should
be....and does this have any bearing on the portability of the code ie
will it be compiler or platform dependent.
also is there a way to avoid these approximations??
are there operators that allow bitwise operations on double??maybe
those can avoid the need to make approximations.
regards
Somesh
Aaron Gage写道：
Aaron Gage wrote:
试试这个
#define SMALL_NON_ZERO 1e-16D / *或其他小的东西* /
#define DBL_EQ（X ，Y）（（X） - （Y）< SMALL_NON_ZERO）/ * X == Y * /
try this
#define SMALL_NON_ZERO 1e-16D /* or something else small */
#define DBL_EQ(X,Y) ( (X) - (Y) < SMALL_NON_ZERO ) /* X == Y */
#define DBL_EQ（X，Y）（fabs（ （X） - （Y））< SMALL_NON_ZERO）/ * X == Y * /
****
-
Karl Heinz Buchegger
kb ****** @ gascad.at
这篇关于双重比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
