Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Алгоритм] нахождение минимального расстояния


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

Автор: psixtes 1.9.2009, 18:11
Вот задача на си++, если вам надо именно на си, то скорей всего надо просто убрать первые 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
спасибо добрый человек))) как я понял это решение "в лоб",просто вычислив по формуле расстояние.а еще есть какой нить способ иной???заранее благодарен

Автор: Cheloveck 1.9.2009, 20:24
Цитата(Default88 @  1.9.2009,  20:34 Найти цитируемый пост)
а еще есть какой нить способ иной?

http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D1%83%D1%82%D0%B8#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D1.8B

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

Автор: Default88 2.9.2009, 07:39
не меня этот способ очень даже устраивает.но мне просто еще надо придумать 2 способа решения помимо этого.вот я и думаю)))

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)