PTA:Python解答1005 继续(3n+1)猜想

1005 继续(3n+1)猜想 (25分)

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里,情况稍微有些复杂。
当我们验证卡拉兹猜想的时候,为了避免重复计算,可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候,我们需要计算 3、5、8、4、2、1,则当我们对 n=5、8、4、2 进行验证的时候,就可以直接判定卡拉兹猜想的真伪,而不需要重复计算,因为这 4 个数已经在验证3的时候遇到过了,我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”,如果 n 不能被数列中的其他数字所覆盖。
现在给定一系列待验证的数字,我们只需要验证其中的几个关键数,就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字,并按从大到小的顺序输出它们。

输入格式:

每个测试输入包含 1 个测试用例,第 1 行给出一个正整数 K (<100),第 2 行给出 K 个互不相同的待验证的正整数 n (1<n<=100)的值,数字间用空格隔开。

输出格式:

每个测试用例的输出占一行,按从大到小的顺序输出关键数字。数字间用 1 个空格隔开,但一行中最后一个数字后没有空格。

输入样例:

6
3 5 6 7 8 11

输出样例:

7 6

解题思路:

对于(3n+1)猜想的继续,我们先自定义一个(3n+1)猜想的函数,这样方便在写代码的时候不会因为嵌套太多层以至于出问题,同时,函数把输入的每个测试用例的递推的数存入列表,再把列表对应测试用例放入字典。接着,我们把每个测试用例形成的字典合并到一个字典a里,找到测试用例里和字典a的值重复的数并存入一个列表b里,列表b里的数就是被“覆盖的数”,最后从测试用例里去除这个列表的数,就能得到所有的“关键数”。需要注意的是,输出格式的最后一个数后面并没有空格。

完整代码:

a = eval(input())
b = list(map(int,input().split()))
def number(n):
    d = {}
    flag = 1
    ls = []
    while flag:
        if n!= 1:
            if n%2 == 0:
                n = n//2
                ls.append(n)
            else:
                n = (3*n + 1)//2
                ls.append(n)
        else:
            del ls[-1]
            flag = 0
    d[i] = ls
    return d

c = {}
for i in b:
    c.update(number(i))
e = []
for j in c:
    for k in b:
        if k in c[j]:
            e.append(k)
for i in e:
    if i in b:
        b.remove(i)
b.sort(reverse=True)
for i in b[:-1]:
    print(i,end=' ')
print(b[-1])
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注