1. 思维导图:敏捷开发

    终于看完了《Agile Principles, Patterns, and Practices in C#》的第一个Section,上学期间读这些书的进度还真不是一般的慢……第一次尝试用MindMap做笔记,感觉不错,不过效率还是不够高。老蒋说我笔记做得太详尽了,像抄书…反思中。

    篇幅所限,书中还是有很多内容不够深入。一些内容需要另一本书的篇幅深入讨论(如重构),甚至需要看一本书才能从纸上谈兵转到实践(如TDD、Acceptance Tests)。。。望不到头的书单啊T_T

    做笔记使用的工具是 XMind

  2. [BHOJ10235] 窗口取数

    时间限制:5000 ms
    内存限制:65535 KB

    描述

    有一串整数在排队……

    有N个整数,你有一个可以框住M个连续段整数的木框,现在你想知道,对于这个队列中任意的连续M个整数,最大和最小的整数是哪个?

    例:(M大小的窗口向右滑动)

    1 2 3 2 1   M=2
    1 2    MAX 2  MIN 1
    2 3    MAX 3  MIN 2
    3 2    MAX 3  MIN 2
    2 1    MAX 2  MIN 1
    

    最后需要输出的是两行:

    1 2 2 1
    2 3 3 2
    

    输入格式

    第一行包含一个整数T,表示有T组测试数据; 以下每组测试数据格式: 第一行包含2个整数N,M表示有N个整数在排队,取连续M个整数。 第二行包含N个整数。 其中N不大于1,000,000,M不大于N。

    输出格式

    按照题目描述格式输出结果,第一行为MIN,第二行为MAX

    问题来源

    软件学院07级数据结构第二次测试

    题解

    很久不考虑算法问题了的说……当然也好久不写解题报告了。上面这题让我体会到久违了的思考的乐趣(i.e.我废掉好久了>_<)

    最显然的解法是利用平衡树始终保持木框内M个数的有序状态,大体是O(NlogM)的复杂度。这个不用多说。

    问题是:能否找到O(N)的解法?在读下去之前你可以好好想想。

    我纠结了好久,终于……也没想出来- – 尽管想出很多优化,终究还是不能达到要求。网上搜了下,看到 CS大牛csdn 上有人给出了一个解法(你也可以在读完全文后再回头看这一段):

    是可以到o(n);

    编程之美上有一个类似的问题:”队列中取最大值操作问题”;
    实际上窗口移动就相当于对队列做了一次出队与入队操作,所以lz这道题可以套用该解法;

    书上是使用两个栈来模拟队列,假设为分别 A,B;

    1) 当入队的时候,push A; 2)

    当出队的时候

    1. 若B非空, pop B,
    2. 若B为空,则先将A中的元素依次 pop 并 push 到 B,再 pop B;

    这样,就使用两个栈达到了队列的功能;

    同时,对于单个栈,由于 pop, push 都是在栈顶进行的,所以每个栈都可以方便地维护自己的最大值与最小值在栈内的索引;
    以最大值为例;
    max_idx 保存栈内最大值的索引;
    另使用一个跟栈的最大长度一样的数组 idx , idx[i] 表示栈的索引范围在0到i-1的元素中的最大值的索引为 idx[i] ;
    1. 当push的时候,比较栈顶元素与栈的已保存的最大值,
    2. 若栈顶元素大于已保存的最大值,那么 idx[top]=max_idx,max_idx=top;
    3. 若栈顶元素不大于已保存的最大值,那么 idx[top]=max_idx (书上是 idx[top]=-1);
    4. 当pop的时候, max_idx=idx[top] (书上是先比较 topmax_idx ,若 top==max_idx ,则 max_idx=idx[top] );

    具体到这个题目; 可以使用两个长度为m的栈来模拟窗口;

    1. 将前m个元素依次push到栈A;
    2. 移动窗口就相当于分别进行 pop B 与 push A 操作;
    3. 窗口的最大值 == max[A.items ...
  3. 小试模板元编程

    cpp

    很久不更新了,再水一下吧。

    前两天新开的数据结构课布置上机作业,里面又出现了不知道之前出现过多少次的输出质数。每次都交表也会很乏味,所以……这次还是要交表 - -||| 不过要玩一点小花样——让编译器在编译期把质数表算出来。

    这个当然涉及到一点模板元编程了。之前虽然看了《Effective C++》里关于模板元的简介挺感兴趣,但看到《学习C++:实践者的方法》里告诫不要在这种“20%场景下的复杂性”上白花时间:

    这些细节或技术在日常编程中极少用到,尤其是各种语言缺陷衍生出来的workarounds, 构成了一个巨大的长尾……绝大多数只在库开发当中需要用到

    我因而一直对模板元编程敬而远之。这次也只是消遣一下,并无深入学习的打算。

    以下是代码:

    #include <iostream>
    #include <vector>
    #include <iterator>
    #include <algorithm>
    
    std::vector<int> Primes;
    
    template <int toTest, int factor> // factor should be odd
    class IsPrime
    {
       public:
          enum {
             result = ( toTest == 2 )
             ||  toTest % factor
              && IsPrime < toTest , factor - 2 >::result
          };
    };
    
    template<int toTest>
    class IsPrime<toTest, 1>
    {
       public:
          enum {result = ( toTest == 2 )  || ( toTest & 1 ) };
    };
    
    template <int upperBound> // upperBound should be odd or 2
    class PrimePick : public PrimePick < upperBound - 2 >
    {
       public:
          enum {
             isPrime = IsPrime < upperBound, ( upperBound >> 1 ) | 1 >::result
          };
          PrimePick<upperBound>() {
             if ( isPrime )
                Primes.push_back ( upperBound );
          }
    };
    
    template<>
    class PrimePick<2>
    {
       public:
          PrimePick<2>() {
             Primes.push_back ( 2 );
          }
    };
    
    template<>
    class PrimePick<1> : public PrimePick<2> {};
    
    int main()
    {
       PrimePick<999> PrimeInitializer;
    
       int m;
       std::cin >> m;
       for ( int i = 0; i < m; ++i ) {
          int n;
          std::cin >> n;
    
          std::vector<int>::iterator end = Primes.begin();
          while ( end != Primes.end() && *end <= n )
             ++end;
    
          std::ostream_iterator<int> out ( std::cout, " " );
          std::copy ( Primes.begin(), end, out );
          std::cout << std::endl;
       }
    }
    

    原理比较简单,主函数第一行初始化 PrimeInitializer 时,由于继承关系,构造函数会层层递归调用,从里至外利用另一个模板类 IsPrime 判断模板参数是否是质数,并把测试确认的质数放进一个 vector 里,这样就得到了编译期计算出的质数表。IsPrime 则使用最原始的试除方法判断质数。代码里一些写得很纠结的地方,一方面是为了尽量简化计算,减少编译时间,另一方面更主要是因为 ...

  4. 恶搞巴赫:Deconstructing Johann

    偶然发现的一段很好玩的视频,是 The King’s Singers 在 2000 年巴赫音乐节表演的 Deconstructing Johann。他们从巴赫的一些有名的作品中选出片段拼凑了一下,填上词,虚构出巴赫在写d小调托卡塔与赋格时与妻子很恶搞的对话。

    注意看歌词哈:

    Deconstructing Johann

    J. S. Bach had a little problem.
    J. S. Bach was in a fix.
    J. S. Bach couldn’t find an answer.
    What to do?
    “I’ve written most of a rather fabulous work!
    Toccata, it’s in D minor, but now I’m feeling a bit of a jerk!
    I can’t think of what should come after it…”
    “Now,” said his wife, who was resting up after her 33rd child,
    “Johann, my dear, you should just go to bed.
    Something always comes up.”
    “Don’t be a tweet!
    It’s a real crisis and I’m working to a deadline!
    What can I fit?
    What to fit after the great toccata?
    Maybe it needs to be something faster?
    I haven’t got a clue
    and in a week the piece is due.
    I’m in a panic!
    I’m stuck like glue!”
    “Don’t get your knickers in a twist, Johann.
    ‘Those are only notes’, you’ve always said.
    There’s only twelve so use your head.
    How many arrangements of twelve notes can there possibly be?”
    “That’s a problem ...

Page 3 / 9