VPF::комбинаторика - Форум программистов

FreeJaile

Дата 6.3.2009, 08:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 28.2.2008

Репутация: нет
Всего: нет

подскажите, плз как реализовать вот это:
На окружности задано 2n точек, пронумерованных от 1 до 2n. Перечислить все способы провести n непересекающихся хорд с вершинами в этих точках.

azesmcar

Дата 6.3.2009, 08:23 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 52
Всего: 211

можно найти те точки, между которыми нет других точек и присойденить их..примерно так

user posted image

Добавлено через 5 минут и 47 секунд
а насчет реализации - создай структуру для координаты, запихни в какой нибудь контейнер все точки, напиши предикат для сортировки..
а дальше

Код


for (std::mycontainer::const_iterator it = points.begin(); it != points.end(); ++it)
{
    circle->connect(it, ++it);
}

что-то вроде того

Albor

Дата 6.3.2009, 10:57 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: 2
Всего: 9

Первое, что пришло в голову:
1. анализировать расстояние между точками и проводить хорды, начиная от минимального ( все хорды должны быть максимально короткими) ;
2. лучами от близлежащих точек;

PS по-моему, задача больше на сортировку. Покопайте в сторону "сортировка точек по координате Х" и "сортировка точек по координате У".

Это сообщение отредактировал(а) Albor - 6.3.2009, 11:02

math64

Дата 6.3.2009, 11:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72

Расстояния вычислять не надо. Пересечение определяется по углам или по номерам (если точки стоят по порядку)

Код


typedef double point; // угол точки в радианах (>=0, < 2*PI) или градусах (>=0, < 360) 
//typedef int point; // или номер точки
struct hord {
  point begin;
  point end;
};
bool intersect ( hord h1, hord h2) {
  if (h1.begin > h1.end) { point tmp; tmp = h1.begin; h1.begin = h1.end; h1.end = tmp; }
  if (h2.begin > h1.begin && h2.begin < h1.end) {
    if (h2.end > h1.begin && h2.end < h1.end) return false;
  }
  if (h2.begin < h1.begin || h2.begin > h1.end) {
    if (h2.end < h1.begin || h2.end > h1.end) return false;
  }
  return true;
}

Albor

Дата 6.3.2009, 11:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: 2
Всего: 9

Цитата(math64 @ 6.3.2009, 10:29

)

Расстояния вычислять не надо

Ну, дык, правильно smile

, если точки отсортированы. Хотя, топикстартер поставил задачу только:

Цитата(FreeJaile @ 6.3.2009, 07:12

)

Перечислить все способы провести n непересекающихся хорд с вершинами в этих точках.

math64

Дата 6.3.2009, 12:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72

Примерно так (за отсутствие ошибок не ручаюсь):

Код


