[已解决]序列拼接，递归的时候有问题

15588686105

例如，AAATAAA和CCCGAAA，k=3，分别首尾3个字符一样，则拼接之后为CCCGAAATAAA
想实现递归功能，当拼接一次后发现拼接后的结果仍可再次拼接则再拼一次

1. # 读文件的函数
   
2. def readfasta(lines):
   
3.     illustrate = []
   
4.     seq = []
   
5.     string = ""
   
6.     num = 0
   
7.     for i in lines:
   
8.         # 判断是否为说明行
   
9.         if '>' in i or ';' in i:
   
10.             newi = i.replace('>','').replace(';','').replace('\n','')
    
11.             illustrate.append(newi)
    
12.             if num != 0:
    
13.                 seq.append(string)
    
14.                 string = ""
    
15.         else:
    
16.             news = i.replace('\n','')
    
17.             string += news
    
18.         num += 1
    
19.         if num == len(lines):
    
20.             seq.append(string)
    
21.     return illustrate,seq
    
22. 
    
23. f = open('12fasta.txt', 'r')
    
24. 
    
25. lines = f.readlines()
    
26. 
    
27. f.close()
    
28. 
    
29. (i, s) = readfasta(lines)
    
30. print(i,s)
    
31. 
    
32. k = int(input("输入K值："))
    
33. 
    
34. dic = {}
    
35. # 拼接函数
    
36. def getoriginal(seq,illu,k):
    
37.     x = 0
    
38.     for n,m in enumerate(seq):
    
39.         temp = m[-k:]
    
40.         for i,j in enumerate(seq):
    
41.             if i != n:
    
42.                 if temp == j[:k]:
    
43.                     name = illu[n] + " " + illu[i]
    
44.                     newstr = m[:-k] + j
    
45.                     dic.update({name:newstr})
    
46.                     x += 1
    
47.     seq = list(dic.values())
    
48.     illu = list(dic.keys())
    
49.     print(seq,illu)
    
50.     if len(illu) == 1 or x == 0:
    
51.         return dic
    
52.     else:
    
53.         return getoriginal(seq,illu,k)
    
54. 
    
55. 
    
56. res = getoriginal(s,i,k)
    
57. print("\n",res)
    

复制代码

测试用例如下：
>Rosalind_0498

AAATAAA

>Rosalind_2391

AAATTTT

>Rosalind_2323

TTTTCCC

>Rosalind_0442

AAATCCC

>Rosalind_5013

GGGTGGG

>Rosalind_123

AAAGAAA

最佳答案

月排行榜 / 总排行榜

陶远航

2023-9-2 21:37:40

15588686105 发表于 2023-9-2 21:34
好的谢谢，这样还是死循环，原因是测试用例本身会造成死循环，拼接之后还是会一直循环是的把

你的问题是关于序列拼接的递归函数，你想知道为什么测试用例会造成死循环。

根据你提供的测试用例，我发现其中有两个序列是相同的，即AAATAAA和AAAGAAA。这意味着无论你如何拼接它们，都会得到相同的结果，即AAATAAA或AAAGAAA。因此，递归函数会一直尝试拼接这两个序列，但永远无法达到退出条件，从而导致死循环。

为了避免这种情况，你可以在递归函数中添加一个判断条件，检查是否有重复的序列出现在seq中。如果有，就跳过拼接操作，直接返回dic。修改后的代码如下所示：

1. # 拼接函数
   
2. def getoriginal(seq, illu, k):
   
3.     x = 0
   
4.     dic = {}
   
5.   
   
6.     # 检查是否有重复的序列
   
7.     if len(seq) != len(set(seq)):
   
8.         return dic
   
9.   
   
10.     for n, m in enumerate(seq):
    
11.         temp = m[-k:]
    
12.         for i, j in enumerate(seq):
    
13.             if i != n:
    
14.                 if temp == j[:k]:
    
15.                     name = illu[n] + " " + illu[ i]
    
16.                     newstr = m[:-k] + j
    
17.                     dic.update({name: newstr})
    
18.                     x += 1
    
19.   
    
20.     seq = list(dic.values())
    
