亚洲国产不卡,国产乱码精品,成人精品三级

求連續(xù)正整數(shù)使得其和為給定的一個正整數(shù)的構(gòu)造性解法

如題：求連續(xù)正整數(shù)使得其和為給定的一個正整數(shù)

下面給出我的解法，幾乎可以一步到位求出來

實現(xiàn)代碼如下：

/**
*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 閱讀(1777) | 評論 (2) | 編輯收藏

DP的幾道練手題

摘要: 年過的差不多了，今天偶爾興起上HOJ上翻幾道DP練手的題來。。。，順便把代碼貼下留念 1.數(shù)塔 Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->/** * */ pack... 閱讀全文

posted @ 2011-02-06 21:13 DoubleH 閱讀(2019) | 評論 (0) | 編輯收藏

基于JDK7 NIO2的高性能web服務(wù)器實踐之二

摘要: 前一篇博客，我簡單提了下怎么為NIO2增加TransmitFile支持，文件傳送吞吐量是一個性能關(guān)注點，此外，并發(fā)連接數(shù)也是重要的關(guān)注點。不過JDK7中又一次做了簡單的實現(xiàn)，不支持同時投遞多個AcceptEx請求，只支持一次一個，返回后再投遞。這樣，客戶端連接的接受速度必然大打折扣。不知道為什么sun會做這樣的實現(xiàn)，WSASend()/WSAReceive()一次只允許一個還是可以理解，... 閱讀全文

posted @ 2009-12-04 17:57 DoubleH 閱讀(3898) | 評論 (6) | 編輯收藏

JDK7 NIO2 實踐: 增加 TransmitFile支持

JDK7的NIO2特性或許是我最期待的，我一直想基于它寫一個高性能的Java Http Server.現(xiàn)在這個想法終于可以實施了。
本人基于目前最新的JDK7 b76開發(fā)了一個HTTP Server性能確實不錯。
在windows平臺上NIO2采用AccpetEx來異步接受連接，并且讀寫全都關(guān)聯(lián)到IOCP完成端口。不僅如此，為了方便開發(fā)者使用，連IOCP工作線程都封裝好了，你只要提供線程池就OK。

但是要注意，IOCP工作線程的線程池必須是 Fix的，因為你發(fā)出的讀寫請求都關(guān)聯(lián)到相應(yīng)的線程上，如果線程死了，那讀寫完成情況是不知道的。

作為一個Http Server，傳送文件是必不可少的功能，那一般文件的傳送都是要把程序里的buffer拷貝到內(nèi)核的buffer，由內(nèi)核發(fā)送出去的。windows平臺上為這種情況提供了很好的解決方案，使用TransmitFile接口

BOOL TransmitFile(
    SOCKET hSocket,
    HANDLE hFile,
    DWORD nNumberOfBytesToWrite,
    DWORD nNumberOfBytesPerSend,
    LPOVERLAPPED lpOverlapped,
    LPTRANSMIT_FILE_BUFFERS lpTransmitBuffers,
    DWORD dwFlags
);

你只要把文件句柄發(fā)送給內(nèi)核就行了，內(nèi)核幫你搞定其余的，真正做到Zero-Copy.
但是很不幸，NIO2里AsynchronousSocketChannel沒有提供這樣的支持。而為HTTP Server的性能考量，本人只好自己增加這個支持。

要無縫支持，這個必須得表現(xiàn)的跟 Read /Write一樣，有完成的通知，通知傳送多少數(shù)據(jù)，等等。

仔細(xì)讀完sun的IOCP實現(xiàn)以后發(fā)現(xiàn)這部分工作他們封裝得很好，基本只要往他們的框架里加?xùn)|西就好了。
為了能訪問他們的框架代碼，我定義自己的TransmitFile支持類在sun.nio.ch包里，以獲得最大的權(quán)限。

package sun.nio.ch;

import java.io.IOException;
import java.lang.reflect.Field;
import java.nio.channels.AsynchronousCloseException;
import java.nio.channels.AsynchronousSocketChannel;
import java.nio.channels.ClosedChannelException;
import java.nio.channels.CompletionHandler;
import java.nio.channels.NotYetConnectedException;
import java.nio.channels.WritePendingException;
import java.util.concurrent.Future;

