Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Многомерные массивы

Автор: Снежанна 9.12.2008, 21:00

Здравствуйте, Уважаемые программисты! Я открыла для себя удивительный язык С++ совсем недавно. Да некоторых пор проблем не возникало (язык легко дается). Но вот задали задачку, к которой я не знаю, с какой стороны подобраться... Звучит она так: Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна! Единственное, что я точно знаю, без многомерных массивов здесь не обойтись. Очень надеюсь на вашу помощь в решении этого вопроса! Заранее благодарна!

Автор: kosmonaFFFt 9.12.2008, 21:20

Можно и без многомерных, обычного вектора (который std::vector) хватит.

Автор: bsa 10.12.2008, 16:36

В принципе, действительно нет необходимости в многомерном массиве... Достаточно 2 одномерных:
1. массив координат точек (на N элементов)
2. массив сумм расстояний для каждой точки (на N элементов)
Что делать - идешь по первому массиву и считаешь сумму расстояний для i-ой точки и записываешь в i-ый элемент второго массива. Затем находишь во втором массиве минимальный элемент - его индекс позволит узнать точку, которой он соответствует.

Автор: Garcian 10.12.2008, 20:10

А, мы такое делали.. Ток не вышло ничего)

Автор: Снежанна 10.12.2008, 20:14

Впринципе понятно... Только с геометрией не все хорошо, smile

Автор: GoldFinch 10.12.2008, 20:39

случай клинический...
есть множество точек {(x,y)}
искомая точка это (Xсредн,Yсредн)

какие многомерные массивы... какие std::vector....
математику учить в школе надо было

Добавлено через 1 минуту и 20 секунд

Цитата(bsa @ 10.12.2008, 16:36

)

Что делать - идешь по первому массиву и считаешь сумму расстояний для i-ой точки и записываешь в i-ый элемент второго массива. Затем находишь во втором массиве минимальный элемент - его индекс позволит узнать точку, которой он соответствует.

бред какой %)

Автор: Снежанна 10.12.2008, 20:52

Может и бред... раздел для новичков) smile

Автор: GoldFinch 10.12.2008, 20:58

Снежанна, какой пример? как среднее арифметическое считать? я как-то забыл как это делается, потому не могу написать, и учебника за 5й класс под рукой нету =\

Автор: Снежанна 10.12.2008, 21:13

Мне понять как это в программе осущетвить. А среднее арифмитическое могу напомнить smile

Автор: J0ker 10.12.2008, 22:45

Цитата(Kallikanzarid @ 10.12.2008, 21:56

)

А вот из-за такой, как гражданка С. один мой знакомый проводит свое свободное время, делая чужую домашнюю работу. Бедный идиот :'-(

а может он не просто так smile

Цитата(GoldFinch @ 10.12.2008, 20:39

)

искомая точка это (Xсредн,Yсредн)

что-то мне это видится более чем не очевидно smile

Добавлено через 8 минут и 28 секунд
или вы имели ввиду средневзвешенное?

Автор: bsa 11.12.2008, 12:31

Цитата(Снежанна @ 10.12.2008, 20:14)

Впринципе понятно... Только с геометрией не все хорошо, smile

расстояние между двумя точками считается, как квадратный корень из суммы квадратов разностей координат:

Код

sqrt( pow(x1 - x2, 2.0) + pow(y1 - y2, 2.0) );

Добавлено через 2 минуты и 31 секунду

M
bsa

Сообщения, не относящиеся к теме, удалил

Автор: Dmi3ev 11.12.2008, 13:09

когда-то писал, может пригодится:
тут класс точки и класс прямой, прямая может возвращать расстояние между точками, которыми задана, tg угла наклона и смещение, те короче
y=kx+b, она может вернуть k, b, а также расстояние между точками, которыми задана...
<myline.h>

Код


#ifndef MYLINE_H
#define MYLINE_H
#include <mypoint.h>
#include <math.h>
class MyLine
{
public:
 MyLine (MyPoint A, MyPoint B){ p1=A; p2=B;};
 double Getk()
  {
   if ((p1.Getx()-p2.Getx())!=0)
     k=(p1.Gety()-p2.Gety())/(p1.Getx()-p2.Getx());//tg
   return k;
  };
 double Getb()
  {
   if ((p1.Getx()-p2.Getx())!=0)
     b=p1.Gety()-((p1.Gety()-p2.Gety())/(p1.Getx()-p2.Getx()))*p1.Getx();//free member
   return b;
  };
 double Getr()//Gip
  {
   r=sqrt(pow((p1.Getx()-p2.Getx()), 2)+pow((p1.Gety()-p2.Gety()), 2));
  }; 
 ~MyLine (){};
private:
 MyPoint p1, p2;
 double k, b, r;
};
#endif

