2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5  След.
 
 
Сообщение29.01.2006, 05:31 
Спасибо Вам большое! Вы всяко разно в Паскале больше моего понимаете. Ясное же дело. У меня еще одна задача есть нерешенная (на графику). Вообще не знаю как к ней подступиться. Я даже домик нарисовать не могу.
Задача:
Соединить конечное множество точек на плоскости замкнутой ломаной линией без
самопересечений с вершинами в этих точках. (Полный перебор не делать;
ответом будет порядок обхода точек плоскости.)

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

 
 
 
 
Сообщение29.01.2006, 08:06 
Аватара пользователя
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 
А зачем тогда эту задачу поместили в тему графическое программирование? Чтобы запутать, того кто решает. Умеют же преподаватели так вопрос задать, что даже не знаешь, о чем они спросили. Или я одна такая? Что до меня не спервого раза доходит?

 
 
 
 
Сообщение29.01.2006, 11:46 
Аватара пользователя
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 
Аватара пользователя
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 
Аватара пользователя
Возвращаясь к нашим баранам (а точнее, к сортировке).

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

 
 
 
 
Сообщение29.01.2006, 20:41 
Аватара пользователя
:evil:
Можно один раз посчитать. Количество элементов в списке не меняется.

 
 
 
 
Сообщение29.01.2006, 21:40 
Аватара пользователя
А можно и не считать! :P И усе получается просто замечательно!

 
 
 
 
Сообщение29.01.2006, 22:59 
Аватара пользователя
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 
Аватара пользователя
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 
Аватара пользователя
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 
Аватара пользователя
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 
В части перевода в полярные координаты и сортировки точек понятно. Но все-таки как на счет нарисовать иллюстрацию к этой задаче? Она по-прежнему из раздела на графику и думаю, что графическая составляющая ответа все-таки нужна.

 
 
 
 Re: на счет нарисовать
Сообщение04.02.2006, 20:32 
Аватара пользователя
Alenka_kiss писал(а):
В части перевода в полярные координаты и сортировки точек понятно. Но все-таки как на счет нарисовать иллюстрацию к этой задаче? Она по-прежнему из раздела на графику и думаю, что графическая составляющая ответа все-таки нужна.


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

 
 
 
 
Сообщение05.02.2006, 07:14 
О графическом программировании на Паскаль я не знаю вообще ничего. Даже домик не умею нарисовать. И вообще, я - журналист.

 
 
 [ Сообщений: 64 ]  На страницу Пред.  1, 2, 3, 4, 5  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group