考虑以下问题：
您收到一些整数m并设置n=1+2+...+m，
现在您需要将所有数字从 to 打印1为n从外部到内部的三角形。
例子：
输入：
m=6
n=1+2+3+4+5+6 = 21
输出：
1
2 15
3 16 14
4 17 21 13
5 18 19 20 12
6 7 8 9 10 11
如果您可以使用任何支持的数据结构，最快的方法是什么？如果你不能使用超过O(1)内存的最快方法是什么？
问问题
586 次
4 回答
7
@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) 用于时间复杂度，您可以通过嵌套循环（不是 JS）打印所有数字（没有填充）：
for(i=0;i<m;i++){ for(j=0;j<=i;j++) print cal(j,i,m); print '\n'}
（ps。我不明白 hashkell，但我猜你的想法是这样的，如果我错过了任何案例，请指出）
于 2013-10-10T10:45:34.627 回答
6
如果您假设尾调用优化可以防止调用堆栈不必要地增长，那么这是一种使用恒定内存量的方法。（代码在 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
于 2013-10-09T12:35:05.727 回答
1
O(1)用于内存。它打印相互插入的三角形的 3 个部分。每个三角形由 3 行数字组成 - 左侧垂直，底部水平，右侧对角线放置数字。对于任何内部三角形，我们都知道由外部三角形计算的起始左上角数。打印过程由 3 个循环组成，打印与当前行对应的三角形部分：
- 打印左垂直部分
- 打印底部
- 打印对角线数字
它遍历所有行 (i) 并保持 t 中的三角形数量。java中的代码，只需将main中的m更改为您想要的任何内容：
公共类三角打印{
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();
}
于 2013-10-10T09:03:32.657 回答
0
来吧，根据 xy 和 m 直接计算值。O(1) 时间，O(1) 空间。我相信这种方法可能是最快的。
更新： Pass By 写了一个漂亮、简洁的概括，似乎受此启发 - 请参阅那个答案。
哈斯克尔代码：
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
于 2013-10-10T01:54:42.120 回答