а это <mypoint.h>

Код


#ifndef MYPOINT_H
#define MYPOINT_H
class MyPoint
{
public:
MyPoint(double a=0.0, double b=0.0){x=a; y=b;};
void Set(double a, double b){x=a; y=b;};
double Getx(){return x;};
double Gety(){return y;};
~MyPoint(){};
private:
double x, y;
};
#endif

Автор: GoldFinch 11.12.2008, 13:57

Признаю я был не прав. Среднее арифметическое там не подходит хотя бы потому что оно выдает точку не обязательно принадлежащую к множеству заданных точек.
Однако я заметил что C++ убило мозг участников форума, т.к. никто так и не попытался решить задачу математически.
При беглом анализе, очевидно что для вырожденного случая с 2я точками обе точки являются решениями, также точки могут совпадать друг с другом. Для вырожденного случая когда все точки находятся на одной прямой, если число точек нечетно, решением является "средняя" точка, если четно - две "средние" точки. Я не проверял, но с большой долей вероятности "средней" точкой является точка ближайшая к центру масс, т.е. к среднему арифметическому координат точек.

Автор: Dmi3ev 11.12.2008, 14:03

Код


Однако я заметил что C++ убило мозг участников форума

Наоборот. Мозг ищет более рациональное решение. Мне, допустим, легче сначала решить эту задачу программно в лоб, а потом, если время позволит произвести анализ решения.

Автор: GoldFinch 11.12.2008, 14:19

Модератор: Сообщение скрыто.

Автор: J0ker 11.12.2008, 18:36

Цитата(GoldFinch @ 11.12.2008, 13:57

)

точка ближайшая к центру масс, т.е. к среднему арифметическому координат точек.

среднеарифметическое и центр масс необязательно совпадают, потому, что это разные вещи

Автор: GoldFinch 11.12.2008, 18:57

J0ker, при одинаковых массах совпадают. Я привел такую формулировку для удобного перехода от более очевидного физического подхода к формулировке задачи к менее очевидному математическому.

upd: убрал очипятку) поспешишь....

Автор: Снежанна 11.12.2008, 20:24

Спасибо, bsa, Dmi3ev (хотя я не совсем представляю, как воспользоваться <mypoint.h>). Также, мне необхадимо указать все некорректные ситуации. Что это значит?

Автор: J0ker 11.12.2008, 20:27

Цитата(GoldFinch @ 11.12.2008, 18:57

)

J0ker, при одинаковых саммах совпадают

при одинаковых массах точек
тогда да

Добавлено через 1 минуту и 55 секунд
но это интуитивное решение... надо-бы как-то подкрепить док-вом... впрочем я думаю оно легко выводится и так оно и будет

Автор: bsa 11.12.2008, 22:06

Цитата(Снежанна @ 11.12.2008, 20:24)

Также, мне необхадимо указать все некорректные ситуации. Что это значит?

Это значит, что ты должна указать все ситуации, когда твоя программа будет работать некорректно. Например, если есть более одной искомой точки (частные варианты: все точки в одном месте, всего 2 точки, все точки в вершинах правильных N-угольков), или всего одна точка в массиве.

Автор: Dmi3ev 11.12.2008, 22:54

Столько споров, давайте посмотрим, я набросал решение (оно не идеально, но...):

Код


//---------------------------------------------------------------------------
#include <mypoint.h>
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

//---------------------------------------------------------------------------


int main()
{
MyPoint A[10];
double min;
double sr[10];
randomize();
for (int i=0; i<10; i++)
 {
  A[i].Set((random(100)-50), (random(100)-50));
  cout<<"A["<<i<<"]"<<"("<<A[i].Getx()<<", "<<A[i].Gety()<<")"<<endl;
 }
for (int i=0; i<10; i++)
 {
  sr[i]=0;
  for (int j=0; j<10; j++)
   {
    if (j!=i)
     {
      sr[i]+=sqrt(pow((A[i].Getx()-A[j].Getx()),2)+pow((A[i].Gety()-A[j].Gety()),2));
     }
   }
 }
min=sr[0];
int mi=0;
for (int i=1; i<10; i++)
 {
  if (sr[i]<min)
   {
    min=sr[i]; mi=i;
   }
 }
cout<<endl<<"Answer: "<<endl;
cout<<"A["<<mi<<"]"<<"("<<A[mi].Getx()<<", "<<A[mi].Gety()<<")"<<endl;
cout<<"Summ for this point="<<min;
return 0;
}
//---------------------------------------------------------------------------

