Вложенная петля с зависимыми границами счетчик поездки

просто из любопытства Я попытался сделать следующее, что оказалось для меня не столь очевидным; Предположим, у меня есть вложенные циклы с во время выполнения границ, например:Вложенная петля с зависимыми границами счетчик поездки

t = 0 // trip count 
for l in 0:N 
    for k in 0:N 
    for j in max(l,k):N 
     for i in k:j+1 
      t += 1 

t is loop trip count

есть ли общий алгоритм/путь (лучше, чем N^4, очевидно) для расчета рассчитывать поездки цикла?

Если нет, мне было бы интересно узнать, как вы подходите именно к этой конкретной петле. вышеуказанный цикл симметричен (это петли над симметричным тензором ранга-4), и меня также интересуют методы обнаружения симметрии петли.

Я работаю над предположением, что границы итераций зависят только от постоянных или предыдущих переменных цикла. link/journal article, Если вы знаете один, было бы здорово.

источник

2010-05-14 Anycorn

Непонятно, чего вы пытаетесь достичь - можете ли вы начать с проблемы, а не с решением? –

@Eli Я добавил разъяснения – Anycorn

@aaa: ну, последний цикл можно заменить на 't + = j + 1 - k' или что-то в этом роде, но я до сих пор не знаю, что вы пытаетесь сделать –

Если вы хотите знать, сколько раз внутренний цикл:

for j in max(l,k):N

бы быть выполнена, просто вычислить: N - max(l, k) предполагая открытый диапазон, N + 1 - max(l, k) предполагая замкнутый круг.

Например, если:

l = 2 
k = 7 
N = 10

, то он будет работать 7, 8, 9, 10 (закрытый диапазон), так что на самом деле 10 + 1 - 7 = 4 раз.

источник

2010-05-14 06:30:06

Мне интересно узнать, сколько раз выполнялись целые i, j, k, l, а не только один цикл – Anycorn

Я думаю, что он хочет получить формулу для окончательного значения 't' без фактического цикла. – IVlad

Я считаю, что внутренний контур будет работать

t = 1/8 * (N^4 + 6 * N^3 + 7 * N^2 + 2 * N)

раз.

Я действительно не решал проблему напрямую, я приложил многочленное выражение 4-го порядка к точно рассчитанному t для N от 1 до 50, надеясь, что я получу точное соответствие.

Для расчета точной т я использовал

sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),N),k,1,N),l,1,N)

, который должен быть эквивалентом на самом деле работает ваши петли.

data fit, log scale http://img714.imageshack.us/img714/2313/plot3.png

Подгонка для N от 1 до 50 матчей точно и расчета его для N = 100 дает 13258775, используя оба метода.

EDIT: упражнение было сделано с использованием системы maxima алгебры с открытым исходным кодом, вот фактический источник (выход отбрасываются):

nr(n):=sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),n),k,1,n),l,1,n); 
M : genmatrix(lambda([i,j],if j=1 then i else nr(i)), 50, 2); 
coefs : lsquares_estimates(M, [x,y], y = A*x^4+B*x^3+C*x^2+D*x+E, [A,B,C,D,E]); 
sol(x):=ev(A*x^4+B*x^3+C*x^2+D*x+E, coefs); 
sol(N); 
S : genmatrix(lambda([i,j], if j=1 then i else sol(i)), 50, 2); 
M-S; 
plot2d([[discrete,makelist([M[N][1],M[N][2]],N,1,50)], sol(N)], [N, 1, 60], [style, points, lines], [color, red, blue], [legend, "simulation", sol(N)], [logy]); 
compare(nr(100),sol(100));

источник

2010-05-14 10:46:41 Unreason

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

Чтобы убедиться в этом, необходимо учитывать следующее:

for x in 0:N 
    for y in 0:f(x) 
    t += 1

Количество поездка т (N), равно сумме Т (N) = F (0) + F (1) + F (2) + F (3) + ... + F (N-1).

Итак, если вы можете получить формуляр закрытой формы для t (N), независимо от f(), вы нашли очень общий метод создания закрытых форм, слишком общих, я бы сказал, потому что то, что вы здесь здесь, соответствует интеграл и известно, что не все интегралы допускают формулировки замкнутых форм.

источник

2010-05-15 19:40:04

Вложенная петля с зависимыми границами счетчик поездки

ответ

Смежные вопросы