• Tag:

     

    文件内建函数open();

    open(file, mode='r', buffering=-1, encoding=None, errors=None, newline=None, closefd=True)

     

    >>> open('f:\\text.txt')  用绝对路径

    <_io.TextIOWrapper name='f:\\text.txt' mode='r' encoding='cp936'>

     

    Character

    Meaning

    'r'

    open for reading (default)

    'w'

    open for writing, truncating the file first

    'a'

    open for writing, appending to the end of the file if it exists

    'b'

    binary mode

    't'

    text mode (default)

    '+'

    open a disk file for updating (reading and writing)

    'U'

    universal newline mode (for backwards compatibility; should not be used in new code)

     

    文件对象的操作:

    >>> dir(f)

    ['_CHUNK_SIZE', '__class__', '__delattr__', '__doc__', '__enter__', '__eq__', '__exit__', '__format__', '__ge__', '__getattribute__', '__getstate__', '__gt__', '__hash__', '__init__', '__iter__', '__le__', '__lt__', '__ne__', '__new__', '__next__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '_checkClosed', '_checkReadable', '_checkSeekable', '_checkWritable', 'buffer', 'close', 'closed', 'detach', 'encoding', 'errors', 'fileno', 'flush', 'isatty', 'line_buffering', 'name', 'newlines', 'read', 'readable', 'readline', 'readlines', 'seek', 'seekable', 'tell', 'truncate', 'writable', 'write', 'writelines']

     

    readline() 方法读取打开文件的一行(读取下个行结束符之前的所有字节). 自动跳到下一行。

    readlines() 方法并不像其它两个输入方法一样返回一个字符串. 它会读取所有(剩余的)行然

    后把它们作为一个字符串列表返回.

    @似乎没法做到scaanf(%s,str)那样的操作

    用完记得close文件


     

     

  •  

    算法导论的课后习题、要求给出点集的极角排序的叉乘实现,(极坐标系)。
    复杂度要求O(n*lg n),就用堆的数据结构来做。初学计算几何,没见过真正的极角排序,自己YY一个模板。
    大致如下,要求顺逆时针输出都可以,只要稍作调整。要求输出起点的话,可以用二分查找到起点,让后按时针序输出其他点,也只要稍作调整。
    01
    02
    03
    04
    05
    06
    07
    08
    09
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71

     

    #include 
    #include 
    #include 
    #include 
    using namespace std; 
    #define maxn 100 
    //用堆排序来实现极角排序,关键在于用叉乘比较极角大小 
    struct point{ 
        int x; 
        int y; 
    }; 
    typedef struct point point; 
    int n,heapSize; 
    point heap[maxn],O;//极角坐标系原点 
     
    int cross(point p1,point p2){ //p1 叉乘 p2: 小于零表示p1在p2的逆时针方向。 
        return  
        (p1.x-O.x)*(p2.y-O.y)-(p2.x-O.x)*(p1.y-O.y); 

     
    void heapfy(int idx){//保持堆的性质 
        int l = idx << 1
        int r = idx << 1 |1
        int est; 
     
        if(l > heapSize )return
     
        if(cross(heap[idx],heap[l]) < 0)//左孩子的极角是否比父节点大 
            est = idx; 
        else  est = l; 
     
        if(r <= heapSize && cross(heap[r],heap[est]) < 0
            est = r;                                //找到极角最大矢量的下标 
        if(est != idx ){ 
            swap( heap[est] , heap[idx] ); 
            heapfy(est);                        
        } 
         

     
    void build(){ 
        for(int i= heapSize/2; i > 0; i--)   //heap从下标1开始存到 heapSize  / 2 都是内部节点  
            heapfy(i); 

     
    void heapSort(){ 
        heapSize=n; 
        build();     
        for(int i=1;i < n; i++){ 
            swap( heap[1] , heap[heapSize--] ); 
            heapfy(1); 
        } 

     
    int main(){ 
        while(scanf("%d", &n) != EOF){ 
            O.x=0
            O.y=0
            for(int i = 1; i <= n; i++) 
                scanf("%d%d", &heap[i].x, &heap[i].y); 
     
            heapSort(); 
     
            for(i=1; i <= n; i++) 
                printf("(%d,%d)\n",heap[i].x,heap[i].y); 
        } 
        return 0

     


     

  • 01
    02
    03
    04
    05
    06
    07
    08
    09
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    // 判给定线段和是否相交 
     
    #include 
    #define  max(a,b) a > b ? a : b 
    #define  min(a,b) a < b ? a : b 
     
    typedef struct { 
         double x, y; 
    } point; 
    double direction (point p1, point p2, point p3) 

         return (p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y); 

     
    bool OnSegment (point p1, point p2, point p3) 

         double minx, miny, maxx, maxy; 
         minx = min(p1.x, p2.x); 
         maxx = max(p1.x, p2.x); 
         miny = min(p1.y, p2.y); 
         maxy = max(p1.y, p2.y); 
         //考虑水平和垂直的特殊情况,x,y的范围都要判断 
         if(p3.x >= minx && p3.x <= maxx && p3.y >= miny && p3.y <= maxy) 
              return true
         else 
              return false

     
    bool segments_intersect(point p1, point p2, point p3, point p4) 

         double d1, d2, d3, d4; 
         d1 = direction(p3, p4, p1); 
         d2 = direction(p3, p4, p2); 
         d3 = direction(p1, p2, p3); 
         d4 = direction(p1, p2, p4); 
         if (d1 * d2 < 0 && d3 * d4 < 0
              return true
         else if (d1 == 0 && OnSegment (p3, p4, p1)) 
              return true
         else if (d2 == 0 && OnSegment (p3, p4, p2)) 
              return true
         else if (d3 == 0 && OnSegment (p1, p2, p3)) 
              return true
         else if (d4 == 0 && OnSegment (p1, p2, p4)) 
              return true
         return false

     
     
     
  • Tag:

     

    01
    02
    03
    04
    05
    06
    07
    08
    09
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
       11 
       22 
       31 
       44 
       51 
       62 
       71 
       88 
       91 
      102 
      111 
      124 
      131 
      142 
      151 
      16:16 
      171 
      182 
      191 
      204 
      211 
      222 
      231 
      248 
      251 
      262 
      271 
      284 
      291 
      302 
      311 
      32:32 
      331 
      342 
      351 
      364 
      371 
      382 
      391 
      408 
      411 
      422 
      431 
      444 
      451 
      462 
      471 
      48:16 
      491 
      502 
      511 
      524 
      531 
      542 
      551 
      568 
      571 
      582 
      591 
      604 
      611 
      622 
      631 
      64:64 
      651 
      662 
      671 
      684 
      691 
      702 
      711 
      728 
      731 
      742 
      751 
      764 
      771 
      782 
      791 
      80:16 
      811 
      822 
      831 
      844 
      851 
      862 
      871 
      888 
      891 
      902 
      911 
      924 
      931 
      942 
      951 
      96:32 
      971 
      982 
      991 

     

  •  



    int getfather(int v){
        if (father[v]==v)
           return v;
        return father[v]=getfather(father[v]);
    }

    void judge(int x ,int y)
     
    {
         fx = getfather(x);
         fy = getfather(y);
     
         if (rank[fx]>rank[fy])
            father[fy] = fx;
         else
         {
            father[fx] = fy;
            if(rank[fx]==rank[fy])
               inc(rank[fy]);
         }
    }

     

    初始化:

    memset(rank,0,sizeof(rank));

     

     

  • Tag:优化

    从大牛roba的搞ACM的你伤不起 看各种优化。

    树型的有木有!!!!状态压缩的有木有!!!!插头的有木有!!!! 
    而且特么写出来就超时啊!!!!!! 
    你得四边形优化啊!!!!你得斜率优化啊!!!!你得队列优化啊!!!! 
    特么恨不得把要算十年的程序优化到一秒啊!!!! 
    你以为学过一个二叉搜索树就是懂数据结构了啊!!!!!! 
    平衡啊旋转啊红啊黑啊有木有!!!! 
    伸展啊随机权重啊合并啊拆分啊有木有!!!!!! 
    你以为学过一个Dijkstra最短路就是懂图算法了啊!!!!!! 
    特么的图里有几百万个点啊!!!!!!得用堆来优化啊!!!! 
    而且边权要是负的就不对了啊!!!!还有环啊!!!! 
    而且特么的你根本看不出是最短路问题啊!!!!!! 
    为神马最短路算法可以用来解不等式啊!!!! 
    还有网络流啊!!!!特么的课本上的算法铁定超时啊!!!!!! 
    你得看论文去研究神马Dinic啊SAP啊!!!!!! 

  • Tag:

     

    在有向图G上求强连通分量

    1、对Gdfs,记录每个节点结束访问的时间

    2、对G的所有边反向

    3、按(1)中记录的时间从大到小对新的图dfs

    4、得到的森林中每棵树对应一个强连通分量

     

    以下图为例。


    深搜时,我们给每个点加一个开始搜索时间戳(用[表示)和一个结束搜索时间

    (]表示)

    这样从4开始搜索得到以下搜索序列:

    [4,[5,[7,[6,[8,8],6],7],5],4]  [1,[2,[3,3],2],1]

    仔细观察这个搜索序列我们发现:

    1)该图得到一个搜索树林共两个搜索树,一个以4为根(4能到达的所有点),一

    个以1为根(1能到达的所有点)。

    24能达到的所有点在搜索序列里面都挨在一起,4不能达到的点形成的搜索序列肯定在其右边。

    3)搜索序列的左右括号是成对出现的,满足括号匹配的原则。某个节点两端括住

    的节点都是他能到达的所有结点。最先开始访问的节点(左括号),肯定也是其搜

    在子树里面最后一个访问的节点(右括号)。

    第二步对图进行反向,再从4点进行深搜,相当于在反向前的原图中求出所有能到

    4的点。

    第三步,按结束时间从大到小进行搜索。我们看搜索序列,最后一个点肯定是第一

    遍深搜时得到的最后一棵树的根r。从他开始深搜,相当于求出所有能达到树根r

    点。这样得到的搜索子树肯定是一个强联通分量。

    问题1:以上图为例,第一遍搜索得到以4为根的子序列(设为S1)和以1为根的子

    树序列(设为s2),图反向后,再从1开始搜索,能搜到的元素肯定不会包含s1

    元素,为什么?

    答:因为s1中的点都不能到达1,而第二遍搜索就是看哪些点能到达1,所以搜不到s1中的点。

    问题2:图反向后对4进行深搜,尽管1能到达4,为什么搜不到1

    因为第一遍深搜时,4不能达到1,所以1肯定位于4的右边,而第二遍深搜是按照结

    束时间进行搜索的,在搜索4之前,已经搜完1,对1设置了删除标志,所以不会

    1并入4的强联通分量。

     

    下面的程序只计算了强连通分量的个数,要求出每个强连通分量具体是什么稍稍改

    一点就可以了:)

    const

            maxn=1000;

    var

            i,m,n,x,y,ans,postid:longint;

            map:array[1..maxn,1..maxn]of boolean;

            chk:array[1..maxn]of boolean;

            post:array[1..maxn]of longint;

    procedure dfs_mark(id:longint);//第一遍深搜,求id能到达的所有点

    var i:longint;

    begin

            chk[id]:=true;

            for i:=1 to n do

                    if (not chk[i])and map[id,i] then dfs_mark(i);

            inc(postid);

            post[postid]:=id;//id的结束时间是postid

    end;

    //////////////////////////////////////////////

    procedure dfs_calc(id:longint);第二遍深搜,求所有能到达id的点

    var i:longint;

    begin

            chk[id]:=false;

            for i:=1 to n do

                    if chk[i] and map[i,id] then dfs_calc(i);

    end;

    ////////////////////////////////////////////

    begin

            readln(n);

            readln(m);

            for i:=1 to m do

            begin

                    readln(x,y);

                    map[x,y]:=true;

            end;

            for i:=1 to n do

                    if not chk[i] then dfs_mark(i);

            for i:=n downto 1 do

                    if chk[post[i]] then

                    begin

                            dfs_calc(post[i]);

                            inc(ans);

                    end;

            writeln(ans);

    end.

     

     

     

  • Tag:勾股数

    勾股数的常用套路


      所谓勾股数,一般是指能够构成直角三角形三条边的三个正整数(a,b,c)。 
    即a^2+b^2=c^2,a,b,c∈N 
    又由于,任何一个勾股数组(a,b,c)内的三个数同时乘以一个整数n得到的新数组(na,nb,nc)仍然是勾股数,所以一般我们想找的是a,b,c互质的勾股数组。 
    关于这样的数组,比较常用也比较实用的套路有以下两种:

    第一套路


      当a为大于1的奇数2n+1时,b=2*n^2+2*n, c=2*n^2+2*n+1。 
    实际上就是把a的平方数拆成两个连续自然数,例如: 
    n=1时(a,b,c)=(3,4,5) 
    n=2时(a,b,c)=(5,12,13) 
    n=3时(a,b,c)=(7,24,25) 
    ... ... 
    这是最经典的一个套路,而且由于两个连续自然数必然互质,所以用这个套路得到的勾股数组全部都是互质的。

    第二套路


      2、当a为大于4的偶数2n时,b=n^2-1, c=n^2+1 
    也就是把a的一半的平方分别减1和加1,例如: 
    n=3时(a,b,c)=(6,8,10) 
    n=4时(a,b,c)=(8,15,17) 
    n=5时(a,b,c)=(10,24,26) 
    n=6时(a,b,c)=(12,35,37) 
    ... ... 
    这是次经典的套路,当n为奇数时由于(a,b,c)是三个偶数,所以该勾股数组必然不是互质的;而n为偶数时由于b、c是两个连续奇数必然互质,所以该勾股数组互质。 
    所以如果你只想得到互质的数组,这条可以改成,对于a=4n (n>=2), b=4*n^2-1, c=4*n^2+1,例如: 
    n=2时(a,b,c)=(8,15,17) 
    n=3时(a,b,c)=(12,35,37) 
    n=4时(a,b,c)=(16,63,65) 
    ... ...

    补充


      ========Edward补充========
    对于N 为质因数比较多的和数时还可以参照其质因数进行 取相应的勾股数补充,即1个N会有多对的勾股数,例如:
    n=9时(a,b,c)=(9,24,25)or (9,12,15) --------3* (3,4,5)
    n=12时(a,b,c)= (12,35,37) or (12,16,20) ----- 4*(3,4,5)
    =========ShangJingbo补充=======
    还有诸如此类的勾股数,20、21、29; 
    119、120、169; 
    696、697、985; 
    4059、4060、5741; 
    23660、23661、33461; 
    137903 137904 195025 
    803760 803761 1136689 
    4684659 4684660 6625109
    ……
    已有三千年研究历史的勾股定理还有研究的空间吗? 我用本文试探索。more

  • Tag:

     

     图的表示(一般用邻接表表示):

    1:邻接表所需的存储空间为 O(V+E);

    2: 邻接表稍加变动,可以用来存加权图。用结构体,将权值随顶点存邻接表中。

    3:不足在于判断某边的存在速度不及邻接矩阵。

     

    广搜bfs

    1.       思想,不断发现新的顶点,向外扩张。primDijkstra都采用了与bfs类似的思想。

    2.       bfs生成一棵广度优先树,根节点到各节点距离为最短距离,即最小边数。可看出权为一的prim。在代码中加一数组p[v];用来记录v的父节点,就能保存一棵广度优先树。

    3.       复杂度------采用邻接表的bfs,每个顶点至多入队一次。每个顶点出队时才会扫描该点的邻接表,每个顶点的邻接表至多扫描一次。全部扫描用时O(|E|).初始化开销O|V|)。

    于是Bfs的总运行时间为OE+V)。

    4.       广度优先算法正确性证明。

    5.       输出优先树中从根节点到某节点v的路径方法。

    Print_path(s,v){

    If(s==v)print(s);

    Print(s,p[v]);

    Print(v);

       }

     

    深度优先搜索。Dfs

    1.       对于新发现的节点,如果有以此为起点而未探测到的边,就继续沿此边探测下去。当顶点v的所有边都已被探测完,搜索将回溯到发现v的有起始点的那些边。

    2.       深度优先的先辈子图形成了一个由数棵深度优先树形成的深度优先森林。多个起点搜非联通图?

    3.       时间戳:每个节点有两个时间戳。入栈时间,出栈时间戳。

    4.       括号定理,深度优先搜索中任意两节点的时间区间[d[u],f[u].] [d[v],f[v]]具有三种关系中的一种。节点v是节点u的后裔当且仅当d[u]<d[v]<f[v]<f[u].

    5.       边的分类

    有向图根据u发现v时的颜色对(uv)进行分类。

    1.       白色,树枝。

    2.       灰色,反向边。

    3.       黑色,正向边,交叉边。

    无向图中要么是树枝,要么是反向边。

     

     

     

  • 出栈次序问题

     一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?

    分析(from 百度百科:卡特兰数


    对于每一 个数来说,必须进栈一次、出栈一次。

    我们把进栈设为状态‘1’,出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。

                       //想象你是一个客栈的服务员,负责记录客人进出。有人进写1,有人出就写0。得到一个01的串

    由于等待 入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),

                       //里不知道按递增进栈是否有必要

    因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位 二进制数,1的累计数不小于0的累计数的方案种数

    //下面用证明了不合要求的方案数为C(n+1,n);

    在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。//C(2n,n)相当于从2n个位置中选取n个位置A(n,2n),由于放的都是1,所以取出的位置间是无差别的故有C(2n,n)=A(n,2n)/A(n,n);


    不 符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,

    此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的 2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。


    反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数, 由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位 数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。


    因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。

    //证明了不合要求的方案数为C(n+1,n);


    显然,不符合要求的方案数为c(2n,n+1)。由此得出 输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。

  • Tag:

    為求得費波那西數列的一般表達式,可以借助線性代數的方法。高中的初等數學知識也能求出。

    初等代數解法 //很诡异的方法

    已知

    • a 1 = 1
    • a 2 = 1
    • a n = a n − 1 + a n − 2

    首先構建等比數列

    a n + αa n − 1 = β(a n − 1 + αa n − 2 )
    化簡得
    a n = (β − α)a n − 1 + αβa n − 2
    比較係數可得:
     \begin{cases}
\beta-\alpha=1 \\
\alpha\beta=1
\end{cases}
    不妨設β > 0,α > 0
    解得:

     \begin{cases}
\alpha=\dfrac{\sqrt{5}-1}{2} \\
\beta=\dfrac{\sqrt{5}+1}{2}
\end{cases}
    所以有a n + αa n − 1 = β(a n − 1 + αa n − 2 ) , 即\left\{a_n +\alpha a_{n-1}\right\} 為等比數列。

    求出數列{a n + αa n − 1 }

    由以上可得:
    \begin{align}a_{n+1} +\alpha a_{n} &=(a_2+\alpha a_1)\beta^{n-1}\\
& = (1+\alpha)\beta^{n-1}\\
& =\beta^n \\
\end{align}

    變形得: \frac{a_{n+1}}{\beta^{n+1}}+\frac{\alpha}{\beta}\frac{a_{n}}{\beta^{n}}=\frac{1}{\beta} 。 令b_n=\frac{a_n}{\beta^n}

    求數列{b n }進而得到{a n }

    b_{n+1}+\frac{\alpha}{\beta}b_{n}=\frac{1}{\beta}
    b_{n+1}+\lambda=-\frac{\alpha}{\beta} (b_{n}+\lambda) ,解得\lambda=-\frac{1}{\alpha+\beta} 。 故數列 \left\{b_n+\lambda\right\} 為等比數列
    b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(b_1+\lambda\right) 。而 b_1=\frac{a_1}{\beta}=\frac{1}{\beta} , 故有 b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(\frac{1}{\beta}+\lambda\right)
    又有 \begin{cases}
\alpha=\dfrac{\sqrt{5}-1}{2} \\
\beta=\dfrac{\sqrt{5}+1}{2}
\end{cases}b_n=\frac{a_n}{\beta^n}
    可得 a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]

    得出 a n 表達式

    a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]

    線性代數解法

     構建一個矩陣方程

    設Jn 為第n個月有生育能力的兔子數量,An 為這一月份的兔子數量。

    {J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}},

    上式表達了兩個月之間,兔子數目之間的關係。而要求的是,An+1 的表達式。

     求矩陣的特徵值λ

    行列式:-λ *(1-λ )-1*1=λ 2-λ -1

    當行列式的值為0,解得λ1 =\frac{1}{2} (1 + \sqrt{5})λ2 =\frac{1}{2} (1 - \sqrt{5})

    特徵向量

    將兩個特徵值代入

    \begin{pmatrix}0&1\\1&1\end{pmatrix}-\lambda \cdot E) \cdot\vec x = 0

    求特徵向量\vec x

    \vec x_1 =\begin{pmatrix} 1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}

    \vec x_2 =\begin{pmatrix} 1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}

     分解首向量

    第一個月的情況是兔子一對,新生0對。

    {J_{1}\choose A_{1}} = \begin{pmatrix}0\\1\end{pmatrix}

    將它分解為用特徵向量表示。

    \begin{pmatrix}0\\1\end{pmatrix}=\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}-\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix} (4)

    數學歸納法 證明

    {J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}} =\lambda \cdot {J_n\choose A_{n}}

    可得

    {J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix}^n \cdot {J_{1}\choose A_{1}} =\lambda^n \cdot {J_{1}\choose A_{1}} (5)

     化簡矩陣方程

    將(4) 代入 (5)

    {J_{n+1}\choose A_{n+1}} = \lambda^n \cdot [\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}-\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}]

    根據 3

    {J_{n+1}\choose A_{n+1}} = \frac{1}{\sqrt{5}} \cdot \lambda_1^n \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}- \frac{1}{\sqrt{5}} \cdot  \lambda_2^n\cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}

     求A的表達式

    現在在6的基礎上,可以很快求出An+1 的表達式,將兩個特徵值代入 6 中

    A_{n+1}=\frac{1}{\sqrt{5}} \cdot \lambda_1^{n+1} - \frac{1}{\sqrt{5}} \cdot \lambda_2^{n+1}
    A_{n+1}=\frac{1}{\sqrt{5}} \cdot (\lambda_1^{n+1} -  \lambda_2^{n+1})
    A_{n+1}=\frac{1}{\sqrt{5}} \cdot ((\frac{1}{2} (1 + \sqrt{5}))^{n+1} -  (\frac{1}{2} (1 - \sqrt{5}))^{n+1}) (7)

    (7)即為An+1 的表達式

    近似值

    F_n \approx \frac{1}{\sqrt{5}} a^n = \frac{1}{\sqrt{5}} \cdot ( \frac{1}{2} (1 + \sqrt{5}) )^n \approx 0.4472135955 \cdot 1.618033988745^n

  • 初等数论中的欧拉定理

    定理内容


      在数论中,欧拉定理 (也称费马-欧拉定理 ) 是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互素,(a,n) = 1,则
    a^φ(n) ≡ 1 (mod n)

    证 明


    首先证明下面这个命题:
    对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不 大于n且与n互素的数,即n的一个化简剩余系,或称简系,或称缩系),考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)}
    则S = Zn
    1) 由于a,n互质,xi也与n互质,则a*xi也一定于n互质,因此
    任意xi,a*xi(mod n) 必然是Zn的一个元素
    2) 对于Zn中两个元素xi和xj,如果xi ≠ xj
    则a*xi(mod n) ≠ a*xj(mod n),这个由a、n互质和消去律可以得出。
    所以,很明显,S=Zn
    既然这样,那么
    (a*x1 × a*x2×...×a*xφ(n))(mod n)
    = (a*x1(mod n) × a*x2(mod n) × ... × a*xφ(n)(mod n))(mod n)
    = (x1 × x2 × ... × xφ(n))(mod n)
    考虑上面等式左边 和右边
    左边等于([a^φ(n)] *(x1 × x2 × ... × xφ(n))) (mod n)
    右边等于x1 × x2 × ... × xφ(n))(mod n)
    而x1 × x2 × ... × xφ(n)(mod n)和n互质
    根据消去律,可以从 等式两边约去,就得到:
    a^φ(n) ≡ 1 (mod n)
    推论:对于互质的数a、n,满足a^(φ(n)+1) ≡ a (mod n)
    费 马定理 :
    a是不能被质 数 p整 除 的正整数,则有a^(p-1) ≡ 1 (mod p)
    证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明。
    同 样有推论:对于不能被质数p整除的正整数a,有a^p ≡ a (mod p)

  • Tag:

    //小素数模板

    int plist[10000],pcount=2;
     
    int prime(int n){
        int i;
        for (i=1;plist[i]*plist[i]<=n;i++)
            if (n%plist[i]==0)return 0;
        return 1;
    }
     
    void initprime(){
        int i;
        for (plist[1]=2,i=3;i<50000;i++)
            if (prime(i))plist[pcount++]=i;
    }

  • http://acm.hdu.edu.cn/showproblem.php?pid=1087

    动态规划着实妙不可言,此题求最大上升子序之和。

    1.设第i个棋子的值为a[i],考虑从起点开始一路跳至第i个棋子的最大上升子序列之和为Sum[i]。

    那么跳到i点的前一步可以是j

    Sum[i]=Max{Sum[j]}+a[i];(其中a[j]

    所以只要建立子问题的最优解,就可以建立原问题的某个示例的最优解。

    2.任意一点都可以直接跳到终点,所以最终解为S*=max{sum[i]};

    Sum[i]=Max{Sum[j]}+a[i];i!=0;

    Sum[0]=0;a[0]=0;起始值设为0;

     

    追踪最大子序的元素(题目不要求):

    设最终求得最大和为Max,自后向前在Sum[i]搜索Sum[i]==M


  • Tag:递归 搜索

    description

    把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

    首先是递归解法(from:http://blog.csdn.net/waterbuffalo/article/details/5972648

    最典型的整数分解,例如给定n个苹果,把苹果放到k个盘子里,允许有的盘子为空(poj1664),不妨设 f(n , k ) (边缘条件为当 n = 0 时,返回1,当 k = 1 时,返回1)表示结果,分析一下可以知道有两中放的方法,一种是有空盘,一种是没空盘,没空盘的情况可以知道每个盘子里至少有一个苹果,也就是说这种情况的总数为 f ( n-k , k ) 。而有空盘的情况,我们可以假设最后一个盘子为空,则这种情况的总数为

    f ( n , k-1 ) (无需考虑多个盘子为空的情况,递归时必然会出现)所以状态转移方程为 f ( n , k ) = f  ( n-k , k ) +  f ( n , k-1 )。

    而如果是不允许有空盘子的情况,则可以由上面的情况推出,设 d ( n , k ) 表示把n个苹果放到k个盘子里,不允许有空盘子的方法总数,则有

    f ( n , k ) =  Σ (  1 <= i <= k ) d ( n , i ) 所以 d ( n , k ) = f ( n , k ) - f ( n , k-1 )

    ==================================================================

    比较难理解的是深搜解法:

    我们定义一个过程,使其反复递归穷举第1份、第2份……第k份,然后寻找出可行的路径,时间复杂度O(nk)。这种方法思路十分便捷,但也许会超时。
    我们有两个很好的剪枝:
    剪枝1如果剩余的够不上最小的则剪去。这是显而易见的常理,但是可以加快速度。剪枝2枚举到剩余1个盘子时判断是否可行。也是加快速度的方法,使在题目所描述的n和k的范围之中完全可行。
    重复的只算一种,我们怎么样处理有关重复的呢?我们可以引入一个参数min,作为至少每一个要达到min,顺序由小而大,逐层递归。
    综上所述,我们可以轻易写出一个优化过的递归搜索程序。

    #include<stdio.h> 
    int sum, n, k, count; 
    void dfs(int step, int min) 

     
        if(step == k + 1
        { 
            if(sum == n)count++; 
            return
        } 
        for(int i = min; i <= n; i++) 
        { 
            sum += i; 
            dfs(step + 1, i); 
            sum -= i; 
        } 
        return

    int main() 

        int t; 
        scanf("%d", &t); 
        count = 0
        while(t--) 
        { 
            scanf("%d%d", &n, &k); 
            sum = 0
            count = 0
            dfs(10); 
            printf("%d\n", count); 
        } 
        return 0

     
  • 参考算法导论实现了带哨兵的双链表。一直皱眉的东西,发现实现起来并不难。

     

    #include  
    struct  node { 
        int  data; 
        node *next; 
        node *pre; 
    }; 
    node memory[100000 ]; 
    int  allocp;//模拟分配 
    //加哨兵的双链表,可以不用双指针不用改表头 
    node *build() 

        node *nil; 
        nil = &memory[allocp++]; 
        nil->next = nil; 
        nil->pre = nil; 
        return  nil; 

    void  insert(node *nil, node *x) 

        x->next = nil->next; //先指向头元素 
        nil->next->pre = x; // 头元素反指 
        nil->next = x; //解决哨兵 
        x->pre = nil; 

    node *search(node *nil, int  key) 

        node *x; 
        x = nil->next; 
        while (x != nil) { 
            if (x->data == key)return  x; 
            x = x->next; 
        } 
        return  nil; 

    void  del(node *nil, node *x) 

        x->pre->next = x->next; 
        x->next->pre = x->pre; 

     
    //=============可以无视以下内容=======================
    int  main () 

        int  n; 
        char  com[10 ]; 
        node *nil; 
        node *t; 
        nil = build(); 
     
        while (scanf("%s" , com) != EOF) { 
            if (com[0 ] == 'i' ) { 
                scanf("%d" , &n); 
                t = &memory[allocp++]; 
                t->data = n; 
                insert(nil, t); 
            } 
            if (com[0 ] == '@' ) { 
                t = nil->next; 
                while (t != nil) { 
                    printf("%d " , t->data); 
                    t = t->next; 
                } 
                printf("\n" ); 
            } 
            if (com[0 ] == 's' ) { 
                scanf("%d" , &n); 
                if (search(nil, n) != nil)printf("in list\n" ); 
                else  printf("not exist\n" ); 
            } 
            if (com[0 ] == 'd' ) { 
                scanf("%d" , &n); 
                del(nil, search(nil, n)); 
            } 
     
            if (com[0 ] == 'e' )break
        } 
        return  0

     
     

     

     

  • Tag:

    2446:Chessboard

    纸牌是2*1,方格是1*1.一张纸牌可以匹配两个方格。所以如果一个方格属于集合X,那么

    它上下左右的方格都属于集合Y。实际上可以把图看成

    0 1 0 1

    1 0 1 0

    0 1 0 1

    1 0 1 0

    对应上面的图的每个方格,0,1表示集合X和Y。由此已知方格的坐标(x,y)可知对应的集合

    为(x%2)^(y%2);这种01矩阵在方格图中还有许多有趣的性质,比如0集合点到0集合点的距

    离为偶数,0集合点到1集合点的距离为奇数。在一些搜索问题中可用于剪枝。

     

    完成01集合元素之间的构图后,用匈牙利算法扫描所有0集合中的点,直接上模板:

     

     

    //匈牙利算法模板
    int path(int u){
    	int v;
    	for(v=0;v<m*n;v++){
    		if(g[u][v]&&!mk[v]){
    			mk[v]=1;
    			
    			if(cy[v]==-1 || path(cy[v]) ){
    				cx[u]=v;
    				cy[v]=u;
    				return 1;
    			}
    		}
    	}
    	return 0;
    }
    
    int maxmatch(){
    	int res=0;
    	memset(cx,0xff,sizeof(cx));
    	memset(cy,0xff,sizeof(cy));
    	for(int j=1;j<=m;j++){
    		for(int i=1;i<=n;i++){
    			if(((i%2)^(j%2))==0&&cx[p(i,j)]==-1){
    		
    			   memset(mk,0,sizeof(mk));
    			   res+=path(p(i,j));
    			}
    		}
    	}
    	return res;
    }
    
    //=============================
    


     

  • Tag:

    转载自:http://www.sunhongfeng.com/2011/01/catalan/

     

    算法课最后一节讲到了卡特兰数,总结和学到了很多以前不知道的东西。

    卡特兰数的递推公式是F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}
    一般性公式为F(n)=C(2n,n)/(n+1)

    可以描述的问题有
    1、n个元素的二叉查找树有多少种。
    2、n*n棋盘从左下角走到右上角而不穿过主对角线的走法。
    3、2n个人排队买票问题,票价50,n个人拿50元,n个人拿100元,售票处无零钱,能顺利卖票的所有排队方式。
    4、n个元素全部入栈并且全部出栈的所有可能顺序。

    这些问题的答案都是卡特兰数F(n)。但是很明显可以看出后三个问题是同质的。
    都可以抽象成2n个操作组成的操作链,其中A操作和B操作各n个,且要求截断到操作链的任何位置都有:A操作(向右走一步、收到50元、元素入栈)的个数不少于B操作(向上走一步、收到100元找出50元、元素出栈)的个数。故问题2、3、4其实是同一个问题。

    下面先证明问题2、3、4和问题1同解,再证明问题2、3、4的解是F(n)=C(2n,n)/(n+1),从而证明问题1的解也是F(n)=C(2n,n)/(n+1)。

    1、问题2、3、4和问题1同解
    问题1的解是F(n)=∑(k=0…n-1){F(k)*F(n-1-k)},因为一棵n个结点的二叉排序树的根可以是1到n的任意结点,设为k,则其左子树结点个数为k,左子树的种类一共有F(k-1)种,右子树结点个数为n-k,右子树的种类一共有F(n-k)。而究竟哪一点为根可以有1到n共n个选择,故k取遍1到n——F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}。

    如果我们能证明问题2的解也可表示为F(n)=∑(k=0…n-1){F(k)*F(n-1-k)},就完成了证明。

    考虑n*n棋盘,记主对角线为L。从左下角走到右上角不穿过对角线L的所有路径,不算起点,一定有第一次接触到L的位置(可能是终点),设此位置为M,坐标为(x,x)——设第一个数为横轴坐标。该路径一定从下方的(x,x-1)而来,而起点处第一步也一定是走向(1,0),两者理由相同——否则就穿过了主对角线。考虑从(1,0)到(x,x-1)的(x-1)*(x-1)的小棋盘中,因为在此中路径一直没有接触过主对角线(M的选取),所以在此小棋盘中路径也一定没有穿过从(1,0)到(x,x-1)的小棋盘的对角线L1。这样在这个区域中的满足条件的路径数量就是一个同构的子问题,解应该是F(x-1),而从M到右上角终点的路径数量也是一个同构的子问题,解应该是F(n-x),而第一次接触到主对角线的点可以从(1,1)取到(n,n),这样就有F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k-1)*F(n-k)}。证毕。

    2、问题2的解为F(n)=C(2n,n)/(n+1)
    思路是先求所有从(0,0)到(n,n)的路径数X,再求所有穿过主对角线L的从(0,0)到(n,n)的路径数Y,用前者减去后者得到所求。
    从(0,0)到(n,n)的路径数显然是C(2n,n),一共要走2n步到达右上角,其中向右和向上各n步,总走法是C(2n,n)。
    考虑一个新增的位置(n-1,n+1),它位于终点的左上角一个格处,设所有从(0,0)到(n-1,n+1)的路径数为Z,下面要证明Y和Z相等,从而通过求Z来求Y。
    考虑从(0,1)到(n-1,n)的对角线L2,对于所有穿过L而到达终点的路径,一定会接触到L2,找出某路径第一次接触到L2的位置M1,将从M1到终点的路径沿L2做对折一定会得到一条从M1到(n-1,n+1)的路径,故每条穿过L到达终点的路径都对应一条到达(n-1,n+1)的路径,即有Y<=Z。

    所有从起点到达(n-1,n+1)的路径都一定会穿过L2,找出某路径第一次穿过L2的位置M2,将M2到(n-1,n+1)的路径沿L2对折,就得到一条M2到(n,n)的路径,且该条路径一定穿过L,故每条到达(n-1,n+1)的路径都对应一条穿过L到达终点的路径,即有Z<=Y。
    故Z==Y。
    接下来通过求Z来求Y。Z是显然的从(0,0)到(n-1,n+1)共需走2n步,其中向右n-1步、向上n+1步,故Z=C(2n,n-1)。
    由以上可知F(n)=X-Y=X-Z=C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)。证毕。

    由以上可知问题1的解也是F(n)=C(2n,n)/(n+1),故求和(k){F(k)*F(n-1-k)}=C(2n,n)/(n+1)。这个数称为卡特兰数,前几项为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796。

    除了上面描述的四个问题外,它对应的问题还有:
    矩阵链所有乘法顺序问题(同问题1)。
    凸多边形剖分成三角形的方法数(同问题1)。

     

  • A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.

    要求构造只含特定素数(2 3 5 7)的 数。

     

  • Tag:

    卡住了,不知道怎么解方程组?先mark下
        D <= | A(H) - A(M) | <= 360-D;   (1)
        D <= | A(H) - A(S) | <= 360-D;   (2)
        D <= | A(M) - A(S) | <= 360-D;   (3)
    其中:
      A(H) = 30H + M/2 + S/120;
      A(M) = 6M + S/10;
      A(S) = 6S;

    p。s:

    在discuss中看到一个用公式近似计算的方法,也不知道神马原理。

    percentage = 100*(1-D/120.0)*(1-D/120.0);