【蓝桥杯真题7 难度:中等】杨辉三角形 2022.12.1

无理想的闲鱼

【2021】省赛

背景:
杨辉三角

杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。
tip：

题目:
如果我们从上到下,从左到右把所有数字排成一列,可以得到以下数列:1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,……
给定一个正整数N，请你输出数列中第一次出现N是在第几个数？

输入描述：输入一个整数N
输出描述：输出一个整数代表答案
输入示例1：6
输出示例1：13
输入示例2：154
输出示例2：11937
输入示例3：456
输出示例3：104198

游客，如果您要查看本帖隐藏内容请回复

[/hide]

lxping

1. pos = 3
   
2. ts = [1,1]
   
3. 
   
4. N = int(input())
   
5. if N == 1:
   
6.     print("1")
   
7. else:
   
8.     while True:
   
9.         ts = [1] + [ts[i] + ts[i+1] for i in range(len(ts)-1)] + [1]
   
10.         if N in ts:
    
11.             print( pos + ts.index(N) + 1)
    
12.             break
    
13.         else:
    
14.             pos += len(ts)

复制代码

hellometa

学习

lxping

应该还可以用递归吧

zhangjinxuan

来一个C凑热闹

1. #include <stdio.h>
   
2. 
   
3. int n, tot = 1, a[1001][1001] = {};
   
4. int main() {
   
5.         a[1][1] = 1;
   
6.         scanf("%d", &n);
   
7.         if (n == 1) {
   
8.                 puts("1");
   
9.                 return 0;
   
10.         }
    
11.         for (int i = 2; i <= 1000; ++i) {
    
12.                 for (int j = 1; j <= i; ++j) {
    
13.                         a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
    
14.                         ++tot;
    
15.                         if (a[i][j] == n) {
    
16.                                 printf("%d", tot);
    
17.                                 return 0;
    
18.                         }
    
19.                 }
    
20.         }
    
21. }

复制代码

zhangjinxuan

lxping 发表于 2022-12-1 13:22
应该还可以用递归吧

完全可以，组合数就是可以用递归来求啊，不过递推不香吗

zhangjinxuan

怎么又在审核啊

lxping

zhangjinxuan 发表于 2022-12-1 14:20
来一个C凑热闹

Cccf$

1. import math
   
2. def FirstAppear(n):
   
3.     ans = [((i * (i + 1) // 2) + j + 1) for i in range(n + 1) for j in range(n // 2 + 2) if math.comb(i,j) == n]
   
4.     return ans[0]
   
5. 
   
6. FirstAppear(6)
   
7. 13
   
8. FirstAppear(154)
   
9. 11937
   
10. FirstAppear(456)
    
11. 104198

复制代码

wangyanren

可怕 想领个币 都那么难

hellometa

学习

怂小白

这个我当年用C++做过作业

香蕉那个不拿拿

可怕 想领个币 都那么难

sdad1990

hangzhoucong

大神，我膜拜你

Ftxz1034

1. #杨辉三角
   
2. N = int(input('给定一个正整数N\n'))
   
3. def jiecheng(x):
   
4.     #阶乘函数
   
5.     a = 1
   
6.     if x == 1:
   
7.         return 1
   
8.     else:
   
9.         for i in range(1,x+1):
   
10.             a *= i
    
11.         return a
    
12. def fun1(x):
    
13.     #生成杨辉三角的每一行
    
14.     s = []
    
15.     if x == 0:
    
16.         s.append(1)
    
17.     else:
    
18.         for i in range(x + 1):
    
19.             a = jiecheng(x)//(jiecheng(i) * jiecheng(x - i))
    
20.             s.append(a)
    
21.     return s
    
22. def fun2(x):
    
23.     #将每一行从上到下，从左到右组合成一个列表
    
24.     s = [1]
    
25.     for i in range(1,x+1):
    
26.         a = fun1(i)
    
27.         s.extend(a)
    
28.     return s
    
29. def fun(x):
    
30.     #寻找整数N的位置
    
31.     i = 1
    
32.     s = fun2(x)
    
33.     while x not in s:
    
34.         s = fun2(x + i)
    
35.         i += 1
    
36.     else:
    
37.         a = 0
    
38.         for i in s:
    
39.             a += 1
    
40.             if i == x:
    
41.                 return a
    
42. print(fun(N))

复制代码

zhangziyi

sleep-boy

仰慕下大神            

鱼ccccvvv

太难了吧｜д)!!

jjkkll1223

全網了