0

Мне необходимо найти некоторую неизвестную, заранее заданную точку в трехмерном пространстве, за наименьшее количество попыток, полагаясь только на функцию, которая может возвращать расстояние от любой переданной вами в нее точки до искомой. Для решения задачи сначала имплементируйте функцию f, которая, принимая координаты любой точки s(x, y, z), возвращает расстояние между этой точкой и условно неизвестной, предварительно произвольно сгенерированной вами точкой r(x, y, z), где x, y, и z могут быть любыми целыми числами между 0 и 100. Например, для произвольно сгенерированной точки r(0, 0, 10), и переданной в функцию точки s(0, 0, 0), результат работы функции будет следующим: f(s) = 10 // расстояние между s(0, 0, 0) и r(0, 0, 10) равно 10 Далее реализуйте сам алгоритм решения задачи. Алгоритм должен находить координаты произвольно сгенерированной точки за наименьшее количество вызовов функции f. К решению приложите текстовое описание работы алгоритма. Алгоритм поиска расстояния есть

function searchDist(base, rand) {
        return Math.sqrt(((rand.x - base.x) ** 2) + ((rand.y - base.y) ** 2) + ((rand.z - base.z) ** 2));
    }

Нужно сделать алгоритм (функцию)поиска искомой точки . Может у кого-то есть какие-то идеи ? Написано должно быть на чистом JS Мои попытки решить это :

nextPoint(basePoint, randPoint);
function nextPoint(base, rand) {
    let prevDis = searchDist(basePoint, randPoint);
    base.x++;
    base.y++;
    base.z++;
    console.log(base);
    const nextDis = searchDist(base, rand);
    console.log(prevDis, nextDis);
    if (nextDis < prevDis) {
        if ((nextDis ^ 0) === nextDis) {
            onePoint(base, rand);
            return(base);
        }
        nextPoint(base, rand);
    }else{
        console.log('stop');
    }
}

function onePoint(base, rand) {
    let prevDis = searchDist(base, rand);
    base.x++;
    let nextDis = searchDist(base, rand);
    console.log(prevDis, nextDis);
    console.log(base, rand);
    if ((nextDis ^ 0) === nextDis) {
        if(nextDis == 0){
            return base;
        }else{
            onePoint(base, rand);
        }
    } else {
        base.x--;
        prevDis = searchDist(base, rand);
        base.y++;
        nextDis = searchDist(base, rand);
        if ((nextDis ^ 0) === nextDis) {
            if(nextDis == 0){
                return base;
            }else{
                onePoint(base, rand);
            }
        } else {
            base.y--;
            prevDis = searchDist(base, rand);
            base.z++;
            nextDis = searchDist(base, rand);
            if ((nextDis ^ 0) === nextDis) {
                if(nextDis == 0){
                    return base;
                }else{
                    onePoint(base, rand);
                }
            }
        }
    }
}
11
  • Ну и где ваши попытки решать задачу? Которая по сути сводится к решению системы уравнений. Например, две точки определяют в общем случае окружность, на которой лежит искомая точка.
    – Harry
    2 авг 2022 в 7:07
  • Сейчас добавлю. Но там ничего особо не получилось
    – SkyFull
    2 авг 2022 в 7:09
  • Алгоритм прост как палка, берём 4 точки, строим на них сферы с найденным радиусами (4 вызова функции) и находим их точку пересечения. Всё.
    – Alexey Ten
    2 авг 2022 в 7:16
  • Не до конца понял как это реализовать
    – SkyFull
    2 авг 2022 в 7:19
  • 1
    Исходя из того, что точка в кубе с положительными координатами, кажется, хватит и трех вызовов...
    – Harry
    2 авг 2022 в 7:31

2 ответа 2

4

Задачу можно решить вызвав тестовую функцию один раз.

