61 lines
1 KiB
Text
61 lines
1 KiB
Text
mata
|
|
struct ans {
|
|
real scalar p,q,s
|
|
string scalar u
|
|
}
|
|
|
|
struct ans scalar function aux(n,k) {
|
|
external dim,opt
|
|
struct ans scalar r,r1,r2
|
|
real scalar s,i
|
|
|
|
if (n==1) {
|
|
r.p = dim[k]
|
|
r.q = dim[k+1]
|
|
r.s = 0
|
|
r.u = strofreal(k)
|
|
return(r)
|
|
} else if (n==2) {
|
|
r.p = dim[k]
|
|
r.q = dim[k+2]
|
|
r.s = r.p*r.q*dim[k+1]
|
|
r.u = sprintf("(%f*%f)",k,k+1)
|
|
return(r)
|
|
} else if (asarray_contains(opt,(n,k))) {
|
|
return(asarray(opt,(n,k)))
|
|
} else {
|
|
r.p = dim[k]
|
|
r.q = dim[k+n]
|
|
r.s = .
|
|
for (i=1; i<n; i++) {
|
|
r1 = aux(i,k)
|
|
r2 = aux(n-i,k+i)
|
|
s = r1.s+r2.s+r1.p*r1.q*r2.q
|
|
if (s<r.s) {
|
|
r.s = s
|
|
r.u = sprintf("(%s*%s)",r1.u,r2.u)
|
|
}
|
|
}
|
|
asarray(opt,(n,k),r)
|
|
return(r)
|
|
}
|
|
}
|
|
|
|
function optim(a) {
|
|
external dim,opt
|
|
struct ans scalar r
|
|
real scalar t
|
|
|
|
timer_clear()
|
|
dim = a
|
|
opt = asarray_create("real",2)
|
|
timer_on(1)
|
|
r = aux(length(a)-1,1)
|
|
timer_off(1)
|
|
t = timer_value(1)[1]
|
|
printf("%10.0f %10.0f %s\n",t*1000,r.s,r.u)
|
|
}
|
|
|
|
optim((1,5,25,30,100,70,2,1,100,250,1,1000,2))
|
|
optim((1000,1,500,12,1,700,2500,3,2,5,14,10))
|
|
end
|