草庐IT

java - 确定给定数字 N 是否可以成为具有所有 3 个整数边的直角三角形的斜边的算法

coder 2024-02-11 原文

假设给定一个直角三角形的斜边，那么如何确定给定的斜边是否可能存在两条整数较小的边。

例如，给定斜边为 5。然后您必须确定给定直角三角形的整数边是否更小。答案将是是，因为我们可以有更小的边为 3和 4，因此得到一个 3-4-5 直角三角形。

类似地，对于像 7 这样的斜边，我们不能有这样的直角三角形。

换句话说，我们要找出一个给定的数 N 是否可以作为 3 边均为整数的直角三角形的斜边。

我浏览了关于 Pythagorean triples 的整篇文章但仍然没有成功。我很困惑要检查什么条件。请帮忙。

最佳答案

你有一个原始毕达哥拉斯三元组:

(p^2 - q^2)^2 + (2 * p * q))^2 = (p^2 + q^2)^2 = N^2

假设 p >= q。那么我们有

N >= 2 * q^2 or q <= sqrt(N / 2)

假设 N = 13，那么我们需要 q <= sqrt(13/2)="">

q = 2 => p^2 = 13 - 4 = 9，这是一个正方形。

因此，您可以从 1..sqrt(N/2) 得到一个数字“i”的小循环，并检查 N - (i^2) 是否为正方形。

对于 原始 毕达哥拉斯元组的成员，这将是 O(sqrt(N))。

C/C++ 示例代码:

#include <stdio.h>
#include <math.h>

void CheckTuple(int n)
{
    int k = sqrt(n/2.0);

    for (int i = 1; i <= k; i++) {
        int tmp = sqrt((double)(n - i * i));
        if ((tmp * tmp) == (n - i * i)) {
            printf("%d^2 + %d^2 = %d^2\n", (tmp*tmp - i*i), 2 * tmp * i, n);
            return;
        }
    }
    printf("%d is not part of a tuple\n", n);
    return;
}


int main(int argc, char *argv[])
{

    CheckTuple(5);
    CheckTuple(6);
    CheckTuple(13);
    CheckTuple(10);
    CheckTuple(25);

    return 0;
}

输出:

3^2 + 4^2 = 5^2
6 is not part of a tuple
5^2 + 12^2 = 13^2
8^2 + 6^2 = 10^2
7^2 + 24^2 = 25^2

关于java - 确定给定数字 N 是否可以成为具有所有 3 个整数边的直角三角形的斜边的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19332978/

给定javasectioncodec++calgorithmgeometry

有关java - 确定给定数字 N 是否可以成为具有所有 3 个整数边的直角三角形的斜边的算法的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  3. ruby - 具有身份验证的私有(private) Ruby Gem 服务器 - 2

    我想安装一个带有一些身份验证的私有(private)Rubygem服务器。我希望能够使用公共(public)Ubuntu服务器托管内部gem。我读到了http://docs.rubygems.org/read/chapter/18.但是那个没有身份验证-如我所见。然后我读到了https://github.com/cwninja/geminabox.但是当我使用基本身份验证(他们在他们的Wiki中有)时，它会提示从我的服务器获取源。所以。如何制作带有身份验证的私有(private)Rubygem服务器？这是不可能的吗？谢谢。编辑:Geminabox问题。我尝试“捆绑”以安装新的gem..

  4. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  5. ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

  6. ruby - 我可以使用 Ruby 从 CSV 中删除列吗？ - 2

    查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html

  7. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  8. ruby - 我可以使用 aws-sdk-ruby 在 AWS S3 上使用事务性文件删除/上传吗？ - 2

    我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的

  9. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  10. ruby-on-rails - 跳过状态机方法的所有验证 - 2

    当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested

随机推荐