1 Востаннє редагувалося HetmanNet (30.10.2012 00:18:03)

Тема: Цікава задачка :P

Є цікава задачка на створення програми, вона пов'язана з алгеброю та геометрією. Одним словом за п'ять хвилин не вирішите :D Кінцевий алгоритм необхідно втілити у програмі (консольній) на С (не С++) для ОС сімейства UNIX.

Умова (пишу по пам'яті) написав:

В просторі маємо від трьох і більше нерухомих точок (кількість може змінюватися в межах від трьох до кількох десятків тисяч) з відповідними координатами: const_1[x1,y1,z1], const_2[x2,y2,z2], const_3[x3,y3,z3] .. N[xN,yN,zN],N+1[xN+1,yN+1,zN+1].
1. Необхідно координати рухомої точки var[x,y,z], якщо відомі лише відстані від цієї точки до нерухомих в межах певної віддаленості F (в межах віддаленості завжди перебуває не менше трьох). При створенні алгоритму необхідно для обчислення координат рухомої точки використовувати найменш можливу кількість координат нерухомих точок.
2. Необхідно обчислювати вектор руху рухомої точки на основі алгоритму пункту 1 зроблених по даних отриманих з рівним інтервалом часу.

P.S. Над нею багато хто страждав. :D А посилили одиниці. :P
P.P.S. Розв'язку вже не маю, але знаю як можна перевірити його правильність.

Re: Цікава задачка :P

Оу, чого ж я тільки дану тему тепер побчив ???
Треба провіритися в окуліста.
Я знаю як цю задачу розв`язати, можу скинути розв`язок.

3

Re: Цікава задачка :P

Hanter написав:

Оу, чого ж я тільки дану тему тепер побчив ???
Треба провіритися в окуліста.
Я знаю як цю задачу розв`язати, можу скинути розв`язок.

То кидай :)

Re: Цікава задачка :P

Ось. правда він неповний...

Post's attachments

IMG_0340.JPG 3.41 mb, 330 downloads since 2012-12-02 

5

Re: Цікава задачка :P

Hanter написав:

Ось. правда він неповний...

а де продовження?

6

Re: Цікава задачка :P

Ха, в продовжені найцікавіше)

Доречі, якщо мати 3 часові проміжки з рівномірним рухом, то по 3-х точка можна вирішувати і коли не в одній площині.

А чого задача тільки для сішки? як буду завтра мати час, то гляну...

7

Re: Цікава задачка :P

Vo_Vik написав:

Ха, в продовжені найцікавіше)

Доречі, якщо мати 3 часові проміжки з рівномірним рухом, то по 3-х точка можна вирішувати і коли не в одній площині.

А чого задача тільки для сішки? як буду завтра мати час, то гляну...

На Сі/C++ через API :)
Як буде рішення - скажу для чого в реальності це може бути потрібно ;)

8

Re: Цікава задачка :P

На Сі/C++ через API smile

Тоді треба формат вхідних даних.

Re: Цікава задачка :P

HetmanNet написав:

Як буде рішення - скажу для чого в реальності це може бути потрібно ;)

А я вже знаю :devil

10

Re: Цікава задачка :P

Наразі зберігаю собі, щоб дома поправити ероз з сегментацією

Прихований текст
#include <stdio.h>
#include <math.h>

int getTarget(float radars[3][3], float radarValues[3], float **target);
float getDistance(float pointA[3], float pointB[3]);
float triangleCalculation(float r1, float r2, float l);
void proectionCoordinates(float pointA[3], float pointB[3], float length, float distance, float *pointC);
void normalVector(float pointA[3], float pointB[3], float pointC[3], float *vector);

