查找两首或多首歌曲交集的算法

2024-04-07

假设我们有一堆收音机,每个收音机都一遍又一遍地循环播放同一首歌。 是否可以同步所有收音机中的所有歌曲?我们能找到一个时间从头听到所有歌曲吗?

为了简单起见,我们会说我们只有两个收音机。

我有以下公式:

c 和 z 代表歌曲的长度(以秒为单位)。 a 和 x 代表歌曲中的当前位置(以秒为单位) S表示C和Z同步的时间。 (两首歌同时开始时)

例如 :

Song 1
a = 17 : the time before the song ends.
b = 8 : the rest of the song.
c = a + b which is the full song in seconds.
And
Song 2 
x = 8 : the time before the song ends.
y = 9 : the rest of the song.
z = 8 + 9 which is the full song in seconds.

Song 1 : a + ( a + b) => S
Song 2 : x +(( x + y ) × n) => S

Song 1 : 17 + ( 17 + 8) => 42
Song 2 : 8 + ((8 + 9)) = 25
So in order to synchronize song 2 with song 1 we have to multiply (x + y)    
by two and add x to it.

Song 2 : 8 + ((8 + 9) x 2) => 42

So S = 42 and so the two songs will synchronize after 42 seconds.

现在第一个例子是最简单的。对于其他情况,我必须将 z 和 c 乘以二以上才能获得适合它们的 S。

我还有一些其他输入,并且我尝试想出一种为我返回 S 的算法,但我没有运气。

这是我到目前为止想到的:

c = a + b
a = 16
b = 4
c = 20
s = 216

And

z = x + y
x = 12
y = 5
z = 17
s = 216
S is the LCM of c and z

在第一个示例中,S 是这样找到的:

s = x +(z × n)
n = ( s − x ) ÷ b
12 + ( 17 × 12) = 216

and

s = a + (c × n)
n = ( s − a ) ÷ b
16 + ( 20 × 10 ) = 216

我根据 S 的值想出了下面两个公式。但是我需要找到一种方法来找到 n 而无需实际使用 S。 或者换句话说,我需要找到一种方法来找到我应该将(a + b)乘以n和(x + y)乘以n多少次才能得到S。

n = ( s − a ) ÷ b
S = x + ( y × n)

但这些公式显然不起作用,因为它们需要 S。我们不能使用它,因为这应该是我试图提出的公式的结果。

以下是一些计算的其他示例:

a2 = 52
b2 = 4
c2 = 56
s2 = 276

x2 = 60
y2 = 12
z2 = 72
s2 = 276

这是永远不会同步的情况:

A1 = 14
B1 = 4
C1 = 18
S1 = Never synchronizes

A2 = 19
B2 = 5
C2 = 24
S2 = Never synchronizes

以下是歌曲已经同步的一些情况:

Case 1

A2 = 17  
B2 = 0 
C2 = 17 
S4 = 0

A3 = 25  
B3 = 0 
C4 = 25  
S4 = 0

Case 2

A4 = 0 
B4 =  13  
C4 = 13  
S4 = 0


A5 = 0 
B5 = 21 
C5 = 21  
S5 = 0

我正在考虑使用最小公倍数,但我不确定如何在这种情况下实现它,或者它是否是这个问题的正确解决方案。

如果歌曲超过 2 首,我想要提出的算法也应该有效。 例如,为 3 或 4 首歌曲找到 S。

这个算法的主要问题是判断两首歌是否同步,计算本身并不难。 你能帮我吗 ?提前致谢


的最小公倍数c and z是歌曲同步的连续时间之间的间隔(如果它们同步的话)。这意味着,如果我们可以确定一个时间,我们可以通过添加(或减去)LCM 的倍数来找到其余的时间。要找到这个时间(实际上是 LCM),请使用扩展欧几里得算法 https://en.wikipedia.org/wiki/Euclidean_algorithm#B.C3.A9zout.27s_identity查找整数T, U满足方程

 (c - a) + T*c = (z - x) + U*z

