E81086713E446D36F62B2AA2A3502B5EB155

Java杂家

杂七杂八。。。一家之言

BlogJava 首页 新随笔 联系 聚合 管理
  141 Posts :: 1 Stories :: 174 Comments :: 0 Trackbacks

置顶随笔 #

如题:求连续正整数使得其和为给定的一个正整数
下面给出我的解法,几乎可以一步到位求出来
实现代码如下:
/**
*Author: Koth (
http://weibo.com/yovn)
*Date:  2011-12-01
*/
#include 
<stdlib.h>
#include 
<stdio.h>
#include 
<stdint.h>

int solve(int Y,int& X){
    
int m=0;
    
int t=Y;
    
if(Y<=0){
        X
=Y;
        
return 1;
    }
    
while((t&1)==0){
        m
+=1;
        t
=t>>1;
    }
    
if(m==32){
        X
=Y;
        
return 1;
    }
    
int lastK=32;
    
for(;lastK>m+1;lastK--){
        
if(Y &(1<<(lastK-1))){
            
            
break;
        }
            
    }

    
//its a number st. exp(2,K)
    if(lastK==(m+1)){
        X
=Y;
        
return 1;
    }
    
int k=1<<(m+1);
    
int b=(Y>>m)-(1<<(lastK-m-1));

    X
=(1<<(lastK-m-2))+(b+1-k)/2;

    
if(X<=0){
        k
=k-1-((0-X)<<1);
        X
=0-X+1;
    }
    
    
return k;

}

int main(int argc,char* argv[]){
    
if(argc<=1){
        fprintf(stdout,
"Usage:%s number\n",argv[0]);
        
return 0;
    }
    
int Y=atoi(argv[1]);
    
int X=0;
    
int k=solve(Y,X);
    fprintf(stdout,
"%d=",Y);
    
for(int i=0;i<k;i++){
        fprintf(stdout,
"%d",X+i);
        
if(i<(k-1)){
            fprintf(stdout,
"+");
        }
    }
    fprintf(stdout,
"\n");
    
return 0;
}
posted @ 2011-12-01 22:09 DoubleH 阅读(1751) | 评论 (2)编辑 收藏

原题:

Command Network

Description

After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.

With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node A to another node B, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.

Input

The input contains several test cases. Each test case starts with a line containing two integer N (N ≤ 100), the number of nodes in the destroyed network, and M (M ≤ 104), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair xi and yi, giving the Cartesian coordinates of the nodes. Then follow M lines each containing two integers i and j between 1 and N (inclusive) meaning a wire can be built between node i and node j for unidirectional command delivery from the former to the latter. littleken’s headquarter is always located at node 1. Process to end of file.

Output

For each test case, output exactly one line containing the shortest total length of wires to two digits past the decimal point. In the cases that such a network does not exist, just output ‘poor snoopy’.


一开始没仔细读题,一看以为是最小生成树呢,结果Krusal算法上去WA了,Prim算法也WA,修修改改一直WA,第二天发现本题是要在有向图上面构造最小树形图。

按照著名的Zhu-Liu算法,仔细实现了一边,终于AC了。
按照我的理解总结下该算法,该算法对每个结点,除根节点外寻找最小入边,
1)如果这些入边不构成环,那么容易证明这些边构成最小树形图。
证明:设加上根节点r一共N个点,那么一共有N-1条边,证明从r能到每个点,若存在一点v,使得从r到v没有路径,那么,假设从v反向回退必然构成环,因为每个点除了r都有入边,如果不构成环,该路径可以无穷大。
2)如果存在环,我们把环收缩成一个点,更新相应的入边和出边,得到新的图G',使得原问题在G'中等效:
怎么收缩呢?
假设我们把环收缩成环上的任意一点v,所有进环的边和出环的边自动变成v的边(如果已有,取长度最短的),其余点标记为删除,更新不在环上的所有点进入该环的长度cost为cost-cost(prev[x],x);其中点x为进入环的边在环上的端点。出边保持不变。

这里为什么这么更新?因为这样更新使得我们的算法在新图上是等效的。任何环的解决后意味着在新图里面得为改收缩后的点寻找新的入边,而实际的花费应该是新的入边减去原有的入边长度,我们的算法在找到环的时候就把环上所有的边的长度计算在花费内了.而对出边是没有影响的。