/**
* @author Yvon
*
*/
public class WindowsTransmitFileSupport {

   //Sun's NIO2 channel implementation class
    private WindowsAsynchronousSocketChannelImpl channel;

    //nio2 framework core data structure
    PendingIoCache ioCache;

   //some field retrieve from sun channel implementation class
    private Object writeLock;
    private Field writingF;
    private Field writeShutdownF;
    private Field writeKilledF; // f

    WindowsTransmitFileSupport()
    {
        //dummy one for JNI code
    }

    /**
     *
     */
    public WindowsTransmitFileSupport(
            AsynchronousSocketChannel
             channel) {

        this.channel = (WindowsAsynchronousSocketChannelImpl)channel;
        try {
        // Initialize the fields
            Field f = WindowsAsynchronousSocketChannelImpl.class
                    .getDeclaredField("ioCache");
            f.setAccessible(true);
            ioCache = (PendingIoCache) f.get(channel);
            f = AsynchronousSocketChannelImpl.class
                    .getDeclaredField("writeLock");
            f.setAccessible(true);
            writeLock = f.get(channel);
            writingF = AsynchronousSocketChannelImpl.class
                    .getDeclaredField("writing");
            writingF.setAccessible(true);

            writeShutdownF = AsynchronousSocketChannelImpl.class
                    .getDeclaredField("writeShutdown");
            writeShutdownF.setAccessible(true);

            writeKilledF = AsynchronousSocketChannelImpl.class
                    .getDeclaredField("writeKilled");
            writeKilledF.setAccessible(true);

        } catch (NoSuchFieldException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (SecurityException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (IllegalArgumentException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }


    /**
     * Implements the task to initiate a write and the handler to consume the
     * result when the send file completes.
     */
    private class SendFileTask<V, A> implements Runnable, Iocp.ResultHandler {
        private final PendingFuture<V, A> result;
        private final long file;//file is windows file HANDLE

        SendFileTask(long file, PendingFuture<V, A> result) {
            this.result = result;
            this.file = file;
        }



        @Override
        // @SuppressWarnings("unchecked")
        public void run() {
            long overlapped = 0L;
            boolean pending = false;
            boolean shutdown = false;

            try {
                channel.begin();



                // get an OVERLAPPED structure (from the cache or allocate)
                overlapped = ioCache.add(result);
                int n = transmitFile0(channel.handle, file, overlapped);
                if (n == IOStatus.UNAVAILABLE) {
                    // I/O is pending
                    pending = true;
                    return;
                }
                if (n == IOStatus.EOF) {
                    // special case for shutdown output
                    shutdown = true;
                    throw new ClosedChannelException();
                }
                // write completed immediately
                throw new InternalError("Write completed immediately");
            } catch (Throwable x) {
                // write failed. Enable writing before releasing waiters.
                channel.enableWriting();
                if (!shutdown && (x instanceof ClosedChannelException))
                    x = new AsynchronousCloseException();
                if (!(x instanceof IOException))
                    x = new IOException(x);
                result.setFailure(x);
            } finally {
                // release resources if I/O not pending
                if (!pending) {
                    if (overlapped != 0L)
                        ioCache.remove(overlapped);

                }
                channel.end();
            }

            // invoke completion handler
            Invoker.invoke(result);
        }



        /**
         * Executed when the I/O has completed
         */
        @Override
        @SuppressWarnings("unchecked")
        public void completed(int bytesTransferred, boolean canInvokeDirect) {


            // release waiters if not already released by timeout
            synchronized (result) {
                if (result.isDone())
                    return;
                channel.enableWriting();

                result.setResult((V) Integer.valueOf(bytesTransferred));

            }
            if (canInvokeDirect) {
                Invoker.invokeUnchecked(result);
            } else {
                Invoker.invoke(result);
            }
        }

        @Override
        public void failed(int error, IOException x) {
            // return direct buffer to cache if substituted


            // release waiters if not already released by timeout
            if (!channel.isOpen())
                x = new AsynchronousCloseException();

            synchronized (result) {
                if (result.isDone())
                    return;
                channel.enableWriting();
                result.setFailure(x);
            }
            Invoker.invoke(result);
        }

    }

    public <V extends Number, A> Future<V> sendFile(long file, A att,
            CompletionHandler<V, ? super A> handler) {

        boolean closed = false;
        if (channel.isOpen()) {
            if (channel.remoteAddress == null)
                throw new NotYetConnectedException();


            // check and update state
            synchronized (writeLock) {
                try{
                if (writeKilledF.getBoolean(channel))
                    throw new IllegalStateException(
                            "Writing not allowed due to timeout or cancellation");
                if (writingF.getBoolean(channel))
                    throw new WritePendingException();
                if (writeShutdownF.getBoolean(channel)) {
                    closed = true;
                } else {
                    writingF.setBoolean(channel, true);
                }
                }catch(Exception e)
                {
                    IllegalStateException ise=new IllegalStateException(" catch exception when write");
                    ise.initCause(e);
                    throw ise;
                }
            }
        } else {
            closed = true;
        }

        // channel is closed or shutdown for write
        if (closed) {
            Throwable e = new ClosedChannelException();
            if (handler == null)
                return CompletedFuture.withFailure(e);
            Invoker.invoke(channel, handler, att, null, e);
            return null;
        }

        return implSendFile(file,att,handler);
    }

    <V extends Number, A> Future<V> implSendFile(long file, A attachment,
            CompletionHandler<V, ? super A> handler) {
        // setup task
        PendingFuture<V, A> result = new PendingFuture<V, A>(channel, handler,
                attachment);
        SendFileTask<V,A> sendTask=new SendFileTask<V,A>(file,result);
        result.setContext(sendTask);
        // initiate I/O (can only be done from thread in thread pool)
        // initiate I/O
        if (Iocp.supportsThreadAgnosticIo()) {
            sendTask.run();
        } else {
            Invoker.invokeOnThreadInThreadPool(channel, sendTask);
        }
        return result;
    }

    private native int transmitFile0(long handle, long file,
            long overlapped);

}

這個操作跟默認(rèn)實現(xiàn)的里的write操作是很像的，只是最后調(diào)用的本地方法不一樣。。

接下來，我們怎么使用呢，這個類是定義在sun的包里的，直接用的話，會報IllegalAccessError,因為我們的類加載器跟初始化加載器是不一樣的。
解決辦法一個是通過啟動參數(shù)-Xbootclasspath，讓我們的包被初始加載器加載。我個人不喜歡這種辦法，所以就采用JNI來定義我們的windows TransmitFile支持類。

這樣我們的工作算是完成了，注意，發(fā)送文件的時候傳得是文件句柄，這樣做的好處是你可以更好的控制，一般是在發(fā)送前，打開文件句柄，完成后在回調(diào)通知方法里關(guān)閉文件句柄。

有興趣的同學(xué)可以看看我的HTTP server項目:
http://code.google.com/p/jabhttpd/

目前基本功能實現(xiàn)得差不多，做了些簡單的測試，性能比較滿意。這個服務(wù)器不打算支持servlet api，基本是專門給做基于長連接模式通信的定做的。

posted @ 2009-11-29 15:19 DoubleH 閱讀(2597) | 評論 (2) | 編輯收藏

向上取整的一個應(yīng)用

問題：
有個鏈表（List)，有N個元素，當(dāng)N很大的時候，我們通常想分批處理該鏈表。假如每次處理M條(0<M<=N),那么需要處理幾次才能處理完所有數(shù)據(jù)呢？

問題很簡單，我們需要<N/M>次，這里我們用<>表示向上取整,[]表示向下取整，那么怎么來表示這個值呢？
我們可以證明：
<N/M>=[(N-1)/M]+1 (0<M<=N,M,N∈Z)

不失一般性，我們設(shè)N=Mk+r(0<=r<M),
1）當(dāng)r>0時，

左邊：<N/M>=<(Mk+r)/M>=<k+r/M>=k+<r/M>=k+1
右邊：[(N-1)/M]+1=[(Mk+r-1)/M]+1=[k+(r-1)/M]+1=k+1+[(r-1)/M]=k+1
2）當(dāng)r=0
左邊：<N/M>=k
右邊：[(N-1)/M]+1=[(Mk-1)/M]+1=[(M(k-1)+M-1)/M]+1=[k-1+(M-1)/M]+1=k+[(M-1)/M]=k

命題得證。

有了這個公式，我們在Java代碼里可以這樣計算:

int nn=(N-1)/M +1

.

因為'/'是往下取整的。

posted @ 2009-05-04 11:45 DoubleH 閱讀(3977) | 評論 (4) | 編輯收藏

POJ 3164 最小樹形圖算法

原題：

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 ≤ 10⁴), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair x_i and y_i, 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’.

一開始沒仔細(xì)讀題，一看以為是最小生成樹呢，結(jié)果Krusal算法上去WA了，Prim算法也WA,修修改改一直WA，第二天發(fā)現(xiàn)本題是要在有向圖上面構(gòu)造最小樹形圖。

按照著名的Zhu-Liu算法，仔細(xì)實現(xiàn)了一邊，終于AC了。
按照我的理解總結(jié)下該算法，該算法對每個結(jié)點，除根節(jié)點外尋找最小入邊，
1）如果這些入邊不構(gòu)成環(huán)，那么容易證明這些邊構(gòu)成最小樹形圖。
證明：設(shè)加上根節(jié)點r一共N個點，那么一共有N-1條邊，證明從r能到每個點，若存在一點v，使得從r到v沒有路徑，那么，假設(shè)從v反向回退必然構(gòu)成環(huán)，因為每個點除了r都有入邊，如果不構(gòu)成環(huán)，該路徑可以無窮大。
2）如果存在環(huán)，我們把環(huán)收縮成一個點，更新相應(yīng)的入邊和出邊，得到新的圖G',使得原問題在G'中等效：
怎么收縮呢？
假設(shè)我們把環(huán)收縮成環(huán)上的任意一點v，所有進環(huán)的邊和出環(huán)的邊自動變成v的邊（如果已有，取長度最短的），其余點標(biāo)記為刪除，更新不在環(huán)上的所有點進入該環(huán)的長度cost為cost-cost(prev[x],x);其中點x為進入環(huán)的邊在環(huán)上的端點。出邊保持不變。

這里為什么這么更新？因為這樣更新使得我們的算法在新圖上是等效的。任何環(huán)的解決后意味著在新圖里面得為改收縮后的點尋找新的入邊，而實際的花費應(yīng)該是新的入邊減去原有的入邊長度，我們的算法在找到環(huán)的時候就把環(huán)上所有的邊的長度計算在花費內(nèi)了.而對出邊是沒有影響的。

到這算法的框架基本出來了。當(dāng)為某點沒找到入邊的時候，意味著無解。為了加快無解的偵測，我們先運行一遍DFS搜索，假如從根節(jié)點出發(fā)，可觸及的節(jié)點數(shù)小于N-1(不含r)則意味著無解。反之，肯定有解。
為什么？
因為如果可觸及數(shù)小于N-1,意味著某點是不可觸及的，也就是原圖不是弱連通。對該點來說不存在從r到它的路徑。反之，從r到某點都有一條路徑，沿著該路徑就能找到結(jié)點的入邊。

第二個問題是，如何快速偵測環(huán)呢？
我使用了一個不相交集。回憶Krusal的算法實現(xiàn)里面也是使用不相交集來避免找產(chǎn)生環(huán)的最小邊。

下面是我的代碼：

// 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 閱讀(2426) | 評論 (0) | 編輯收藏

《算法概論》第一章習(xí)題35證明（Wilson定理)

   今天買了本《算法概論》影印注釋版，仔細(xì)看了第一章，果然名不虛傳，很是吸引人。
