`
OpenMind
  • 浏览: 179588 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

Project Euler Problem 75

阅读更多
It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L  1,500,000 can exactly one integer sided right angle triangle be formed?

Note: This problem has been changed recently, please check that you are using the right parameters.

下面是java解题方法:
public static void main(String[] args) {
		Map<Integer, ABC> dict = new HashMap<Integer, ABC>();
		int L = 1500000;
		int M =  (int)Math.sqrt(L / 2);
		for (int m = 1; m <= M; m++) {
			for (int n = 1; n < m; n++) {
				int a = m * m - n * n;
				int b = 2 * m * n;
				int c = m * m + n * n;
				int l = a + b + c;
				int k = L / l;
				for (int i = 1; i <= k; i++) {
					int[] abc = { i * a, i * b, i * c };
					Arrays.sort(abc);
					check(i, l, abc, dict);
				}
			}
		}
		int count = 0;
		for (ABC abc : dict.values()) {
			count += abc.got;
		}
		System.out.println(count);
	}

	private static void check(int i, int l, int[] abc, Map<Integer, ABC> dict) {
		int ll = i * l;
		ABC tmp = dict.get(ll);
		if (tmp != null) {
			if (tmp.got == 1) {
				int[] tmp1 = tmp.abc;
				for (int x = 0; x < 3; x++) {
					if (tmp1[x] != abc[x]) {
						tmp.got = 0;
						break;
					}
				}
			}
		} else {
			dict.put(ll, new ABC(abc));
		}
	}

	static class ABC {
		public ABC(int[] abc) {
			this.abc = abc;
		}

		int got = 1;
		int[] abc;

	}

这个解法的时间在秒级,解法利用了下面勾股数的性质:
1,通过a = m^2 − n^2, b = 2mn, c = m^2 + n^2 (1)可以生成所有的素勾股数和一部分派生勾股数(a,b,c),其在(m>n,m,n为正整数);
2,勾股数分为素勾股数和派生勾股数,而且所有派生勾股数都是由素勾股数派生而来的;
3,根据1,2,利用式(1),遍历m,n并加上派生规则可以生成所有勾股数。

注:正整数a,b,c满足a^2+b^2=c^2<=>(a,b,c)是勾股数,如果(a,b,c)=1(即a,b,c互素),则(a,b,c)称为素勾股数,对于整数k,(ka,kb,kc)是由(a,b,c)派生的勾股数。
分享到:
评论

相关推荐

    project euler problem 5

    题目:Project Euler问题5——寻找最小公倍数 在Project Euler的问题集中,问题5要求我们找到能被1至20所有数字整除的最小正整数。这个问题实际上是在寻找这组数字的最小公倍数(LCM)。对于较小的参数值,如本例中...

    project_euler:Project Euler 问题的解决方案 https

    project_euler Project Euler 问题的解决方案 ###Problem 1 - 3 和 5 的倍数### 如果我们列出所有 10 以下是 3 或 5 的倍数的自然数,我们得到 3、5、6 和 9。这些倍数的和是 23。求1000 以下所有 3 或 5 的倍数之...

    projecteuler:通过https解决Euler项目问题

    项目欧拉(Project Euler)是一个在线平台,提供了一系列数学和计算机科学问题,旨在鼓励学习者在解决问题的过程中提高编程技能和理解复杂算法。本项目聚焦于使用JavaScript语言来解答Project Euler中的问题,这是一...

    project-euler-problem-downloader:将所有 projecteuler.net 问题下载到您的本地存储

    而"project-euler-problem-downloader"是一个实用工具,它允许用户将Project Euler的所有问题下载到本地,以便离线浏览和解决。这个工具特别适合那些经常在没有网络连接或者希望通过本地编辑器解决Project Euler问题...

    ProjectEuler:我放置 ProjectEuler 代码的地方

    "ProjectEuler:我放置 ProjectEuler 代码的地方"这个标题揭示了一个专注于解决Project Euler问题的项目。Project Euler是一个在线平台,提供了一系列富有挑战性的数学和计算机科学问题,旨在提高编程技能并推动对...

    euler project.r.zip_R Euler project_project

    这个压缩包`euler project.r.zip_R Euler project_project`包含了R语言实现的Euler项目前14题的答案。让我们深入探讨这些题目所涵盖的知识点,并了解如何利用R语言解决这些问题。 1. **Problem 1: 多少个数小于1000...

    ProjectEuler:我针对ProjectEuler问题的解决方案

    ProjectEuler是一个在线平台,它提供了许多数学和计算机科学的挑战问题,旨在通过解决这些问题来提升编程技巧和算法理解。这些问题通常涉及到数论、组合数学、几何、概率以及一些基本的计算理论。在这个项目中,你...

    js.projecteuler

    在js.projecteuler-master项目中,我们可以看到三个具体的Problem实例。这些实例可能涵盖了数字理论、组合数学、序列生成等主题。通过分析这些例子,我们可以学习如何用JavaScript实现高效的解题策略,例如: 1. ...

    Euler:Project Euler Java 解决方案

    【标题】"Euler: Project Euler Java 解决方案" 是一个专门为解决 Project Euler 提供的 Java 实现项目。Project Euler 是一个在线平台,提供了一系列具有挑战性的数学和计算机科学问题,旨在鼓励学习者通过编程来...

    ProjectEuler:Java项目Euler

    【标题】"ProjectEuler:Java项目Euler" 指的是一个使用Java语言解决Project Euler问题的开源项目。Project Euler是一个在线平台,提供了一系列具有挑战性的数学和计算机科学问题,旨在提高编程技能和数学洞察力。这...

    project_euler_python:Python中解决Project Euler的问题

    以Python语言来解Project Euler问题。 Project Euler: 针对数学和程式爱好者,设计了一系列的问题,至今已有五百多道,供大家挑战,每一题都要求应在1分钟内计算出答案。我使用硬体Raspberry Pi 2与软体Raspbian,...

    Project-Euler-Problem-8

    【标题】"Project-Euler-Problem-8"是著名的编程挑战网站Project Euler中的一个问题,它旨在测试编程者解决数学和算法问题的能力。该问题通常涉及数值计算、数学优化或者组合数学,鼓励程序员用创新的方式解决问题。...

    project_euler:包含 Project Euler 问题的解决方案

    Project Euler 是一个在线平台,提供了一系列数学和计算机科学的挑战问题,旨在提高解题技巧,同时也涉及编程技术。这些问题通常需要巧妙的算法和数学洞察力来解决。在本项目中,我们关注的是使用 JavaScript 语言...

    projecteuler:用于投影仪的haskell解决方案

    在本项目中,“projecteuler:用于投影仪的haskell解决方案”显然指的是使用Haskell编程语言来解决Project Euler的问题。Project Euler是一个著名的在线系列数学与计算机科学问题,旨在提高编程技巧和数学理解。...

    projectEuler:https

    在 `projectEuler-master` 这个压缩包中,你可能会找到不同问题的解决方案,每个问题可能对应一个或多个 Java 文件。文件命名可能反映了问题的编号或者问题的主要概念,例如 "Problem001_MultiplesOf3And5.java"。...

    ProjectEuler:5个ProjectEuler问题及其解决方案

    Project Euler是一个著名的在线平台,它提供了许多数学和计算机科学的挑战问题,旨在通过解决这些问题来提升编程技巧和算法理解。本项目聚焦于五个Project Euler问题,每个问题都提供了JavaScript实现的解决方案。...

    ProjectEuler:一系列具有挑战性的数学计算机编程问题

    【Problem-solving】在ProjectEuler中,解决问题的关键在于理解问题背后的数学模型,然后设计出高效的算法来求解。这通常需要将复杂问题分解成更小的部分,采用递归、动态规划、贪心策略或者回溯等算法设计技巧。...

    projectEuler

    在"projectEuler-master"这个压缩包中,我们可以期待找到一系列的JavaScript和Ruby源代码文件,每个文件对应Project Euler的一个问题。这些文件可能是按问题编号命名的,例如 "problem001.js" 或 "problem001.rb"。...

    Project-Euler-Problem-1:实践

    【标题】"Project-Euler-Problem-1:实践" 是一个关于解决Project Euler中的第一个问题的编程挑战。Project Euler是一个著名的在线系列数学与计算机科学问题,旨在鼓励学习者通过编程来解决问题并提升技能。问题1涉及...

    euler:一些 Project Euler 解决方案

    在这个“euler-master”文件夹中,每个子文件可能对应一个具体的问题,例如`problem001.js`、`problem002.js`等。文件内部可能包含了解决问题的JavaScript代码,以及可能的注释,解释了算法的工作原理。 通过阅读和...

Global site tag (gtag.js) - Google Analytics