21.     illu = list(dic.keys())
    
22.     print(seq, illu)
    
23.   
    
24.     if len(illu) == 1 or x == 0:
    
25.         return dic
    
26.     else:
    
27.         return getoriginal(seq, illu, k)
    
28. 
    
29. res = getoriginal(s, i, k)
    
30. print("\n", res)
    

复制代码

通过这样的修改，递归函数会在遇到重复序列时停止拼接，并返回最终的结果。

希望这可以帮助到你！如果还有其他问题，请随时提问。

跳转到最佳答案楼层

陶远航

根据你提供的代码，我注意到在递归函数getoriginal中，你将最初的序列存储在了字典dic中，并在每次拼接后更新了seq和illu。然而，你没有在递归调用时传递更新后的seq和illu，导致在递归过程中使用的仍然是原始的seq和illu，而不是拼接后的结果。

为了解决这个问题，你可以将递归调用的返回值赋值给seq和illu，以便在下一次递归中使用更新后的结果。修改后的代码如下所示：

1. # 拼接函数
   
2. def getoriginal(seq, illu, k):
   
3.     x = 0
   
4.     dic = {}
   
5.   
   
6.     for n, m in enumerate(seq):
   
7.         temp = m[-k:]
   
8.         for i, j in enumerate(seq):
   
9.             if i != n:
   
10.                 if temp == j[:k]:
    
11.                     name = illu[n] + " " + illu[ i]
    
12.                     newstr = m[:-k] + j
    
13.                     dic.update({name: newstr})
    
14.                     x += 1
    
15.   
    
16.     seq = list(dic.values())
    
17.     illu = list(dic.keys())
    
18.     print(seq, illu)
    
19.   
    
20.     if len(illu) == 1 or x == 0:
    
21.         return dic
    
22.     else:
    
23.         return getoriginal(seq, illu, k)
    
24. 
    
25. res = getoriginal(s, i, k)
    
26. print("\n", res)
    

复制代码

通过这样的修改，递归函数会正确使用更新后的seq和illu进行下一次递归调用，直到满足退出条件。

希望这可以帮助到你！如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案

isdkz

问题出在递归函数中，每次递归都会重新定义一个空的字典 dic ，导致之前拼接的结果丢失。解决方法是将字典 dic 作为参数传入递归函数中，并在每次递归时更新字典的值。以下是修改后的代码：

1. def getoriginal(seq, illu, k, dic):
   
2.     x = 0
   
3.     for n, m in enumerate(seq):
   
4.         temp = m[-k:]
   
5.         for i, j in enumerate(seq):
   
6.             if i != n:
   
7.                 if temp == j[:k]:
   
8.                     name = illu[n] + " " + illu[ i]
   
9.                     newstr = m[:-k] + j
   
10.                     dic.update({name: newstr})
    
11.                     x += 1
    
12.     seq = list(dic.values())
    
13.     illu = list(dic.keys())
    
14.     print(seq, illu)
    
15.     if len(illu) == 1 or x == 0:
    
16.         return dic
    
17.     else:
    
18.         return getoriginal(seq, illu, k, dic)
    
19. 
    
20. 
    
21. res = getoriginal(s, i, k, {})
    
22. print("\n", res)
    

复制代码

这样修改后，每次递归时都使用同一个字典 dic ，可以保留之前拼接的结果。

15588686105

不递归结果没问题，加上递归是死循环

15588686105

陶远航 发表于 2023-9-2 21:07
根据你提供的代码，我注意到在递归函数getoriginal中，你将最初的序列存储在了字典dic中，并在每次拼接后更 ...

好的谢谢，这样还是死循环，原因是测试用例本身会造成死循环，拼接之后还是会一直循环是的把

陶远航

15588686105 发表于 2023-9-2 21:34
好的谢谢，这样还是死循环，原因是测试用例本身会造成死循环，拼接之后还是会一直循环是的把

你的问题是关于序列拼接的递归函数，你想知道为什么测试用例会造成死循环。

