求给定数组的每个 (n-1) 个子集的乘积

2024-04-19

很抱歉删除了原来的问题,这里是: 我们有一个包含 n 个整数的包或数组,我们需要找到每个 (n-1) 个子集的乘积。例如:

S = {1,0,3,6}
ps[1] = 0*3*6 = 0;
ps[2] = 1*3*6 = 18; ETC。

经过讨论,我们需要处理三种情况,如下所示:

1. S is a set (contains one zero element)
  for i=1 to n
    if s[i]=0
      sp[i] = s[1] * s[2] * ...* s[i-1] * s[i+1] *.....*s[n]
    else
      sp[i] = 0;

2. S is a bag (contains more than one zero element) 
  for i=1 to n
      sp[i] = 0;

3. S is a set (contains no zero elements)
   product = 1
   for i=1 to n
     product *= s[i];
   for i=1 to n
     sp[i] = product / s[i];

Thanks.


如果集合非常大,可能会方便:

  • 预先计算所有元素的乘积 P,然后
  • 对于每个元素 x,获得 (n-1) 个乘积作为 P/x

如果集合包含零(即 P=0,x=0),则必须将其作为特殊情况处理。

EDIT。这是Scheme中的一个解决方案,考虑到andand的答案。我是一个完全的初学者 - 有人可以帮助我改进以下代码(使其更高效、更易读、更 lisp)吗? (随意编辑我的答案。)

#!/usr/bin/env guile !#
(use-modules (ice-9 pretty-print))

(define (count-zeros l)
    (cond ((null? l) 0)
          ((= 0 (car l)) (+ 1 (count-zeros (cdr l))))
          (else (count-zeros (cdr l)))))

(define (non-zero-product l)
    (define (non-zero-product-loop l product)
        (cond ((null? l) product)
              ((= 0 (car l)) (non-zero-product-loop (cdr l) product))
              (else (non-zero-product-loop (cdr l) (* (car l) product)))))
    (non-zero-product-loop l 1))

(define (n-1-products l)
    (let ((nzeros (count-zeros l)))
         (cond ((> nzeros 1)
                   (map (lambda (x) 0) l))
               ((= 1 nzeros)
                   (map (lambda (x) (if (= 0 x) (non-zero-product l) 0)) l))
               (else 
                   (map (lambda (x) (/ (non-zero-product l) x)) l)))))

