一、 实验目的及任务
分治法求解最大子数组问题
二、 实验环境
c++或java
三、 问题描述
Input : 一个数组
Output:最大连续子数组。
四、 编程任务
一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。
五、 数据输入
随机产生1000以上的数据(有正有负),放入输入文件input.txt
六、 结果输出
比如数组{2,4,-7,5,2,-1,2,-4,3}的最大连续子数组为{5,2,-1,2},最大连续子数组的和为5+2-1+2=8。
七、 实验报告内容
import random import math #随机生成数 def randomData(): # 打开input文件 file = open('input.txt', 'w', encoding='utf8'); print("正在随机生成数据,写入input.txt文件") # 产生10万个数据,从0到100000 i = 0; while i < 110000: file.write(str(random.randint(-5000, 110000))+"\n") i = i + 1; file.close() print("写入input.txt文件完毕") #一、输入n个整数,求出连续的m个的和最大。 #打开input.txt文件 读取文件 def readLine(): # 行数 count_line = 0; # 定义存储的元组 arr1 = [] file = open('input.txt', 'r', encoding='utf8'); for line in file.read().splitlines(): arr1.append(int(line)) count_line = 1 + count_line; # 计算行数 file.close(); return arr1; def writeLine(A,arrA): # 打开input文件 file = open('output.txt', 'w', encoding='utf8'); print("正在打开output.txt文件") i = arrA[0]; while i < arrA[1]: file.write(str(A[i]) + "\n") i = i + 1; file.close() print("结果写入output.txt文件完毕") def FIND_MAXIMUM_SUBARRAY(A,low,high): if high == low: return [low,high,A[low-1]] else: mid = math.floor((low+high)/2) #向下取整 left = FIND_MAXIMUM_SUBARRAY(A,low,mid) right = FIND_MAXIMUM_SUBARRAY(A, mid+1, high) cross = FIND_MAX_CROSSING_SUBARRAY(A, low, mid,high) if left[2] >= right[2] and left[2] >= cross[2]: return left elif right[2] >= left[2] and right[2] >= cross[2]: return right else: return cross def FIND_MAX_CROSSING_SUBARRAY(A,low, mid,high): left_sum = -1568413122 sum = 0 max_left = 0 for i in range(mid, low,-1): sum = sum + int(A[i]) if sum > left_sum: left_sum = sum max_left = i right_sum = -1568413122 sum = 0 max_right = 0 for j in range(mid+1,high): sum = sum + A[j] if sum > right_sum: right_sum = sum max_right = j return [max_left,max_right,(left_sum+right_sum)] #结果 [0, 109999, 2888566239] if __name__ == '__main__': #随机生成数据并存放在input.txt文件中 randomData(); #读取数据 print("正在获取数据") A = readLine(); # A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7] low = 0; high = len(A) arrA = FIND_MAXIMUM_SUBARRAY(A,low,high) print("结果",arrA) writeLine(A,arrA) # for i in "100000": # print(i) # print(random.randint(1,100))
实验结果
结果1:使用课本上的测试数据:[12,5,1,9,-11]进行排序
结果2:随机生成1100000个数字,从-5000到182000,存入到input1.txt文件中