2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 
Сообщение29.01.2006, 05:31 


06/01/06
66
Спасибо Вам большое! Вы всяко разно в Паскале больше моего понимаете. Ясное же дело. У меня еще одна задача есть нерешенная (на графику). Вообще не знаю как к ней подступиться. Я даже домик нарисовать не могу.
Задача:
Соединить конечное множество точек на плоскости замкнутой ломаной линией без
самопересечений с вершинами в этих точках. (Полный перебор не делать;
ответом будет порядок обхода точек плоскости.)

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

 Профиль  
                  
 
 
Сообщение29.01.2006, 08:06 
Аватара пользователя


20/01/06
64
оттуда
Alenka_kiss писал(а):
...задача есть нерешенная (на графику)...

Это ж разве на графику ? Ведь
Цитата:
ответом будет порядок обхода точек плоскости

И раз есть указание
Цитата:
Указание: перейти к полярным координатам и упорядочить точки по значениям
угла, а для точек с одинаковым значением угла - по расстоянию до полюса.

то нужно всего лишь пересчитать массив в полярные координаты, а потом два раза отсортировать. Вот так, например (вроде не ошибся):
Код:
const N = 10; (* количество точек *)

type tPoint = record
    x, y: real;
    n: integer;
end; (* record *)

type tPoints = array [1..N] of tPoint;

procedure dec2pol (var p: tPoint);
    var t: tPoint;
begin (* dec2pol *)
    t. n := p. n;
    if p. x = 0 then
        t. x := 90
    else
        t. x := 180 * arctan (p. y / abs (p. x)) / Pi;
    if p. x < 0 then
        t. x := 180 - t. x
    else
        if p. y < 0 then
            t. x := 360 + t. x;
    t. y := sqrt (sqr (p. x) + sqr (p. y));
    p := t;
end; (* dec2pol *)

var points: tPoints;
    t: tPoint;
    i, j: integer;

begin (* main program *)
    (* получаем значения массива *)
    for i := 1 to N do begin
        points [i]. n := i;
        read (points [i]. x, points [i]. y);
        dec2pol (points [i]);
    end;
    (* сортируем по значению угла *)
    for i := 1 to N - 1 do
        for j := i + 1 to N do
            if points [j]. x < points [i]. x then begin
                t := points [j];
                points [j] := points [i];
                points [i] := t;
            end; (* if *)
    (* сортируем по значению радиуса *)
    for i := 1 to N - 1 do
        for j := i + 1 to N do
            if (points [j]. x = points [i]. x) and (points [j]. y < points [i]. y) then begin
                t := points [j];
                points [j] := points [i];
                points [i] := t;
            end; (* if *)
    (* вывод порядка *)
    for i := 1 to N do
        writeln (points [i]. n);
end. (* main program *)

 Профиль  
                  
 
 
Сообщение29.01.2006, 09:50 


06/01/06
66
А зачем тогда эту задачу поместили в тему графическое программирование? Чтобы запутать, того кто решает. Умеют же преподаватели так вопрос задать, что даже не знаешь, о чем они спросили. Или я одна такая? Что до меня не спервого раза доходит?

 Профиль  
                  
 
 
Сообщение29.01.2006, 11:46 
Аватара пользователя


20/01/06
64
оттуда
Cube писал(а):
...(вроде не ошибся):

Ошибся, не C всё-таки :)
Раз:
Код:
...
procedure dec2pol (var p: tPoint)

Два:
Код:
...
    if p. x = 0 then
        t. x := 90;
    else
        t. x := 180 * arctan (p. y / abs (p. y)) / Pi;
...

Три:
Код:
...
for i := 1 to N do begin
        read (points [i]. x, points [i]. y);
...

