VPF::[Алгоритм] нахождение минимального расстояния

Default88

Дата 1.9.2009, 11:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 1.9.2009

Репутация: нет
Всего: нет

помогите реализовать задачу на делфи или же си.вобщем на клеточном поле заданы N точек.Найти точку до которой суммарное расстояние от заданных будет минимальным

psixtes

Дата 1.9.2009, 18:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 41
Регистрация: 8.4.2008
Где: Москва

Репутация: 2
Всего: 2

Вот задача на си++, если вам надо именно на си, то скорей всего надо просто убрать первые 3 строки, и ввод/вывод сделать через printf, scanf.
Я сделала через массивы. Хотя наверно лучше было бы класс создать..

Код


#include <iostream>
#include <math.h>
using namespace std;

int main(){
    int n; //кол-во всех точек на поле
    int k; //кол-во заданных точек 
    
    //Ввод всех точек
     cout<<"Vvedite kol-vo tochek na pole :"; cin>>n;
    double A[100][3]; //массив со всеми n точками. 
                      //в 0-ом столбце будет координата x, в 1-ом координата y,
                      //а во 2-ом сумма расстояний от данной точки до заданных
    for(int i=0; i<n; i++){
        cout<<"Point "<<i<<": "<<endl;
        cout<<"x="; cin>>A[i][0];
        cout<<"y="; cin>>A[i][1];
        cout<<"\n";
    }
    
    //Ввод точек для вычисления расстояния
    cout<<"Vvedite kol-vo tochek do kotoryh vy budete vychyslyat rasstoyanie:"; cin>>k;
    double B[100][2];
    for(int i=0; i<k; i++){
        cout<<"Point "<<i<<": "<<endl;
        cout<<"x="; cin>>B[i][0];
        cout<<"y="; cin>>B[i][1];
        cout<<"\n";
    }
    
    //Вычисление расстояний от всех точек до заданных в массиве B
    //Расстояния заносим в массив A ( в третий столбец)
    double rass=0;
    for(int i=0; i<n; i++){
        rass=0.0;
        for(int j=0; j<k; j++)
            if(i!=j) rass=rass+sqrt((A[i][0]-B[j][0])*(A[i][0]-B[j][0])+(A[i][1]-B[j][1])*(A[i][1]-B[j][1]));
        A[i][2]=rass;
    }
    
    //Вычисление минимального расстояния
    double min=A[0][2], minx, miny;
    for(int i=0; i<n; i++)
        if(A[i][2]<=min){ min=A[i][2]; minx=A[i][0]; miny=A[i][1]; }
        cout<<"Result:"<<endl;
        cout<<"Tochka x="<<minx<<" y="<<miny<<endl;
    
    return 0;
}

Default88

Дата 1.9.2009, 19:34 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 1.9.2009

Репутация: нет
Всего: нет

спасибо добрый человек))) как я понял это решение "в лоб",просто вычислив по формуле расстояние.а еще есть какой нить способ иной???заранее благодарен

Cheloveck

Дата 1.9.2009, 20:24 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1578
Регистрация: 26.7.2008
Где: Тула

Репутация: нет
Всего: 32

Цитата(Default88 @ 1.9.2009, 20:34

)

а еще есть какой нить способ иной?

есть кучи способов

--------------------

psixtes

Дата 1.9.2009, 20:48 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 41
Регистрация: 8.4.2008
Где: Москва

Репутация: 2
Всего: 2

Default88, ну да способов много, но расстояние вычислять надо в любом случае.
Чем вас этот не устраивает?

Default88

Дата 2.9.2009, 07:39 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 1.9.2009

Репутация: нет
Всего: нет

не меня этот способ очень даже устраивает.но мне просто еще надо придумать 2 способа решения помимо этого.вот я и думаю)))

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »