Алгоритм поиска комбинаций чисел удовл. заданным условиям

[AleksK]

Задача состоит в следующем, дано любое целое неотрицательное число, найти все комбинации из 2,3,4.... чисел, так же неотрицательных и целых (для каждого случая отдельно) сумма которых равна заданному числу.

P.S. Если ктонибудь занимался алгоритмами для аналитического разбора и упрощения выражений откликнитесь.

[bot]

Какие выборки слагаемых рассматриваются - с повторениями или без, упорядоченные или нет? От этого зависит их число.
А зачем их перечислять-то?

[AleksK]

необходимо сгенерировать многочлен вида C_{1}x^{n_{1}}y^{n_{2}}z^{n_{3}}...+ C_{2}x^{n_{1}}y^{n_{2}}z^{n_{3}}... + ... + C_{N}x^{n_{1}}y^{n_{2}}z^{n_{3}}... где сумма всех n_{i} в каждом слагаемом будет равна заранее заданному числу, тоесть надо получить однородный (если я не ошибаюсь) многочлен заранее заданного порядка. Соответственно необходимо получить все возможны варианты слагаемых. Двумерный вариант решается элементарным циклом с двумя переменными, а вот на счёт 3-х и более измерений я сообразить не могу. Наверняка есть алгоритмы, но даже не представляю где искать.

[bot]

Стало быть выборки упорядоченные с повторениями, их число $C_{k+n-1}^n$, где $k$ - число переменных, а $n$ - степень однородности.
Ну а перечислить все слагаемые - это перечислить все решения уравнения
$n_1+n_2+...+n_k=n$ в неотрицательных целых числах.
Реализуется очевидно $k-1$ вложенными друг в друга циклами. А куда же тут денешься?

[enko]

Может не верно, времени не было, не проверял.

var
  A:array[1..maxk]of word;//вектор решений

procedure Search(M,k:word);
var
  x:word;
begin
  if k=1 then
  begin
    A[k]:=M;
    OutRes;//вывод вектора в файл или куда нужно.
  end
  else
    for x:=0 to M do Search(M-x,k-1);
end;

AleksK, какого аналитического разбора, интерпритатор символьных выражений? - этим немного занимался.
Может вам это нужно для симметрических полиномов?
Я занимался представлением симметрических полиномов через элементарные влоб, т.е. без СЛУ , а так как в доказательстве основной теоремы о симметрических полиномах (теорема о возможности представления ч.з. эл.сим.)

[AleksK]

enko
Необходимо сгенерировать однородный многочлен заданной размерности и заданного порядка . Потом применить к нему оператор дифференциальный оператор, тоесть необходимо будет продифференцировать по одной или нескольким переменным (скорее всего несколько раз) потом упростить выделить однородные слагаемые из коэффициентов при них составить систему однородных уравнений и решить её.

[enko]

AleksK На чем вы собираетесь все это писать? И с какой целью?
Над каким полем многочлен? Какой оператор?

[AleksK]

enko
Писать на BlacBox язык Component Pascal. Оператор допустим $\frac{\partial^{2}}{\partial^{2} x} + \frac{\partial}{\partial x}$. Цель научная работа. Над каким полем многочлен? - не понял вопроса.

[enko]

AleksK писал(а):

Над каким полем многочлен? - не понял вопроса.

Ну из какого поля коэффециенты R, C, Q, F_{p^n}
или может из кольца, например Z, Z_n?
Что такое BlacBox? не слышал, дайте ссылку почитаю или расскажите кратко.
Для начала определитесь с тем, как будете представлять многочлены. Какие у вас соображения?
Советую начать со сложения, умножения и приведения подобных, а дифф. потом добавить.
Процедуру проверяли?

[worm2]

AleksK писал(а):

Писать на BlacBox язык Component Pascal.

Вы случаем не из Орла? Там любят BlackBox. Но, кроме того, любят мучать студентов всякими разными инвариантами циклов и прочей теорией. Так что, боюсь, просто работающей программой Вам не отделаться.

[AleksK]

enco
Коэффициенты - действительные числа. BlacBox - среда разработки на Component Pascal на нём же и написана. Вот ссылочка oberoncore.ru. В общем-то это рапзвитие Pascal. Синтакси почти тот же, изменилась объектная модель но это в данном случае не важно. Для представления многочлена пишу классы, один клас (если говорить языком CP - модуль) для одночлена и класс для многочлена. Может не совсем разумный подход но других идей пока в голову не приходило. Соотвественно в модуле одночлена будет содержаться структура в которой хранятся степени перменных, числовой множитель и служебная информация, в модуле многочлена будет массив из одночленов. На счёт операций над ними пока ещё не поределился.

Добавлено спустя 1 минуту 46 секунд:

worm2
Нет я из Ельца, хотя вы почти угадали

[enko]

Alexk если хочешь посмотри мой программки и их исходники, может что-то пригодится. www.silchenko-evg.narod.ru/arh/pol.rar