文档章节

Project Euler Problem 75

BlackJoker
 BlackJoker
发布于 2015/10/13 13:24
字数 522
阅读 8
收藏 0
点赞 0
评论 0
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)派生的勾股数。

© 著作权归作者所有

共有 人打赏支持
BlackJoker
粉丝 1
博文 17
码字总数 9270
作品 0
深圳
高级程序员
Bad Coder(2011-01-04)

再优美的语言,如果你真的把它当作草稿来用,也还真是可以写出一些自惭形秽的-_-! 依然以奋斗在 Project Euler 界的我为例(这次的热情貌似久了一点)。 Problem 27 我们拿到的只是坐标,并非...

Pope怯懦懦地
2017/12/09
0
0
Euler Project Problem 6

The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025......

长平狐
2012/10/16
51
0
纸笔的力量(2011-01-01)

对 Mathematica 着迷了,虽然我知道这热情不会持续多久。还是喜欢在解决问题中学习,这次是 Project Euler 的第 38 问。 提问:一个数依次×1,×2,……把所得连接成一个 9 位数,如果这个 ...

Pope怯懦懦地
2017/12/09
0
0
CodeMade:寻找开源物联网项目的优秀网站

大多数刚开始学习编程的用户在刚开始学习的前几个月都会遭遇相同的问题--根据书籍或网站来学习编程的基础知识,在成功打印出“HelloWorld”之后在自己编程之后总会遇到各种问题。遇到这些问题...

达尔文
2016/12/06
2.8K
5
微分方程数值分析基础:Euler法

微分方程数值分析基础:Euler法 Euler法作为数值分析的一种方法,主要解决微分方程在求出精确公式没有必要,求不到或者非常困难情况下有用。为数值分析提供了一种渐变的分析手段,但是也要看...

zhangphil
01/05
0
0
Using Visual Studio 2005 with .NET Framework 3.5

If you want to try out the new features available in .NET 3.5, then the first thing you should do is download the 3.5 Framework from Microsoft using the link below: Download .NE......

wwww_wu
2013/05/15
0
0
从 Project Euler 中我们学到了什么?(2010-12-26)

最近做 Project Euler 的第41问时学到了不少东西,数论、Mathematica⋯⋯ 题目是这样的: 如果一个 n 位数的各位数字中恰好 1 到 n 各出现了一次,那么就说这个数 pandigital 。比如,2143 ...

Pope怯懦懦地
2017/12/11
0
0
18 个锻炼编程技能的网站

本文由伯乐在线 -Reset 翻译。未经许可,禁止转载! 英文出处:codecondo。欢迎加入翻译组。 编程几乎已经成为了人类所知每个行业的必要组成部分,它帮助组织和维护大型系统的方式是无可比拟...

伯乐在线
2016/08/03
0
0
51nod 1024 矩阵中不重复的元素

1024 矩阵中不重复的元素 Project Euler 难度:2级算法题 收藏 关注 一个m*n的矩阵。 该矩阵的第一列是a^b,(a+1)^b,.....(a + n - 1)^b 第二列是a^(b+1),(a+1)^(b+1),.....(a + n - 1)^(b+1...

Fire_to_cheat_
02/23
0
0
OpenFOAM 2.1.0 发布,面向对象的CFD类库

OpenFOAM是一个完全由C++编写的面向对象的CFD类库,采用类似于我们日常习惯的方法在软件中描述偏微分方程的有限体积离散化,支持多面体网格(比如CD-adapco公司推出的CCM+生成的多面体网格)...

红薯
2012/03/30
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Django时区详解

引言 相信使用Django的各位开发者在存储时间的时候经常会遇到这样子的错误: RuntimeWarning: DateTimeField received a naive datetime while time zone support is active. 这个错误到底...

bobway
10分钟前
0
0
改造工程步骤

背景: 对于存在有问题的项目(包括 代码不规范 数据库表命名不规范 )需要改造 步骤: 1 新建工程 : 将需要改造的项目拷贝一份 修改项目名称 2 将相应的表结构拷贝到新的数据库中 修改不直...

猿神出窍
17分钟前
0
0
node报错{ xxx, xxx}

nodemon 启动语法报错 重新打开项目node代码报错,在node4.4.2下报错,把node版本切换到6就没有问题

x29
19分钟前
0
0
防火墙未来的发展趋势在哪里?

防火墙(Firewall),也称防护墙,是由Check Point创立者Gil Shwed于1993年发明并引入国际互联网。当下互联网时代,无论是大小企业,大部分都会部署有防火墙的设备,但这些防火墙往往并不是都利...

六库科技
20分钟前
0
0
Elasitcsearch High Level Rest Client学习笔记(二) 基础API

1、index API IndexRequest request = new IndexRequest( "posts", //index "doc",  //type 类型,我对类型的理解有点类似于数据库中的表 index类似于数据库中的datab...

木子SMZ
22分钟前
0
0
[DUBBO] Ignore empty notify urls for subscribe url

学习dubbo,按照官方文档编写了 provider consumer 使用的注册中心是Multicast 多播(组播),报了上面的警告,客户端服务端都有类似的警告,并且服务消费者不能发现服务。网上找了各种解决办...

颖辉小居
35分钟前
0
0
unorder_map 随机元素

对于hash的结构来说 思路1:直接随机内部list 即可,但是数据量大的话 iter 要定位起来是个很麻烦的事情 思路2:先随机到一个可用bucket 然后再里面随机一个元素即可

梦想游戏人
40分钟前
0
0
g++编译过程

gcc & g++现在是gnu中最主要和最流行的c & c++编译器 。 g++是将默认语言设为c++,链接时自动使用C++标准库而不用 c标准库 C++标准库:http://www.runoob.com/cplusplus/cpp-standard-librar...

SibylY
42分钟前
0
0
docker更换镜像源

国内下载docker镜像大部分都比较慢,下面给大家介绍2个镜像源。 一、阿里云的docker镜像源 注册一个阿里云用户,访问 https://cr.console.aliyun.com/#/accelerator 获取专属Docker加速器地址...

xiaomin0322
43分钟前
0
0
7.07-获取多少天之前(之后)的日期

public String getDate(Date date,int days){ Calendar calendar=Calendar.getInstance(); calendar.setTime(date); calendar.add(Calendar.DATE,days); ......

静以修身2025
45分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部