Центр масс имеет место быть ))) По-моему мнению. А вото mypoint.h

Код


#ifndef MYPOINT_H
#define MYPOINT_H
class MyPoint
{
public:
MyPoint(double a=0.0, double b=0.0){x=a; y=b;};
void Set(double a, double b){x=a; y=b;};
double Getx(){return x;};
double Gety(){return y;};
~MyPoint(){};
private:
double x, y;
};
#endif

Добавлено через 7 минут и 27 секунд
хотя алгоритм нахождения центра масс фигуры, а потом сравнивание этого центра с каждой точкой (какая ближе)...
хз, по-моему, так проще, хотя, может, прав не я... smile

Автор: Dmi3ev 11.12.2008, 23:48

Вообщем, как говорится, ЧТД
Решил двумя способами, 1-сумма расстояний, 2-расстояние до центра масс, ответы совпадают )))

Код


//---------------------------------------------------------------------------
#include <mypoint.h>
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

//---------------------------------------------------------------------------


int main()
{
MyPoint A[10];
MyPoint Cm;
double xcm, ycm;
double min;
double sr[10];
double srcm[10];
double mincm;
int micm;
randomize();
for (int i=0; i<10; i++)
 {
  A[i].Set((random(100)-50), (random(100)-50));
  cout<<"A["<<i<<"]"<<"("<<A[i].Getx()<<", "<<A[i].Gety()<<")"<<endl;
 }
for (int i=0; i<10; i++)
 {
  xcm+=A[i].Getx();
  ycm+=A[i].Gety();
 }
xcm/=10;
ycm/=10;
Cm.Set(xcm, ycm);
for (int i=0; i<10; i++)
 {
  sr[i]=0;
  for (int j=0; j<10; j++)
   {
    if (j!=i)
     {
      sr[i]+=sqrt(pow((A[i].Getx()-A[j].Getx()),2)+pow((A[i].Gety()-A[j].Gety()),2));
     }
    srcm[i]=sqrt(pow((A[i].Getx()-Cm.Getx()),2)+pow((A[i].Gety()-Cm.Gety()),2));
   }
 }
min=sr[0];
int mi=0;
mincm=srcm[0];
micm=0;
for (int i=1; i<10; i++)
 {
  if (sr[i]<min)
   {
    min=sr[i]; mi=i;
   }
  if (srcm[i]<mincm)
   {
    mincm=srcm[i]; micm=i;
   }
 }
cout<<endl<<"Answer 1: "<<endl;
cout<<"A["<<mi<<"]"<<"("<<A[mi].Getx()<<", "<<A[mi].Gety()<<")"<<endl;
cout<<"Summ for this point="<<min<<endl;
cout<<endl<<"Answer 2: "<<endl;
cout<<"C ("<<Cm.Getx()<<", "<<Cm.Gety()<<")"<<endl;
cout<<"A["<<micm<<"]"<<"("<<A[micm].Getx()<<", "<<A[micm].Gety()<<")"<<endl;
cout<<"A--->C"<<mincm<<endl;
return 0;
}
//---------------------------------------------------------------------------

Автор: J0ker 12.12.2008, 01:09

Цитата(Dmi3ev @ 11.12.2008, 23:48

)

это не может считаться док-вом, т.к. верно на ограниченом множестве проверенным с помощью вашей программы например

Автор: Dmi3ev 12.12.2008, 01:50

J0ker, Вы не юрист? или математик? просто эти люди любят к словам докапываться. Хорошо, не чтд. Скажу так, данная программа выдает из 10(0) раз одинаковые решения обоими способами, я задавал множество и побольше размером, точно все также... Вобщем, на доказательство не претендую, но ... Мне кажется все стало ясно... Себе я доказал, что хотел... Решил поделиться с другими своими изысканиями... Но другие слишком умные... Можно еще не только целые координаты задавать(у меня они только целые в программе)... Я согласен с тем, что это доказательство не может считаться неопровержимым. Да я и не в том смысле говорил чтд. Я имел в виду, что догадки GoldFinch да и ваши тоже оказались подкреплены и программой...

Автор: J0ker 12.12.2008, 02:59

я бы на месте препода точно-бы докопался smile

Добавлено через 1 минуту и 12 секунд

Цитата(Dmi3ev @ 12.12.2008, 01:50

)