int main()
{
  //init radars array
  int i,j;
  float radars[3][3]={{0,0,0},{10,2,0},{10,-2,0}};
  float targets[3][2][3], **target;
  //set radars values
  float radarValues[3][3]={{11.5,2.5,2.5},{12,3,3},{13,4,4}};
  float radarValue[3];
  printf("Hello, world\n");
  for(i=0;i<3;i++)
  {
    for(j=0;j<3;j++)
    {
      radarValue[j]=radarValues[i][j];
    }
    if(!getTarget(radars, radarValue, **target)){
      return 0;
    }
  }
  
  return 0;
}
/*Function calculates coordinates of target*/
int getTarget(float radars[3][3], float radarValues[3], float **target)
{
  float l1, l2, x1, x2, h1, h2, nvl=0;
  float point1[3], point2[3], point3[3], vn[3], t1[3], t2[3], r1[3], r2[3], r3[3];
  int i,j;
  printf("Radar coordinats are:\n");
  for(i=0;i<3;i++)
  {
    for(j=0;j<3;j++)
    {
      printf("%.2f",radars[i][j]);
      if(j==2)
      {
        printf(" Distance are %.2f\n",radarValues[i]);
      }
      else
      {
        printf(", ");
      }
    }
  }
  for(i=0;i<3;i++)
  {
    r1[i]=radars[0][i];
    r2[i]=radars[1][i];
    r3[i]=radars[2][i];
  }
  //get l1
  l1 = getDistance(r2,r3);
  printf("l1 is %.2f\n",l1);
  if(radarValues[1]+radarValues[2]<l1)
  {
    printf("Incorrect values\n");
    return 0;
  }
  //get first proection length
  x1=triangleCalculation(radarValues[1], radarValues[2], l1);
  printf("x1 is %.2f\n",x1);
  //get first proection coords
  proectionCoordinates(r2, r3, x1, l1, point1);
  printf("point1 is %.2f,%.2f,%.2f\n",point1[0],point1[1],point1[2]);
  //calculate height for proection
  h1=sqrt(pow(radarValues[1],2)-pow(x1,2));
  printf("h1 is %.2f\n",h1);
  //do the same for second proection
  l2=getDistance(r1, point1);
  printf("l2 is %.2f\n",l2);
  if(radarValues[0]+h1<l2)
  {
    printf("Incorrect values\n");
    return 0;
  }
  //get first proection length
  x2=triangleCalculation(radarValues[0], h1, l2);
  printf("x2 is %.2f\n",x2);
  //get first proection coords
  proectionCoordinates(r1, point1, x2, l2, point2);
  printf("point2 is %.2f,%.2f,%.2f\n",point2[0],point2[1],point2[2]);
  //calculate height for proection
  h2=sqrt(pow(radarValues[0],2)-pow(x2,2));
  printf("h2 is %.2f\n",h2);
  
  //find normal vector for plane
  normalVector(r1, r2, r3, vn);
  printf("vn is %.2f,%.2f,%.2f\n",vn[0],vn[1],vn[2]);
  
  //find coords of target
  for(i=0;i<3;i++)
  {
    point3[i]=point2[i]+vn[i];
    nvl+=pow(vn[i],2);
  }
  proectionCoordinates(point2, point2, h2, nvl, t1);
  printf("t1 is %.2f,%.2f,%.2f\n",t1[0],t1[1],t1[2]);
  proectionCoordinates(point2, point2, -h2, nvl, t2);
  printf("t2  is %.2f,%.2f,%.2f\n",t2[0],t2[1],t2[2]);
  for(i=0;i<3;i++)
  {
    target[0][i]=t1[i];
    target[1][i]=t2[i];
  }
printf("target[0] is %.2f,%.2f,%.2f\n",target[0][0],target[0][1],target[0][2]);
  printf("Target coordinates are:\n");
  for(i=0;i<2;i++)
  {
    for(j=0;j<3;j++)
    {
      printf("%.2f",target[i][j]);
      if(j==2)
      {
        printf("\n");
      }
      else
      {
        printf(", ");
      }
    }
  }
  
  return 1;
}
/*Function calculates distance between two points*/
float getDistance(float pointA[3], float pointB[3])
{
  float suareSum=0;
  int i;
  for(i=0;i<3;i++)
  {
    suareSum+=pow(pointA[i]-pointB[i],2);
  }
  return fabs(sqrt(suareSum));
}
/*Function calculates length of proection*/
float triangleCalculation(float r1, float r2, float l)
{
  float r12,r22,l2;
  r12=pow(r1,2);
  r22=pow(r2,2);
  l2=pow(l,2);
  if(r12>r22+l2)
  {
    return l+(r12-r22-l2)/2/l;
  }
  else if(r22>r12+l2)
  {
    return -(r22-r12-l2)/2/l;
  }
  else
  {
    return (r12-r22+l2)/2/l;
  }
}
/*Function calculates coordinates of proection*/
void proectionCoordinates(float pointA[3], float pointB[3], float length, float distance, float *pointC)
{
  int i;
  float k;
  k=length/distance;
  for(i=0;i<3;i++)
  {
    pointC[i]=k*(pointB[i]-pointA[i])+pointA[i];
  }
}
/*Function calculates normal verctor for plane*/
void normalVector(float pointA[3], float pointB[3], float pointC[3], float *vector)
{
  float v1[3],v2[3];
  int i;
  for(i=0;i<3;i++)
  {
    v1[i]=pointC[i]-pointA[i];
    v2[i]=pointB[i]-pointA[i];
  }
  vector[0]=v1[1]*v2[2]-v2[1]*v1[2];
  vector[1]=v1[2]*v2[0]-v2[2]*v1[0];
  vector[2]=v1[0]*v2[1]-v2[0]*v1[1];
}

11 Востаннє редагувалося Vo_Vik (04.12.2012 06:47:25)

Re: Цікава задачка :P

Тримайте свою систему глобального позиціювання, правда ще здалось би визначити, які з варіантів положення точки в часі визначають прямолінійний рух, але нині вже нема настрою.
Весело було згадати сішку, я виявляється багато чого був забув уже.

Прихований текст
#include <stdio.h>
#include <math.h>

int getTarget(float radars[3][3], float radarValues[3], float *target1, float *target2);
float getDistance(float pointA[3], float pointB[3]);
float triangleCalculation(float r1, float r2, float l);
void proectionCoordinates(float pointA[3], float pointB[3], float length, float distance, float *pointC);
void normalVector(float pointA[3], float pointB[3], float pointC[3], float *vector);