到这算法的框架基本出来了。当为某点没找到入边的时候,意味着无解。为了加快无解的侦测,我们先运行一遍DFS搜索,假如从根节点出发,可触及的节点数小于N-1(不含r)则意味着无解。反之,肯定有解。
为什么?
因为如果可触及数小于N-1,意味着某点是不可触及的,也就是原图不是弱连通。对该点来说不存在从r到它的路径。反之,从r到某点都有一条路径,沿着该路径就能找到结点的入边。


第二个问题是,如何快速侦测环呢?
我使用了一个不相交集。回忆Krusal的算法实现里面也是使用不相交集来避免找产生环的最小边。

下面是我的代码:

// 3164.cpp : Defines the entry point for the console application.
//

#include 
<iostream>
#include 
<cmath>


using namespace std;

typedef 
struct _Point
{

    
double x;
    
double y;

    
double distanceTo(const struct _Point& r)
    {
          
return sqrt((x-r.x)*(x-r.x)+(y-r.y)*(y-r.y));

    }

}Point;



const int MAX_V=100;
const int MAX_E=10000;
const double NO_EDGE=1.7976931348623158e+308;

Point vertexes[MAX_V]
={0};
int parents[MAX_V]={0};
int ranks[MAX_V]={0};
double G[MAX_V][MAX_V]={0};
bool visited[MAX_V]={0};
bool deleted[MAX_V]={0};
int prev[MAX_V]={0};

int nVertex=0;
int nEdge=0;




int u_find(int a)
{
    
if(parents[a]==a)return a;
    parents[a]
=u_find(parents[a]);
    
return parents[a];
}
void u_union(int a,int b)
{
    
int pa=u_find(a);
    
int pb=u_find(b);
    
if(ranks[pa]==ranks[pb])
    {
        ranks[pa]
++;
        parents[pb]
=pa;
    }
else if(ranks[pa]<ranks[pb])
    {
        parents[pa]
=pb;
    }
    
else
    {
        parents[pb]
=pa;
    }
}

void DFS(int v,int& c)
{

    visited[v]
=true;
    
for(int i=1;i<nVertex;i++)
    {
        
if(!visited[i]&&G[v][i]<NO_EDGE)
        {
            c
+=1;

            DFS(i,c);
        }

    }

}



void doCycle(int s,int t,double& cost)
{
    memset(visited,
0,sizeof(bool)*nVertex);
    
int i=s;
    
do
    {
        visited[i]
=true;
        cost
+=G[prev[i]-1][i];
        
//cout<<"from "<<(prev[i]-1)<<" to "<<i<<" (cycle)"<<" weight:"<<G[prev[i]-1][i]<<endl;
        i=prev[i]-1;

    }
while(i!=s);


    
do
    {
        

        
for(int k=0;k<nVertex;k++)
        {
            
if(!deleted[k]&&!visited[k])
            {
            
                
if(G[k][i]<NO_EDGE)
                {
                    
if(G[k][i]-G[prev[i]-1][i]<G[k][s])
                    {


                        G[k][s]
=G[k][i]-G[prev[i]-1][i];
                        
//cout<<"1.update ["<<k<<","<<s<<"] at "<<i<<" as "<<G[k][s]<<endl;
                    }
                    

                }
                
if(G[i][k]<NO_EDGE)
                {
                    
if(G[i][k]<G[s][k])
                    {

                        G[s][k]
=G[i][k];
                        
//cout<<"2.update ["<<s<<","<<k<<"] at "<<i<<" as "<<G[s][k]<<endl;
                    }
                    
                }
            }
        }


        
if(i!=s)
        {
            deleted[i]
=true;
            
//cout<<"mark "<<i<<" as deleted"<<endl;
        }
        i
=prev[i]-1;


    }
while(i!=s);



}




