-
Допустим, есть какое-то число m=260,
которое нужно разложить на n=8 разных слагаемых
(одинаковые слагаемые не допускаются), каждое
из которых не превосходит s=n^2=64 (лежат в диапазоне от 1 до 64).
Как найти количество разбиений числа m на n таких слагаемых в общем виде?
-
m=n*(n^2+1)/2=260 при n=8
-
конечно брутфорс есть алгоритм (и не один),
но хотелось бы что-нибудь получше
поскольку на таких числах временные затраты велики
-
> временные затраты велики
ну и что? просчитай заранее, занеси в таблицу. исходя из "лежат в диапазоне от 1 до 64"
это ряд чисел m от 36 до 484, что не так уж много.
-
Я только за деньги готов - вспоминать надо
-
> Я только за деньги готов - вспоминать надо
да брутфорс там вообще примитивный
например,
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
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));
-
> исходя из "лежат в диапазоне от 1 до 64"
n тоже переменная и n^2 может быть значительно больше 64, поэтому
я думаю нет смысл заранее рассчитывать - ресурсов не хватит...
-
//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;
-
> Sha © (23.06.18 16:31) [7]
а как вывести получившееся суммы?
чего-то больно много получается
-
Как вывести, не знаю.
Не думаю, что получится простая формула.
Так считает немного быстрее за счет исключения последнего цикла:
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;
-
-
там опечатка в координатах, но смысл тот же - сумма координат ферзей дает магическую константу (что легко выводится формульно), однако наоборот неверно - если разложить магическую константу на n слагаемых - это не значит что получившиеся координаты будут координатами не угрожающих друг другу ферзей - необходимо еще вычесть количество диагональных коллизий...
-
> Sha © (23.06.18 17:30) [9]
причем основная проблема этих чертовых ферзей - это как раз диагональные коллизии
Как думаешь их кол-во реально посчитать без генерации самих координат?
-
Все давно посчитано.
Перебором )
-
-
Еще немного быстрее (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;
-
чего-то больно большие числа выдает алгоритм.
Мне кажется он не учитывает что числа разложения должны быть разными.
Может переформулировать задачу.
Например, сколько определителей равных единице существует для матрицы размером n x n.
Сами элементы матрицы равны или 0 или 1.
Местоположение 1 определяет координаты ферзя на доске.
Соответственно единиц ровно n штук в матрице.
И судя по определению, неединичные определители могут возникать только если в столбце и/или в строке более одной единицы.
-
вообще по идее таких определителей должно быть n! (n факториал).
> Sha
или нет?
-
> И судя по определению, неединичные определители могут возникать
> только если в столбце и/или в строке более одной единицы.
а так как количество единиц ограничено то получается
тогда существует строка или столбец где все элементы нулевые -
значит и определитель равен нулю
-
хотя возможно определитель еще может быть равен -1
тогда всех определителей равных -1 и 1 ровно n! а сколько равных только единице непонятно.
???
Есть новые 
Нет новых [134427 +34][b:0][p:0.001]