|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 20 Oct 2001 01:52:15
To : Michael Sedov
Subject : Re: Задачка!
--------------------------------------------------------------------------------
"Michael Sedov" <Michael.Sedov@p2.f185.n5015.z2.fidonet.org> wrote in
message news:3757916161@p2.f185.n5015.z2.ftn...
> Заaeачка такого плана. ужно посчитатue количество счастливых
> билетов, ну в смысле таких, у которых сумма первой половины
> чисел равна сумме второй. Полный перебор не приемлим. Вхоaeные
> aeанные: n - кол-во oeифер в кажaeой половине, k - система счисления.
> n <= 127, k <= 127. При полном переборе, на пример, aeля n = 4 и k = 50
> считает мой комп около 25 минут. По этому нужно приaeуматue что-нибуaeue
> оригиналueное.
Скорее всего есть комбинаторные формулы для числа
комбинаций K чисел из диапазона 0..N-1. Hо я не помню :(
А с ними достаточно просто было бы.
Поэтому привожу очень грязный код который вместо этих
простых формул делает прямое суммировние.
s0,s1,s2,s3 - содержат количество комбинаций соответственно
1-го, 2-х, 3-х, 4-х чисел, дающих сумму равную индексу.
Система счисления+1 задается, а количество цифр просто
набрано повторением циклов.
При увеличении числа цифр или системы счисления возможны
проблемы с переполением. Hо так пока считает и довольно быстро.
const int N=128;
__int64 CalculateLuckyTicketsNumber(){
int s0[4*N], s1[4*N], s2[4*N], s3[4*N];
for(int i=0; i<4*N; i++) s0[i]=s1[i]=s2[i]=s3[i]=0;
for(int i=0; i<N; i++) s0[i]=1;
for(int i=0; i<2*N; i++)for(int k=0; k<=i && k<N; k++) s1[i]+=s0[i-k];
for(int i=0; i<3*N; i++)for(int k=0; k<=i && k<N; k++) s2[i]+=s1[i-k];
for(int i=0; i<4*N; i++)for(int k=0; k<=i && k<N; k++) s3[i]+=s2[i-k];
__int64 r=0;
for(int i=0; i<4*N; i++){ __int64 v =s3[i]; r+=v*v; }
return r;
}
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Задачка! 
