используя рекурсию для решения Эйлера 18 в д - PullRequest
Новая
       5

используя рекурсию для решения Эйлера 18 в д

0 голосов
/ 25 февраля 2019

Я написал этот код в q для решения проблемы Эйлера 18, как описано в ссылке ниже, с использованием рекурсии.

/4178966/proekt-eilera-18-podhod

Несмотря на то, что код работает, он неэффективен и вызывает переполнение стека при пирамидах размером более 3000. Как я могу сделать этот код намного более эффективным. Я считаю, что оптимальный код может быть меньше 30символы. 

pyr:{[x]
    lsize:count x;
    y:x;
    $[lsize <=1;y[0];
    [.ds.lastone:x[lsize - 1];
    .ds.lasttwo:x[lsize - 2];
    y:{{max (.ds.lasttwo)[x] +/: .ds.lastone[x],.ds.lastone[x+1]}each til count .ds.lasttwo};
    $[(count .ds.lasttwo)=1;y:{max (.ds.lasttwo) +/: .ds.lastone[x],.ds.lastone[x+1]}0;y:y[]];
    x[lsize - 2]:y;
    pyr[-1_x]]]
 }

1 Ответ

0 голосов
/ 25 февраля 2019

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

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

q)input:(75;95 64;17 47 82;18 35 87 10;20 04 82 47 65;19 01 23 75 03 34;88 02 77 73 07 63 67;99 65 04 28 06 16 70 92;41 41 26 56 83 40 80 70 33;41 48 72 33 47 32 37 16 94 29;53 71 44 65 25 43 91 52 97 51 14;70 11 33 28 77 73 17 78 39 68 17 57;91 71 52 38 17 14 91 43 58 50 27 29 48;63 66 04 68 89 53 67 30 73 16 69 87 40 31;04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)
q)last input
4 62 98 27 23 9 70 98 73 93 38 53 60 4 23
q)1_(|) prior last input
62 98 98 27 23 70 98 98 93 93 53 60 60 23

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

q)foo:{y+1_(|) prior x}
q)foo[input 14;input 13]
125 164 102 95 112 123 165 128 166 109 122 147 100 54

Затем, чтобы применить эту функцию ко всему, используйте наречие over: 

q)foo over reverse input
,1074

РЕДАКТИРОВАТЬ: Подход, описанный выше, может быть обобщен далее.

q предоставляет функцию макс. Перемещения mmax.При этом вы можете найти "x -элемент, перемещающий максимум числа y", который обобщает использование prior выше.Например, вы можете использовать это, чтобы найти максимум движения пар или триплетов в последней строке ввода: 

q)last input
4 62 98 27 23 9 70 98 73 93 38 53 60 4 23
q)2 mmax last input
4 62 98 98 27 23 70 98 98 93 93 53 60 60 23
q)3 mmax last input
4 62 98 98 98 27 70 98 98 98 93 93 60 60 60

mmax можно использовать для упрощения fooвыше: 

q)foo:{y+1_ 2 mmax x}

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

    5
  5 6 7
6 7 3 9 1
...