И четыре (поскольку нужен порядок:
Код:
...
    (* выводим значения массива *)
    for i := 1 to N do begin
        writeln (points [i]. x, ", ", points [i]. y);
...

Мда... Всё исправил в предыдущем сообщении.

 Профиль  
                  
 
 
Сообщение29.01.2006, 12:01 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Cube писал(а):
Код:
...
    if p. x = 0 then
        t. x := 90;
    else
        t. x := 180 * arctan (p. y / abs (p. x)) / Pi;
    if p. x < 0 then
        t. x := 180 - t. x;
...



Код:
...
  if p.x=0 then
    begin
      if p.y>0 then t.x:=90 else
        if p.y<0 then t.x:=270 else t.x:=0
    end
  else
    t.x:=180*arctan(p.y/abs(p.x))/Pi;
  if p.x<0 then t.x:=180+t.x;
...


Сам кое-каких ошибок наделал. Кроме того, там должно быть не

Код:
  if p.x<0 then t.x:=180-t.x;


а

Код:
  if p.x<0 then t.x:=180+t.x;


И ещё. Не проще будет отсортировать один раз?

Код:
if (points[j].x<points [i].x) or ((points[j].x=points[i].x) and (points[j].y<points[i].y)) then

 Профиль  
                  
 
 
Сообщение29.01.2006, 16:16 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Возвращаясь к нашим баранам (а точнее, к сортировке).

Пока мы сортируем массив методом обмена, то все впорядке: сначала обрабатываем весь массив до конца, до N-го элемента, потом до N-1 и т.д. до второго элемента. В случае со списком мы можем определить, где у нас последний элемент (это у которого поле next = nil), а вот как определить, где предпоследний эл-т (и т.д.)?

 Профиль  
                  
 
 
Сообщение29.01.2006, 20:41 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Можно один раз посчитать. Количество элементов в списке не меняется.

 Профиль  
                  
 
 
Сообщение29.01.2006, 21:40 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
А можно и не считать! :P И усе получается просто замечательно!

 Профиль  
                  
 
 
Сообщение29.01.2006, 22:59 
Аватара пользователя


20/01/06
64
оттуда
Someone писал(а):
...Кроме того, там должно быть не

Код:
  if p.x<0 then t.x:=180-t.x;


а

Код:
  if p.x<0 then t.x:=180+t.x;


Нет, потому что
Цитата:
Код:
...
    ...abs(p.x))/Pi;
  if p.x<0 then t.x:=180+t.x;
...

Но хоть abs, хоть не abs для углов >270 оба дают отрицательные значения. Тогда уж
Код:
...
    t.x:=180*arctan(p.y/abs(p.x))/Pi;
  if p.x<0 then t.x:=180+t.x else if p.y<0 then t.x:=360+t.x;
...

Цитата:
И ещё. Не проще будет отсортировать один раз?

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

 Профиль  
                  
 
 
Сообщение30.01.2006, 02:23 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Cube писал(а):
Someone писал(а):
...Кроме того, там должно быть не

Код:
  if p.x<0 then t.x:=180-t.x;


а

Код:
  if p.x<0 then t.x:=180+t.x;


Нет, потому что

Код:
...
    ...abs(p.x))/Pi;
  if p.x<0 then t.x:=180+t.x;
...


Да, правда. Прекрасный пример того, что человек видит не то, что есть (arctan(p.y/abs(p.x))), а то, что ожидает увидеть (arctan(p.y/p.x)).

Cube писал(а):
Цитата:
И ещё. Не проще будет отсортировать один раз?

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


Ну почему же? Если правильное условие написать, то сразу всё и отсортируется:

Код:
if (points[j].x<points [i].x) or ((points[j].x=points[i].x) and (points[j].y<points[i].y)) then

 Профиль  
                  
 
 
Сообщение30.01.2006, 08:14 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Someone писал(а):
Ну почему же? Если правильное условие написать, то сразу всё и отсортируется:
Код:
if (points[j].x<points [i].x) or ((points[j].x=points[i].x) and (points[j].y<points[i].y)) then


Тут под x подразумеваются углы, а под y - радиусы?

 Профиль  
                  
 
 
Сообщение30.01.2006, 14:32 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Sanyok писал(а):
Someone писал(а):
Ну почему же? Если правильное условие написать, то сразу всё и отсортируется:
Код:
if (points[j].x<points [i].x) or ((points[j].x=points[i].x) and (points[j].y<points[i].y)) then


Тут под x подразумеваются углы, а под y - радиусы?


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

 Профиль  
                  
 
 на счет нарисовать
Сообщение04.02.2006, 06:57 


06/01/06
66
В части перевода в полярные координаты и сортировки точек понятно. Но все-таки как на счет нарисовать иллюстрацию к этой задаче? Она по-прежнему из раздела на графику и думаю, что графическая составляющая ответа все-таки нужна.

 Профиль  
                  
 
 Re: на счет нарисовать
Сообщение04.02.2006, 20:32 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Alenka_kiss писал(а):
В части перевода в полярные координаты и сортировки точек понятно. Но все-таки как на счет нарисовать иллюстрацию к этой задаче? Она по-прежнему из раздела на графику и думаю, что графическая составляющая ответа все-таки нужна.


Вы на Турбо Паскале программируете? Ну посмотрели бы описание модуля Graph. Там есть процедуры MoveTo(X,Y:Integer), чтобы отметить первую точку, и LineTo(X,Y:Integer), чтобы нарисовать линию от предыдущей точки до новой.

 Профиль  
                  
 
 
Сообщение05.02.2006, 07:14 


06/01/06
66
О графическом программировании на Паскаль я не знаю вообще ничего. Даже домик не умею нарисовать. И вообще, я - журналист.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 64 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group