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

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.

然后 return 交换的数量和最终答案的校验和。我的程序似乎根据需要进行排序和校验和。但是除了他们给出的测试输入之外，我的最终答案是错误的。

所以：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 1291223，当正确答案是 39 3485793。

这是我目前拥有的：

# 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

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

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

您正在逐位计算 2967439240707483842747064867463187179639043276268209559266227857859127247091613388169792999692421001863750412763159556330418794527699666 的 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, 37504, 1, 27631, 59556, 33041, 87, 9, 45276, 99666]

的 Checksum

修正：

# 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。

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

Unsure why program similar to bubble-sort is not working

python

python-2.7

checksum

bubble-sort