这在替换下是等价的V = -U to

 T*c + V*z = (c - a) - (z - x).

详细地,求 GCDc and z,检查它是否可以划分(c - a) - (z - x),然后将 Bézout 系数乘以((c - a) - (z - x))/GCD(c, z).

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

查找两首或多首歌曲交集的算法 的相关文章

  • MEX 文件中的断言导致 Matlab 崩溃

    我正在使用mxAssert 宏定义为matrix h在我的 C 代码中 mex 可以完美编译 当我调用的 mex 代码中违反断言时 该断言不会导致我的程序崩溃 而是导致 Matlab 本身崩溃 我错过了什么吗 这是有意的行为吗 当我查看 M
  • Qt - 无法让 lambda 工作[重复]

    这个问题在这里已经有答案了 我有以下功能 我想在其中修剪我的std set
  • 通信对象 System.ServiceModel.Channels.ServiceChannel 不能用于通信

    通信对象System ServiceModel Channels ServiceChannel 无法用于通信 因为它处于故障状态 这个错误到底是什么意思 我该如何解决它 您收到此错误是因为您让服务器端发生 NET 异常 并且您没有捕获并处理
  • std::map 和二叉搜索树

    我读过 std map 是使用二叉搜索树数据结构实现的 BST 是一种顺序数据结构 类似于数组中的元素 它将元素存储在 BST 节点中并按其顺序维护元素 例如如果元素小于节点 则将其存储在节点的左侧 如果元素大于节点 则将其存储在节点的右侧
  • ZLIB 解压缩

    我编写了一个小型应用程序 该应用程序应该解压缩以 gzip deflate 格式编码的数据 为了实现这一点 我使用 ZLIB 库 使用解压缩功能 问题是这个功能不起作用 换句话说 数据不是未压缩的 我在这里发布代码 int decompre
  • 获取从属性构造函数内部应用到哪个属性的成员?

    我有一个自定义属性 在自定义属性的构造函数内 我想将属性的属性值设置为属性所应用到的属性的类型 是否有某种方式可以访问该属性所应用到的成员从我的属性类内部 可以从 NET 4 5 using CallerMemberName Somethi
  • C++11 函数局部静态 const 对象的线程安全初始化

    这个问题已在 C 98 上下文中提出 并在该上下文中得到回答 但没有明确说明有关 C 11 的内容 const some type create const thingy lock my lock some mutex static con
  • 是否有与 C++11 emplace/emplace_back 函数类似的 C# 函数?

    从 C 11 开始 可以写类似的东西 include
  • 为什么 std::allocator 在 C++17 中丢失成员类型/函数?

    一边看着std 分配器 http en cppreference com w cpp memory allocator 我看到成员 value type pointer const pointer reference const refer
  • 范围和临时初始化列表

    我试图将我认为是纯右值的内容传递到范围适配器闭包对象中 除非我将名称绑定到初始值设定项列表并使其成为左值 否则它不会编译 这里发生了什么 include
  • 通过不同 DLL 或 EXE 中的指针或引用访问 STL 对象时发生访问冲突

    我在使用旧版 VC6 时遇到以下问题 我只是无法切换到现代编译器 因为我正在处理遗留代码库 http support microsoft com kb 172396 http support microsoft com kb 172396
  • 用于从字符串安全转换的辅助函数

    回到 VB6 我编写了一些函数 让我在编码时无需关心字符串的 null 和 数字的 null 和 0 等之间的区别 编码时 没有什么比添加特殊情况更能降低我的工作效率了用于处理可能导致一些不相关错误的数据的代码 9999 10000 如果我
  • C# using 语句、SQL 和 SqlConnection

    使用 using 语句 C SQL 可以吗 private static void CreateCommand string queryString string connectionString using SqlConnection c
  • Qt - 设置不可编辑的QComboBox的显示文本

    我想将 QComboBox 的文本设置为某些自定义文本 不在 QComboBox 的列表中 而不将此文本添加为 QComboBox 的项目 此行为可以在可编辑的 QComboBox 上实现QComboBox setEditText cons
  • 32位PPC rlwinm指令

    我在理解上有点困难rlwinmPPC 汇编指令 旋转左字立即然后与掩码 我正在尝试反转函数的这一部分 rlwinm r3 r3 0 28 28 我已经知道什么了r3 is r3在本例中是一个 4 字节整数 但我不确定这条指令到底是什么rlw
  • 无法使用 Ninject 将依赖项注入到从 Angular 服务调用的 ASP.NET Web API 控制器中

    我将 Ninject 与 ASP NET MVC 4 一起使用 我正在使用存储库 并希望进行构造函数注入以将存储库传递给其中一个控制器 这是实现 StatTracker 接口的上下文对象 EntityFramework public cla
  • 热重载时调用方法

    我正在使用 Visual Studio 2022 和 C 制作游戏 我想知道当您热重新加载应用程序 当它正在运行时 时是否可以触发一些代码 我基本上有 2 个名为 UnloadLevel 和 LoadLevel 的方法 我想在热重载时执行它
  • 在基类集合上调用派生方法

    我有一个名为 A 的抽象类 以及实现 A 的其他类 B C D E 我的派生类持有不同类型的值 我还有一个 A 对象的列表 abstract class A class B class A public int val get privat
  • Swagger 为 ASP.CORE 3 中的字典生成错误的 URL

    当从查询字符串中提取的模型将字典作为其属性之一时 Swagger 会生成不正确的 URL 如何告诉 Swagger 更改 URL 中字典的格式或手动定义输入参数模式而不自动生成 尝试使用 Swashbuckle 和 NSwag 控制器 pu
  • 如何创建向后兼容 Windows 7 的缩放和尺寸更改每显示器 DPI 感知应用程序?

    我是 WPF 和 DPI 感知 API 的新手 正在编写一个在 Windows 7 8 1 和 10 中运行的应用程序 我使用具有不同每个显示器 DPI 设置的多个显示器 并且有兴趣将我的应用程序制作为跨桌面配置尽可能兼容 我已经知道可以将

随机推荐

  • sqlalchemy.exc.OperationalError:(sqlite3.OperationalError)尝试创建数据库时无法打开数据库文件错误[重复]

    这个问题在这里已经有答案了 我正在 AWS 上的 Ubuntu 18 04 Lightsail 实例中工作 当我在 python3 中运行以下代码时 出现以下错误 该脚本中的每一行都运行良好 除了最后一行Base metadata crea
  • 如何在 d3 力定向图中将链接渲染为弯头连接器

    我对 D3 很陌生 这就是我到目前为止所做的here http jsfiddle net gj2y87z8 13 实际的代码在这里 var width 1840 height 1480 constant 100 color BCD8CD v
  • 在 for 循环的开头组合数组 (Bash)

    可以做这样的事情吗 a 1 2 3 b 4 5 6 for num in a b or for num in a b do echo num done Outputs 1 2 3 4 5 6 我知道你可以先将它们组合起来 然后循环它们 但是
  • 优化截击

    我在android中使用Volley库 我在浏览器中运行相同的url 它在不到一秒的时间内返回 我想知道 如何优化Volley 不清楚 Cache Queue Take 代表什么以及为什么它是 3 6 秒 或者为什么添加缓存队列获取和网络完
  • 使用 iTExtsharp 将表格添加到现有 PDF 中

    我有一个 PDF 其中有一个表格是动态的 我想在现有 PDF 中动态地将下面的另一个表格添加到该表格中 有什么方法可以在现有 PDF 中的特定位置添加表格 现有表格 不在文档末尾 已完成 然后我想添加我的表格 我该如何添加 请给我推荐一些好
  • Nginx WordPress

    我目前正在尝试让我的 Nginx Mysql Wordpress 在 Fedora 18 x64 上工作 做了以下手册http www howtoing com install wordpress using lamp or lemp on
  • 对城市的区域名称进行地理编码以获取纬度和经度

    我有我所在城市的区域名称列表 我需要相同的纬度和经度 我可以使用任何服务来获取数据吗 我不想使用任何地图 我想进行简单的 api 调用并通过 json 或 xml 获取经纬度 虽然问题已经得到解答 但我想补充一点 谷歌并不是唯一提供地理编码
  • 搜索 django 中表中的所有字段

    如何使用过滤子句在django中搜索表中的所有字段 ex table object filter 表中的任何字段 sumthing Thanks 我同意阿拉斯代尔的观点 但你问题的答案是这样的 from django db models i
  • react-native-google-places-autocomplete 给它一个值,而不仅仅是默认(初始)值

    我有一个工作
  • 在eclipse中播放ogg文件

    所以我试图在我的乒乓球游戏中添加声音 但由于某种原因我似乎无法播放声音 没有错误消息 这意味着路径是正确的 但声音根本不正确玩 以下是我的背景音乐代码 把pong的东西都删掉了 先谢谢了 import java applet Applet
  • Maui-blazor 渐变闪屏

    是否可以设置渐变启动画面 在例子中 https learn microsoft com en us dotnet maui user interface images splashscreen tabs android
  • Misra 2012 不允许在不同指针之间进行转换的基本原理

    我目前正在开发一个项目 该项目要求代码符合 Misra 2012 标准 在整个项目中 我们有很多必需的 Misra 警告 告诉我们无法将指向一种类型的指针转 换为指向另一种类型的指针 事情很简单void memcpy void to con
  • GET/POST 参数数量超出设置。DATA_UPLOAD_MAX_NUMBER_FIELDS

    我收到错误 GET POST 参数的数量超出了设置 DATA UPLOAD MAX NUMBER FIELDS 错误表明 TooManyFieldsSent 在 api upload 我在我的views py def upload requ
  • 如何使用 vaadin 网格导出到 csv/excel?

    在 Vaadin 14 中 我正在创建网格 并希望用户有一种稳定 简单的方法将网格内容导出到 csv 或最好是 Excel 为此 我很惊讶 Vaadin 似乎没有提供此功能 因此必须使用第 3 方开发人员插件 例如https vaadin
  • 三个点应该怎么写?

    简单的问题 我想设置一个 TextView 其中我想要三个点 省略号 喜欢 Read more 到字符串中 这三个点应该怎么写呢 在字符串文字中写入 u2026 看http www fileformat info info unicode
  • Google Maps API v3 - 为什么没有事件上下文?

    第一次使用 Google Maps API v3 我得到了一张带有一堆标记的地图 我想做到这一点 以便当您单击其中一个时 将显示一个特定的信息窗口 特定于您单击的标记 我真的很惊讶点击事件没有告诉您被点击的实际标记 我知道有一个解决方案使用
  • 使用批量/更新方法将“标签”应用于数百万个文档

    我们的 ElasticSearch 实例中有大约 55 000 000 个文档 我们有一个带有 user ids 的 CSV 文件 最大的 CSV 有 9M 个条目 我们的文档以 user id 作为键 所以这很方便 我发布这个问题是因为我
  • 基于欧几里德距离的 3D 连接点标记

    目前 我正在开发一个项目 该项目尝试通过将连通性指定为最小欧几里德距离来对数据集中的 3d 点进行分组 我现在的算法只是简单的洪水填充的 3D 改编 size t PointSegmenter growRegion size t seed
  • C# 特定进程的参数,使用 url 打开浏览器

    我正在编写一个应用程序 该应用程序应该通过单击按钮来打开某个进程 但是 用户可以添加新按钮 我使用以下代码来执行单击按钮时启动进程的操作 private void StartProcess string path ProcessStartI
  • 查找两首或多首歌曲交集的算法

    假设我们有一堆收音机 每个收音机都一遍又一遍地循环播放同一首歌 是否可以同步所有收音机中的所有歌曲 我们能找到一个时间从头听到所有歌曲吗 为了简单起见 我们会说我们只有两个收音机 我有以下公式 c 和 z 代表歌曲的长度 以秒为单位 a 和