日韩一区欧美一区,成人免费视频视频,国产精品18久久久久久久久久久久

如題：求連續正整數使得其和為給定的一個正整數

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

實現代碼如下：

/**
*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.數塔 Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->/** * */ pack... 閱讀全文

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

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

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

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

JDK7 NIO2 實踐: 增加 TransmitFile支持

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

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

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

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

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

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

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

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);

}

這個操作跟默認實現的里的write操作是很像的，只是最后調用的本地方法不一樣。。

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

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

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

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

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

向上取整的一個應用

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

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

不失一般性，我們設N=Mk+r(0<=r<M),
1）當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）當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’.

一開始沒仔細讀題，一看以為是最小生成樹呢，結果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 閱讀(2426) | 評論 (0) | 編輯收藏

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

   今天買了本《算法概論》影印注釋版，仔細看了第一章，果然名不虛傳，很是吸引人。
第一章的習題難度適中，這里抽出第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 閱讀(2046) | 評論 (1) | 編輯收藏

[算法]09考研數據結構試題解法

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

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

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

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

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

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;
    }

對每個結點，該算法都只訪問一次，因此復雜度O(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;
    }

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

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

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

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

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

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

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

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

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

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;
    }

那么題目現在變成從狀態111022轉換成狀態0000000，所需最少的步驟.

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

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

.,1+OPT(tk));

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

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

整個算法如下：

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();

    }

}

運行結果：

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) | 編輯收藏

【分享】今日某公司的電話面試題

寫一個函數，輸出前N個數（從7開始），這N個數滿足如下3個條件中的任意一個
1.整出7
2.各位上的數字之和整除7，(比如34)
3.任意位上包含數字7

附我的代碼：

void printN(int n)
{


    int c=0;
    int i=7;
    do
    {
        if(i%7 ==0)
        {
            printf("%d\n",i);
            c++;
        }
        else
        {
            int j=i%10;
            int k=j;
            int s=k;
            int p=10;
            while(k<i)
            {

                if(j==7)
                {
                    printf("%d\n",i);
                    s=0;
                    c++;
                    break;

                }
                else
                {
                    j=((i-k)/p)%10;
                    s+=j;
                    k=j*p+k;
                    p*=10;

                }
            }
            if(s&&s%7==0)
            {

                printf("%d\n",i);
                c++;
            }


        }
        i++;
    } while (c<n);
}

posted @ 2008-12-10 21:44 DoubleH 閱讀(3227) | 評論 (8) | 編輯收藏

Java雜家

公告

常用鏈接

留言簿(15)

隨筆分類

隨筆檔案

相冊

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