根据你提供的测试用例，我发现其中有两个序列是相同的，即AAATAAA和AAAGAAA。这意味着无论你如何拼接它们，都会得到相同的结果，即AAATAAA或AAAGAAA。因此，递归函数会一直尝试拼接这两个序列，但永远无法达到退出条件，从而导致死循环。

为了避免这种情况，你可以在递归函数中添加一个判断条件，检查是否有重复的序列出现在seq中。如果有，就跳过拼接操作，直接返回dic。修改后的代码如下所示：

1. # 拼接函数
   
2. def getoriginal(seq, illu, k):
   
3.     x = 0
   
4.     dic = {}
   
5.   
   
6.     # 检查是否有重复的序列
   
7.     if len(seq) != len(set(seq)):
   
8.         return dic
   
9.   
   
10.     for n, m in enumerate(seq):
    
11.         temp = m[-k:]
    
12.         for i, j in enumerate(seq):
    
13.             if i != n:
    
14.                 if temp == j[:k]:
    
15.                     name = illu[n] + " " + illu[ i]
    
16.                     newstr = m[:-k] + j
    
17.                     dic.update({name: newstr})
    
18.                     x += 1
    
19.   
    
20.     seq = list(dic.values())
    
21.     illu = list(dic.keys())
    
22.     print(seq, illu)
    
23.   
    
24.     if len(illu) == 1 or x == 0:
    
25.         return dic
    
26.     else:
    
27.         return getoriginal(seq, illu, k)
    
28. 
    
29. res = getoriginal(s, i, k)
    
30. print("\n", res)
    

复制代码

通过这样的修改，递归函数会在遇到重复序列时停止拼接，并返回最终的结果。

希望这可以帮助到你！如果还有其他问题，请随时提问。

琅琊王朝

要实现递归功能以拼接字符串，您可以使用以下Python代码：

1. def recursive_splice(str_list, k):
2.     # 创建一个空列表，用于存储拼接后的字符串
3.     new_list = []
4.     flag = False  # 判断是否发生了拼接
5.    
6.     # 遍历列表中的字符串对
7.     for i in range(len(str_list) - 1):
8.         # 提取首尾两个字符串
9.         first_str = str_list[i]
10.         last_str = str_list[i+1]
11.         
12.         # 检查首尾k个字符是否相同
13.         if first_str[-k:] == last_str[:k]:
14.             new_list.append(first_str + last_str[k:])
15.             flag = True  # 发生了拼接
16.         else:
17.             new_list.append(first_str)
18.    
19.     # 将最后一个字符串添加到列表中
20.     new_list.append(str_list[-1])
21.    
22.     # 如果发生了拼接，则递归调用函数
23.     if flag:
24.         return recursive_splice(new_list, k)
25.     else:
26.         return new_list
28. # 测试用例
29. test_cases = ["AAATAAA", "CCCGAAA"]
31. # 调用递归拼接函数
32. result = recursive_splice(test_cases, 3)
34. # 输出结果
35. print(''.join(result))

复制代码

这段代码定义了一个名为`recursive_splice`的递归函数。它接受一个字符串列表和整数`k`作为输入参数。函数首先创建一个空列表`new_list`来存储拼接后的字符串。然后，它遍历字符串列表中的字符串对，并检查首尾`k`个字符是否相同。如果相同，则将拼接后的字符串添加到`new_list`中，并设置`flag`为`True`。最后，它将最后一个字符串添加到`new_list`中。如果发生了拼接（`flag`为`True`），则递归调用`recursive_splice`函数来继续拼接。否则，返回`new_list`作为结果。

在测试用例中，我们将输入字符串作为列表传递给`recursive_splice`函数，并指定`k=3`。最后，我们使用`''.join(result)`将结果列表转换为字符串，并打印输出。

希望这可以帮助您解决问题！如果您有任何其他问题，请随时提问。
此内容为ChatGPT回答，如果胡说八道，请不要理会
如果对你有帮助，请设置一个最佳答案！

15588686105

陶远航 发表于 2023-9-2 21:37
你的问题是关于序列拼接的递归函数，你想知道为什么测试用例会造成死循环。

根据你提供的测试用例，我 ...

感谢感谢