ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 复活节最短源代码分析

复活节最短源代码分析

原创 Linux操作系统 作者:regonly1 时间:2011-04-27 10:27:48 0 删除 编辑
题目:
本周日,也就是4月24日,是今年的复活节,复活节(Easter),是纪念耶稣基督复活的节日,西方信基督教的国家都过这个节。
复活节的日期是不固定的在西方教会传统里,春分之后第一次满月之后的第一个星期日即为复活节。东方教会则规定,如果满月恰逢星期日,则复活节再推迟一周。 因此,节期大致在3月22日至4月25日之间。复活节是最古老最有意义的基督教节日之一,庆祝的是基督的复活,世界各地的基督徒每年都要举行庆祝。

节日的算法也不劳大家去找了

QUOTE:
现在有一个简便的算法供大家参考!

年份只限于1900年到2099年
1 设要求的那一年是Y年,从Y减去1900,其差记为N。
2 用19作除数去除N,余数记为A。
3 用4作除数去除N,不管余数,把商记为Q。
4 用19去除7A+1,把商记为B,不管余数。
5 用29去除11A+4-B,余数记为M。
6 用7去除N+Q+31-M,余数记为W。
7 计算25-M-W。

得出答数即可定出复活节的日期。若为正数,月份为4月,如为负数,月份为3月。若为0,则为3 月31日。

现在提出比赛要求:
  • 用最短的代码,求出2011~2099之间的复活节,具体为:

    • Q1:2011~2099之间每一年的复活节的具体日期
    • Q2:2011~2099之间,几月几号出现得最多?3月出现得最多的是几号?4月出现得最多的又是几号?分别出现了多少次?
    • Q3:2011~2099之间的复活节,3月22日至4月25日之间哪些日子没有出现过?
    • Q4:2011~2099之间“愚蛋节”的总次数,即4月1日同时又是复活节的总数量以及都在哪些年份出现。
  • 答案要求用Package给出,package名为easter:

    • package声明为create or replace package easter
    • Q1的声明为procedure showAllEasterDay,无参数,输出为一列表,形式如下所示:
      YEAR     DAY
      2011    04-24
      2012    04-08
      …………
    • Q2的声明为procedure showMaxOccurenceEasterDay,无参数,输出为一行数据,日期后面跟着输出出现的次数,如果是多个日期,则按从小到达,用“/”分隔显示,形式如下所示:
      MAXOCC   MO_CNT        MAXOCC_3   MO3_CNT              MAXOCC_4          MO4_CNT   
      xx-xx                x1               03-xx                 x2            04-xx/04-yy                       x3
    • Q3的声明为procedure showLeapEasterDay,无参数,连续未出现的日期用一行显示,输出为一列表,形式如下所示:
      ABSENT_START      ABSENT_END
      03-22                             03-25
      04-02                             04-02
      04-11                             04-22
      ………………(以上为示例数据,并非真实数据)
    • Q4的声明为procedure showFoolEasterDay,无参数,输出为一列表,形式如下所示(假设出现了n次):
      YEAR        TOTAL
      yyyy1            n
      yyyy2            n
      …………
      yyyyn            n
  • 包名和Q1~Q4的四个过程必须按约定给出,若需要在包中加入其他过程,请 自便,但需要注意,目标是源代码字节数最小哦!空格、TAB、CR、LF都不算字节数,代码中不要包含注释,注释请写在另外的文件中,4月22日提交你的 结果,期间可在本帖随意show你的代码的字节数

##############################################################

本来提交的人不多,到后来每个选手的字节数也越来越少,我的应该是1500字节以内最多的了,不过在野花版主的鼓励下,决定还是写一写。

解题分析:
1、所有类型都以varchar2(99)替代,包括int类型的转换,都是用Oracle内部的转换实现,使得所有类型都只以一个字符表达。

2、打印封装为一个P函数

3、初始化时,做以下事情:
3.1、将所有复活节都以“yyyy  mm-dd”方式存储在数组v中,数组v在package初始化时加载
3.2、获取所有复活节在4月1日的年份,放入数组r中
3.3、将每个日期最大的出现次数保存在数组u中,数组以mm-dd为索引,存放相应出现的次数
3.4、将三月份、四月份以总共出现的次数最高的次数放到变量m/n/q中

4、打印:
4.1、showAllEasterDay:打印v数组。
4.2、showMaxOccurenceEasterDay:从数组u中轮询,将每个日期出现次数为q/m/n的日期分别拼接起来,打印最终的字符串d/e/f即相应的次数q/m/n。
4.3、showLeapEasterDay:这个是要打印没有在指定区间的出现过的日期,如果是连续的则要求只输出开始日期和结束日期。一开始很自然的想到了野花的连续号段处理,但是得用sql来实现。我想了下,预计用sql实现会比较长,所以直接考虑用pl/sql来实现。

----------------------------------------------------------------------
             我的算法(字节长度1442)
----------------------------------------------------------------------
        首先,我们知道,要打印的是一个开始时间和一个结束时间,如果只有一天,则结束时间=开始时间,所以先定义这两个变量。

        然后,得到要求区间所有的日期(也就是3.22-4.25),通过 1 .. date'1-4-25' - date'1-3.22'+1,轮询每个日期。

        再给定一个标识,指定如果当前日期在数组中存在,则标识0,如果不存在,则标识1,然后到下一条记录的时候,首先判断当前日期是否存在于数组中:
        A> 如果不存在,则将结束日期置为当前日期,并判断标识是否为0,如果为0,则将开始日期也置为当前日期。并将标识置为1。
        B> 如果存在,则判断标识是否为1,如果为1,则说明上个日期是出现在数组中的,所以要打印开始和结束日期。然后将标识置为0。

