2024蓝桥杯每日一题（递归）

备战2024年蓝桥杯 -- 每日一题

Python大学A组

        试题一：有序分数

        试题二：正则问题

        试题三：带分数

        试题四：约数之和

        试题五：分形之城

---

试题一：有序分数

【题目描述】

 【输入格式】

        共一行，包含一个整数 N。

【输出格式】

        按照从小到大的顺序，输出所有满足条件的分数。

        每个分数占一行，格式为 a/b，其中 a为分子， b 为分母。

【数据范围】

        1≤N≤160

【输入样例】

5

【输出样例】

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

 【解题思路】

        可以采取最简单直接的方法，直接枚举出所有分数，需要用到gcd(a,b)进行约分。然后去重接着排序即可。

【Python程序代码】

from math import *
n = int(input())
tep = set()
for i in range(1,n+1):
    for j in range(1,i+1):
        k = gcd(i,j)
        ii,jj = i//k,j//k
        tep.add( (jj/ii,jj,ii) )
tep = list(tep)
tep.sort()
print('0/1')
for i in range(len(tep)):
    print( '%d/%d'%(tep[i][1],tep[i][2]) )

---

试题二：正则问题

【题目描述】

        考虑一种简单的正则表达式：只由 x ( ) | 组成的正则表达式。小明想求出这个正则表达式能接受的最长字符串的长度。例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。

【输入格式】

        一个由x()|组成的正则表达式。

【输出格式】

        输出所给正则表达式能接受的最长字符串的长度。

【数据范围】

        输入长度不超过100，保证合法。

【输入样例】

((xx|xxx)x|(x|xx))xx 

【输出样例】

6

【解题思路】

        采用递归回溯的方法，首先建立两条规则：

        规则1：() 的意思是有括号的先算括号里面的，优先级最高，把括号计算的结果在和括号外的字符拼接，即括号是相对独立，完整的个体

        规则2：|的意思是|这个符号两侧的字符串只能选其中一个，由于这题要求能拼接的字符串最长，因此应该选择字符|字符串xxx...长度较大的一侧

        比如样例中的字符串((xx|xxx)x|(x|xx))xx对应的递归搜索树如下：

【Python程序代码】

s = input()
k = 0
def dfs():
    global k
    res = 0
    while k

本网站所收集的部分公开资料来源于AI生成和互联网，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。