c++程序 大一 急！可有偿

来源：蜘蛛抓取(WebSpider) 时间：2022-05-06 05:34 标签： C++求和

题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离.

编程练习题 – 最多水容器 (递归)

最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度. 可以用递归来实现, 但是递归需要额外O(n) 的空间 – 调用堆栈:

我们这里定义了一个 f(j) 表示从0号柱子到 j 号柱子的最大装水量. 那么两种情况, 要么 j 号柱子是最终最右边的那个柱子(这时候需要穷举左边柱子从0到 j-1 号), 要么不是 f(j-1).

时间复杂度为O(n^2), 空间复杂度为 O(n) – 调用堆栈. 实际上, 我们可以较简单的用 O(n^2) 来穷举每一对, 代码显得更简单, 并且空间复杂度也只需要常数级 O(1).

实际上, 最优解是 O(n), 我们最先在两端建立一个容易, 两个指针, 同时记录当前最大装水量, 每次移动最短边逐渐往中间移动. 为什么呢? 因为如果你移动最长边的那端, 装水量肯定不会增加, 因为装水量是由最短边确定的. 移动最短边有可能获得更大的装水量(来弥补X轴距离的缩短). 这也就是贪心.

前两种都是O(n^2) 的算法, 大概通过50个测试点需要费时1秒钟, 而最后一种 O(n) 算法只需要12毫秒.

本文一共 421 个汉字, 你数一下对不对.

　　有没有熟悉DICOM3.0标准和PACS系统的大牛，用C++语言实现DICOM图像传输至PACS软件，可以具体交流一下。

楼主发言：1次 发图：0张 | 添加到话题 |

请遵守言论规则，不得违反国家法律法规

我要回帖

更多关于 C++求和 的文章

 

随机推荐