Самый быстрый способ распечатать список целых чисел как треугольник от внешнего к внутреннему

Ответ 1

@groovy: Я хотел бы добавить комментарий к вашему сообщению, но я не могу (я новичок здесь). Я думаю, что эту функцию можно упростить как:

var a=0;
var atemp=0;
var edge=0;
function cal(x,y,m){
    a=Math.min((y-x),(x),(m-1-y));
    atemp=(((m+(m-3*a+1))*3*a)/2);
    edge=m-3*a;
    if(a==x){
        return atemp+1+y-a*2;
    }else if(a==m-1-y){
        return atemp+edge+x-a;
    }else{
        return atemp+edge*2-2+m-y-a;
    }
}

Простите, что я не привык давать хорошие имена, и у меня нет компилятора, поэтому я написал его в памяти JS, O (1) для:

a (minimum number of the position to the bottom, left and right), 
atemp (the total number of the outer loops of triangle caused i.e. for m=4, when we print number 10, 1-9 forms the outer loop of triangle and atemp is 9), 
edge (the edge is the longest edge of the current triangle)

O (n) для временной сложности для того, чтобы вы распечатывали все номера (без paddings) с помощью вложенного цикла sth like (not JS):

for(i=0;i<m;i++){ for(j=0;j<=i;j++) print cal(j,i,m); print '\n'}

(ps. Я dun понимаю hashkell, но я думаю, что ваша идея как-то так, пожалуйста, укажите, не пропустил ли я какой-либо случай)

Ответ 2

Здесь метод, который использует постоянный объем памяти, если вы предполагаете оптимизацию "хвостового вызова", предотвращает ненужное увеличение стека вызовов. (код находится в Python, но не использует любые конструкции, которые не легко переносятся)

#returns the value at the given position in the triangle of a particular size.
def valueAt(x,y,size):
    #is position out of bounds?
    if x >= size or y >= size or x > y:
        return None
    #is position on the left edge of the triangle?
    if x == 0:
        return y+1
    #is position on the bottom edge of the triangle?
    if y == size - 1:
        return x + size
    #is position on the right edge of the triangle?
    if x == y:
        return 3*size - 2 - x
    #position must lie somewhere within the triangle.
    return 3*size - 3 + valueAt(x-1, y-2, size-3)

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

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

#adds spaces to the start of the string.
def pad(v, amt):
    while len(v) < amt:
        v = " " + v
    return v

def showTriangle(size):
    #figure out how many characters long each value should be, 
    #based on the length of the largest number
    maxValue = size * (size+1) / 2
    maxLength = len(str(maxValue))

    for y in range(size):
        print "\n",
        for x in range(y+1):
            val = valueAt(x,y,size)
            if val:
                print pad(str(val), maxLength),

for i in range(3, 12+1, 3):
    showTriangle(i)
    print "\n"

Результат:

1
2 6
3 4 5


 1
 2 15
 3 16 14
 4 17 21 13
 5 18 19 20 12
 6  7  8  9 10 11


 1
 2 24
 3 25 23
 4 26 39 22
 5 27 40 38 21
 6 28 41 45 37 20
 7 29 42 43 44 36 19
 8 30 31 32 33 34 35 18
 9 10 11 12 13 14 15 16 17


 1
 2 33
 3 34 32
 4 35 57 31
 5 36 58 56 30
 6 37 59 72 55 29
 7 38 60 73 71 54 28
 8 39 61 74 78 70 53 27
 9 40 62 75 76 77 69 52 26
10 41 63 64 65 66 67 68 51 25
11 42 43 44 45 46 47 48 49 50 24
12 13 14 15 16 17 18 19 20 21 22 23

Изменить: если ваша конкретная система не реализует оптимизацию хвостового вызова, вы можете реализовать итеративную форму самостоятельно:

def valueAt(x,y,size):
    acc = 0
    while True:
        #is position out of bounds?
        if x >= size or y >= size or x > y:
            return None
        #is position on the left edge of the triangle?
        if x == 0:
            return acc + y+1
        #is position on the bottom edge of the triangle?
        if y == size - 1:
            return acc + x + size
        #is position on the right edge of the triangle?
        if x == y:
            return acc + 3*size - 2 - x
        #position must lie somewhere within the triangle.
        acc += 3*size - 3
        x-= 1
        y -= 2
        size -= 3

Ответ 3

O (1) для памяти. Он печатает 3 части треугольников, вставленных друг в друга. Каждый треугольник состоит из 3 строк чисел - слева вертикальный, горизонтальный снизу и числа, расположенные по диагонали правой стороны. Для любого внутреннего треугольника мы знаем начальное значение верхнего левого числа, которое вычисляется внешним. Процедура печати состоит из трех циклов, которые печатают части треугольников, соответствующие текущей строке:

• печать левой вертикальной части
• распечатать нижнюю часть
• печатать диагональные номера

Он проходит через все строки (i) и сохраняет количество треугольников в t. Код в java, просто измените m в main на то, что вы хотите:

