1、进制转换（10分）
题目内容：
给定一个M进制的数，请将其转换为N进制并输出
输入格式:
两行，第一行为空格分隔的两个数字，分别为10进制表示的M与N；其中M, N均满足2 ≤ M、N ≤ 36
第二行为待转换的数字，其中每位超过9的部分从10至36分别用大写字母A-Z表示；输入数据保证其中最大位数对应数字不超过M
输出格式：
一行字符串，表示转换后的N进制数
输入样例：
8 16
473
输出样例：
13B
时间限制：500ms内存限制：32000kb
解题思路：
先将M进制转换为十进制，再转为N进制
参考代码如下，但用例1未通过
def toStr(numdec,N):
# 十进制转换为其他进制
convString = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
if numdec < N:
return convString[numdec]
else:
return toStr(numdec//N, N) + convString[numdec%N]
M, N = list(map(int,input().split()))
num = input()
# 先转十进制
numdec = int(num,M)
print(toStr(numdec, N))
2、四柱汉诺塔（10分）
题目内容：
如课上所说，汉诺塔问题源于印度一个古老传说。对于原始的汉诺塔游戏，可供玩家操作的空间一共只有三根柱子，导致按原传说的要求，需要超过1.8*10^19步才能解开。
透过新增柱子可以大幅度地减少需要的步数。此处要求在给出指定的盘数，柱子数量为4（即限制为4根柱子）且不改变原有传说的其他规则的限制下，找出完成迁移的最小步骤数。
输入格式:
一个非负整数M，M代表盘数，M<=1000。
输出格式：
一个非负整数，表示完成迁移的最小步骤数。
输入样例：
3
输出样例：
5
时间限制：500ms内存限制：32000kb
解题思路：
首先三柱汉诺塔问题的最优解次数g(n) = 2^n -1，设四柱汉诺塔问题 的最优解次数为f(n)。
将四柱汉诺塔问题分为三步来解，假设有a,b,c,d四个柱子，a柱子上有n个盘子：
1.将a柱上的 x个盘子(1<= x < n)，移动到c柱上，该过程可以使用柱子b和d，所以是一个四柱汉诺塔问题，最优次数为f(x)。
2.再将a柱上剩下的n-x个盘子移动到d柱，因为剩下的盘子都比c柱上现有的盘子大，所以只能通过b柱来移动，这是一个三柱汉诺塔问题，最优次数为 2^(n-x) - 1。
3.最后将c柱上的x个盘子移动到d柱，可以通过a，b柱来移动，所以是一个四柱汉诺塔问题，和第一步相同最优次数为f(x)。
所以四柱汉诺塔问题需要的总次数f(n) = f(x) + 2^(n-x) - 1 + f(x) =2* f(x) + 2^(n-x) -1,最优次数与x的取值有关，已知 f(1) = 1；f(2) = 3, 可以用循环遍历来找f(n)的最小值。
def hnt_4(num):
if num == 0:
return 0
f_list = [1,3]
for i in range(2,num):
ans_list = []
for j in range(i):
ans_list.append(2*f_list[j]+2**(i-j)-1)
f_list.append(min(ans_list))
return f_list[num-1]
print(hnt_4(int(input())))
3、ASCII谢尔宾斯基地毯（10分）
题目内容：
image.png
谢尔宾斯基地毯是形如上图的正方形分形图案，每个地毯可分为等大小的9份，其中中央挖空，其余均由更小的地毯组成。
现给定地毯大小（行数）与组成地毯的字符元素，请打印相应的地毯图形。
注：空腔以半角空格表示；当给定字符元素长度不为1时空格数须与字符长度对应
输入格式:
输入为两行，分别为地毯大小正整数N与组成元素字符串c
输入数据保证N为3的正整数幂
输出格式：
由N行长度为N*len(c)的字符串构成的谢尔宾斯基地毯
输入样例：
9
[]
输出样例：
[][][][][][][][][]
[] [][] [][] []
[][][][][][][][][]
[][][] [][][]
[] [] [] []
[][][] [][][]
[][][][][][][][][]
[] [][] [][] []
[][][][][][][][][]
参考程序模板：
def carpet(N,char):
# code here
pass
n=int(input())
c=input()
carpet(n,c)
时间限制：500ms内存限制：32000kb
解题思路：将绘图点对应横纵坐标xy，例如n=3,如图
[][][]
[] []
[][][]
0<=x,y<3 其中x,y=1,1时为false
利用循环
for x in range(N):
for y in range(N):
代码 但是OJ用例没通过。暂时没有找到原因
def carpet(N, char):
#
def judge(n, x, y):
if n == 1:
return True
n1 = n // 3
if n1 <= x < n1 * 2 and n1 <= y < n1 * 2:
return False
return judge(n1, x % n1, y % n1)
d = ''
for x in range(N):
for y in range(N):
if judge(N, x, y):
d += char
else:
d += (len(char) * ' ')
d = d + '\n'
return d
n = int(input())
c = input()
print(carpet(n, c))
网友评论