int main()
{
    //init radars array
    int i,j,k;
    float radars[3][3]={{0,0,0},{10,2,1.5},{10,-2,-1.5}};
    float targets[3][2][3];
    float target1[3]; float target2[3];
    //set radars values
    float radarValues[3][3]={{10,2.5,2.5},{11,3,3},{10.5,4,4}};
    float radarValue[3];
    printf("Hello, world\n");
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            radarValue[j]=radarValues[i][j];
        }
        if(!getTarget(radars, radarValue, target1, target2)){
            return 0;
        }
        for(k=0;k<3;k++)
        {
            targets[i][0][k]=target1[k];
            targets[i][1][k]=target2[k];
        }
        printf("Target coordinates are:\n");
        for(j=0;j<2;j++)
        {
            for(k=0;k<3;k++)
            {
                printf("%.2f",targets[i][j][k]);
                if(k==2)
                {
                    printf("\n");
                }
                else
                {
                    printf(", ");
                }
            }
        }
    }
    return 0;
}
/*Function calculates coordinates of target*/
int getTarget(float radars[3][3], float radarValues[3], float *target1, float *target2)
{
    float l1, l2, x1, x2, h1, h2, nvl=0;
    float point1[3], point2[3], point3[3], vn[3], t1[3], t2[3], r1[3], r2[3], r3[3];
    int i,j;
    printf("Radar coordinats are:\n");
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            printf("%.2f",radars[i][j]);
            if(j==2)
            {
                printf(" Distance are %.2f\n",radarValues[i]);
            }
            else
            {
                printf(", ");
            }
        }
    }
    for(i=0;i<3;i++)
    {
        r1[i]=radars[0][i];
        r2[i]=radars[1][i];
        r3[i]=radars[2][i];
    }
    //get l1
    l1 = getDistance(r2,r3);
    if(radarValues[1]+radarValues[2]<l1)
    {
        printf("Incorrect values\n");
        return 0;
    }
    //get first proection length
    x1=triangleCalculation(radarValues[1], radarValues[2], l1);
    //get first proection coords
    proectionCoordinates(r2, r3, x1, l1, point1);
    //calculate height for proection
    h1=sqrt(pow(radarValues[1],2)-pow(x1,2));
    //do the same for second proection
    l2=getDistance(r1, point1);
    if(radarValues[0]+h1<l2)
    {
        printf("Incorrect values\n");
        return 0;
    }
    //get first proection length
    x2=triangleCalculation(radarValues[0], h1, l2);
    //get first proection coords
    proectionCoordinates(r1, point1, x2, l2, point2);
    //calculate height for proection
    h2=sqrt(pow(radarValues[0],2)-pow(x2,2));
    //find normal vector for plane
    normalVector(r1, r2, r3, vn);
    //find coords of target
    for(i=0;i<3;i++)
    {
        point3[i]=point2[i]+vn[i];
        nvl+=pow(vn[i],2);
    }
    proectionCoordinates(point2, point3, h2, nvl, target1);
    proectionCoordinates(point2, point3, -h2, nvl, target2);
    return 1;
}
/*Function calculates distance between two points*/
float getDistance(float pointA[3], float pointB[3])
{
    float suareSum=0;
    int i;
    for(i=0;i<3;i++)
    {
        suareSum+=pow(pointA[i]-pointB[i],2);
    }
    return fabs(sqrt(suareSum));
}
/*Function calculates length of proection*/
float triangleCalculation(float r1, float r2, float l)
{
    float r12,r22,l2;
    r12=pow(r1,2);
    r22=pow(r2,2);
    l2=pow(l,2);
    if(r12>r22+l2)
    {
        return l+(r12-r22-l2)/2/l;
    }
    else if(r22>r12+l2)
    {
        return -(r22-r12-l2)/2/l;
    }
    else
    {
        return (r12-r22+l2)/2/l;
    }
}
/*Function calculates coordinates of proection*/
void proectionCoordinates(float pointA[3], float pointB[3], float length, float distance, float *pointC)
{
    int i;
    float k;
    k=length/distance;
    for(i=0;i<3;i++)
    {
        pointC[i]=k*(pointB[i]-pointA[i])+pointA[i];
    }
}
/*Function calculates normal verctor for plane*/
void normalVector(float pointA[3], float pointB[3], float pointC[3], float *vector)
{
    float v1[3],v2[3];
    int i;
    for(i=0;i<3;i++)
    {
        v1[i]=pointC[i]-pointA[i];
        v2[i]=pointB[i]-pointA[i];
    }
    vector[0]=v1[1]*v2[2]-v2[1]*v1[2];
    vector[1]=v1[2]*v2[0]-v2[2]*v1[0];
    vector[2]=v1[0]*v2[1]-v2[0]*v1[1];
}

12

Re: Цікава задачка :P

І що так ніхто і не глянув, я знаю де я там наробив лишніх конструкцій, думав мо хтось покритикує, а то тиша.