открытый класс TrianglePrint {

public static void main(String[] args) {
    int m = 9;
    int t = 1;
    int p = 2;
    for (int i = 1; i <= m; i++) {
        if (t*2 < i && t+i < m) {
            t++;
        }
        int m1 = 0;
        for (int k = 1; k <= t && k <= i; k++) {
            System.out.print((i-(k - 1)*2 + m1)  + " ");
            m1 = getEnd(m, k); 
        }
        if (m - t + 1 == i) {
            t--;
            m1 = getEnd(m, t) + m-3*t;
            for (int k = 1; k <= p; k++) {
                System.out.print((k + m1)  + " ");
            }
            p += 3;
        }
        for (int k = t; k > 0; k--) {
            if (i < 2*k) {
                continue;
            }
            m1 = getEnd(m, k) + 2*k;
            System.out.print((m1 - i)  + " ");
        }
        System.out.println();
    }
}

private static int getEnd(int m, int t) {
    if (t == 0) {
        return 0;
    }
    int e = 3*m - 3;
    for (int k = 1; k < t; k++) {
        e += 3*(m - 3*k) - 3;
    }
    return e;
}

Результаты пары:

1 
2 6 
3 4 5

1 
2 33 
3 34 32 
4 35 57 31 
5 36 58 56 30 
6 37 59 72 55 29 
7 38 60 73 71 54 28 
8 39 61 74 78 70 53 27 
9 40 62 75 76 77 69 52 26 
10 41 63 64 65 66 67 68 51 25 
11 42 43 44 45 46 47 48 49 50 24 
12 13 14 15 16 17 18 19 20 21 22 23

Изменить код после некоторой оптимизации:

for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= i; j++) {
            int t = Math.min(Math.min(i - j + 1, j), m - i + 1);
            int tSide = m - 3 * (t - 1);
            int end = (m + tSide + 1) * (m - tSide) / 2;
            if (t == j) {
                // vertical line
                System.out.print(end + i - t * 2 + 2 + " ");
            } else if (t == m - i + 1) {
                // bottom line
                System.out.print(end + tSide + j - t + " ");
            } else {
                // diagonal
                System.out.print(end + tSide * 2 + m - i - t + " ");
            }
        }
        System.out.println();
    }

Ответ 4

Здесь вы идите, прямое вычисление значения, основанное на x y и m. O (1), O (1). Я считаю, что этот тип метода может быть самым быстрым.

UPDATE: Pass By написал красивое, сжатое обобщение, похоже, вдохновленное этим - см. этот ответ.

Код Haskell:

import Control.Monad (forM_)

f x y m 
  | rem m 3 /= 0 = error "Can only construct triangle if m is divisible by 3."
  | x > m || y > m || x < 1 || y < 1 = error "x and/or y out of bounds."
  | y == 1       = 1
  | y == m       = x - 1 + m
  | y <= lastTop = if x > div (if even y then y else y - 1) 2 + 1
                      then xOnHypotenuse
                      else xOnAltitude
  | otherwise    = let x0 = div (div (2*m) 3) 2 + 1 - (y - 2 * div m 3)
                       x1 = x0 + 2 + 3*(y - 2 * div m 3 - 1)
                   in if x < x0 
                         then xOnAltitude
                         else if x > x1 
                                 then xOnHypotenuse
                                 else xOnBase x0
 where top y = div (m*(m + 1)) 2 
             - div ((m - 3 * div y 2)*(m - 3 * div y 2 + 1)) 2
       lastTop = div (2 * m) 3
       xOnAltitude = let triangleNum = x
                         appropriateY = 2*(triangleNum - 1)
                         toAdd = y - appropriateY
                     in top appropriateY + toAdd
       xOnHypotenuse = let triangleNum = y - x + 1
                           appropriateY = 2*triangleNum 
                           toSubtract = y - appropriateY
                       in top appropriateY - toSubtract
       xOnBase baseStartingPosition = 
         let triangleNum = m - y + 1
             appropriateY = 2*(triangleNum - 1)
             baseStartingNum = top appropriateY 
                             + m - (2 + if triangleNum > 2 
                                           then 3*(triangleNum-2) 
                                           else 0) - 1
             toAdd = x - baseStartingPosition
         in baseStartingNum + toAdd

display m = 
  let maxLength = length . show $ div (m*(m + 1)) 2
      pad num = let x = length . show $ num 
                in concat (replicate (maxLength - x) " ") ++ show num
  in forM_ [1..m] (\y -> 
       forM_ [1..y] (\x -> if x == y 
                              then putStrLn (pad $ f x y m) 
                              else putStr $ (pad $ f x y m) ++ " "))

Вывод:

*Main> f 3 4 6
21

*Main> f 5 7 9
44

*Main> f 4 11 12
44

*Main> f 53214 64321 99999
2777096745
(0.01 secs, 518532 bytes)

*Main> display 6
 1
 2 15
 3 16 14
 4 17 21 13
 5 18 19 20 12
 6  7  8  9 10 11