Да я и не в том смысле говорил чтд

ну звиняйте
для меня чтд означает "что и требовалось доказать" smile

Автор: Dmi3ev 12.12.2008, 04:10

Цитата

я бы на месте препода точно-бы докопался smile

я ж говорю, шибко умный ВЫ smile

у меня с математикой неплохо, я все это прекрасно знаю, что такое ЧТД и даже еще кое-что smile

но медальками не звеню, в отличии от ВАС smile

Ладно, боюсь сказать лишнего, а то ВЫ определениями задавите smile

Автор: GoldFinch 12.12.2008, 19:01

Цитата(Dmi3ev @ 12.12.2008, 04:10

)

у меня с математикой неплохо, я все это прекрасно знаю, что такое ЧТД и даже еще кое-что

чето незаметно

Автор: Kallikanzarid 12.12.2008, 19:13

Добавлю, что лучше в таком случае считывать x- и y-координаты в бинарные деревья, чтобы потом быстро найти точку, ближе всего лежащую к среднему арифметическому.

Автор: Dmi3ev 12.12.2008, 19:55

Цитата

чето незаметно

GoldFinch! Докажи обратное))) Если бы ты сидел со мной рядом и я бы тебе сказал, что точки принадлежащие одной прямой не лежат в одной плоскости, или, что шар квадратный, ты вряд ли бы стал спорить))) А кричать о том, что ты умный, не значит быть умным))) Скорее это значит обратное))) Что конкретно в программной реализации тебя не устраивает??? По делу говори, а не посты зарабатывай...))) заметно, незаметно... Удачи...

Автор: Ln78 12.12.2008, 20:26

Цитата(J0ker @ 11.12.2008, 20:27

)

но это интуитивное решение... надо-бы как-то подкрепить док-вом... впрочем я думаю оно легко выводится и так оно и будет

Цитата(Dmi3ev @ 12.12.2008, 01:50

)

J0ker, Вы не юрист? или математик? просто эти люди любят к словам докапываться. Хорошо, не чтд. Скажу так, данная программа выдает из 10(0) раз одинаковые решения обоими способами, я задавал множество и побольше размером, точно все также... Вобщем, на доказательство не претендую, но

Dmi3ev, это инженерное доказательство, но не математическое. Если математическое, то примерно так:

user posted image

В производной здесь опечатка, понятно, что если дифференцируем по x, то игрековой части не будет. Лень перерисовывать.

Автор: Dmi3ev 12.12.2008, 21:17

Ln78, да я не претендовал на доказательство математическое. Просто пока разводились базары, решил быстренько написать программку, которая собственно и являлась целью вопроса автора. Но когда я её написал, опять начались базары, только уже по поводу того, что я не совсем правильно выразился, сказал чтд, ***ны в рот. Но я так сказал, всего лишь потому, что решил двумя способами, они давали, как предполагалось одинаковое решение. И тут вдруг опять споры... Ненавижу эти споры... Всё, доказывайте, спорьте, делайте, что хотите, для меня все ясно с самого начала... Всем удачи...

Автор: GoldFinch 12.12.2008, 21:33

Цитата(Dmi3ev @ 12.12.2008, 21:17

)

***ны в рот

это ты про себя так сказал?

Автор: J0ker 13.12.2008, 02:53

Цитата(Dmi3ev @ 12.12.2008, 21:17

)

Всё, доказывайте, спорьте, делайте, что хотите, для меня все ясно с самого начала... Всем удачи...

вот именно таким образом рождаются самые заковыристые заблуждения smile

просто надо понять, что не всегда то, что очевидно - верно

Автор: Снежанна 14.12.2008, 15:58

а что за функция рандом? Компилятор не распознает.

Автор: J0ker 14.12.2008, 22:55

Цитата(Снежанна @ 14.12.2008, 15:58)

а что за функция рандом? Компилятор не распознает.

Код


inline void randomize()
{
    srand((unsigned int)time(NULL));
}

inline int random(int n)
{
    return (int)((double)rand()/RAND_MAX * n);
}

Автор: Снежанна 23.12.2008, 22:17

Код



#include <mypoint.h>
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>