可能逻辑说明有点枯燥,举个例子吧:
比如说,有以下日期列表:
日期   是否存在数组中(1表示不存在,因为实际要打印的是不存在的日期)
3.22   1  --此时3.22不在数组中,所以置开始日期和结束日期为3.22,由于变量标
                  识flag初始化为0,所以此时不打印,然后置flag=1;
3.23   0  --此时3.23在数组中,开始日期和结束日期还是3.22,但是此时flag=1,
                  所以此时打印,并置flag=0;
3.24   0  --此时3.23在数组中,开始日期和结束日期还是3.22,但是此时flag=0,
                  所以此时不打印,并置flag=0;
3.25   1  --此时3.25不在数组中,开始日期和结束日期被置为3.25,并且flag=0,
                  所以此时不打印,并置flag=1;
3.26   1  --此时3.26不在数组中,开始日期仍为3.25,结束日期被置为3.26,此时
                  flag=1,所以此时仍不打印,并置flag=1;
3.27   1  --此时3.27不在数组中,开始日期仍为3.25,结束日期被置为3.27,并且
                  flag=1,所以此时仍不打印,并置flag=1;
3.28   0  --此时3.28在数组中,开始日期为3.25,结束日期为3.27,且flag=1,所
                  以此时打印开始和结束日期,并置flag=0;

        也就是每次满足存在数组中,而且上次存在标识为不存在,则打印变量中的开始和结束日期。

        如果不存在数组中,则轮询第一次首先将开始日期和结束日期置为当前轮询日期,然后接下去日期还不存在于数组中,则将结束日期置为当前日期,开始日期不变。直到轮询到日期存在为止,然后按上个步骤判断是否打印。

        特殊情况:当结束日期直到超过4.25时,还没有出现存在的日期,就直接打印开始和结束日期。

    4.4、showFoolEasterDay:打印r数组即可。

代码:
create or replace package body easter as
    subtype w is varchar2(99);

    type s is table of w index by w;
    u s;
    r s;
    v s;
    t w;
    q w := 0;
    m w := 0;
    n w := 0;
   
    a w;
    b w;
    c w;
    d w;
    e w;
    f w := 1900;

    procedure p(a w)as begin dbms_output.put_line(a); end;

    procedure showAllEasterDay as
    begin
        p('YEAR    DAY');
        for i in 1 .. v.count loop
            p(v(i));
        end loop;
    end;

    procedure showMaxOccurenceEasterDay as
        d  w;
        e  w;
        f   w;
    begin
        a := u.first;
        while a is not null loop
            b := u(a);--取每个日期的出现次数
            if b = q then --当该日期出现次数为最大出现次数时
                d := d || '/' || a;--将符合要求的日期拼接到字符串中
            end if;
            if a like '03%' and b = m then--三月份出现最多的
                e := e || '/' || a;
            elsif b = n then--除了三月份,就是四月份了
                f := f || '/' || a;
            end if;
            a := u.next(a);
        end loop;

--打印时,没去掉第一个/符号
        p('MAXOCC             MO_CNT  MAXOCC_3      MO3_CNT    MAXOCC_4     MO4_CNT    ');
        p(d || '  '  || q || '       ' ||
          e || '         '  || m  || '          '  ||
          f || '  '  || n);
    end;

    procedure showLeapEasterDay as
    begin
        f := 0;
        p('ABSENT_START  ABSENT_END');
        for i in 0 .. date'1-4-25' - date'1-3-22' + 1 loop
            a := to_char(date'1-3-22' + i, 'mm-dd');
            if u.exists(a) then--日期存在
                if f = 1 then
                    p(b || '          ' || e);--上次不存在则打印
                end if;
                f := 0;--置本次存在标识为0,即存在
            else
                e := a;--结束日期=当前日期
                if f = 0 then
                    b := a;--如果上次存在,则开始日期=当前日期
                end if;
                if a = '04-25' then--到4.25还没有存在的日期就直接打印
                    p(b || '          ' || e);
                end if;
                f := 1;--置存在标识为1,即不存在
            end if;
        end loop;
    end;

    procedure showFoolEasterDay as
    begin
        p('YEAR    TOTAL');
        for i in 1 .. r.count loop
            p(r(i) || '     ' || t);
        end loop;
    end;

begin
    u.delete;
    t := 0;
    for i in f .. 2099 loop
        d := i - f;
        a := d mod 19;
        c := (11 * a + 4 - trunc((7 * a + 1)/19)) mod 29;
        b := 25-c-mod(d + trunc(d/4) + 31 - c, 7);

        if b > 0
        then a := '04'; c := b;
        else a := '03'; c := 31+b;
        end if;
        c := lpad(c,2,0);

        b := a||'-'||c;
        v(d+1) := i || '    ' || b;
        if b = '04-01' then t := t + 1; r(t) := i;  end if;
        if u.exists(b) then
            e := u(b) + 1;--累计每个日期的出现次数
            q := greatest(e,q);--取最大次数算法
            if b like '03%' then--取三月份最大次数算法
                m := greatest(e,m);
            else--四月份最大次数算法
                n := greatest(e,n);
            end if;
        else e := 1;
        end if;
        u(b) := e;
    end loop;
end;
/

最后,为了照顾到代码的完整性,可以将开始年份和结束年份变成以参数输入。这个就不再贴出代码了,改动很简单。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/12932950/viewspace-693846/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2008-05-10

  • 博文量
    257
  • 访问量
    1070168