草庐IT

python - 找到三个整数，使它们的余弦值之和成为最大值

coder 2023-08-13 原文

有三个整数x、y和z(每个都>=1)和一个给定的上限整数 n <>n = x + y + z 和 output = cos(x) + cos(y) + cos(z)。

练习是最大化输出。

我为此写了一个简单的脚本，但是时间复杂度是O(n^3)。有什么办法可以简化这个吗？

from math import cos

n = 50
x = 1
y = 1
z = 1

total = cos(x) + cos(y) + cos(z)

for x in xrange(n):
    for y in xrange(n):
        for z in xrange(n):
            if x + y + z == n:
                temp = cos(x) + cos(y) + cos(z)
                if temp > total: total = temp

print round(total, 9)

最佳答案

正如 Jean-François Fabre 在评论中指出的那样，您可以应用很多技巧来提高性能，但首先

  • 注意到 a 和 b 的值决定了 c 的值，
  • 注意到三个变量中至少有一个 WLOG a 小于或等于 N/3，
  • 使用 b 和 c 中剩余的对称性将 b 绑定(bind)在 a 和 (N - a)//2 + 1
  • 预先计算 cos 的所有相关值，并尽量避免快速连续查找相同的值，
  • 当 cos(a) 的给定值永远不会导致新的最大值时，修剪外部循环以提前停止，
  • 使用Numba JIT 编译代码并免费获得一些性能(对于 N = 500 大约是 400 倍)，

然后对于 N = 1000000，否则暴力解决方案会相对快速地终止:

import numpy as np
from numba import jit

@jit
def maximize(N):
    cos = np.cos(np.arange(N))
    m = -3
    for a in range(1, N//3 + 1):
        cosa = cos[a]
        if m - 2 > cosa:
            continue
        for b in range(a, (N - a)//2 + 1):
            c = N - a - b
            res = cosa + cos[b] + cos[c]
            if res > m:
                m = res
                bestabc = (a, b, c)
    return m, bestabc

maximize(1000000)  # (2.9787165245899025, (159775, 263768, 576457))

值得注意的是，上面利用的对称性仅在人们愿意忽略数值问题导致 float 的加法通常不可交换这一事实时才成立；即 cos(a) + cos(b) 不必与 cos(b) + cos(a) 相同。不过，您很可能不会为此担心。

关于python - 找到三个整数，使它们的余弦值之和成为最大值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53569487/

之和pythoncodecossectionoptimizationnumberscombinationsmathematical-optimization

有关python - 找到三个整数，使它们的余弦值之和成为最大值的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  3. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

  4. ruby-on-rails - capybara ::ElementNotFound:无法找到 xpath "/html" - 2

    我正在学习http://ruby.railstutorial.org/chapters/static-pages上的RubyonRails教程并遇到以下错误StaticPagesHomepageshouldhavethecontent'SampleApp'Failure/Error:page.shouldhave_content('SampleApp')Capybara::ElementNotFound:Unabletofindxpath"/html"#(eval):2:in`text'#./spec/requests/static_pages_spec.rb:7:in`(root)'

  5. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  6. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  7. python - 如何读取 MIDI 文件、更改其乐器并将其写回？ - 2

    我想解析一个已经存在的.mid文件，改变它的乐器，例如从“acousticgrandpiano”到“violin”，然后将它保存回去或作为另一个.mid文件。根据我在文档中看到的内容，该乐器通过program_change或patch_change指令进行了更改，但我找不到任何在已经存在的MIDI文件中执行此操作的库.他们似乎都只支持从头开始创建的MIDI文件。 最佳答案 MIDIpackage会为您完成此操作，但具体方法取决于midi文件的原始内容。一个MIDI文件由一个或多个音轨组成，每个音轨是十六个channel中任何一个上的

  8. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

  9. ruby-on-rails - 在 heroku 的 .fonts 文件夹中包含自定义字体，似乎无法识别它们 - 2

    Heroku支持人员告诉我，为了在我的Web应用程序中使用自定义字体(未安装在系统中，您可以在bash控制台中使用fc-list查看已安装的字体)我必须部署一个包含所有字体的.fonts文件夹里面的字体。问题是我不知道该怎么做。我的意思是，我不知道文件名是否必须遵循heroku的任何特殊模式，或者我必须在我的代码中做一些事情来考虑这种字体，或者如果我将它包含在文件夹中它是自动的......事实是，我尝试以不同的方式更改字体的文件名，但根本没有使用该字体。为了提供更多详细信息，我们使用字体的过程是将PDF转换为图像，更具体地说，使用rghostgem。并且最终图像根本不使用自定义字体。在

  10. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

随机推荐