python - 不确定为什么类似于冒泡排序的程序不起作用

Question

我一直在应对编程挑战，problem here ，它基本上指出:

Given integer array, you are to iterate through all pairs of neighbor elements, starting from beginning - and swap members of each pair where first element is greater than second.

然后返回进行的交换数量以及最终答案的校验和。我的程序似乎根据需要进行排序和校验。但我的最终答案除了他们提供的测试输入之外的所有内容都无效。

所以:1 4 3 2 6 5 -1使用我的程序产生正确的输出:3 5242536。

但是类似:

2 96 7439 92999 240 70748 3 842 74 706 4 86 7 463 1871 7963 904 327 6268 20955 92662 278 57 8 5912 724 70916 13 388 1 697 99666 6924 2 100 186 37504 1 27631 59556 33041 87 9 45276 -1

当正确答案为 39 3485793 时，结果为:39 1291223。

这是我目前所拥有的:

# Python 2.7

def check_sum(data):
    data = [str(x) for x in str(data)[::]]
    numbers = len(data)
    result = 0

    for number in range(numbers):
        result += int(data[number])
        result *= 113
        result %= 10000007

    return(str(result))

def bubble_in_array(data):
    numbers = data[:-1]
    numbers = [int(x) for x in numbers]
    swap_count = 0

    for x in range(len(numbers)-1):
        if numbers[x] > numbers[x+1]:
            temp = numbers[x+1]
            numbers[x+1] = numbers[x]
            numbers[x] = temp
            swap_count += 1

    raw_number = int(''.join([str(x) for x in numbers]))
    print('%s %s') % (str(swap_count), check_sum(raw_number))
bubble_in_array(raw_input().split())

有人知道我哪里出了问题吗？

Answer 1

问题在于您计算校验和的方式。当数组中的数字超过一位时，它会失败。例如:

2 96 7439 92999 240 70748 3 842 74 706 4 86 7 463 1871 7963 904 327 6268 20955 92662 278 57 8 5912 724 70916 13 388 1 697 99666 6924 2 100 186 37504 1 27631 59556 33041 87 9 45276 -1

您正在计算 29674392407074838427470648674631871796390432762682095592662278578591272470916133881697929996924210018637 的校验和 50412763159556330418794527699666 逐位计算 Checksum 的 [2, 96, 7439, 240, 70748, 3, 842, 74, 706, 4, 86, 7, 463 , 1871, 7963, 904, 327, 6268, 20955, 92662, 278, 57, 8, 5912, 724, 70916, 13, 388, 1, 697, 92999, 6924, 2, 100, 186, 3750 4, 1, 27631 , 59556, 33041, 87, 9, 45276, 99666]


修复:

# Python 2.7

def check_sum(data):
    result = 0

    for number in data:
        result += number
        result *= 113
        result %= 10000007

    return(result)

def bubble_in_array(data):
    numbers = [int(x) for x in data[:-1]]
    swap_count = 0

    for x in xrange(len(numbers)-1):
        if numbers[x] > numbers[x+1]:
            numbers[x+1], numbers[x] = numbers[x], numbers[x+1]
            swap_count += 1

    print('%d %d') % (swap_count, check_sum(numbers))

bubble_in_array(raw_input().split())

更多注释:

• 要在 Python 中交换两个变量，不需要使用 temp 变量，只需使用 a,b = b,a。
• 在 python 2.X 中，使用 xrange 而不是 range。