nyfor 复活节比短代码解题说明

cow977

原帖由 nyfor 于 2011-4-29 22:10 发表
s := (11 * s + 4 - trunc((7 * s + 1) / 19)) mod 29;
x := 25 - s - (y - 2344 + trunc(y / 4) - s) mod 7;
s 值最大的可能取值为28，而我们已知 y>=1900
故而 (y - 2344 + trunc(y / 4) -s ) 这部分可以推知，必定 〉0，因此 mod 7 的结果也必定 >=0
故而，我们可以将 （y -2344 + trunc(c / y) -s ）加上7的正整数倍后 mod 7 结果将不变。
由此我们加上 7*334 = 2338 继而变成 (y - 6 + trunc(c / y) - s). 最终就是：
s := (11 * s + 4 - trunc((7 * s + 1) / 19)) mod 29;
x := 25 - s - (y - 6 + trunc(y / 4) - s) mod 7;

这样又可以节省 3 个字节，减少为 1192 字节

再次重申，这种推理变换应该不属于出题者禁止的中间结果吧 ？

这才是精髓所在。

算法的恒等变换。

lastwinner

原帖由 nyfor 于 11-4-29 22:10 发表
s := (11 * s + 4 - trunc((7 * s + 1) / 19)) mod 29;
x := 25 - s - (y - 2344 + trunc(y / 4) - s) mod 7;
s 值最大的可能取值为28，而我们已知 y>=1900
故而 (y - 2344 + trunc(y / 4) -s ) 这部分可以推知，必定 〉0，因此 mod 7 的结果也必定 >=0
故而，我们可以将 （y -2344 + trunc(c / y) -s ）加上7的正整数倍后 mod 7 结果将不变。
由此我们加上 7*334 = 2338 继而变成 (y - 6 + trunc(c / y) - s). 最终就是：
s := (11 * s + 4 - trunc((7 * s + 1) / 19)) mod 29;
x := 25 - s - (y - 6 + trunc(y / 4) - s) mod 7;

这样又可以节省 3 个字节，减少为 1192 字节

再次重申，这种推理变换应该不属于出题者禁止的中间结果吧 ？

算法是可以变换的，毕竟题目给出的仅仅是一种算法，不是唯一的算法
即便是原算法，对原算法的等价变换，通过编程是很难做到的，人工变换并无不妥

rollingpig

强。

jboracle1981

原帖由 rollingpig 于 2011-5-2 10:48 发表
强。

大师可否提供下，你那压缩文件的解压密码。
想学习下！

rollingpig

我的密码是rpg

〇〇

原帖由 rollingpig 于 2011-5-3 10:43 发表
我的密码是rpg

哦

rollingpig

showLeapEasterDay是最容易出问题的。
Nyfor似乎在这里垮了，如果4/24是复活节而4/25不是复活节，代码不能输出4/25
根据二楼的代码
把2099替换成2013

  exec easter.showAllEasterDay

YEAR DAY
2011 04-24
2012 04-08
2013 03-31


exec easter.showLeapEasterDay
ABSENT_START ABSENT_END
03-22   03-30   
04-01   04-07   
04-09   04-23

nyfor

原帖由 rollingpig 于 2011-5-3 10:47 发表
showLeapEasterDay是最容易出问题的。
Nyfor似乎在这里垮了，如果4/24是复活节而4/25不是复活节，代码不能输出4/25

〇〇已经发现这个问题了,只需要把里边的 s<x 修改成 s=s 即可. 疏忽了.

rollingpig

参考你的做法后，把你的精髓和我的做法合作，最后出来 1159 byte。

http://www.itpub.net/thread-1425942-1-1.html

rollingpig

呵呵
这个简化是标准简化步骤。
mod 内不应该出现比除数还大的常数。

原帖由 nyfor 于 2011-4-29 22:10 发表
s := (11 * s + 4 - trunc((7 * s + 1) / 19)) mod 29;
x := 25 - s - (y - 2344 + trunc(y / 4) - s) mod 7;
s 值最大的可能取值为28，而我们已知 y>=1900
故而 (y - 2344 + trunc(y / 4) -s ) 这部分可以推知，必定 〉0，因此 mod 7 的结果也必定 >=0
故而，我们可以将 （y -2344 + trunc(c / y) -s ）加上7的正整数倍后 mod 7 结果将不变。
由此我们加上 7*334 = 2338 继而变成 (y - 6 + trunc(c / y) - s). 最终就是：
s := (11 * s + 4 - trunc((7 * s + 1) / 19)) mod 29;
x := 25 - s - (y - 6 + trunc(y / 4) - s) mod 7;

这样又可以节省 3 个字节，减少为 1192 字节

再次重申，这种推理变换应该不属于出题者禁止的中间结果吧 ？