int main()
{
MyPoint A[1000];
double min;
double sr[10];
int n;
double ax, ay;
cout<<"Enter number of elements: ";
cin>>n;
for (int i=0; i<n; i++)
 {
  cout<<"A["<<i+1<<"] x=";
  cin>>ax;
  cout<<"A["<<i+1<<"] y=";
  cin>>ay;
  cout<<endl;
  A[i].Set(ax,ay);
 }
for (int i=0; i<n; i++)
 {
  sr[i]=0;
  for (int j=0; j<n; j++)
   {
    if (j!=i)
     {
      sr[i]+=sqrt(pow((A[i].Getx()-A[j].Getx()),2)+pow((A[i].Gety()-A[j].Gety()),2));
     }
    //srcm[i]=sqrt(pow((A[i].Getx()-Cm.Getx()),2)+pow((A[i].Gety()-Cm.Gety()),2));
   }
 }
min=sr[0];
int mi=0;
//mincm=srcm[0];
//micm=0;
for ( i=1; i<n; i++)
 {
  if (sr[i]<min)
   {
    min=sr[i]; mi=i;
   }

 }
cout<<endl<<"Answer 1: "<<endl;
cout<<"A["<<mi<<"]"<<"("<<A[mi].Getx()<<", "<<A[mi].Gety()<<")"<<endl;
cout<<"Summ for this point="<<min<<endl;
return 0;
}

Вообщем выдает 2 ошибки...

Цитата

Êîìïèëÿòîð: Default compiler
Âûïîëíåíèå  g++.exe...
g++.exe "C:\Users\5\Desktop\Ïðîãðàììèðîâàíèå\Ëàá ðàá 6\ëîë.cpp" -o "C:\Users\5\Desktop\Ïðîãðàììèðîâàíèå\Ëàá ðàá 6\ëîë.exe"   -g3  -I"C:\Dev-Cpp\lib\gcc\mingw32\3.4.2\include"  -I"C:\Dev-Cpp\include\c++\3.4.2\backward"  -I"C:\Dev-Cpp\include\c++\3.4.2\mingw32"  -I"C:\Dev-Cpp\include\c++\3.4.2"  -I"C:\Dev-Cpp\include"   -L"C:\Dev-Cpp\lib" -g3
In file included from C:\Users\5\Desktop\Ïðîãðàììèðîâàíèå\Ëàá ðàá 6\ëîë.cpp:2:

C:/Dev-Cpp/include/c++/3.4.2/backward/mypoint.h:14:7: warning: no newline at end of file
In file included from C:/Dev-Cpp/include/c++/3.4.2/backward/iostream.h:31,
                 from C:\Users\5\Desktop\Ïðîãðàììèðîâàíèå\Ëàá ðàá 6\ëîë.cpp:3:
C:/Dev-Cpp/include/c++/3.4.2/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.
C:\Users\5\Desktop\Ïðîãðàììèðîâàíèå\Ëàá ðàá 6\ëîë.cpp: In function `int main()':
C:\Users\5\Desktop\Ïðîãðàììèðîâàíèå\Ëàá ðàá 6\ëîë.cpp:44: error: name lookup of `i' changed for new ISO `for' scoping
C:\Users\5\Desktop\Ïðîãðàììèðîâàíèå\Ëàá ðàá 6\ëîë.cpp:19: error:   using obsolete binding at `i'

Âûïîëíåíèå çàâåðøåíî

В чем проблема?

Автор: mes 23.12.2008, 23:12

Цитата(Снежанна @ 23.12.2008, 22:17

)

for ( i=1; i<n; i++)

for (int i=1; i<n; i++)

и в самом конце текста добавьте пустую строку.

Автор: Dmi3ev 23.12.2008, 23:25

mes, спасибо, а то она в личку пишет, почему не работает??? а я не знаю, у меня на компе рабочая версия этой проги, я же не знаю, что она видоизменяет после моего написания smile

у меня в этом месте ошибки нет, а человек стер int и нашел себе проблемы... smile

Снежанна, то, что после // можно и убрать, я просто тебе отослал с ними, потому, что быстро исправлял... а ты могла бы и навести красоту, ты же девушка...

Автор: bsa 24.12.2008, 00:23

Снежанна, вот это:

Код

#include <mypoint.h>
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

Надо писать так:

Код

#include <mypoint.h>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>

using std::cout;
using std::cin;
using std::endl;

Автор: Снежанна 24.12.2008, 20:25

уж извините, что в универе на компах 90х приходится с Борландом работать smile

Там пишет мультипат дикларэйшон или что то типа того) Спасибо, bsa

Автор: Снежанна 24.12.2008, 21:36

Да и еще, до этого я составляла только входные и выходные файлы. А как сделать файл протокола, который содержал бы в себе оба этих файла, так и еще показывал все промежуточные рассчеты и неккоректные ситуации (с которыми, собственно говоря, тоже не успеваю разобраться), покажите, пожалуйста