(pretty-print (n-1-products '(1 2 3 4 5)))
(pretty-print (n-1-products '(0 1 2 3 4)))
(pretty-print (n-1-products '(0 1 2 3 0)))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

求给定数组的每个 (n-1) 个子集的乘积 的相关文章

  • 使到 n 个点的集合的欧氏距离之和最小的点

    我有一组点W x1 y1 x2 y2 xn yn 在 2D 平面上 你能找到一种算法 将这些点作为输入并返回一个点 x y 在 2D 平面上 距以下点的距离之和最小W 换句话说 如果 di Euclidean distance x y xi
  • Python 给定 k 个分区的整数分区

    我正在尝试寻找或开发Python 的整数分区代码 仅供参考 整数分区将给定整数 n 表示为小于 n 的整数之和 例如 整数5可以表示为4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 我为此找到了许多解决方案 ht
  • 从日志文件中获取前 100 个 URL

    我的一位朋友在接受采访时被问到以下问题 谁能告诉我如何解决它 我们有一个相当大的日志文件 大约 5GB 日志文件的每一行都包含一个用户在我们网站上访问过的 URL 我们想要找出用户访问最多的 100 个 URL 怎么做 如果我们有超过 10
  • 字符串排序真的是 O(n^2logn) 吗? [复制]

    这个问题在这里已经有答案了 我读了以下内容 排序需要 O NlogN 那么它怎么是 O N 2logN 我们在这里想念的是 两个字符串的比较不是 O 1 在最坏的情况下 需要 在 所以最终的复杂度是O N 2logN 它是否正确 我一直认为
  • 如何求解:T(n) = T(n - 1) + n

    我已经解决了以下问题 T n T n 1 n O n 2 现在 当我解决这个问题时 我发现界限非常松散 我是否做错了什么 或者只是这样 您还需要一个递归关系的基本情况 T 1 c T n T n 1 n 为了解决这个问题 您可以首先猜测一个
  • 编程 Pearls - 随机选择算法

    Programming Pearls 第一版第 120 页介绍了从 N 个整数总体中选择 M 个等概率随机元素的算法 InitToEmpty Size 0 While Size lt M do T RandInt 1 N if not Me
  • 检索受“rowspan”影响的行的列索引的最有效方法是什么?

    考虑下表 table thead tr th th th A th th B th th C th tr thead tbody tr th 1 th td Apples td td Oranges td td Pears td tr tb
  • 快速搜索压缩文本文件

    我需要能够在大量压缩文件 txt 中搜索文本 压缩可能会改变为其他东西 甚至成为专有的 我想避免解压所有文件并压缩 编码 搜索字符串并在压缩文件中搜索 这应该可以通过对所有文件使用相同的码本使用霍夫曼压缩来实现 我不想重新发明轮子 所以 任
  • 如何确定算法函数的复杂度?

    您如何知道算法函数对于特定操作是否需要线性 常数 对数时间 它取决于CPU周期吗 您可以通过三种方式 至少 做到这一点 在网上查找算法 看看它是如何描述其时间复杂度的 根据输入大小 自己检查算法 查看嵌套循环和递归条件等内容 以及每个循环运
  • 找到一系列间隔的最有效分组

    我有一个应用程序 其中有一系列不重叠的固定宽度间隔 每个间隔都有一个给定的键 每个间隔具有相同的宽度 并且可以存在连续的间隔 本质上 我想以最小化单独间隔的数量的方式对间隔和键进行分组 这可以通过合并具有相同键的连续间隔或查找匹配间隔并将它
  • 将字符串中的“奇怪”字符转换为罗马字符

    我需要能够将用户输入仅转换为 a z 罗马字符 不区分大小写 所以 我感兴趣的角色只有26个 然而 用户可以输入他们想要的任何 形式 的字符 西班牙语 n 法语 e 和德语 u 都可以包含用户输入中的重音符号 这些重音符号会被程序删除 我已
  • 从每个子集中选择最大值

    我在这里敲头 我觉得自己很愚蠢 因为我确信我以前做过类似的事情 但我一辈子都不记得是怎么做的 我想那一天 gt 假设我有以下数据 gt 和一个返回此数据的查询 gt 但我想要这个 ID FirstID ID FirstID ID First
  • 使用多级解决方案计算二维网格中的最近邻

    我有一个问题 在 x y 大小的网格中 我提供了一个点 并且我需要找到最近的邻居 在实践中 我试图在 pygame 中找到距离光标最近的点 该点跨越颜色距离阈值 计算如下 sqrt rgb1 0 rgb2 0 2 rgb1 1 rgb2 1
  • 使用并集查找(又名不相交集)检测图是否是二分图

    我正在 Spoj 上做一个问题 基本上可以简化为检测图是否是二分图 我正在尝试使用 dfs 为图表着色 但它太慢了 有人评论这个 没有 bfs 没有 dfs 没有二部图 简单的并查集就可以做到 确实速度很快 提示 1 偶数长度的环不会影响两
  • C# 中的 strstr() 等效项

    我有两个byte 我想找到第二个的第一次出现byte 在第一个byte 或其中的一个范围 我不想使用字符串来提高效率 翻译第一个byte to a string会效率低下 基本上我相信就是这样strstr 在 C 中做 最好的方法是什么 这
  • 直接选择排序与交换选择排序

    有什么区别直接选择排序 vs 交换选择排序 今天我陷入了一场争论 我的教授在他的讲义中使用了这两个术语 维基百科和任何教科书或网站都会为您提供的选择排序就是他所说的 交换选择排序 我以前从未听说过 交换选择排序 这个术语 仅 选择排序 并且
  • 计算两点之间的最短路线

    过去几周我一直在开发一款多人 HTML5 游戏 使用nodejs and websockets 我已经被这个问题困扰了一段时间 想象一下 我用数组实现了这个平铺地图 如下所示 1 or 棕色瓷砖 路上有障碍物 玩家无法通过 0 or 绿色瓷
  • 通过 R 中的数据子集执行计算

    我想对数据框的 PERMNO 列中的每个公司编号进行计算 其摘要可以在此处查看 gt summary companydataRETS PERMNO RET Min 10000 Min 0 971698 1st Qu 32716 1st Qu
  • 归并排序中递归树的高度log(n)+1是怎么来的

    我按照 stackoveflow 的建议阅读了一些问题和答案 我正在遵循 cormen 的 算法简介 一书进行自学 那本书里已经解释得很清楚了 但唯一没有解释的是如何在合并排序分析中计算树的高度 如果在后面的章节中对此进行解释的话 我仍然在
  • 从一种数字系统转换为另一种数字系统后会有多少位数字

    主要问题 有多少位数字 让我解释 我有一个二进制数 11000000 十进制数是192 转换为十进制后 它有多少位 以十进制表示 在我的示例中 它是 3 位数字 但是 这不是问题 我在互联网上搜索并找到了一种用于整数部分的算法和一种用于小数

随机推荐

  • 如果缺少一台主机,Datastax Java 驱动程序将无法连接

    如果我没记错的话 可以连接到 Cassandra 集群 至少知道集群中的一个节点 然后可以发现其他节点 假设我有三个节点 1 2 和 3 并且我像这样连接到这些节点 Cluster builder addContactPoints 1 2
  • jquery选择器在ajax加载时找不到元素

    没有任何 jQuery 选择器能够通过 Ajax 请求处理从服务器加载的元素 但它在正常模式下工作得很好 myid change function alert OK
  • 如何继承 ASP.NET MVC 控制器并仅更改视图?

    我有一个从基本控制器继承的控制器 我想知道如何利用基本控制器的所有逻辑 但返回与基本控制器使用的不同的视图 基本控制器填充模型对象并将该模型对象传递到其视图 但我不确定如何在子控制器中访问该模型对象 以便将其传递到子控制器的视图 有几点 如
  • 这种基于 Flexbox 的布局是否需要额外的标记?

    我现在开始使用 Flexbox 尝试了解如何从使用传统 CSS 网格过渡 我有两种布局 一种是用 CSS 网格制作的 另一种是使用 Flexbox 制作的 这两个示例的基本布局都非常基本 页眉 导航 内容部分和页脚 从设计角度来看 它们看起
  • Rails 5.1.1 弃用警告已更改_属性

    我刚刚从 Rails 5 0 0 升级到 5 1 1 并开始收到大量弃用警告 如下所示 弃用警告 的行为changed attributes代替 after 回调将在下一版本的 Rails 中发生变化 新的 返回值将反映之后调用该方法的行为
  • 阻止 UIScrollView 的子视图调整大小?

    我有一个UIScrollView 具有由返回的视图的多个级别的子视图viewForZoomingInScrollView 在缩放期间 我希望其中一些子视图调整大小 而其他子视图不调整大小 无论我尝试什么 所有子视图都会调整大小 在子视图的超
  • 查询 mongodb 返回今天创建的文档

    我如何编写今天创建的结果文档的过滤器 我知道 ObjectId 有时间戳 我试过这个 db doc find id gte ObjectId getTimestamp getTime 我可以写吗 db doc find id getTime
  • Qml中的QScrollArea:Flickable + QQuickPaintedItem

    我正在尝试实现类似的东西QScrollArea 在小部件世界中 在 Qml 的帮助下 我决定一探究竟Flickable plus QQuickPaintedItem基于项目 在我的例子中名为抽屉 Flickable onContentXCh
  • Rails:backbone-on-rails gem-

    尝试按照 Ryan Bates Backbone js 教程构建抽奖应用程序 但我已经遇到了第一部分代码的问题 在 application js 的 init 函数中 他初始化了 Raffler 路线的新实例 该实例应该触发警报 主页 但我
  • 如何从Java中的Apple公钥JSON响应中获取公钥?

    我们正在尝试在 iOS 应用程序中添加 使用 Apple 登录 当客户端工作正常时 我们的后端是用 Java 编写的 我们无法解码 Apple 的公钥 当您点击网址时https appleid apple com auth keys htt
  • 无法登录 Magento 管理员

    我在登录我们的一个临时站点上的 Magento 管理面板时遇到问题 它在我们的 webdev 服务器上 100 工作 不久前在临时服务器上也工作得很好 我做了一些研究 大多数人认为这与在本地主机上运行 Magento 以及浏览器不为域名中没
  • Lucene:如何在单个字段下索引和搜索多个值

    如何在单个字段下索引和搜索多个值 例如说我有一个领域处理器这可能有i3 i5 i7 or i3 or i3 i5价值观 现在想象一下笔记本电脑的数据如下 data1 name laptop name price laptop price p
  • 接受任意切片的 Express 函数

    我想表达一个可以取任何切片的函数 我想我可以这样做 func myFunc list interface for i range list some other fun i where some other fun 本身需要一个interf
  • 如何将 GMP C 参数约定转换为更自然的东西?

    例如 我想做这样的事情 include
  • 如何使用“prototype”函数正确编写 JavaScript 属性和方法?

    我正在尝试学习如何使用 javascript 原型创建和使用 javascript 属性和方法 但遇到了一些困难 在下面的代码中 我尝试创建一个名为 radius 的简单对象 其半径为 4 并具有一个名为 getCircumference
  • 如果 cookie 未发送到服务器,则可以安全地将访问令牌存储在客户端 cookie 中

    我正在开发一个主干应用程序 其中包含 Laravel 后端的 REST api 这意味着我使用从社交媒体 例如 Facebook Google 等 收到的访问令牌对每个请求进行身份验证 我的计划是存储用 Javascript 生成的客户端
  • Node.js 或 Erlang

    当谈到它们可以处理的并发级别时 我真的很喜欢这些工具 Erlang OTP 看起来是更稳定的解决方案 但需要更多的学习和深入研究函数式语言范例 看起来 Erlang OTP 在多核 CPU 方面做得更好 如果我错了 请纠正我 但我应该选择哪
  • 在 Xcode 4 中本地化 iPhone 应用程序名称

    当我选择 Info plist 文件以便本地化应用程序名称并尝试构建项目时 构建失败并显示错误 提示找不到 Info plist 文件 如果我将 Info plist 文件路径更改为PROJECTNAME en lproj Info pli
  • 如何在 ASP.net MVC 中正确执行异步方法?

    如何从控制器方法内执行异步方法并返回 HttpStatusCodeResult 200 而异步委托不会提前终止其执行 我正在开发一个 asp net 应用程序 我的家庭控制器的一个操作需要很长时间才能运行 10 30 秒 我想返回 Http
  • 求给定数组的每个 (n-1) 个子集的乘积

    很抱歉删除了原来的问题 这里是 我们有一个包含 n 个整数的包或数组 我们需要找到每个 n 1 个子集的乘积 例如 S 1 0 3 6 ps 1 0 3 6 0 ps 2 1 3 6 18 ETC 经过讨论 我们需要处理三种情况 如下所示