Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > C/C++/С#


Ответ
 
Опции темы Опции просмотра
Старый 17.01.2016, 17:30   #1 (permalink)
Alex1895
Новичок
 
Регистрация: 14.01.2016
Сообщений: 3
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Расстояние между точками

Даны два массива вещественных чисел, x и y. Их длина одинакова и равна n. Каждый (i-й) элемент массива x содержит абсциссу некоторой точки ri на плоскости, а элемент массива y - её ординату. Найти пару точек, расстояние между которыми минимально ( если таких пар несколько, можно выбрать любую). Напечатать номера точек и расстояние между ними.
Помогите пожалуйста решить задачу, на языке С++.
Alex1895 вне форума   Ответить с цитированием

Старый 17.01.2016, 17:30
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Я думаю, что проблему решать легче есть набраться больше информации

Минимальное расстояние между точками C++
Расстояние сближает ли?

Старый 02.03.2016, 23:00   #2 (permalink)
nikniknik2016
Новичок
 
Регистрация: 02.03.2016
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Код:
//для std::cout
#include <iostream>

//математические функции
#include <cmath>

//для NaN (переменная без значения)
#include <limits>

using namespace std;

namespace {

//исходные массивы данных (количество элементов в обоих должно совпадать)
const float x_coords[] = { 1,2,2,4,10 }; //координаты по оси X
const float y_coords[] = { 1,2,4,4,20 }; //координаты по оси Y

//определяем NaN
const float NaN = numeric_limits<float>::quiet_NaN();

//структура данных для хранения координат точки
struct Point
{
  float x;
  float y;
  Point(float x = NaN, float y = NaN) : x(x), y(y) {}

  //передача данных точки в поток вывода
  void to_std_cout() {
    std::cout << x << ',' << y;
  }
};

//получить неотрицательное значение
float abs_float(float f) {
    return f >= 0 ? f : -f;
}

//рассчет расстояния между точками
float calc_distance(const Point& a, const Point& b)
{
  /*
    рассчет расстояния осуществляется с помощью свойств прямоугольного треугольника,
    а точнее - квадрат гипотенузы равен сумме квадратов катетов
  */
  const float k0 = abs_float(a.x - b.x); //первый катет
  const float k1 = abs_float(a.y - b.y); //второй катет

  const float g2 = pow(k0, 2) + pow(k1, 2); //квадрат гипотенузы
  return sqrt(g2); //извлекаем квадратный корень и получаем расстояние между точками
}

void process()
{
  //здесь хранятся минимальное расстояние и точки, для которых это расстояние найдено
  Point min_a;
  Point min_b;
  float min_distance = NaN; //сначала минимальное расстояние не имеет значения
  /*
    определяем количество заданных точек
    для этого узнаем размер в байтах всего массива x_coords и делим на размер элемента в байтах
    если бы x_coords был передан в качестве указателя, то такой способ бы не подошел
  */
  const unsigned cnt_of_points = sizeof(x_coords) / sizeof(x_coords[0]);

  //запустим цикл для всех заданных точек
  for(unsigned i = 0; i < cnt_of_points; ++i)
  {
      /*
        i - индекс первой точки в паре
        j - индекс второй точки в паре
        вторую точку надо искать только из последующих точек (начиная с j = i + 1),
        т.к. предыдущие точки уже были рассчитаны
       */
      for(unsigned j = i + 1; j < cnt_of_points; ++j)
      {
        const Point a(x_coords[i], y_coords[i]); //первая точка
        const Point b(x_coords[j], y_coords[j]); //вторая точка
        const float distance = calc_distance(a, b); //расстояние между точками

        /*
          если минимальное расстояние не имеет значеня
          или
          текущее расстояние меньше минимального,
          то запоминаем текущее расстояние как минимальное,
          также запоминаем текущие точки
        */
        if(isnan(min_distance) || distance < min_distance)
        {
            min_distance = distance;
            min_a = a;
            min_b = b;
        }
      }
  }

  //отдаем полученную информацию на устройство вывода (консоль, например)
  std::cout << "min distance: " << min_distance << endl;
  std::cout << "point A: ";
  min_a.to_std_cout();
  std::cout << endl;
  std::cout << "point B: ";
  min_b.to_std_cout();
  std::cout << endl;
}

} //namespace

int main()
{
    process();
    return 0;
}
nikniknik2016 вне форума   Ответить с цитированием
Старый 02.03.2016, 23:06   #3 (permalink)
nikniknik2016
Новичок
 
Регистрация: 02.03.2016
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Здесь, правда, печатаются не номера точек, а их координаты

Вот код функции process, где еще печатаются номера точек:

Код:
void process()
{
  //здесь хранятся минимальное расстояние и точки, для которых это расстояние найдено
  Point min_a;
  Point min_b;
  float min_distance = NaN; //сначала минимальное расстояние не имеет значения
  unsigned min_i = -1;
  unsigned min_j = -1;
  /*
    определяем количество заданных точек
    для этого узнаем размер в байтах всего массива x_coords и делим на размер элемента в байтах
    если бы x_coords был передан в качестве указателя, то такой способ бы не подошел
  */
  const unsigned cnt_of_points = sizeof(x_coords) / sizeof(x_coords[0]);

  //запустим цикл для всех заданных точек
  for(unsigned i = 0; i < cnt_of_points; ++i)
  {
      /*
        i - индекс первой точки в паре
        j - индекс второй точки в паре
        вторую точку надо искать только из последующих точек (начиная с j = i + 1),
        т.к. предыдущие точки уже были рассчитаны
       */
      for(unsigned j = i + 1; j < cnt_of_points; ++j)
      {
        const Point a(x_coords[i], y_coords[i]); //первая точка
        const Point b(x_coords[j], y_coords[j]); //вторая точка
        const float distance = calc_distance(a, b); //расстояние между точками

        /*
          если минимальное расстояние не имеет значеня
          или
          текущее расстояние меньше минимального,
          то запоминаем текущее расстояние как минимальное,
          также запоминаем текущие точки
        */
        if(isnan(min_distance) || distance < min_distance)
        {
            min_distance = distance;
            min_a = a;
            min_b = b;
            min_i = i;
            min_j = j;
        }
      }
  }

  //отдаем полученную информацию на устройство вывода (консоль, например)
  std::cout << "min distance: " << min_distance << endl;
  std::cout << "point A: [" << min_i << "] ";
  min_a.to_std_cout();
  std::cout << endl;
  std::cout << "point B: [" << min_j << "] ";
  min_b.to_std_cout();
  std::cout << endl;
}
nikniknik2016 вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 02:15.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.