Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник |
Коллекция курьезных вопросов из форумов
KOL и MCK |
KOL и MCK - Компактные программы на Delphi
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »
Страницы: 1 2

Количество разбиений на слагаемые?


xayam ©   (22.06.18 05:24

Допустим, есть какое-то число 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! а сколько равных только единице непонятно.

???


Страницы: 1 2 версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо