`E81086713E446D36F62B2AA2A3502B5EB155`

Java杂家

BlogJava 首页 新随笔 联系 聚合 管理
 40 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 阅读(1630) | 评论 (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`’.

1）如果这些入边不构成环，那么容易证明这些边构成最小树形图。

2）如果存在环，我们把环收缩成一个点，更新相应的入边和出边，得到新的图G',使得原问题在G'中等效：

// 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 阅读(2298) | 评论 (0)编辑 收藏

今天买了本《算法概论》影印注释版，仔细看了第一章，果然名不虚传，很是吸引人。

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

这样，我们证明了一个方向了，下面我们证明另一个方向

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 阅读(1816) | 评论 (1)编辑 收藏

2011年12月1日 #

/**
*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 阅读(1630) | 评论 (2)编辑 收藏

2011年2月6日 #

摘要: 年过的差不多了，今天偶尔兴起上HOJ上翻几道DP练手的题来。。。，顺便把代码贴下留念  1.数塔 Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->/**  *   */ pack...  阅读全文
posted @ 2011-02-06 21:13 DoubleH 阅读(1901) | 评论 (0)编辑 收藏

2009年12月4日 #

摘要: 前一篇博客，我简单提了下怎么为NIO2增加TransmitFile支持，文件传送吞吐量是一个性能关注点，此外，并发连接数也是重要的关注点。 不过JDK7中又一次做了简单的实现，不支持同时投递多个AcceptEx请求，只支持一次一个，返回后再投递。这样，客户端连接的接受速度必然大打折扣。不知道为什么sun会做这样的实现，WSASend()/WSAReceive()一次只允许一个还是可以理解，...  阅读全文
posted @ 2009-12-04 17:57 DoubleH 阅读(3680) | 评论 (6)编辑 收藏

2009年11月29日 #

JDK7的NIO2特性或许是我最期待的，我一直想基于它写一个高性能的Java Http Server.现在这个想法终于可以实施了。

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

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

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)

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

<extends Number, A> Future<V> implSendFile(long file, A attachment,
CompletionHandler
<V, ? super A> handler) {

PendingFuture<V, A> result = new PendingFuture<V, A>(channel, handler,
attachment);

// initiate I/O (can only be done from thread in thread pool)

// initiate I/O
}
else {
}

return result;
}

private native int transmitFile0(long handle, long file,

long overlapped);

}

posted @ 2009-11-29 15:19 DoubleH 阅读(2404) | 评论 (2)编辑 收藏

2009年5月4日 #

<N/M>=[(N-1)/M]+1    (0<M<=N,M,N∈Z)

1）当r>0时，

2）当r=0

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

posted @ 2009-05-04 11:45 DoubleH 阅读(3756) | 评论 (4)编辑 收藏

2009年4月24日 #

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`’.

1）如果这些入边不构成环，那么容易证明这些边构成最小树形图。

2）如果存在环，我们把环收缩成一个点，更新相应的入边和出边，得到新的图G',使得原问题在G'中等效：

// 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 阅读(2298) | 评论 (0)编辑 收藏

2009年4月10日 #

今天买了本《算法概论》影印注释版，仔细看了第一章，果然名不虚传，很是吸引人。

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

这样，我们证明了一个方向了，下面我们证明另一个方向

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 阅读(1816) | 评论 (1)编辑 收藏

2009年1月17日 #

public class Node
{

public int data;

}

public int printRKWithRecur(Node head,int k)
{

return 0;
}

private final int _recurFind(Node node, int k) {

{

return 1;
}

if(sRet==k-1)
{
System.out.println(
"Got:"+node.data);

return k;
}

return sRet+1;
}

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

CycleIntQueue queue
=new CycleIntQueue(k);
Node cur

while(cur!=null)
{
queue.push(cur.data);
cur
}

if(queue.numPushed()<k)return 0;

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

return 1;
}

posted @ 2009-01-17 13:56 DoubleH 阅读(2052) | 评论 (5)编辑 收藏

2009年1月6日 #

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

OPT(S)=min(1+OPT(t1),1+OPT(t2),.,1+OPT(tk));

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 阅读(3726) | 评论 (3)编辑 收藏

2008年12月10日 #

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 阅读(3061) | 评论 (8)编辑 收藏