int main(void)
{



    
    
while(cin>>nVertex>>nEdge)
    {

        
int s,t;

        
int nv=0;
        
bool cycle=0;
        
double cost=0;
        memset(vertexes,
0,sizeof(vertexes));
        memset(visited,
0,sizeof(visited) );

        memset(deleted,
0,sizeof(deleted));
        memset(G,
0,sizeof(G));
        memset(prev,
0,sizeof(prev));


        memset(ranks,
0,sizeof(ranks));

        memset(parents,
0,sizeof(parents));

        
for(int i=0;i<nVertex;i++)
        {

            cin
>>vertexes[i].x>>vertexes[i].y;
            parents[i]
=i;
            
for(int j=0;j<nVertex;j++)
            {
                G[i][j]
=NO_EDGE;
            }

        }
        
for(int i=0;i<nEdge;i++)
        {

            cin
>>s>>t;
            
if(t==1||s==t)continue;
            G[s
-1][t-1]=vertexes[s-1].distanceTo(vertexes[t-1]);

        }



        DFS(
0,nv);
        
if(nv<nVertex-1)
        {

            cout
<<"poor snoopy"<<endl;
            
continue;
        }



        
do {
            cycle
=false;
            
for(int i=0;i<nVertex;i++){parents[i]=i;}
            memset(ranks,
0,sizeof(bool)*nVertex);
        

            
for (int i = 1; i < nVertex; i++) {
                
double minimum=NO_EDGE;
                
if(deleted[i])continue;
                
for(int k=0;k<nVertex;k++)
                {
                    
if(!deleted[k]&&minimum>G[k][i])
                    {
                        prev[i]
=k+1;
                        minimum
=G[k][i];
                    }
                }
                
if(minimum==NO_EDGE)
                {
                

                    
throw 1;
                }
                
if (u_find(prev[i]-1== u_find(i)) {
                    doCycle(prev[i]
-1,i, cost);
                    cycle 
= true;
                    
break;
                }
                
else
                {
                    u_union(i,prev[i]
-1);
                }

            }


        } 
while (cycle);

        
for (int i = 1; i < nVertex; i++) {
            
if(!deleted[i])
            {
                cost
+=G[prev[i]-1][i];
                
//cout<<"from "<<(prev[i]-1)<<" to "<<i<<" weight:"<<G[prev[i]-1][i]<<endl;
            }

        }

        printf(
"%.2f\n",cost);


    }


}



posted @ 2009-04-24 16:39 DoubleH 阅读(2397) | 评论 (0)编辑 收藏

   今天买了本《算法概论》影印注释版,仔细看了第一章,果然名不虚传,很是吸引人。
第一章的习题难度适中,这里抽出第35题来,这题是证明Wilson定理。
Wilson定理:
   N是一个素数当且仅当: (N-1)! ≡ -1(mod N)

证明:
  首先我们证明若N是素数,那么等式成立,对于N=2,这是很明显的。以下证明N>2 的情形。
  1)若N是素数,那么关于N同余的乘法群G={1,2,3....N-1}
    群G每个元素都有逆元,映射 f:a -> a^-1 ,f(a)=a^-1 是一个一一映射。现在,任取一个元素,它的逆元要么是其它一个元素,或者是它本身。 我们假设其中元素x的逆元是它本身,那么x*x ≡1(mod N) =>(x+1)*(x-1)=K*N,而N是素数,所以要么x=N-1,要么x=1。也就是说,除了这两个元素,其它的元素的逆元都是映射到别的元素的。而N>2,是奇数,所以元素共有N-1个,也就是偶数个元素。这样,除了1和N-1外剩余的N-3个元素刚好结成两两一对(x,y)(逆元是唯一的)使得f(x)=y=x^-1,也就是xy≡1(mod N).
现在把G的元素全部乘起来,让互为逆元的元素组成一对那么(N-1)!=1*(N-1)*(x1*y1)*(x2*y2)...(xk*yk)≡1*(N-1)*1*1...1 (mod N)≡-1(mod N).
    这样,我们证明了一个方向了,下面我们证明另一个方向

  2)若(N-1)! ≡ -1(mod N)成立,则N是素数,若不然,令 N是和数。则(N-1)!肯定整除N,因为N的每个因子p满足p>1,p<N。
   现在令(N-1)!=K1*N.又(N-1)! ≡ -1(mod N) => K1*N ≡ -1(mod N),由同余性质知,存在K2使得K1*N+1=K2*N,两边同时除以N得K1+1/N=K2.显然,这是不可能的,所以若(N-1)! ≡ -1(mod N)成立,则N是素数

证明完毕!

这里用群的概念能够简化一定的描述,其实可以完全不用群的概念的,只不过这样一来,描述更长点,繁琐点!





posted @ 2009-04-10 22:38 DoubleH 阅读(1995) | 评论 (1)编辑 收藏

仅列出标题  下一页