Представление чисел с плавающей запятой в двоичном формате

Question

Я работаю над проблемой из трещин. Кодирование Интервью, в котором спрашивается: учитывая двумерный граф с точками на нем, найдите линию, которая пропускает наибольшее количество точек.

Решение: провести бесконечную линию между каждыми двумя точками и, используя хеш-таблицу, отслеживать, какая линия наиболее распространена. Чтобы найти наиболее распространенную строку, мы перебираем все сегменты линии, используя хеш-таблицу, чтобы подсчитать количество раз, когда мы видели каждую строку.

Автор далее говорит, что есть осложнение: «мы определяем две линии равными, если линии имеют один и тот же наклон и y-перехват. Затем мы также используем линии на основе этих значений (в частности, на основе наклона). Проблема с числами с плавающей запятой не всегда может быть точно представлена ​​в двоичном формате. Мы разрешаем это, проверяя, находятся ли два числа с плавающей запятой в пределах значения epsilon друг от друга ».

Вот где я в замешательстве. Даже если наклон является плавающей точкой, мы не можем использовать это как хэш-ключ? Если да, почему бы не просто набросить наклон как строку? Почему нам нужно вводить в хэширование кода на основе ключей, которые находятся внутри epsilon друг от друга?

Answer 1

Посмотрите на следующий пример, написанный на C++.

#include <stdio.h> 
#include <stdlib.h> 

int main() { 
    double a=10.0; 
    double b=a/3; 
    double c=(b-3)*3; 

    printf("a: %20.50lf\n", a); 
    printf("b: %20.50lf\n", b); 
    printf("c: %20.50lf\n", c); 
    return 0; 
} 

«c» должно быть равно 1, но из-за округления с плавающей запятой вышеуказанный код производит следующее.

a: 10.00000000000000000000000000000000000000000000000000 
b: 3.33333333333333348136306995002087205648422241210938 
c: 1.00000000000000044408920985006261616945266723632812 

Answer 2

1. алгоритм вы описываете не нуждается в какой-либо хэш-таблицу.

   Вместо этого используйте гистограмму. Этот ответ является точным примером этой задачи в C++

   • Given n points on a 2D plane, find the maximum number of points that lie on the same straight line

2. Если вы все еще хотите использовать поплавки в качестве ключей

   Затем вам нужно усечь их, чтобы они могли сравниваться как двоичные. Для примера рассмотрим предположим, что вы получили (при условии, C++ синтаксис):

   const float da=1.5*M_PI/180.0; // [rad] comparison precision 
   float a; 
   a=atan2(dy,dx); // [rad] your line angle from deltas 
   a=floor(a/da); // [da] truncated angle 
   

   Где dx,dy ваша линия дельта и da ваш угол сравнения точности. Теперь, чтобы получить доступ к float a в двоичной форме для хэширования целей вы можете просто сделать это:

   union { float f32; DWORD u32; } b; 
   b.f32=a; 
   // here b.u32 is your hash key