Требуется отыскать точку с целыми координатами из множества [0, 100] × [0, 100] × [0, 100]. Существует точка в пространстве такая что расстояния от неё до всех целых точек из куба со стороной 100 различны. Ниже подсчитывается количество различных квадратов расстояний от всех точек куба до до точки (100, 5100, 510100) и сравнивается с числом точек в кубе:

const s = new Set();

const xs = 100;
const ys = 5100;
const zs = 510100;
let c = 0;
for (let x = 0; x < 101; ++x) {
    for (let y = 0; y < 101; ++y) {
        for (let z = 0; z < 101; ++z) {
            ++c;
            s.add((xs - x) ** 2 + (ys - y) ** 2 + (zs - z) ** 2);
        }
    }
}
console.log(s.size, c);

Как я отыскал такую точку пусть пока побудет секретом. Имея её мы можем различать любые точки в кубе.

В коде ниже searchR получает на вход функцию f и вызывает её один раз для точки (100, 5100, 510100). Полученное расстояние возводится в квадрат и округляется - мы ищем сумму квадратов разниц координат, она должна быть целой. Точности вещественных чисел JavaScript хватает чтобы восстановить квадрат расстояния точно. Затем для всех точек куба вычисляются квадраты расстояний. Если очередной квадрат совпадает со значением полученным на предыдущем шаге, точка найдена. Ещё раз напомню что эти квадраты различны для всех точек куба.

const makeP = (x, y, z) => ({x: x, y: y, z: z});

const dist = (p, q) =>
    Math.sqrt((p.x - q.x) ** 2 + (p.y - q.y) ** 2 + (p.z - q.z) ** 2);

const makeF = r => p => dist(r, p);

const searchR = f => {
    const xs = 100;
    const ys = 5100;
    const zs = 510100;
    const s = makeP(xs, ys, zs);
    const d = f(s);
    const d2 = Math.round(d ** 2);
    for (let x = 0; x < 101; ++x) {
        for (let y = 0; y < 101; ++y) {
            for (let z = 0; z < 101; ++z) {
                if ((xs - x) ** 2 + (ys - y) ** 2 + (zs - z) ** 2 === d2) {
                    return makeP(x, y, z);
                }
            }
        }
    }
};

const randomX = () => Math.floor(101 * Math.random());

const randomP = () => makeP(randomX(), randomX(), randomX());

const main = () => {
    const r = randomP();
    console.log(r);
    const f = makeF(r);
    console.log(searchR(f));
};

main();

P.S. Спасибо автору вопроса за прекрасную задачу!

P.P.S. Как отыскать точку (100, 5100, 510100)? Одномерная задача: надо выбрать число, все расстояния от которого до чисел из [0, 100] различны. Минимальное положительное такое число 100 - можно угадать. Двумерная задача: надо выбрать ys такое что расстояния от [100, ys] до всех точек квадрата [0, 100] × [0, 100] различны. Линейный поиск отыщет минимальное ys = 5100. Трёхмерную задачу решаем для точки [100, 5100, zs] и куба [0, 100] × [0, 100] × [0, 100]. Снова линейный поиск. Довольно быстрый, кстати, несмотря на большую оценку числа операций - 510 * 109.

Возможно есть точки с меньшей нормой. Маленькая норма - хорошо. Надо различать расстояния, а разрядность вещественных чисел ограничена (напомню, что поиск ведётся по корню квадратному).

Отличная задача: найти "радарную" точку с минимальной нормой (1) и доказать что это она (2). Предъявить эффективный алгоритм.

2

Вроде бы так (код не пишу) — пользуемся ограничениями задачи, и находим расстояние до искомой точки от точки (0,0,0) (пусть L), от точки (0,0,100) (обозначим Lz) и от точки (0,100,0) (обозначим Ly).

Тогда если я и Wolfram не ошиблись, координаты точки равны

введите сюда описание изображения

введите сюда описание изображения

введите сюда описание изображения

Ну, или взять y и z выше, а x найти как

введите сюда описание изображения

"По-моему, так" (с) Пух

Ну, код несложный, напишите сами :)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.