Форум Flasher.ru
Страница 1 из 2 1 2 >
Показывать 40 сообщений этой темы на одной странице

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)
-   -   По графам (http://www.flasher.ru/forum/showthread.php?t=128237)

Герыч 03.08.2009 01:37
По графам
 
Пишу сюда, потому что по общим вопросам программирования ветки нет:mad:
Итак, есть n вершин, у каждой может быть максимум k рёбер. Как посчитать, сколько у всего графа будет максимально рёбер?
Это мне нужно, чтобы оптимально просчитать размер пула для динамического создания связей в желе.

Добавлено через 5 минут
Пока получается наверно такая формула: round(n*k/2)

r_r_f_r 03.08.2009 11:20
Используй списки, с ними флеш отлично дружит, только перед помещением в пул обязательно линки на частицы желе затереть нужно.

Герыч 03.08.2009 13:30
=) я сразу так сделал. Вопрос не в этом, вопрос в оптимальном размере для пула. Для каждой частицы я разрешаю максимум k связей, поэтому узнав эту формулу я узнаю оптимальный размер для пула. Вот как)
P.S. пул - это у меня связный список

r_r_f_r 03.08.2009 13:42
что-то не понимаю зачем нужен размер пула?// извиняюсь если что:)

Element:
Код AS3:
 

public static var pool:Element;

public var next:Element;

public var prev:Element;
Container:
Код AS3:
public function addElement(value:Element):Element

{

        Element.pool.prev = value;

        value.next = Element.pool;

        value.prev = null;

        Element.pool = value;

        return element;

}

 

public function removeElement(value:Element):void

{

        if (value == Element.pool)

        {

                Element.pool = Element.pool.next;

        }

        else

        {

                value.prev.next = value.next;

                value.next.prev = value.prev;

        }

        value.next = null;

        value.prev = null;

}

 

public function doSmt():void

{

        var element:Element = Element.pool;

        while (element)

        {

//                element.doSmt();

                element = element.next;

        }

}
Всё же нужно вчитываться лучше, ступил, сорри.
Но всё таки я не понимаю, зачем в списке нужен размер?
Ты же не выделяешь пямять под него.

Герыч 03.08.2009 13:51
Ты путаешь пул со связным списком.
Сам пул я организовал как связный список(это не так важно, это чисто реализация), но его сначала надо инициализировать некоторым числом элементов. Поскольку у меня почти гарантированно происходит ситуация, когда у каждой частицы желе будет достигнуто максимальное число связей, то пул мне лучше сразу инициализировать нужным числом объектов - связей.

r_r_f_r 03.08.2009 14:03
Ну хозяин как говорится - барин.
Но формула у вас неверна, при к=5 и n=3, а на другую мозгов не хватает.

Я бы сделал инициализацию по требованию.
Код AS3:
curentEelement = Element.pool ? Element.pool : Element.pool = new Element();

Герыч 03.08.2009 14:08
Сейчас именно такая инициализация)
Просто
Цитата:
Сообщение от Герыч (Сообщение 840150)
...у меня почти гарантированно происходит ситуация, когда у каждой частицы желе будет достигнуто максимальное число связей, то пул мне лучше сразу инициализировать нужным числом объектов - связей.
а, я забыл про k и n сказать) k<<n, т.е. к примеру n=200, k=20

r_r_f_r 03.08.2009 14:18
Тут тем более, я не знаю математического способа как можно описать "много меньше":)

Герыч 03.08.2009 14:19
Так, зря я всех тут тревожил. Я просто немного ошибся. Формула отлично работает)
P.S. На будущее: перепроверять код, написанный в час ночи=)

udaaff 03.08.2009 15:00
Количество ребер, по идее, будет зависеть от того, как мы соединим вершины. Поэтому точную формулу, скорее всего, вывести нельзя. Есть формула для полного графа, где все вершины соединены: n * (n - 1) / 2. Т.е. как твоя формула, только без округления, так как оно тут не нужно. В правильной формуле округление бы не понадобилось.
К примеру: У графа с четырьмя вершинами и максимальным количеством ребер 2, может быть 4 ребра, а может быть и три.


Часовой пояс GMT +4, время: 19:03.
Страница 1 из 2 1 2 >
Показывать 40 сообщений этой темы на одной странице

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.