Конференция "Прочее" » Количество разбиений на слагаемые?
 
  • xayam © (22.06.18 05:24) [0]
    Допустим, есть какое-то число m=260,
    которое нужно разложить на n=8 разных слагаемых
    (одинаковые слагаемые не допускаются), каждое
    из которых не превосходит s=n^2=64 (лежат в диапазоне от 1 до 64).

    Как найти количество разбиений числа m на n таких слагаемых в общем виде?
  • xayam © (22.06.18 05:31) [1]
    m=n*(n^2+1)/2=260 при n=8
  • xayam © (23.06.18 05:19) [2]
    конечно брутфорс есть алгоритм (и не один),
    но хотелось бы что-нибудь получше
    поскольку на таких числах временные затраты велики
  • KilkennyCat © (23.06.18 09:33) [3]

    >  временные затраты велики

    ну и что? просчитай заранее, занеси в таблицу. исходя из "лежат в диапазоне от 1 до 64"
    это ряд чисел m от 36 до 484, что не так уж много.
  • картман © (23.06.18 11:29) [4]
    Я только за деньги готов - вспоминать надо
  • xayam © (23.06.18 11:34) [5]

    > Я только за деньги готов - вспоминать надо

    да брутфорс там вообще примитивный
    например,

    function min(k,x:Integer):Integer;
    begin
         if k<x then min:=k
         else min:=x;
    end;

    procedure F(x: integer; k: integer; s:string);
    var
     i : integer;
    begin
     if (x = 0) then begin
        //здесь фильтрация вывода - if ...
        Form1.MemoOutput.Lines.Add(s);
     end
     else
        for i := 1 to min(k, x) do
           F(x - i, i, s + ' ' + IntToStr(i));
    end;

    procedure TForm1.Button1Click(Sender: TObject);
    begin
    F(7,7,'');
    ShowMessage(IntToStr(Form1.MemoOutput.Lines.Count));

  • xayam © (23.06.18 11:43) [6]

    > исходя из "лежат в диапазоне от 1 до 64"

    n тоже переменная и n^2 может быть значительно больше 64, поэтому
    я думаю нет смысл заранее рассчитывать - ресурсов не хватит...
  • Sha © (23.06.18 16:31) [7]
    //xayam ©   (22.06.18 05:24)
    //Число m=260 нужно разложить на n=8 разных слагаемых (одинаковые не допускаются),
    //каждое из которых не превосходит s=n^2=64 (лежат в диапазоне от 1 до 64).

    //Количество кортежей (слагаемые упорядочены по величине)
    function xayam(Max, Sum, Count: integer): integer;
    var
     i: integer;
    begin;
     Result:=0;
     if Max>Sum then Max:=Sum;
     if Count>0 then for i:=Max downto 1 do Result:=Result + xayam(i-1, Sum-i, Count-1)
     else if Sum=0 then Result:=1;
     end;

    procedure TForm1.Button1Click(Sender: TObject);
    begin;
     ShowMessage(IntToStr(xayam(64,260,8))); //35154340
     end;
  • xayam © (23.06.18 17:07) [8]

    > Sha ©   (23.06.18 16:31) [7]

    а как вывести получившееся суммы?
    чего-то больно много получается
  • Sha © (23.06.18 17:30) [9]
    Как вывести, не знаю.
    Не думаю, что получится простая формула.

    Так считает немного быстрее за счет исключения последнего цикла:
    function xayam2(Max, Sum, Count: integer): integer;
    var
     i: integer;
    begin;
     Result:=0;
     if Count>1 then begin;
       if Max>Sum then Max:=Sum;
       for i:=Max downto 1 do Result:=Result + xayam2(i-1, Sum-i, Count-1);
       end
     else if (Count=1) and (0<Sum) and (Sum<=Max) then Result:=1;
     end;
  • xayam © (23.06.18 17:36) [10]

    > Sha ©   (23.06.18 17:30) [9]
    > Как вывести, не знаю.
    > Не думаю, что получится простая формула.

    самое интересное что эта задача прямо соотносится с задачей о расстановки ферзей.
    И связано с магической константой квадрата.
    Вот накатал пример
    https://ic.pics.livejournal.com/xayam/26173943/38977/38977_900.png
  • xayam © (23.06.18 17:56) [11]
    там опечатка в координатах, но смысл тот же - сумма координат ферзей дает магическую константу (что легко выводится формульно), однако наоборот неверно - если разложить магическую константу на n слагаемых - это не значит что получившиеся координаты будут координатами не угрожающих друг другу ферзей - необходимо еще вычесть количество диагональных коллизий...
  • xayam © (23.06.18 18:06) [12]

    > Sha ©   (23.06.18 17:30) [9]

    причем основная проблема этих чертовых ферзей - это как раз диагональные коллизии
    Как думаешь их кол-во реально посчитать без генерации самих координат?
  • Sha © (23.06.18 18:07) [13]
    Все давно посчитано.
    Перебором )
  • xayam © (23.06.18 18:09) [14]

    > Sha ©   (23.06.18 18:07) [13]
    > Все давно посчитано.
    > Перебором )

    до n=27 а дальше тупик
    https://oeis.org/search?q=A000170
  • Sha © (24.06.18 16:09) [15]
    Еще немного быстрее (1.25 сек на i7-7700)
    function xayam3(Max, Sum, Count: integer): integer;
    begin;
     Result:=0;
     if Count<=1 then begin;
       if (0<Sum) and (Sum<=Max) then Result:=1;
       end
     else begin;
       if Max>Sum then Max:=Sum;
       while Max>=Count do begin;
         Result:=Result + xayam3(Max-1, Sum-Max, Count-1);
         dec(Max);
         end;
       end;
     end;
  • xayam © (01.07.18 06:50) [16]
    чего-то больно большие числа выдает алгоритм.
    Мне кажется он не учитывает что числа разложения должны быть разными.
    Может переформулировать задачу.
    Например, сколько определителей равных единице существует для матрицы размером n x n.
    Сами элементы матрицы равны или 0 или 1.
    Местоположение 1 определяет координаты ферзя на доске.
    Соответственно единиц ровно n штук в матрице.
    И судя по определению, неединичные определители могут возникать только если в столбце и/или в строке более одной единицы.
  • xayam © (01.07.18 06:57) [17]
    вообще по идее таких определителей должно быть n! (n факториал).

    > Sha

    или нет?
  • xayam © (01.07.18 06:59) [18]

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

    а так как количество единиц ограничено то получается
    тогда существует строка или столбец где все элементы нулевые -
    значит и определитель равен нулю
  • xayam © (01.07.18 07:08) [19]
    хотя возможно определитель еще может быть равен -1
    тогда всех определителей равных -1 и 1 ровно n! а сколько равных только единице непонятно.

    ???
 
Конференция "Прочее" » Количество разбиений на слагаемые?
Есть новые Нет новых   [118232   +40][b:0][p:0.001]