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

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

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


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

???


xayam ©   (01.07.18 07:16[20]


> а сколько равных только единице непонятно

хотя по идее почти все симметрично и их ровно n!/2-1
минус один так как единичная матрица (все единицы на диагоналях) не имеет симметричного представления


xayam ©   (01.07.18 07:22[21]


> хотя по идее почти все симметрично и их ровно n!/2-1

опс точнее (n!-1)/2
но это только если n нечетно.
Если же n четно то непонятно.


Sha ©   (01.07.18 11:06[22]

>xayam ©   (01.07.18 06:50) [16]
>чего-то больно большие числа выдает алгоритм.

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

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

Можно все это проделать намного быстрее, если отказаться от рекурсии:
function xayam5(Max, Sum, Count: integer): integer;
var
 a, b: array of array of integer;
 p: pointer;
 m, s, k, i, v: integer;
begin;
 Result:=0;
 if (Count<=0) or (Sum<=0) or (Max<=0) then exit;

 if Max>Sum then Max:=Sum;
 SetLength(a,1+Sum,1+Max);
 SetLength(b,1+Sum,1+Max);
 for s:=0 to Sum do for m:=0 to Max do b[s,m]:=0;
 for m:=1 to Max do b[m, m]:=1;
 for k:=2 to Count do begin;
   p:=pointer(a); pointer(a):=pointer(b); pointer(b):=p;
   for s:=0 to Sum do for m:=0 to Max do b[s,m]:=0;
   for s:=k to Sum do begin;
     i:=s; if i>Max then i:=Max;
     for m:=1 to i do begin;
       v:=0;
       for i:=1 to m-1 do v:=v+a[s-m,i];
       b[s,m]:=v;
       end;
     end;
   end;

 for i:=1 to Max do Result:=Result+b[Sum, i];
 end;


Можно все это проделать до запредельных значений,
если поменять тип результата на int64.

Было бы желание.


Mystic ©   (03.07.18 09:20[23]

Кешировать надо, у вас много повторений (ИМХО). Например, если рассмотреть 64, 61, а потом 63, 62, то при Max <= 60 у нас будут абсолютно идентичное количество, которое вы честно будете считать два раза. Так что лучше иметь массив 260x64x8, куда записывать уже вычисленные результаты (133k элементов).

Вообще, такой массив хочется заполнять снизу а не сверху, чтобы избежать проверок, а вычислено ли.


Sha ©   (03.07.18 10:20[24]

> Mystic ©   (03.07.18 09:20) [23]

... а вот это попробуйте )


Mystic ©   (03.07.18 13:07[25]

Попробовал сильно не вникая в оптимизацию

#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define N 8
#define SUM 260
#define MAX 64

uint64_t cache[N][SUM+1][MAX+1];

uint64_t phi(void)
{
   /* No variants if MAX = 0 */
   for (uint64_t n=0; n<N; ++n)
   for (uint64_t sum=0; sum <= SUM; ++sum) {
       cache[n][sum][0] = 0;
   }  
   
   /* Fill data for N = 1 */
   for (uint64_t max = 1; max <= MAX; ++max)
   for (uint64_t sum = 1; sum <= SUM; ++sum) {
       cache[0][sum][max] = sum <= max;
   }  
   
   /* Calculate everything */
   for (uint64_t n=1; n<N; ++n)
   for (uint64_t max=1; max <= MAX; ++max)
   for (uint64_t sum=1; sum <= SUM; ++sum) {
       const uint64_t qinclude = sum > max ? cache[n-1][sum-max][max-1] : 0;
       const uint64_t qmiss = cache[n][sum][max-1];
       cache[n][sum][max] = qinclude + qmiss;
   }  
   
   return cache[N-1][SUM][MAX];
}

int main()
{
   printf("phi(%d, %d, %d) = %lu\n", N, SUM, MAX, phi());
   return 0;
}


$ gcc xayam.c -o xayam && time ./xayam
phi(8, 260, 64) = 35154340

real 0m0.001s
user 0m0.001s
sys 0m0.000s


Mystic ©   (03.07.18 13:08[26]

Угадал с ответом?


Mystic ©   (03.07.18 14:03[27]

http://tpcg.io/yM0RNx


Sha ©   (03.07.18 14:27[28]

> Mystic ©   (03.07.18 13:08) [26]
> Угадал с ответом?

Да, ответ верный и время совпадает.

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


Mystic ©   (03.07.18 16:37[29]

А почему время совпадает?


> Еще немного быстрее (1.25 сек на i7-7700)


У меня же получилось 0.001 секунды, при том, что

$ cat /proc/cpuinfo | grep 'model name' | head -1
model name : Intel(R) Core(TM) i3-4160 CPU @ 3.60GHz


Mystic ©   (03.07.18 16:50[30]

У меня такое чувство, что мы скорее упрёмся в производительность процессора, чем в память.

У моём примере используется 1085760 byte памяти (мегабайт).

Если увеличить все параметры в пять раз, а max в 50, мы получим

$ gcc xayam.c -o xayam && time ./xayam
sz = 1 332 640 320
phi(40, 1300, 3200) = 6 182 872 580 981 006 930

real 0m2.192s
user 0m1.903s
sys 0m0.288s


Т. е. надо около гигабайта памяти и почти переполнение типа uint64_t (30% от MAX_UINT64).


Sha ©   (03.07.18 17:02[31]

> Mystic ©   (03.07.18 16:37) [29]
> А почему время совпадает?

Это [15], которая с рекурсией, работает больше секунды.
А время [22], которая без рекурсии, тоже 0 ms.

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


Sha ©   (03.07.18 17:48[32]

> Mystic ©   (03.07.18 16:50) [30]
> Если увеличить все параметры в пять раз, а max в 50, мы получим

При таких размерах кеш сумм будет очень полезен.

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


версия для печати

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

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







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


Наверх

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