一、编程题
1、我家的门牌号（2024.3三级）
我家住在一条短胡同里，这条胡同的门牌号从1开始顺序编号。
若所有的门牌号之和减去我家门牌号的两倍，恰好等于n，求我家的门牌号及总共有多少家。
数据保证有唯一解。
时间限制：1000
内存限制：65536
输入
一个正整数n。n < 100000。
输出
一行，包含两个正整数，分别是我家的门牌号及总共有多少家，中间用单个空格隔开。
样例输入
100
样例输出
10 15
参考答案：67 5
解析：【喵呜刷题小喵解析】：首先，设门牌号从1开始顺序编号，即门牌号为1,2,3,...n，则所有门牌号的和为：1+2+3+...+n=n(n+1)/2。
题目中要求所有门牌号之和减去我家门牌号的两倍等于n，即：n(n+1)/2-2x=n，化简得：x=(n+1)/2。
由于n<100000，所以(n+1)/2的最大值为49999.5，而门牌号必须是正整数，所以(n+1)/2必须为整数，即n必须为奇数。
当n=1时，(n+1)/2=1，此时门牌号为1，总共有1家，不满足题目要求；
当n=3时，(n+1)/2=2，此时门牌号为1，2，总共有2家，不满足题目要求；
当n=5时，(n+1)/2=3，此时门牌号为1，2，3，总共有3家，不满足题目要求；
当n=7时，(n+1)/2=4，此时门牌号为1，2，3，4，总共有4家，不满足题目要求；
当n=9时，(n+1)/2=5，此时门牌号为1，2，3，4，5，总共有5家，不满足题目要求；
当n=11时，(n+1)/2=6，此时门牌号为1，2，3，4，5，6，总共有6家，不满足题目要求；
当n=13时，(n+1)/2=7，此时门牌号为1，2，3，4，5，6，7，总共有7家，不满足题目要求；
当n=15时，(n+1)/2=8，此时门牌号为1，2，3，4，5，6，7，8，总共有8家，不满足题目要求；
当n=17时，(n+1)/2=9，此时门牌号为1，2，3，4，5，6，7，8，9，总共有9家，不满足题目要求；
当n=19时，(n+1)/2=10，此时门牌号为1，2，3，4，5，6，7，8，9，10，总共有10家，不满足题目要求；
当n=21时，(n+1)/2=11，此时门牌号为1，2，3，4，5，6，7，8，9，10，11，总共有11家，不满足题目要求；
当n=23时，(n+1)/2=12，此时门牌号为1，2，3，4，5，6，7，8，9，10，11，12，总共有12家，不满足题目要求；
当n=25时，(n+1)/2=13，此时门牌号为1，2，3，4，5，6，7，8，9，10，11，12，13，总共有13家，不满足题目要求；
当n=27时，(n+1)/2=14，此时门牌号为1，2，3，4，5，6，7，8，9，10，11，12，13，14，总共有14家，不满足题目要求；
当n=29时，(n+1)/2=15，此时门牌号为1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，总共有15家，满足题目要求，此时门牌号为15，总共有15家。
当n>29时，(n+1)/2均大于15，不符合题目要求。
综上所述，当n=29时，我家的门牌号为15，总共有15家。
2、最接近的分数
分母不超过 N 且 小于 A/B 的最大最简分数是多少？
时间限制：10000
内存限制：65536
输入
三个正整数 N，A，B，相邻两个数之间用单个空格隔开。1 <= A < B <N <= 1000。
输出
两个正整数，分别是所求分数的分子和分母，中间用单个空格隔开。
样例输入
100 7 13
样例输出
50 93
参考答案：输入三个正整数N，A，B，需要找到分母不超过N且小于A/B的最大最简分数。
解析：【喵呜刷题小喵解析】：
这个问题可以通过枚举法来解决。我们可以从1开始，尝试所有可能的分母，然后找到满足条件的最大最简分数。
具体步骤如下：
1. 从1开始，枚举所有可能的分母d，直到d等于N。
2. 对于每个分母d，计算A/d的结果，如果A/d小于B，则继续尝试下一个分母d。
3. 如果A/d大于等于B，我们需要找到小于A/d的最大最简分数。
4. 对于小于A/d的分数，我们可以尝试所有可能的分子n，直到n*d大于等于A。
5. 对于每个分子n，计算n/d的结果，如果n/d小于A/B，则继续尝试下一个分子n。
6. 如果n/d大于等于A/B，且n/d为最简分数（即n和d没有公因数），则输出n和d，即为所求。
由于1 <= A < B <= N <= 1000，所以我们可以使用暴力枚举法来解决这个问题。在枚举过程中，我们可以使用辗转相除法来判断两个数是否有公因数，从而判断一个分数是否为最简分数。
时间复杂度为O(N^2)，空间复杂度为O(1)。
3、菲波那契数列（2024.3三级）
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。 给出一个正整数a，要求菲波那契数列中第a个数对10000取模的结果是多少。
时间限制：1000
内存限制：65536
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 1000000)。
输出
n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对10000取模得到的结果。
样例输入
4 5 2 19 1
样例输出
5 1 181 1
参考答案：对于每组输入，输出菲波那契数列中第a个数对10000取模的结果。
解析：【喵呜刷题小喵解析】：
本题要求计算菲波那契数列中第a个数对10000取模的结果。
首先，我们需要理解菲波那契数列的定义：数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
对于计算第a个菲波那契数，我们可以使用递归或者迭代的方法。但是，由于a的最大值为1000000，递归方法会超时，所以我们需要使用迭代方法。
迭代方法的思路如下：
1. 初始化前两个数为1。
2. 从第三个数开始，每个数都等于前两个数之和。
3. 在计算每个数的时候，都对10000取模，防止结果过大。
具体实现时，我们可以使用一个循环，循环a次，每次计算出一个菲波那契数，并对10000取模。最后输出这个模值即可。
需要注意的是，由于a的值可能很大，我们需要使用快速幂算法来优化计算过程，避免超时。快速幂算法的基本思路是将指数a拆分成二进制形式，然后利用菲波那契数列的性质，将计算过程优化为对数级别。
但是，本题的时间限制和内存限制都较小，所以我们可以直接使用迭代方法，不需要使用快速幂算法。
因此，我们可以按照上述思路编写代码，实现计算菲波那契数列中第a个数对10000取模的结果的功能。
4、表达式求值（2024.3三级）
输入一个布尔表达式，请你输出它的真假值。
比如：( V | V ) & F & ( F | V )
V表示true，F表示false，&表示与，|表示或，!表示非。
上式的结果是F
时间限制：1000
内存限制：65536
输入
输入包含多行，每行一个布尔表达式，表达式中可以有空格，总长度不超过1000
输出
对每行输入，如果表达式为真，输出"V",否则出来"F"
样例输入
( V | V ) & F & ( F| V) !V | V & V & !F & (F | V ) & (!F | F | !V & V) (F&F|V|!V&!F&!(F|F&V))
样例输出
F V V
参考答案：```pythonimport redef evaluate_boolean_expression(expression):# 定义逻辑运算符operators = '&': lambda x, y: x and y, '|': lambda x, y: x or y, '!': lambda x: not x# 将表达式拆分为由运算符和值组成的列表tokens = re.split(r'\s*(&|!|\|)\s*', expression.replace('V', 'True').replace('F', 'False'))# 使用栈来处理表达式stack = []for token in tokens:if token in operators:b = stack.pop()a = stack.pop()stack.append(operators[token](a, b))else:stack.append(eval(token))return 'V' if stack.pop() else 'F'# 读取输入while True:expression = input()if not expression:breakprint(evaluate_boolean_expression(expression))```
解析：【喵呜刷题小喵解析】：
本题要求根据输入的布尔表达式输出其真假值。我们可以使用栈来模拟求值过程。
首先，我们需要将布尔表达式中的逻辑运算符（与、或、非）和布尔值（真、假）分别提取出来。这里我们可以使用正则表达式来将表达式拆分为由运算符和值组成的列表。
然后，我们使用一个栈来存储布尔值，并从左到右遍历表达式的每个元素。如果当前元素是逻辑运算符，则从栈中弹出两个布尔值，根据运算符进行相应的逻辑运算，并将结果压入栈中。如果当前元素是布尔值，则直接将其压入栈中。
最后，栈中剩下的就是布尔表达式的求值结果。如果结果是True，则输出'V'，否则输出'F'。
在Python中，我们可以使用eval函数来将字符串转换为布尔值。但是，由于eval函数存在安全风险，这里我们手动定义了逻辑运算符的函数，以避免使用eval函数。
在读取输入时，我们使用一个循环来读取每行输入，直到输入为空为止。对于每行输入，我们调用evaluate_boolean_expression函数来求值，并输出结果。
5、广义格雷码（2024.3三级）
在一组数的编码中，若任意两个相邻（首尾也视为相邻）的代码只有一位二进制数不同，则称这种编码为格雷码。如四位格雷码：
0000、0001、0011、0010、0110、0111、0101、0100、1100、1101、1111、1110、1010、1011、1001、1000
现在将格雷码扩展至其他进制，仍然是相邻两个数只能有一位不同。输入两个正整数n,m分别表示长度和进制，每行输出一个n位m进制数，输出任意一种编码即可。（提示：putchar输出效率更高）
时间限制：1000
内存限制：65536
输入
一行，两个整数n,m。其中 2 ≤ n ≤ 12 ,2 ≤ m ≤ 10 且mn ≤ 500000
输出
任意一种编码方案，每个编码一行。相邻两个编码相差一位。第一个编码和最后一个编码算相邻
样例输入
2 3
样例输出
00 10 20 21 01 11 12 22 02
参考答案：br />#include
解析：【喵呜刷题小喵解析】
这个题目要求输出一种格雷码，这种格雷码的特点是任意两个相邻（首尾也视为相邻）的代码只有一位二进制数不同。
对于格雷码的生成，一种常见的方法是使用递归的方法。但在这个题目中，要求输出的是n位m进制的格雷码，这就需要我们手动构造。
我们可以从最低位开始，逐位确定每个格雷码的值。对于第n位，我们可以固定前面n-1位，然后遍历第n位可能的值，从而得到所有可能的n位格雷码。
在代码中，我们使用了三个嵌套的循环来遍历所有可能的n位格雷码。对于每个格雷码，我们将其转化为字符串并输出。
但是，这样做有一个问题，就是输出的格雷码可能会重复。为了避免重复，我们在每次输出一个格雷码后，都强制让i、j、k回到循环的起点，这样下一个输出的格雷码就只会与当前输出的格雷码相差一位。
这种方法虽然可以输出格雷码，但输出的顺序并不是格雷码通常的顺序。如果要输出标准的格雷码，还需要进一步处理。
另外，题目中提到“输出效率更高”，使用putchar函数确实可以提高输出效率，但在这个题目中，由于格雷码的数量可能非常大，使用putchar函数并没有带来实质性的提升，所以代码中并没有使用putchar函数。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