void find_hords(int N);
  point* p = new point[2*N];
  bool* used = new bool[N];
  hord* h = new hord[N];
  for (int i = 0; i < 2*N; i++) {
    p[i] = i;
    used[i] = false;
  }
  addhord (p, used, h, 0, N);
  delete h;
  delete used;
  delete p;
}
void addhord (point* p, bool* used, hord* h, int k, int N) {
   if (k == N) {
      for (int i = 0; i < N; i++) {
        cout << '(' << h[i].begin << ',' << h[i].end << ')'
        if (i != N-1)
          cout << ", ";
      }
      cout << endl;
      return;
   }
   for (int i = 0; i <= 2*N; i++) {
     if (!used[i]) {
       h[k].begin = p[i];
       used[i] = true;
       for (int j = i+1; j <= 2*N; j++) {
         if (!used[j]) {
           h[k].end = p[j];
           used[j] = true;
           bool isect = false;
           for (int n = 0; n < k; n++) {
             if (intersect(p[n], p[k]) {
               isect = true;
               break;
             }
           }
           if (!isect)
             addhord (p, used, h, k+1, N);
           used[j] = false;
         }
       }
       used[i] = false;
       break; 
     }
   }
}

azesmcar

Дата 6.3.2009, 12:52 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 52
Всего: 211

Цитата

Перечислить все способы

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

тогда как сказал math64

Anikmar

Дата 6.3.2009, 13:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

Цитата(math64 @ 6.3.2009, 11:29

)

Пересечение определяется по углам или по номерам (если точки стоят по порядку)

Точки могут и не по порядку стоять. Кто мешает хорды в виде куста сделать?

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

Albor

Дата 6.3.2009, 14:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: 2
Всего: 9

Цитата(Anikmar @ 6.3.2009, 12:33

)

Нужно составить все возможные попарные комбинации точек

Не-а, не нужно. В любом случае точки нужно упорядочить, а вариантов 2:
1. по контуру окружности;
2. "кустом" ;
Вариант 1 имеет 2 подварианта расположения хорд, а вариант 2 имеет n подвариантов

Anikmar

Дата 6.3.2009, 14:34 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

Цитата(Albor @ 6.3.2009, 14:17

)

Не-а, не нужно. В любом случае точки нужно упорядочить, а вариантов 2:

В общем-то можно пары и не составлять, но еще есть вариант треугольника (для 6 точек) либо многоугольника.

Для варианта 4-х точек в виде квадрата получается 14 подходящих вариантов и 1 неподходящий.

Albor

Дата 6.3.2009, 14:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: 2
Всего: 9

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

Anikmar

Дата 6.3.2009, 14:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

Цитата(Albor @ 6.3.2009, 14:39

)

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

Это надо у автора темы спросить. Сколько хорд можно из одной точки вести. Принципиально разницы нет - считать пересечением общую точку и все.

Главное перебрать все варианты исключая повторяющиеся.
Грубо говоря из массива
A1, A2, ... A2n
Собрать N пар с соблюдением порядка (в смысле A1-A2 подходит, а A2-A1 - нет).

FreeJaile

Дата 7.3.2009, 13:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 28.2.2008

Репутация: нет
Всего: нет

да, вы правы. общих точек у хорд вообще не должно быть.

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

Код


#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <vector>

using namespace std;

int k,l,i,n=1; //n-число точек
vector<int>a;

void change(int first, int second){  //перестановка двух элементов
    int tmp;
    tmp=a[first];
    a[first]=a[second];
    a[second]=tmp;
}

void print_res(){ //результат текущей перестановки
    for(i=0;i<(n-1);i+=2)
        printf("(%i,%i) ",a[i],a[i+1]);
    printf("\n");
}

void add_hords(){ //добавляет непересекающиеся хорды
    int add=0;
    for(i=0;i<(n-1);i+=2)
        if((a[i+1]-a[i])%2!=0)add++;
    if (add==n/2) print_res();
}

int main()
{
    while(n%2!=0){ //по условию должно быть четное число, нечетное не принимаем
        printf ("enter n\n");
        scanf("%i",&n);
    }
    for(i=0;i<n;i++)
        a.push_back(i+1);

    print_res();
    
    for(k=0;k<(n-1);k++){
        for(l=1;l<n;l++){
            if(k==l)continue;
            change(k,l);
            add_hords();
        }
    }

    getch();
    return 0;
}

Albor

Дата 8.3.2009, 07:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: 2
Всего: 9

Я не сильно понял, зачем ты переставляешь точки? Нужно сделать обход точек сначала от 1й, потом от 2й - так мы получим все варианты хорд "контурного обхода", то есть если мы задали n=4, то должны получить пары 1и2, 3и4, либо 2и3, 4и1. После - 2й способ - создаём пары 1и n, 2 и n-1, 3 и n-2 и т.д. Затем смещаемся на одну точку и повторяем создание пар, смещаться нужно не до n, а до n/2 иначе пойдут повторы.

FreeJaile

Дата 8.3.2009, 10:40 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 28.2.2008

Репутация: нет
Всего: нет

1й способ я уже пробовала. он корректно только для маленьких чисел работает(варианты не все выводит). а 2ой не поняла

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »