Project Euler Problem 276, 268, 347

〇〇 · 发表于 2012-1-14 17:03

本帖最后由〇〇于 2012-1-14 19:41 编辑

〇〇发表于 2012-1-14 16:59
从前几个数来看，a必须是偶数，但不知道怎么证明
create or replace procedure q224b(n number default ...

--其实b也必须是偶数

create or replace procedure q224c(n number default 1000)
as
TYPE t_row IS TABLE OF  BINARY_INTEGER;
T T_row:=t_row();
s1 number;
s2 number;
s3 number;
cnt number:=0;
begin
t.EXTEND(n);
for i in 1..n loop
t(i):=i*i;
end loop;
for l1 in 1..n/2.828 loop
s1:=t(l1*2); --l1*l1;
for l2 in l1..n/2 loop
s2:=t(l2*2); --l2*l2;
s3:=floor(sqrt(s1+s2))+1;
if s3>n then exit; end if;
if s1+s2=s3*s3-1 then
cnt:=cnt+1;
end if;
end loop;
end loop;

dbms_output.put_line(cnt);
end;
/
SQL> exec q224c
126

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.20
SQL> exec q224c(2000)
257

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.70
请数学大师帮我证明了：

wayne

管理员

发短消息

加为好友

wayne 当前在线 威望342 星金币3554 枚贡献3579 分经验4006 点鲜花297 朵魅力77 点下载67 次阅读权限255 在线时间1466 小时注册时间2009-2-12 最后登录2012-1-14

管理员
帖子3278 精华5 积分14542 鲜花297 朵主题141 帖

2#
发表于半小时前 | 只看该作者踩窝窝送礼物问候Ta

1# 〇〇
如果a,b一奇一偶，那么a^2+b^2被4除余1，于是c必须为偶数，但 c^2-1被4整除余3，矛盾，故不存在。
如果a,b均为奇数，那么a^2+b^2被8除余2，于是c必须为奇数，但 c^2-1被8整除，矛盾，故不存在。

故a,b均为偶数

〇〇 · 发表于 2012-1-14 19:36

本帖最后由〇〇于 2012-1-14 19:56 编辑

〇〇发表于 2012-1-14 17:03
--其实b也必须是偶数

create or replace procedure q224c(n number default 1000)

用整数和平方根相等判断代替乘法，快了一点
create or replace procedure q224d(n number default 1000)
as
TYPE t_row IS TABLE OF  BINARY_INTEGER;
T T_row:=t_row();
s1 number;
s2 number;
s3 number;
cnt number:=0;
begin
t.EXTEND(n);
for i in 1..n loop
t(i):=i*i;
end loop;
for l1 in 1..n/2.828 loop
s1:=t(l1*2); --l1*l1;
for l2 in l1..n/2 loop
s2:=t(l2*2); --l2*l2;
s3:=sqrt(s1+s2+1);
if s3>n then exit; end if;
if s3=floor(s3) then
cnt:=cnt+1;
end if;
end loop;
end loop;

dbms_output.put_line(cnt);
end;
/

SQL> exec q224d
126

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.20
SQL> exec q224d(2000)
257

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.60
SQL> exec q224d(4000)
502

PL/SQL 过程已成功完成。

已用时间:  00: 00: 02.40

但奇怪的事：加上数学分析，反而更慢了
因为当a固定时，对一个b，只能有一个c，那么下一个待尝试的第3边至少是c+1。而(c+1)^2=c^2+2c+1
所以下一个b^2和当前b^2的差至少2c+1，设下一个b=当前b+d，
(b+d)^2=b^2+2bd+d^2,
d^2+2bd>=2c+1解不等式d>=sqrt(b^2+2c+1)-b
跨度小于此数的b都是无效的尝试。所以：
当求出一个c以后，下一个b=ceil(sqrt(b^2+2c+1)

create or replace procedure q224e(n number default 1000)
as
TYPE t_row IS TABLE OF  BINARY_INTEGER;
T T_row:=t_row();
s1 number;
s2 number;
s3 number;
cnt number:=0;
l2 number;
begin
t.EXTEND(n);
for i in 1..n loop
t(i):=i*i;
end loop;
for l1 in 1..n/2.828 loop
s1:=t(l1*2); --l1*l1;
--for l2 in l1..n/2 loop
l2:=l1;
while l2<=n/2 loop
s2:=t(l2*2); --l2*l2;
s3:=sqrt(s1+s2+1);
if s3>n then exit; end if;
if s3=floor(s3) then
cnt:=cnt+1;
l2:=ceil(sqrt(s2+2*s3+1)/2);
else
l2:=l2+1;
end if;
end loop;
end loop;

dbms_output.put_line(cnt);
end;
/
SQL> exec q224e
126

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.20
SQL> exec q224e(2000)
257

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.80
SQL> exec q224e(4000)
502

PL/SQL 过程已成功完成。

已用时间:  00: 00: 03.00
SQL> exec q224e(8000)
996

PL/SQL 过程已成功完成。

已用时间:  00: 00: 11.70
SQL> exec q224d(8000)
996

PL/SQL 过程已成功完成。

已用时间:  00: 00: 09.40

好像是while loop比for loop慢，去掉了l2的赋值，还是差不多的时间

〇〇 · 发表于 2012-1-14 20:57

根据51楼的结论，c必须是奇数，那么下一个c=c+2,平方的间隔是4c+4,但速度依旧很慢
create or replace procedure q224e(n number default 1000)
as
TYPE t_row IS TABLE OF  BINARY_INTEGER;
T T_row:=t_row();
s1 number;
s2 number;
s3 number;
cnt number:=0;
l2 number;
begin
t.EXTEND(n);
for i in 1..n loop
t(i):=i*i;
end loop;
for l1 in 1..n/2.828 loop
s1:=t(l1*2); --l1*l1;
--for l2 in l1..n/2 loop
l2:=l1;
while l2<=n/2 loop
s2:=t(l2*2); --l2*l2;
s3:=sqrt(s1+s2+1);
if s3>n then exit; end if;
if s3=floor(s3) then
cnt:=cnt+1;
l2:=ceil(sqrt(s2+4*s3+4)/2);
else
l2:=l2+1;
end if;
end loop;
end loop;

dbms_output.put_line(cnt);
end;
/

SQL> exec q224e(4000)
502

PL/SQL 过程已成功完成。

已用时间:  00: 00: 03.00
SQL> exec q224e(8000)
996

PL/SQL 过程已成功完成。

已用时间:  00: 00: 11.07

〇〇 · 发表于 2012-1-15 07:01

〇〇发表于 2012-1-14 20:57
根据51楼的结论，c必须是奇数，那么下一个c=c+2,平方的间隔是4c+4,但速度依旧很慢
create or replace proc ...

从a入手，随着b的增加，(b+1)^2-b^2=2b+1越来越大，如果a^2+1不足2b+1,那么后面的b都无效
因此b的上限是a^2/2

create or replace procedure q224f(n number default 1000)
as
TYPE t_row IS TABLE OF  BINARY_INTEGER;
T T_row:=t_row();
s1 number;
s2 number;
s3 number;
cnt number:=0;
l2 number;
u number;
begin
t.EXTEND(n);
for i in 1..n loop
t(i):=i*i;
end loop;
for l1 in 1..n/2.828 loop
s1:=t(l1*2); --l1*l1;
--for l2 in l1..n/2 loop
l2:=l1;
u:=case when s1/4<n/2 then s1/4 else n/2 end;
while l2<=u loop
s2:=t(l2*2); --l2*l2;
s3:=sqrt(s1+s2+1);
if s3>n then exit; end if;
if s3=floor(s3) then
cnt:=cnt+1;
l2:=ceil(sqrt(s2+4*s3+4)/2);
else
l2:=l2+1;
end if;
end loop;
end loop;

dbms_output.put_line(cnt);
end;
/
SQL> exec q224f(4000)
502

PL/SQL 过程已成功完成。

已用时间:  00: 00: 02.05
SQL> exec q224f(8000)
996

PL/SQL 过程已成功完成。

已用时间:  00: 00: 09.08
SQL> exec q224d(8000)
996

PL/SQL 过程已成功完成。

已用时间:  00: 00: 09.02

〇〇 · 发表于 2012-1-15 07:14

Problem 367
14 January 2012

Bozo sort, not to be confused with the slightly less efficient bogo sort, consists out of checking if the input sequence is sorted and if not swapping randomly two elements. This is repeated until eventually the sequence is sorted.

If we consider all permutations of the first 4 natural numbers as input the expectation value of the number of swaps, averaged over all 4! input sequences is 24.75.
The already sorted sequence takes 0 steps.

In this problem we consider the following variant on bozo sort.
If the sequence is not in order we pick three elements at random and shuffle these three elements randomly.
All 3!=6 permutations of those three elements are equally likely.
The already sorted sequence will take 0 steps.
If we consider all permutations of the first 4 natural numbers as input the expectation value of the number of shuffles, averaged over all 4! input sequences is 27.5.
Consider as input sequences the permutations of the first 11 natural numbers.
Averaged over all 11! input sequences, what is the expected number of shuffles this sorting algorithm will perform?

Give your answer rounded to the nearest integer.

〇〇 · 发表于 2012-1-15 18:59

p 224论坛上的解释
a = 2u, b = 2v, and c = 2w + 1,
u^2 + v^2 = w(w+1)

both w and (w+1) can be written as sum of 2 squares

ie. if w can be written as (m^2+n^2) and (w+1) as (p^2+q^2),
then w(w+1) can be written as (mp+nq)^2+(mq-np)^2 or (mp-nq)^2 + (mq+np)^2

0 <= m, n, p, q and 1 <= w