第一章的習(xí)題難度適中，這里抽出第35題來，這題是證明Wilson定理。
Wilson定理：
   N是一個素數(shù)當(dāng)且僅當(dāng): (N-1)! ≡ -1(mod N)

證明：
首先我們證明若N是素數(shù)，那么等式成立，對于N=2,這是很明顯的。以下證明N>2 的情形。
1）若N是素數(shù)，那么關(guān)于N同余的乘法群G={1,2,3....N-1}
    群G每個元素都有逆元，映射 f:a -> a^-1 ，f(a)=a^-1 是一個一一映射。現(xiàn)在，任取一個元素，它的逆元要么是其它一個元素，或者是它本身。我們假設(shè)其中元素x的逆元是它本身，那么x*x ≡1(mod N) =>(x+1)*(x-1)=K*N,而N是素數(shù)，所以要么x=N-1,要么x=1。也就是說，除了這兩個元素，其它的元素的逆元都是映射到別的元素的。而N>2,是奇數(shù)，所以元素共有N-1個，也就是偶數(shù)個元素。這樣，除了1和N-1外剩余的N-3個元素剛好結(jié)成兩兩一對(x,y)(逆元是唯一的）使得f(x)=y=x^-1,也就是xy≡1(mod N).
現(xià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是素數(shù)，若不然，令 N是和數(shù)。則(N-1)!肯定整除N,因為N的每個因子p滿足p>1,p<N。
   現(xiàn)在令(N-1)!=K1*N.又(N-1)! ≡ -1(mod N) => K1*N ≡ -1(mod N),由同余性質(zhì)知，存在K2使得K1*N+1=K2*N,兩邊同時除以N得K1+1/N=K2.顯然，這是不可能的，所以若(N-1)! ≡ -1(mod N)成立，則N是素數(shù)

證明完畢！

這里用群的概念能夠簡化一定的描述，其實可以完全不用群的概念的，只不過這樣一來，描述更長點，繁瑣點！

posted @ 2009-04-10 22:38 DoubleH 閱讀(2046) | 評論 (1) | 編輯收藏

[算法]09考研數(shù)據(jù)結(jié)構(gòu)試題解法

今天去網(wǎng)上看了一下09年的考研試題，看見該題目(圖片)：

先來定義結(jié)點（為了簡便，省略set/get)：

public class Node
{
public int data;
public Node link;
}

我能想到的兩種解法，一個基于遞歸：

遞歸版的思路就是，基于當(dāng)前結(jié)點，如果后一個是倒數(shù)第K-1,那么當(dāng)前結(jié)點是所求，若不然，返回當(dāng)前是倒數(shù)第幾個。

public int printRKWithRecur(Node head,int k)
    {
        if(k==0||head==null||head.link==null)return 0;
        if(_recurFind(head.link,k)>=k)return 1;
        return 0;
    }
    private final int _recurFind(Node node, int k) {
        if(node.link==null)
        {
            return 1;
        }
        int sRet=_recurFind(node.link,k);
        if(sRet==k-1)
        {
            System.out.println("Got:"+node.data);
            return k;
        }
        return sRet+1;
    }

對每個結(jié)點，該算法都只訪問一次，因此復(fù)雜度O(N).

第二解法，相對遞歸來說，這種方法可以算是消除遞歸版，而且從某種意義上來說比遞歸更高效，跟省空間，遞歸版實際上是把回溯的數(shù)據(jù)存在棧上，而版方法是自己存儲，且利用數(shù)組實現(xiàn)一個循環(huán)隊列，只存儲K個元素。

public static class CycleIntQueue
    {
        int[] datas;
        int top=0;
        int num=0;
        public CycleIntQueue(int n)
        {
            datas=new int[n];
        }

        public void push(int i)
        {
            datas[(top++)%datas.length]=i;
            num++;

        }
        public int numPushed()
        {
            return num;
        }


        public int getButtom()
        {
            return datas[top%datas.length];
        }
    }
    public int printRKWithCycleQueue(Node head,int k)
    {
        if(k==0||head==null)return 0;
        CycleIntQueue queue=new CycleIntQueue(k);
        Node cur=head.link;
        while(cur!=null)
        {
            queue.push(cur.data);
            cur=cur.link;
        }
        if(queue.numPushed()<k)return 0;

        System.out.println("Got:"+queue.getButtom());
        return 1;
    }

本算法，都每個結(jié)點也只放一次，另外進行一次入隊操作，該操作復(fù)雜度O(1),從而，整個算法復(fù)雜度仍是O(N).

posted @ 2009-01-17 13:56 DoubleH 閱讀(2283) | 評論 (5) | 編輯收藏

一個青蛙過河程序及其解析

近日在CSDN上看到中軟一道面試題，挺有意思的。
題目：一條小溪上7塊石頭，如圖所示：

分別有六只青蛙：A，B，C，D，E，F(xiàn)。A，B，C三只蛙想去右岸，它們只會從左向右跳；D，E，F(xiàn)三只蛙想去左岸，它們只會從右向左跳。青蛙每次最多跳到自己前方第2塊石頭上。請問最少要跳幾次所有青蛙上岸。寫出步驟。

這個題是個路徑搜索的問題，在解空間搜索所有的解，并找出最優(yōu)的解法（即步驟最少的）。
那么怎么算是一個解呢？具體而言就是最后石頭上沒有青蛙了。

我們先給題目建模，7塊石頭，其上可以是沒青蛙，可以有一只往左跳的青蛙，也可以有一只往右跳的青蛙。可以把這7塊石頭看成一個整體，來表示一個狀態(tài)。這里我們把這7塊石頭看成一個數(shù)組，里面只能有0,1,2三種值，這樣表示，那么初始時為：

1,1,1,0,2,2,2

我們把它再表示成一個數(shù)字，來表示狀態(tài)值，這個值把這個數(shù)組按三進制拼成一個數(shù)字，我們用一個輔助函數(shù)來做這件事情：

private final int makeS() {

        int r=0;
        int p=1;
        for(int i=0;i<7;i++)
        {
            r+=p*states[i];
            p*=3;
        }
        return r;
    }

那么題目現(xiàn)在變成從狀態(tài)111022轉(zhuǎn)換成狀態(tài)0000000，所需最少的步驟.

那么狀態(tài)是怎樣轉(zhuǎn)換的呢？
很顯然。，每次青蛙跳都會觸發(fā)狀態(tài)的轉(zhuǎn)換，我們在每個狀態(tài)時搜索每種可能的轉(zhuǎn)換，我們記初始狀態(tài)為S(S等于三進制111022）記要求解的值為OPT(S),假如可以轉(zhuǎn)換到t1,t2,...tk.
那么，顯然

OPT(S)=min(1+OPT(t1),1+OPT(t2),

.,1+OPT(tk));

另外，由于最終狀態(tài)為0,所以O(shè)PT(0)=0,就是說已經(jīng)在最終狀態(tài)了，就不需要一步就可以了。
有了上面這個等式，我們可以遞歸求解了，但是如果單純的遞歸，會導(dǎo)致大量的重復(fù)計算，所以這里我們用備忘錄的方法，記下已經(jīng)求解出來的OPT(x),放在一個數(shù)組里，由于只有7塊石頭，所以最多我們需要3^7=2187個狀態(tài)。我們用一個2187個元素的數(shù)組, 其中第i個元素表示OPT(i)，初始化每個元素用-1表示還未求解。OPT(0) 可直接初始化為0.

到此我們還有一個問題，怎么能夠在算法結(jié)束的時候打印出最優(yōu)的步驟呢？按照這個步驟，我們可以重建出青蛙是如何在最優(yōu)的情況下過河的。為此，我們可以再用一個步驟數(shù)組，每次在采取最優(yōu)步驟的時候記錄下來。

整個算法如下：

package test;

import java.util.Arrays;
/**
*
* @author Yovn
*
*/
public class FrogJump {

    private int steps[];
    private int states[];


    private static class Step
    {
        int offset=-1;
        int jump;
        int jumpTo;
    }


    private Step jumps[];
    private int initS;
    public FrogJump()
    {
        steps=new int[81*27];
        states=new int[7];
        for(int i=0;i<3;i++)states[i]=1;
        for(int i=4;i<7;i++)states[i]=2;
        Arrays.fill(steps, -1);
        steps[0]=0;
        jumps=new Step[81*27];
        initS=makeS();
    }

    public int shortestSteps(int s)
    {
        if(steps[s]==-1)
        {

            int minStep=Integer.MAX_VALUE;
            Step oneStep=new Step();
            for(int i=0;i<7;i++)
            {
                if(states[i]==1)
                {
                    if(i>4)
                    {
                        states[i]=0;
                        minStep = recurFind(minStep,oneStep,i,7-i);
                        states[i]=1;
                    }
                    else
                    {
                        if(states[i+1]==0)
                        {
                            states[i]=0;
                            states[i+1]=1;
                            minStep = recurFind(minStep,oneStep,i,1);
                            states[i]=1;
                            states[i+1]=0;

                        }
                        if(states[i+2]==0)
                        {
                            states[i]=0;
                            states[i+2]=1;
                            minStep = recurFind(minStep,oneStep,i,2);
                            states[i]=1;
                            states[i+2]=0;

                        }
                    }
                }
                else if(states[i]==2)
                {
                    if(i<2)
                    {
                        states[i]=0;

                        minStep = recurFind(minStep,oneStep,i,-1-i);
                        states[i]=2;
                    }
                    else
                    {
                        if(states[i-1]==0)
                        {
                            states[i]=0;
                            states[i-1]=2;
                            minStep = recurFind(minStep,oneStep,i,-1);
                            states[i]=2;
                            states[i-1]=0;

                        }
                        if(states[i-2]==0)
                        {
                            states[i]=0;
                            states[i-2]=2;
                            minStep = recurFind(minStep,oneStep,i,-2);
                            states[i]=2;
                            states[i-2]=0;

                        }
                    }
                }

            }
            steps[s]=minStep;
            jumps[s]=oneStep;


        }
        return steps[s];

    }

    private final int recurFind(int minStep, Step oneStep, int pos, int jump) {
        int toS=makeS();
        int r=shortestSteps(toS);
        if(r<minStep-1)
        {
            oneStep.jump=jump;
            oneStep.offset=pos;
            oneStep.jumpTo=toS;
            minStep=r+1;
        }
        return minStep;
    }



    public void printPath()
    {
        int s=initS;
        int i=1;

        while(s!=0)
        {


            System.out.println("["+(i++)+"] Frog at #"+jumps[s].offset+" jumps #"+jumps[s].jump);
            s=jumps[s].jumpTo;

        }
    }
    private final int makeS() {

        int r=0;
        int p=1;
        for(int i=0;i<7;i++)
        {
            r+=p*states[i];
            p*=3;
        }
        return r;
    }

    /**
    * @param args
    */
    public static void main(String[] args) {
        FrogJump fj=new FrogJump();
        int steps=fj.shortestSteps(fj.initS);

        System.out.println("use "+steps+" steps!");
        fj.printPath();

    }

}

運行結(jié)果：

use 21 steps!
[1] Frog at #2 jumps #1
[2] Frog at #4 jumps #-2
[3] Frog at #5 jumps #-1
[4] Frog at #3 jumps #2
[5] Frog at #1 jumps #2
[6] Frog at #0 jumps #1
[7] Frog at #2 jumps #-2
[8] Frog at #0 jumps #-1
[9] Frog at #4 jumps #-2
[10] Frog at #2 jumps #-2
[11] Frog at #0 jumps #-1
[12] Frog at #5 jumps #2
[13] Frog at #3 jumps #2
[14] Frog at #1 jumps #2
[15] Frog at #5 jumps #2
[16] Frog at #3 jumps #2
[17] Frog at #5 jumps #2
[18] Frog at #6 jumps #-1
[19] Frog at #5 jumps #-2
[20] Frog at #3 jumps #-2
[21] Frog at #1 jumps #-2

posted @ 2009-01-06 22:27 DoubleH 閱讀(4054) | 評論 (3) | 編輯收藏

Java雜家

公告

常用鏈接

留言簿(15)

隨筆分類

隨筆檔案

相冊

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