febb

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

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

From:

tcikuta.livejournal.com

Так ты не оплошал?

From:

diffio.livejournal.com

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

From:

Это нельзя назвать таким словом :)))

From:

Какую програмку?)

From:

tcikuta.livejournal.com

Ты их сделал? :)

From:

Впервые эту задачку поставил один профессор из Браун университета, а решил другой из Карнеги-Мелон. У меня было 3 минуты и я не успел :)

From:

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

From:

Очень любопытная задачка!

From:

С одинаковыми шариками всё просто:
http://en.wikipedia.org/wiki/Close-packing_of_spheres

From:

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

From:

нужно составить новый массив из сумм соседних чисел. алгоритм для этого прост. но вот, что этот новый массив нам даст, и каков следующий шаг?

From:

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

From:

да, с одинаковыми шариками все просто, поэтому стоит ввести ограничение в программу, что число размеров должно быть от 2 до, скажем, 9. ну и также предотвратить создание кластеров в модели, чтобы программа не жульничала.

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

From:

Ограничения врядли помогут. Если аналитическое решение затруднительно, то просто "кухне" они вряли помешают.
Задача напоминает о гравитации многих тел. Ведь компактность - минимум энерги... Кажись шравитация 3-х - это максимум на что способна аналитика.

From:

Алгоритм очень просто - 15 строчек :)
И сложность O(n).

From:

Ну это простой перебор.
Простой перебор не считается в среде программистов "алгоритмом"! :)

From:

leeeto.livejournal.com

омг. вот мой вариант :)
нужен пост про правильно :)

<%

//int arr[]={-1,0,2,7,-10,8,4,3,-4,1};

int arr[]={3,0,2,-7,5,-8,4,3,-4,1};

int max = 0, sum = 0, step=0, firstpos = 0, a=0, b=0;
for (int i=0;i<10;i++)out.println(arr[i]+" ");
out.println("
");

boolean isfirst=true;
if(arr[1]<0)isfirst=false;

for (int i=0;i<10;i++)
{
if (arr[i]<0) {
if(sum>max)
{
max=sum;
a=firstpos;
b=firstpos+step-1;

}

sum=0;
isfirst=true;
step=0;
}
else {
if(isfirst) {
firstpos=i+1;
step=0;
isfirst=false;
}
sum = sum+arr[i];
step++;
}

}

out.println("max= "+max+" a = "+a+ " b= "+b);

%>

From:

У меня тоже была сначала идея, что нужно искать по отрицательным элементам.
Но это на самом деле не так. Ведь за небольшим отрицательным может быть очень хорошее положительное!
Надо быть оптимистом! :)
Спасибо!

From:

построить дерево от листьев к вершине

листья - элементы массива

сумма 2 соседних элементов - узлы первого уровня (если нечетное к-во элементов, до дополняем до четного псевдоэлементом == 0)
сумма 4 соседних элементов - узлы 2 уровня
итд до корня

потом обойти дерево и найти узел/лист, в котором значение максимально

From:

ну и на всякий случай - первое дерево строим с array[0] второе точно так же но начиная с array[1]

и алгоритм выполняем дважды соответственно

From:

Можно придумать массив, для котрого этот алгоритм бессилен.

From:

И вообще нужно всё сделать в один проход :)

From:

leeeto.livejournal.com

хм.
а ведь вы правы. :)))))))))

ладно. буду думать дальше.

From:

Вообще да, я поторопился :)

и как же правильно решается задача?

From:

или однопроходный алгоритм с двумя ползущими указателями и "ощупыванием" вперед переднего на 1 элемент и назад от заднего на 1 элемент, запоминаем для макс. суммы значение и 2 индекса

From:

обижаете. какой же это перебор? это преобразование.

From:

Жаль. Такая програмка здорово бы помогла в разработке сверхтвердых керамик и сплавов, но раз аналитика не может помочь, то будем алхимичить по-старому, интуитивно. Авось, что-нибудь испечется съедобное.

From:

В принципе это известный класс задач.
Нахождение минимум функционала с ограничениями.
Задачу надо центрировать.
Центр - это центр тяжести кластера.
Надо найти минимум его момента инерции.
Ограничения просты - расстояния между точками больше суммы радиусов.
Можно пофантазировать, что на самом деле кластеров будет не один, а много...
И тп.п.

From:

Я бы сделал такое моделирование: на каждом шаге шарик пытается приблизится к своему ближайшему соседу на минимальное возможное расстояние. Считается как можно дольше с некоторой перетряской. Когда система устаканится, можно посмотреть, что получается.

From: