3 
def abc(s):
    filter = [i for i in s.lower() if i in 'abcdefghijklmnopqrstuvwxyz']
    for i in range(len(filter) - 1):
        if filter[i] > filter[i+1]:
            return print(s, "is not abcdearian")
    return print(s,  "is abcdearian")


while True:
    try:
        s = input("String? ")
abc(s)

我无法制作 abc(s) 的递归版本。有任何想法吗？

4

3 回答 3

3

非递归解决方案：

def issorted(L):
    return all(x <= y for x, y in zip(L, L[1:]))

要创建递归函数，您应该找到一种方法将问题拆分为可以以相同方式解决的更小和/或更简单的子问题：

#!/usr/bin/env python3
from string import ascii_lowercase

def abcdearian(s):
    return issorted_recursive([c for c in s.lower() if c in ascii_lowercase])

def issorted_recursive(L):
    return L[0] <= L[1] and issorted_recursive(L[1:]) if len(L) > 1 else True

这issorted_recursive()是一个递归函数。基本情况是len(L) <= 1（具有零或一个元素的列表始终排序，因此True在这种情况下返回）。在递归情况下 ( len(L) > 1)，L如果第一项按排序顺序 ( L[0] <= L[1])并且列表的其余部分 ( L[1:]) 也已排序，则认为列表已排序。每次函数接收越来越小的输入，直到找到乱序元素（L[0] > L[1]）或遇到基本情况并且函数完成。

例子

while True:
    s = input("String? ")
    if not s:
        break
    print("{} is {}abcdearian".format(s, "" if abcdearian(s) else "not "))

输入

    美国广播公司
    背书

输出

String? abc is abcdearian
String? bac is not abcdearian
String?
于 2012-11-30T02:34:31.077 回答
0

试试这个代码，它相当于问题中发布的代码，但以递归风格编写：

from string import ascii_lowercase

def abc(s):
    f = [c for c in s.lower() if c in ascii_lowercase]
    if aux(f, 0):
        return s + " is abcdearian"
    else:
        return s + " is not abcdearian"

def aux(s, i):
    if i >= len(s)-1:
        return True
    elif s[i] > s[i+1]:
        return False
    else:
        return aux(s, i+1)

像这样使用它：

while True:
    s = input("String? ")
    if not s:
        break
    print(abc(s))

请注意，我将问题分为两部分：首先，“main”函数abc()负责过滤字符串，aux使用正确的初始值调用过程并在最后返回结果字符串（或者：您可以返回一个布尔值，创建结果字符串别处。）

真正的工作是在辅助aux函数中完成的，它递归地遍历字符串，检查字符串中所有连续字符对的“abcdearian”条件是否为真。遍历字符串的方式aux是高效的（撇开我们使用递归的事实不谈），因为它从不使用s[1:]. 它也是尾递归算法的一个例子，它密切反映了迭代解决方案的结构。

于 2012-11-30T01:12:52.950 回答
0

接受答案的最初编写方式似乎过于复杂。我已经提交了一个编辑，希望能解决这个问题。但是当我意识到这一点时，我已经写了下面的答案和解释。保留它，以防解释对某人有用：

def abc(s):
    filtered = [i for i in s.lower() if i in 'abcdefghijklmnopqrstuvwxyz']
    optionalNotString = ('' if _abc(filtered) else ' not')
    print( '{0} is{1} abcdearian'.format( repr(s), optionalNotString ) )

# Recursively process the "rest" (remainder) of the string.
# At each step, examine the first two characters.
def _abc(rest):
    if len(rest) < 2:
        # We've successfully compared all successive pairs, so return True.
        return True
    if (rest[0] > rest[1]):
        return False
    return _abc(rest[1:])

在使用中（最重要的测试案例，包括太短的字符串，以及在字符串 'acb' 的末尾以及字符串 'bac' 的开头检测到 False 条件。我第一次写的时候遇到了一个错误它，它未能将 'bac' 捕获为 False！）：

abc( '' )
abc( 'a' )
abc( 'ac' )
abc( 'abc' )
abc( 'acb' )
abc( 'bac' )

输出：

'' is abcdearian
'a' is abcdearian
'ac' is abcdearian
'abc' is abcdearian
'acb' is not abcdearian
'bac' is not abcdearian

解释：

  1. 过滤只需要进行一次，所以在主“abc”函数中进行，而不是在递归“_abc”函数中。

  2. 在每一步，算法都需要查看两个相邻的字符。在每次调用“_abc”时，这些将是前两个字符。

  3. “_abc”需要处理两种情况：

    • 情况 1：字符串太短，无法进行比较。例如''或'a'。这样的字符串满足 abcderian 标准，所以返回 True。

    • 情况 2：字符串至少有两个字符。执行前两个的 abcderian 计算。如果失败，则答案为 False。否则，使用除第一个字符以外的所有字符进行递归。

  4. "repr(s)" 是一种让 "s" 与周围的引号一起打印的简单方法。

  5. “optionalNotString”：在真/假情况下所需的答案字符串仅因存在/不存在“不”而有所不同。所以使用 "if .. else .." 表达式，来控制 'not' 是否包含在格式化输出中。如果不需要，请替换空字符串 ''。

于 2013-12-12T21:12:19.467 回答