递归

2020-12-30  本文已影响0人  奋斗的喵儿

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))
上一篇 下一篇

猜你喜欢

热点阅读