卡拉兹(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

编程语言：Python

解题思想：

1.判断数列中的数字是否属于可覆盖数字集合，如果属于则跳到下一个数字

2.如果不属于，则对该数进行卡拉兹变换，并将变换过程中的数字存入可覆盖数字集合

3.数列中所有数字都变换完成后，再逐个判断是否属于可覆盖数字集合

4.若不属于则添加到关键数字列表中

时间复杂度：O(nlogn)

代码如下：

NON = int(input())
Coverable = set()  # 可覆盖数字的集合
KeyNumber = list()  # 关键数字的列表
Number = list(map(int, input().split()))
for i in range(NON):
    Temp = Number[i]  # 将需要进行卡拉兹判断的数使用一个临时变量代替
    if Temp in Coverable:  # 该数属于可覆盖数字：优化1
        continue
    else:  # 该数不属于可覆盖数字
        while Temp != 1:
            if Temp % 2 == 0:
                Temp //= 2
            else:
                Temp = (3 * Temp + 1) // 2
            if Temp in Coverable:  # 在变换过程中，出现可覆盖数字则不再变换：优化2
                break
            Coverable.add(Temp)  # 将卡拉兹变换后的数字添加到可覆盖数字集合中
for i in range(NON):
    if Number[i] not in Coverable:  # 该数字不属于可覆盖数字
        KeyNumber.append(Number[i])  # 将该数字添加到关键数字中
KeyNumber.sort(reverse=True)  # 从大到小排序
for i in range(len(KeyNumber) - 1):
    print(KeyNumber[i], end=" ")
print(KeyNumber[len(KeyNumber) - 1])

< >

评论板

共有 7 条评论

fruinly

After 14 years of follow up, we have not observed a single failure in our patients whose tumors express nuclear 4ICD and received tamoxifen as their sole therapeutic intervention cialis vs viagra

2023-03-21 22:05 回复
FoorryNox

Wegman P, Vainikka L, StГҐl O, NordenskjГ¶ld B, Skoog L, Rutqvist L E, Wingren S Genotype of metabolic enzymes and the benefit of tamoxifen in postmenopausal breast cancer patients buy cialis generic online

2023-05-13 19:55 回复
cheap jordans online

Read reviews and was a little hesitant since I had already inputted my order. actually but thank god, I had no issues. themselves received item in a timely matter, they are in new condition. in any event so happy I made the purchase. Will be definitely be purchasing again.
cheap jordans online https://www.cheaprealjordan.com/

2023-05-15 20:34 回复
jordans for cheap

Read reviews and was a little hesitant since I had already inputted my order. or perhaps but thank god, I had no issues. significantly received item in a timely matter, they are in new condition. in either case so happy I made the purchase. Will be definitely be purchasing again.
jordans for cheap https://www.cheapjordanssneakers.com/

2023-05-16 06:36 回复
cheap jordans

Read reviews and was a little hesitant since I had already inputted my order. and even but thank god, I had no issues. including the received item in a timely matter, they are in new condition. anyway so happy I made the purchase. Will be definitely be purchasing again.
cheap jordans https://www.realjordansretro.com/

2023-05-16 18:01 回复
louis vuitton outlet online

Read reviews and was a little hesitant since I had already inputted my order. alternatively but thank god, I had no issues. prefer received item in a timely matter, they are in new condition. no matter what so happy I made the purchase. Will be definitely be purchasing again.
louis vuitton outlet online https://www.louisvuittonsoutletonline.com/

2023-05-17 15:03 回复
Preliaf

Changes in the chemical shifts of protein residues were monitored by 15 N HSQC spectra levitra generique allemagne Involvement of estradiol 17beta and its membrane receptor, G protein coupled receptor 30 GPR30 in regulation of oocyte maturation in zebrafish, Danio rario

2023-06-19 23:13 回复

PAT乙级:1005 继续(3n+1)猜想