Школьная задачка для разминки и занять время - страница 5

Новый комментарий
 
Aleksey Nikolayev:

1) Сложность в доказательстве факта, что вершины мн-ка с максимальной площадью должны лежать на одной окружности (теорема Крамера). Не знаю как это доказать или где почитать док-во.

2) Не очень верю в существование аналитической формулы для максимальной площади или для радиуса окружности.

3) Сумму элементов массива можно посчитать функцией MathSum()

1) По-моему это очевидный факт. И доказать легко через понимание того, что максимальная площадь треугольника, имеющего заданную вершину A, среднюю линию h и заданную противоположну сторону a - это площадь равнобедренного треугольника, когда угол в заданной вершине максимален. И равна площадь такого треугольника h*a/2

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

2) Я верю

3) Не нашел такой формулы ни в MQL4, ни в MQL5

 
Nikolai Semko:

1) По-моему это очевидный факт.

интуитивно да, но даже на нестрогое доказательство это не тянет с любыми натяжками.

2) Я верю

если бы она была, ее можно было бы найти, есть только система уравнений

Aleksey Nikolayev:

1) Сложность в доказательстве факта, что вершины мн-ка с максимальной площадью должны лежать на одной окружности (теорема Крамера). Не знаю как это доказать или где почитать док-во.

не нашел такой теоремы вообще, только упоминания об этом свойстве.

Олег avtomat:

http://algolist.ru/maths/geom/polygon/area.php 

как всегда бесполезные ссылки и ни слова по делу.

 
Andrei Trukhanovich:


как всегда бесполезные ссылки и ни слова по делу.

для тебя это действительно бесполезно

 
Nikolai Semko:

1) По-моему это очевидный факт. И доказать легко через понимание того, что максимальная площадь треугольника, имеющего заданную вершину A, среднюю линию h и заданную противоположну сторону a - это площадь равнобедренного треугольника, когда угол в заданной вершине максимален. И равна площадь такого треугольника h*a/2

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

2) Я верю

3) Не нашел такой формулы ни в MQL4, ни в MQL5

1) Наверное, это можно как-то это формализовать в виде равенства нулю вариации (производной) площади мн-ка по координатам вершин когда они лежат на одной окружности. Только это условие локальной экстремальности, а нам нужно доказать 1) что это максимум и 2) что он глобальный.

3)  MathSum()

#include <Math\Stat\Math.mqh>
void OnStart()
{
  double a[] = {1.0, 2.0, 3.0}, s;
  s = MathSum(a);
  Print("s=", s);
}

s=6.0



 

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

 
Andrei Trukhanovich:

интуитивно да, но даже на нестрогое доказательство это не тянет с любыми натяжками.

если бы она была, ее можно было бы найти, есть только система уравнений

не нашел такой теоремы вообще, только упоминания об этом свойстве.

как всегда бесполезные ссылки и ни слова по делу.

гуглил "maximum area polygon given sides", нашёл только что этот результат "well known") и численные решения типа приведённого Николаем.

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

 

Приведенное выше решение справедливо только для многоугольников, центр описанной окружности которых, лежит внутри периметра. Попробуйте треугольник {2,2,3.9}

В общем виде (приближение по точности double) решается так:

enum EEqual {LESS=-1,EQUALY,MORE};
//-------------------------------------------------------
struct SRes{
   double s;
   double r;
   double degDelta;
   SRes(){ZeroMemory(this);}
   SRes(double _s,double _r,double _degDelta):s(_s),r(_r),degDelta(_degDelta){}
   SRes(const SRes &other) {this=other;}
   bool operator !() {return !s;}
};
//-------------------------------------------------------
const double _2PI=2*M_PI;
//-------------------------------------------------------
EEqual Check(double &array[],int size){
   int ii=0;
   double max=0.0,
          tmp=0.0,
          sum=0.0;
   for (int i=0;i<size;++i){
      if (array[i]<=0.0) return false;
      max=MathMax(max,array[i]);
      if (max!=tmp){
         ii=i;
         tmp=max;}
      sum+=array[i];}
   EEqual ret=max<sum/2?MORE:LESS;
   if (ret==MORE){
      tmp=array[ii];
      array[ii]=array[--size];
      array[size]=tmp;}
   return ret;}
//---------------------------------------------------
SRes ComputeCenterOut(const double &array[], double deg){
   int size=ArraySize(array)-1;
   double r=array[size]/2.0/sin((deg-M_PI)/2.0);
   double sum=0.0,
          square=-r*cos(deg/2.0)*array[size]/2.0;
   for (int i=0;i<size;++i){
      double _deg=2.0*MathArcsin(array[i]/2.0/r);
      sum+=_deg;
      square+=r*cos(_deg/2.0)*array[i];}
   return SRes(square,r,deg-M_PI-sum);
}
//---------------------------------------------------
SRes ComputeCenterIn(const double &array[], double deg){
   int size=ArraySize(array)-1;
   double r=array[size]/2.0/sin(deg/2.0);
   double sum=deg,
          square=r*cos(deg/2.0)*array[size]/2.0;
   for (int i=0;i<size;++i){
      double _deg=2.0*MathArcsin(array[i]/2.0/r);
      sum+=_deg;
      square+=r*cos(_deg/2.0)*array[i]/2.0;}
   return SRes(square,r,_2PI-sum);
}
//---------------------------------------------------
SRes ComputeSquare(const double &array[],double min,double max,SRes &prev){
   double a=(min+max)/2.0;
   if (a==min||a==max) return prev;
   SRes res=a>M_PI?ComputeCenterOut(array,a):ComputeCenterIn(array,a);
   if (res.degDelta==0.0||res.s==prev.s) return res;
   if (res.degDelta>0.0) min=a;
   else max=a;
   return ComputeSquare(array,min,max,res);}
//---------------------------------------------------
SRes Square(const double &in[]){
   double tmp[];
   int size=ArrayCopy(tmp,in);
   if (Check(tmp,size)!=MORE) return SRes();
   double aMax=_2PI,
          a=aMax/size;
   return ComputeSquare(tmp,a,aMax,SRes());
}

void OnStart(void)
{
   double arr[]={2,3.9,2};
   ulong time=GetMicrosecondCount();
   SRes res=Square(arr);
   time=GetMicrosecondCount()-time;
   if (!res) Print("Многоугольника с заданными сторонами не существует");
   else PrintFormat("Time=%lli %ss\n"
                    "Square=%f\n"
                    "Radii=%f",time,"\xB5",res.s,res.r);
}
 
Vladimir Simakov:

Приведенное выше решение справедливо только для многоугольников, центр описанной окружности которых, лежит внутри периметра. Попробуйте треугольник {2,2,3.9}

...

А причем тут треугольник, если задача - найти многоугольник с максимальной площадью при заданных размерах сторон?

 

Упс. У меня у самого только один из вариантов правильно считает)))

UPD: Поправил

 
Dmitry Fedoseev:

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

вот функция зависимости суммы всех углов от радиуса. Зеленым выделена область решения 2пи.

может поможет. 
Мне как-то лень напрягать мозги, тем более в вышке не силен.

Файлы:
Zadacha2.mq5  4 kb
12345678
Новый комментарий