Olá pessoal,
Essa é para os matemáticos. 
Estou trabalhando na solução de um problema (desafio de programação), mas o algoritmo que escrevi tem complexidade n^5, o que inviabiliza sua execução mesmo para valores pequenos de entrada.
O que preciso é realizar o somatório de múltiplos somatórios (a função está em anexo).
O algoritmo que tenho, extremamente lento, é o seguinte.
[code]BigInteger n = new BigInteger( “20” );
BigInteger soma = BigInteger.ZERO;
for ( BigInteger i = BigInteger.ONE; !(i.compareTo( n ) > 0); i = i.add( BigInteger.ONE ) ) {
for ( BigInteger j = BigInteger.ONE; !(j.compareTo( n ) > 0); j = j.add( BigInteger.ONE ) ) {
for ( BigInteger k = BigInteger.ONE; !(k.compareTo( n ) > 0); k = k.add( BigInteger.ONE ) ) {
for ( BigInteger l = BigInteger.ONE; !(l.compareTo( n ) > 0); l = l.add( BigInteger.ONE ) ) {
for ( BigInteger m = BigInteger.ONE; !(m.compareTo( n ) > 0); m = m.add( BigInteger.ONE ) ) {
soma = soma.add( ( i.subtract( j ).multiply( j.subtract( k ).multiply( k.subtract( l ).multiply( l.subtract( m ).multiply( m.subtract( i ) ) ) ) ) ).abs() );
}
}
}
}
}[/code]
Queria saber se tem como simplificar a função para que o algoritmo fique mais rápido. Preciso executar ele cerca de 1000 vezes em menos de 3 segundos, para valores de n que variam de 1 a 2000000000.
Para valores de n variando de 1 a 20 eu tenho os seguintes resultados. Imagem para n = 2000000000.
0
0
120
3200
35160
237120
1164800
4572160
15174720
44200640
115961560
279227520
625888120
1320242560
2643301440
5057720320
9300436160
16511760000
28411609720
47535762560
Já procurei bastante. O WolframAlpha só me retorna resultados para dois somatórios consecutivos. A partir do terceiro ele já não resolve, não entende o que estou pedindo. Se alguém tiver o Mathematica ou o MATLab e puder avaliar a expressão para mim, vendo se sugerem alguma simplificação, eu agradeço.
Se alguém quiser dar uma olhada no problema, é esse aqui: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3295
[]'s
Ah, mas você não mostrou o problema corretamente. Você não viu o “módulo 10007” depois dos somatórios? Obviamente para você resolver o problema para n = 2000000000 (que é o maior valor possível) você tem de levar em conta que há esse “módulo”.
Esse problema não pode ser resolvido simplesmente calculando todos os somatórios, e depois achando o módulo. Você tem de achar a fórmula já levando em conta a presença desse módulo.
Dica: comece com 2 somatórios (porque você precisa ter i e j) e então veja se você consegue alguma generalização para 3 ou mais somatórios.
Tem mais uma coisinha interessante. Veja o número 2000000000 que ele passou. Ele é menor que 2^31 - 1, então isso quer dizer que você, de alguma forma, nem precisa usar “long”, talvez se você souber a fórmula certa precise apenas de fazer contas com “int”. Mas isso é para você descobrir.
Note também que 10007 é um número primo, e números primos costumam ter propriedades interessantes.
Oi entanglement, realmente, falou explicar isso. Não postei minha solução completa, mas no final, o que é exibido é o resto da divisão por 10007.
Tentei encontrar um ciclo, igual nesse problema aqui (que já resolvi), mas não consegui.
Pensei em algo do tipo que você mencionou, mas não saiu nada. Não pensei em levar em consideração o módulo, mas sim somente o “miolo” do problema. Realmente o número é representável por um long, o problema é o número gerado pela função, que como você mencionou, talvez não seja usado, visto o tempo necessário para gerá-lo.
Vou tentar encontrar um ciclo… Acho que talvez seja uma saída.
Obrigado!
bem legal essa questão.
Eu sei que existe simplificação para somatoria simples.
exemplo:
somatoria de 1 a n = (n*n+n)/2
vou pensar e se encontrar algum caminho posto aqui.
Nesse caso acho que ele quer o resto da divisão por 10007 porque o resultado dos somatorios seria muito grande.
Dando o resto da divisão por um numero primo fica mais fácil
As respostas variam de 0 a 10006, o problema é conseguir gerar o que deve ser dividido por 10007 ou então encontrar uma alternativa que dividida por 10007 dê o mesmo resultado.
Os números gerados são múltiplos de seus geradores.
já pensou em fazer com numeros pequenos, por exemplo de 0 à 30 e colocar em um gráfico para ver como é a curva?
Olha só, eu comecei pequeno:
<script>
var n=12
var result=0;
var temp;
for(var a=1; a<n; a++)
{
for(var b=1; b><n; b++)
{
temp=Math.abs(a-b);
result+=temp;
document.write( ""+a+" - "+b+" = "+temp+" result = "+result+"><br>")
}
}
</script>
A curva segue algum padrão conhecido ou é muto caótica?
acho que encontrei um caminho:
<script>
var n=10
var result=0;
var temp;
for(var a=1; a<n; a++)
{
for(var b=1; b><n; b++)
{
temp=Math.abs(a-b);
result+=temp;
document.write( ""+a+" - "+b+" = "+temp+" result = "+result+"><br>")
}
document.write( "<br>")
}
</script>
Olha só, eu coloquei esse BR depois do segundo for. Ele separa blocos. O primeiro bloco é exatamente oposto ao ultimo. O segundo é oposto ao penultimo e assim vai.
E se colocar mais uma variável? E mais uma? Para duas é bastante trivial.
vc sabe a formula para duas variaveis?
<script>
var result;
var temp;
var fim=0;
for( var n=1; n<=12; n++)
{
result=0;
for(var a=1; a<=n; a++)
{
for(var b=1; b<=n; b++)
{
temp=Math.abs(a-b);
result+=temp;
//document.write( ""+a+" - "+b+" = "+temp+" result = "+result+"<br>")
}
//document.write( "<br>")
}
document.write( result+" = "+ (result-fim) )
document.write( "<br>")
fim=result;
}
</script>
Encontrei uma P.A.
Agora vou testar para as outras variaveis
A sacada do problema é conhecer triangulo de pascal e arranjos.
Não sou muito bom nisso por isso estou deduzindo de outra forma.
analizando as diferêncas atá encontrar uma razão.
a solucao para 3 variaveis é essa:
((r*(r+1)(r+2)/3) + (n(n+1)(n+2)(n+3)*(n+4)/60)*7)
onde r=n+1 e n qualquer inteiro
Esse é o caminho
[]'s
<script>
var result;
var temp;
var fimA=0;
var fimB=0;
var fimC=0;
var fimD=0;
var fimE=0;
var fimF=0;
var r;
for( var n=1; n<=12; n++)
{
r=n-1
result=0;
for(var a=1; a<=n; a++)
{
for(var b=1; b<=n; b++)
{
tempA=Math.abs(a-b)
for(var c=1; c<=n; c++)
{
tempB=tempA*Math.abs(b-c);
result+=tempB;
}
}
}
fimB = result-fimA
fimA = result;
fimC = fimB-fimC
fimD = fimC-fimD
fimE = fimD-fimE
fimF = fimE-fimF
document.write( " "+fimA+" -- diffs: "+fimB+" "+ fimC + " "+ fimD+" "+ fimE+" "+ fimF)
fimF = fimE
fimE = fimD
fimD = fimC
fimC = fimB
document.write( "<br>" )
}
//================================================================
// solucao para 3 variaveis
//================================================================
for( var n=-1; n<11; n++)
{
r=n+1
//document.write(" - "+ ((r*(r+1)*(r+2)/6)*2 + (n*(n+1)*(n+2)*(n+3)*(n+4)/120)*14) )
document.write(" - "+ ((r*(r+1)*(r+2)/3) + (n*(n+1)*(n+2)*(n+3)*(n+4)/60)*7) )
document.write( "<br>" )
}
/*
//================================================================
// possivelmente poderemos usar
//================================================================
n*(n+1)/2 = 1 3 6 10 15 21 28...
n² = 1 4 9 16 25 36 49...
n*(3n-1)/2 = 1 5 12 22 35 51 70...
n*(4n-2)/2 = 1 6 15 28 45 66 91...
n*(5n-3)/2 = 1 7 18 34 55 81 112...
n*(3n-2) = 1 8 21 40 65 96 133...
//================================================================
chave para as soluções futuras
//================================================================
n*(n+1)/2 = 1 3 6 10 15 21...
n*(n+1)*(n+2)/6 = 1 4 10 20 35 56...
n*(n+1)*(n+2)*(n+3)/24 = 1 5 15 35 70 126...
n*(n+1)*(n+2)*(n+3)*(n+4)/120 ...
*/
</script>
4 variaveis:
<script>
var result;
var temp;
var fimA=0;
var fimB=0;
var fimC=0;
var fimD=0;
var fimE=0;
var fimF=0;
var fimG=0;
var fimH=0;
var r;
for( var n=1; n<=12; n++)
{
result=0;
for(var a=1; a<=n; a++)
{
for(var b=1; b<=n; b++)
{
tempA=Math.abs(a-b)
for(var c=1; c<=n; c++)
{
tempB=tempA*Math.abs(b-c);
//result+=tempB;
for(var d=1; d<=n; d++)
{
tempC=Math.abs(c-d);
result+=tempC*tempB;
}
}
}
}
fimB = result-fimA
fimA = result;
fimC = fimB-fimC
fimD = fimC-fimD
fimE = fimD-fimE
fimF = fimE-fimF
fimG = fimF-fimG
fimH = fimG-fimH
document.write( " "+fimA+" -- diffs: "+fimB+" "+fimC +" "+fimD+" "+fimE+" "+fimF+" "+fimG+" "+fimH)
fimH = fimG
fimG = fimF
fimF = fimE
fimE = fimD
fimD = fimC
fimC = fimB
document.write( "<br>" )
}
//================================================================
// solucao para 4 variaveis
//================================================================
for( var q=-4; q<11; q++)
{
p=q+1
o=q+2
n=q+3
m=q+4
document.write(" - "+ ( (m*(m+1)*(m+2)/6)*2 +
(n*(n+1)*(n+2)*(n+3)/24)*52 +
(o*(o+1)*(o+2)*(o+3)*(o+4)/120)*256 +
(p*(p+1)*(p+2)*(p+3)*(p+4)*(p+5)/720)*408 +
(q*(q+1)*(q+2)*(q+3)*(q+4)*(q+5)*(q+6)/5040)*204 ) )
document.write( "<br>" )
}
/*
//================================================================
chave para as soluções futuras
//================================================================
for( var o=1; o<20; o++)
{
//1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190
//document.write( o*(o+1)/2 )
//1 4 10 20 35 56 84 120 165 220 286 364 455 560 680 816 969 1140 1330
//document.write( o*(o+1)*(o+2)/6 )
//1 5 15 35 70 126 210 330 495 715 1001 1365 1820 2380 3060 3876 4845 5985 7315
//document.write( o*(o+1)*(o+2)*(o+3)/24 )
//1 6 21 56 126 252 462 792 1287 2002 3003 4368 6188 8568 11628 15504 20349 26334 33649
//document.write( o*(o+1)*(o+2)*(o+3)*(o+4)/120 )
//1 7 28 84 210 462 924 1716 3003 5005 8008 12376 18564 27132 38760 54264 74613 100947 134596
//document.write( o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)/720 )
//1 8 36 120 330 792 1716 3432 6435 11440 19448 31824 50388 77520 116280 170544 245157 346104 480700
//document.write( o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)*(o+6)/5040 )
//1 9 45 165 495 1287 3003 6435 12870 24310 43758 75582 125970 203490 319770 490314 735471 1081575 1562275
//document.write( o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)*(o+6)*(o+7)/40320 )
document.write( " " )
}
*/
</script>
Solução:
<script>
var result;
var temp;
var fimA=0;
var fimB=0;
var fimC=0;
var fimD=0;
var fimE=0;
var fimF=0;
var fimG=0;
var fimH=0;
var fimI=0;
var fimJ=0;
var fimK=0;
var r;
for( var n=1; n<=20; n++)
{
result=0;
for(var i=1; i<=n; i++)
{
for(var j=1; j<=n; j++)
{
tempA=Math.abs(i-j)
for(var k=1; k<=n; k++)
{
tempB=tempA*Math.abs(j-k);
//result+=tempB;
for(var l=1; l<=n; l++)
{
tempC=tempB*Math.abs(k-l);
//result+=tempC;
for(var m=1; m<=n; m++)
{
tempD=tempC*Math.abs(l-m)*Math.abs(m-i);
result+=tempD;
}
}
}
}
}
fimB = result-fimA
fimA = result;
fimC = fimB-fimC
fimD = fimC-fimD
fimE = fimD-fimE
fimF = fimE-fimF
fimG = fimF-fimG
fimH = fimG-fimH
fimI = fimH-fimI
fimJ = fimI-fimJ
fimK = fimJ-fimK
document.write( " "+fimA+" -- diffs: "+fimB+" "+fimC +" "+fimD+" "+fimE+" "+fimF+" "+fimG+" "+fimH+" "+fimI+" "+fimJ+" "+fimK)
fimK = fimJ
fimJ = fimI
fimI = fimH
fimH = fimG
fimG = fimF
fimF = fimE
fimE = fimD
fimD = fimC
fimC = fimB
document.write( "<br>" )
}
//================================================================
// solucao para 5 variaveis - FALTA SIMPLIFICAR!
//================================================================
for( var x=0; x<20; x++)
{
//r=s+1
t=-5+x;
s=t+1
r=t+2
q=t+3
p=t+4
o=t+5
document.write(" - "+ (
(o*(o+1)*(o+2)*(o+3)*(o+4)/120)*120 +
(p*(p+1)*(p+2)*(p+3)*(p+4)*(p+5)/720)*2480 +
(q*(q+1)*(q+2)*(q+3)*(q+4)*(q+5)*(q+6)/5040)*15280 +
(r*(r+1)*(r+2)*(r+3)*(r+4)*(r+5)*(r+6)*(r+7)/40320)*38720 +
(s*(s+1)*(s+2)*(s+3)*(s+4)*(s+5)*(s+6)*(s+7)*(s+8)/362880)*42800 +
(t*(t+1)*(t+2)*(t+3)*(t+4)*(t+5)*(t+6)*(t+7)*(t+8)*(t+9)/3628800)*17120
)%10007 )
document.write( "<br>" )
}
/*
//================================================================
// possivelmente poderemos usar
//================================================================
n*(n+1)/2 = 1 3 6 10 15 21 28...
n² = 1 4 9 16 25 36 49...
n*(3n-1)/2 = 1 5 12 22 35 51 70...
n*(4n-2)/2 = 1 6 15 28 45 66 91...
n*(5n-3)/2 = 1 7 18 34 55 81 112...
n*(3n-2) = 1 8 21 40 65 96 133...
//================================================================
chave para as soluções
//================================================================
for( var o=1; o<20; o++)
{
//1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190
//document.write( o*(o+1)/2 )
//1 4 10 20 35 56 84 120 165 220 286 364 455 560 680 816 969 1140 1330
//document.write( o*(o+1)*(o+2)/6 )
//1 5 15 35 70 126 210 330 495 715 1001 1365 1820 2380 3060 3876 4845 5985 7315
//document.write( o*(o+1)*(o+2)*(o+3)/24 )
//1 6 21 56 126 252 462 792 1287 2002 3003 4368 6188 8568 11628 15504 20349 26334 33649
//document.write( o*(o+1)*(o+2)*(o+3)*(o+4)/120 )
//1 7 28 84 210 462 924 1716 3003 5005 8008 12376 18564 27132 38760 54264 74613 100947 134596
//document.write( o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)/720 )
//1 8 36 120 330 792 1716 3432 6435 11440 19448 31824 50388 77520 116280 170544 245157 346104 480700
//document.write( o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)*(o+6)/5040 )
//1 9 45 165 495 1287 3003 6435 12870 24310 43758 75582 125970 203490 319770 490314 735471 1081575 1562275
//document.write( o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)*(o+6)*(o+7)/40320 )
document.write( " " )
}
*/
</script>
[]'s