资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。

输入格式

　　一行两个正整数n和m

输出格式

　　一个实数P表示答案，保留4位小数。

样例输入

2 3

样例输出

0.7500

数据规模和约定

　　1≤n，m≤20

n,m=map(int,input().split())
dp=[[0 for i in range(n+1)]for i in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if(j>i):
            dp[i][j]=0
        elif(j==1):
            dp[i][j]=pow(1/n,i-1)
        else:
            dp[i][j]=(dp[i-1][j])*(j*1.0/n) + (dp[i-1][j-1])*((n-j+1)*1.0/n)

print("{:.4f}".format(dp[m][n]))
    

参考了这些文章

蓝桥Python算法——印章_些凉的博客-CSDN博客https://blog.csdn.net/qq_46038474/article/details/121633599?spm=1001.2101.3001.6650.10&utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~Rate-10.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~Rate-10.pc_relevant_default&utm_relevant_index=19蓝桥杯试题 算法训练 印章_python_个人练习_图南_的博客-CSDN博客https://blog.csdn.net/weixin_43539781/article/details/121353101?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164309464716780271517282%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164309464716780271517282&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-2-121353101.pc_search_insert_es_download&utm_term=%E5%8D%B0%E7%AB%A0Python&spm=1018.2226.3001.4187蓝桥杯-印章_Kkooe的博客-CSDN博客https://blog.csdn.net/Kkooe/article/details/121326116?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164302949516780269880509%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164302949516780269880509&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-3-121326116.pc_search_insert_es_download&utm_term=%E5%8D%B0%E7%AB%A0&spm=1018.2226.3001.4187蓝桥杯试题 算法训练 印章 (dp&详解)_m0_58245389的博客-CSDN博客https://blog.csdn.net/m0_58245389/article/details/121877031?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-2.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-2.pc_relevant_default&utm_relevant_index=51001印章_Small_Mie的博客-CSDN博客https://blog.csdn.net/Small_Mie/article/details/121803550?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-1.pc_relevant_aa&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-1.pc_relevant_aa&utm_relevant_index=2

#错的错的
n,m=map(int,input().split())
if(n>m):
    p=0
elif(n==m):
    p=1
    for i in range(n):
        p=1/n*p*(i+1)
else:
    cs=n
    p=1
    for i in range(n):
        p=1/n*p*(i+1)
    pz=p
    while(cs<m):
        k=p*pow((1/n),cs-n+1)*(n-1)
        pz=pz+k
        cs+=1
    p=pz

print("{:.4f}".format(p))

Python“蓝桥杯”练习试题–阶乘计算

#问题描述

输入一个正整数n，输出n!的值。
其中n!=123*…*n。

#算法描述

n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。

#输入格式

输入包含一个正整数n，n<=1000。

#输出格式

输出n!的准确值。

#样例输入

10

#样例输出

3628800

#代码部分：该代码来源：
https://blog.csdn.net/weixin_51472001/article/details/115789227（感谢博主的分享）

n = int(input())
li = [1]
date = 1  # 位数

for i in range(1, n + 1):  # n个数阶乘
    for j in range(date):  # 每位都乘i
        li[j] *= i
    for j in range(date - 1):  # (除最高位的)进位
        if (li[j] >10):
            li[j + 1] = li[j] // 10 + li[j + 1]
            li[j] = li[j] % 10
    if (li[date - 1] >10):  # 最高位进位
        li.append(0)
        li[date] = li[date - 1] // 10 + li[date]
        li[date - 1] = li[date - 1] % 10
        date += 1

# 逆向打印
a = date - 1
for i in range(date):
    print(li[a], end='')
    a -= 1

#测试结果
当我把该代码上传至蓝桥测试后只有90%的正确率，查看评测详情后发现当输入值为130时，输出结果出错，把不一致的地方贴上，如下：

红框中第一列是系统给出的正确输出，而我们的代码给出的却是第二列。仔细查看代码后发现当每一位与i相乘后为10并未进位，因此代码修改为

n = int(input())
li = [1]
date = 1  # 位数

for i in range(1, n + 1):  # n个数阶乘
    for j in range(date):  # 每位都乘i
        li[j] *= i
    for j in range(date - 1):  # (除最高位的)进位
        if (li[j] >=10):
            li[j + 1] = li[j] // 10 + li[j + 1]
            li[j] = li[j] % 10
    if (li[date - 1] >=10):  # 最高位进位
        li.append(0)
        li[date] = li[date - 1] // 10 + li[date]
        li[date - 1] = li[date - 1] % 10
        date += 1

# 逆向打印
a = date - 1
for i in range(date):
    print(li[a], end='')
    a -= 1

再次放到蓝桥中测试，结果正确。

试题 算法训练 数字游戏

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
　　例如:
　　3 1 2 4
　　4 3 6
　　7 9
　　16
　　现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。

输入格式

　　第1行为两个正整数n，sum

输出格式

　　一个1～N的一个排列

样例输入

4 16

样例输出

3 1 2 4

数据规模和约定

　　0<n<=10

 时间复杂度高，超时

通过70%

n,su=map(int,input().split())
a=[]#a = ["" for x in range(1,n+1)]
for i in range(1,n+1):
    a.append(i)
    
flag=[]
memory=[]
go=True
def dfs(n,su,x):#列出全排列
    global go
    if(n==0):
        if(game(x,flag,su)==True):
            go=False
        return
    for k in a:
        if(go==False):
            break
        if k not in memory:
            flag.append(k)
            memory.append(k)
            dfs(n-1,su,x)
            memory.pop()
            flag.pop()
def game(n,flag,su):#判断是否满足题意
    co=flag.copy()
    while n :
        for i in range(n-1):
            co[i]=co[i]+co[i+1]
        n-=1
    if (co[0]==su):
        flag=list(map(str,flag))#flag = [str(i) for i in flag]
        print(" ".join(flag))
        return True
dfs(n,su,n)