Output an example of Yang hui triangle in Python
- 2020-04-02 13:47:04
- OfStack
What is the Yang hui triangle? Turn right to wikipedia: Yang hui triangle
Take a look at a slightly more intuitive picture:
1
11
121
1331
14641
15 10 10 51
16 15 20 15 61
17 21 35 35 21 71
18 28 56 70 56 28 81
Yang hui triangle has the following characteristics:
The value of each term is equal to the sum of the number in the upper left corner and the number in the upper right corner.
There are always one more entries in the NTH layer than in the n-1 layer
To calculate the Yang hui triangle in the NTH layer, you must know the number of the n-1 layer, and then add the Numbers of the adjacent two terms, you can get all the Numbers except the two ones in the next layer. It sounds a little bit like a recursive idea, but let's just assume that we already know the number of N minus 1, so let's calculate the number of N.
def _yanghui_trangle(n, result):
if n == 1:
return [1]
else:
return [sum(i) for i in zip([0] + result, result + [0])]
In the above code, result represents the number of Yang hui triangle in n-1 layer. In practice, we added a 0 to each end of listing 2, and then calculated the sum of the adjacent items, and we got the result directly.
Tweak the code a bit:
def yanghui_trangle(n):
def _yanghui_trangle(n, result):
if n == 1:
return [1]
else:
return [sum(i) for i in zip([0] + result, result + [0])]
pre_result = []
for i in xrange(n):
pre_result = _yanghui_trangle(i + 1, pre_result)
yield pre_result
if __name__ == "__main__":
for line in yanghui_trangle1(5):
print line
_yanghui_trangle can be shortened to lambda, but the readability feels worse, so leave it as it is.
Tips: the above program does not consider data formatting, which means the output is not a perfect triangle.
Since I have been learning Erlang recently, a new version of Erlang has not been tested in terms of performance, but I am still amazed by the expressive power of functional languages:
-module(yanghui).
-author(lfyzjck).
-export([triangle/1]).
triangle_next(P) ->
lists:zipwith(fun(X, Y) -> X+Y end, [0|P], P ++ [0]).
triangle(1) ->
[[1]];
triangle(N) ->
L = triangle(N - 1),
[H|_] = L,
[triangle_next(H)|L].