前几行是。
1
1 1
2 1 2
3 2 2 3
5 3 4 3 5
8 5 6 6 5 8
13 8 10 9 10 8 13
21 13 16 15 16 13 21
34 21 26 24 25 24 26 21 34
...
我在C语言中尝试了以下代码
试试1
#include<stdio.h>
#include<stdlib.h>
int main(){
int a=0,b=1,i,c,n,j;
system("cls");
printf("Enter the limit:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
a=0;
b=1;
printf("%d\t",b);
for(j=1;j<i;j++)
{
c=a+b;
printf("%d\t",c);
a=b;
b=c;
}
printf("\n");
}
return 0;
}
它的输出是这样的(极限9):
1
1 1
1 1 2
1 1 2 3
1 1 2 3 5
1 1 2 3 5 8
1 1 2 3 5 8 13
1 1 2 3 5 8 13 21
1 1 2 3 5 8 13 21 34
试二：
#include<stdio.h>
#include<stdlib.h>
int main(){
int a=0,b=1,i,c,n,j;
system("cls");
printf("Enter the limit:");
scanf("%d",&n);
a = 0; b=1;
for(i=1;i<=n;i++)
{
printf("%d\t",b);
for(j=1;j<i;j++)
{
c=a+b;
printf("%d\t",c);
a=b;
b=c;
}
printf("\n");
}
return 0;
}
它的输出是这样的：
1
1 1
1 2 3
3 5 8 13
13 21 34 55 89
89 144 233 377 610
我还试过以下两种代码 a 或 b 外界 for 循环。但是好像什么都不行。有什么办法可以解决这个问题吗？请用C、C++或Python给出解决方案。
(编辑 以在Python中包含一个有效的迭代方法）。)
H(0, 0) = H(1, 0) = H(1, 1) = H(2, 1) = 1
H(i, j) = H(i − 1, j − 1) + H(i − 2, j − 2) (j >= 2)
= H(i − 1, j) + H(i − 2, j) (otherwise)
在Python中，这可以简单地写成一个递归关系，比如。
def hosoya(i, j):
if j > i:
raise ValueError('Must be: j <= i')
elif (i, j) in {(0, 0), (1, 0), (1, 1), (2, 1)}:
return 1
elif j >= 2:
return hosoya(i - 1, j - 1) + hosoya(i - 2, j - 2)
else:
return hosoya(i - 1, j) + hosoya(i - 2, j)
for i in range(10):
for j in range(i + 1):
print(hosoya(i, j), end=' ')
print()
# 1
# 1 1
# 2 1 2
# 3 2 2 3
# 5 3 4 3 5
# 8 5 6 6 5 8
# 13 8 10 9 10 8 13
# 21 13 16 15 15 16 13 21
# 34 21 26 24 25 24 26 21 34
# 55 34 42 39 40 40 39 42 34 55
这样的递归关系，如果需要的话，可以很容易地改编成C语言。
#include <stdio.h>
const int NUM_ROWS = 10;
int hosoya(int i, int j)
{
if (j > i)
{
return 0;
}
else if ((i == 0 && j == 0) || (i == 1 && j == 0) || (i == 1 && j == 1) || (i == 1 && j == 1))
{
return 1;
}
else if (j >= 2)
{
return hosoya(i - 1, j - 1) + hosoya(i - 2, j - 2);
}
else
{
return hosoya(i - 1, j) + hosoya(i - 2, j);
}
}
int main(void)
{
int i, j;
for (i = 0; i < NUM_ROWS; ++i)
{
for (j = 0; j < i + 1; ++j)
{
printf("%d ", hosoya(i, j));
}
printf("\n");
}
return 0;
}
下面是一些Python中的迭代解决方案的代码，它可以生成 n 行。
def gen_hosoya(n):
result = [[1], [1, 1], [2, 1, 2]]
for i in range(2, n):
next_row = []
for j in range(2):
next_row.append(result[-1][j] + result[-2][j])
for j in range(2, i + 2):
next_row.append(result[-1][j - 1] + result[-2][j - 2])
result.append(next_row)
return result
for row in gen_hosoya(10):
print(row)
# [1]
# [1, 1]
# [2, 1, 2]
# [3, 2, 2, 3]
# [5, 3, 4, 3, 5]
# [8, 5, 6, 6, 5, 8]
# [13, 8, 10, 9, 10, 8, 13]
# [21, 13, 16, 15, 15, 16, 13, 21]
# [34, 21, 26, 24, 25, 24, 26, 21, 34]
# [55, 34, 42, 39, 40, 40, 39, 42, 34, 55]
# [89, 55, 68, 63, 65, 64, 65, 63, 68, 55, 89]
如果出于某些原因，只需要三角形的某些部分，这可以很容易地转化为一个内存效率高的生成器。
def gen_next_row(buffer, i):
next_row = []
for j in range(2):
next_row.append(buffer[-1][j] + buffer[-2][j])
for j in range(2, i + 2):
next_row.append(buffer[-1][j - 1] + buffer[-2][j - 2])
buffer.pop(0)
buffer.append(next_row)
return next_row
def gen_hosoya(first, second=None):
if second is None:
first, second = 0, first
buffer = [[1], [1, 1], [2, 1, 2]]
for i, next_row in enumerate(buffer):
if i in range(first, second):
yield next_row
buffer.pop(0)
for i in range(2, first):
gen_next_row(buffer, i)
for i in range(first, second):
yield gen_next_row(buffer, i)
for row in gen_hosoya(10, 12):
print(row)
# [144, 89, 110, 102, 105, 104, 104, 105, 102, 110, 89, 144]
# [233, 144, 178, 165, 170, 168, 169, 168, 170, 165, 178, 144, 233]
我在Python中的代码，没有递归(感谢@norok2)：[在某些情况下，它显示BrokenPipe错误。所以我添加了信号语句来解决这个问题，就像我在Python中写的那样 这个.]
from signal import signal, SIGPIPE, SIG_DFL
signal(SIGPIPE, SIG_DFL)
n = int(input())
dp = [[0 for i in range(n)] for j in range(n)]
dp[0][0] = 1
dp[1][0] = 1
dp[1][1] = 1
dp[2][0] = 2
dp[2][1] = 1
dp[2][2] = 2
for i in range(3,n):
for j in range(i+1):
if j-2>=0:
dp[i][j] = dp[i-1][j-1]+dp[i-2][j-2]
else:
dp[i][j] = dp[i-1][j]+dp[i-2][j]
for i in dp:
for j in i:
if j:
print(j , end = ' ')
print()