在C++的sort排序中永远让比较函数对相等的值返回false

發表於 2014-03-24

很久之前，线上的程序跑着跑着，莫名其妙的就coredump了，找了很久都不知道原因。因为coredump的次数不是很多，有时好几天了也才dump了一次，所以也很难确定是在哪个地方出错了。通过版本回溯，慢慢缩小了出错的范围，可是我还是不知道在哪里出错了，直到今天晚上组长和我说了可能出错的地方，才知道原来有这么一个坑存在。

他说使用sort排序时，比较函数编写时，如果两个值相等返回true可能会存在问题，于是我看了自己写的，两个值相等时，正是返回true.

1
2
3

int cmp(const int &a, const int &b) {
    return a >= b;
}

可是我还是看不出这里有什么错误，google之后找到了解答,在一篇文章里说到，当排序的个数超过16个时，且这些书数全部相等时，如果比较函数在两个值相等返回true时就会出错。这是因为sort行数的实现中，当超过16个数时，使用快速排序，而且假定一定存在两个数不相等。具体可参看http://blog.sina.com.cn/s/blog_79d599dc01012m7l.html

联系作者

安装Maven

By robinjia

發表於 2014-03-08

很早之前，在写第一个Servlet时，一直配置不成功，写一个Hello World!都成问题，于是转而奔向PHP，最近由于工作需要，要重新拾起Java那套东西。因为是用Maven做的管理，于是要安装Maven，到网上找参考资料，竟没安装好，于是到官网找解答，最终找到。

安装Maven之前，已经假设你安装好JDK.有一点需要注意的是,Maven3.2要求JDK1.6及以上,Maven3.0/3.1则要求JDK1.5及以上，否则会出现版本错误

1.下载Maven

到官网http://maven.apache.org/下载Maven,当前最新稳定版本为3.2.1

对于Windows系统，下载Maven 3.2.1 (Binary zip)

2.解压Maven,配置环境变量

将Maven解压，这里假设放在d:\apache-maven-3.2.1

之后进行环境变量配置，

在系统变量中增加M2_HOME,值为d:\apache-maven-3.2.1

在系统变量中增加M2,值为%M2_HOME%\bin

如果已经存在用户变量Path，则在值的前面增加%M2%；注意一定要加上这个分号

如果不存在用户变量Path,则新建它，并赋值为%M2%

3.测试Maven

在命令行中执行mvn –version，在我的电脑上显示如下,

Apache Maven 3.2.1 (ea8b2b07643dbb1b84b6d16e1f08391b666bc1e9; 2014-02-15T01:37:5

2+08:00)

Maven home: d:\apache-maven-3.2.1

Java version: 1.6.0_15, vendor: Sun Microsystems Inc.

Java home: D:\Java\jdk1.6.0\jre

Default locale: zh_CN, platform encoding: GBK

OS name: “windows 7”, version: “6.1”, arch: “x86”, family: “windows”

如果不是这样，看看环境变量是否配置正确，以及JDK版本是否匹配

4.Eclipse的Maven插件安装

在插件安装上，网上的资料很多已经过时了，因为都是很早之前的链接。顺着官网找到了eclipse的Maven插件安装链接http://download.eclipse.org/technology/m2e/releases/

我用的是Eclipse Kepler.在Help->Install new software中，将以上安装链接加入，名字为Maven，之后即可下载插件

5.配置Maven插件

在Window->Preferences中,选择Maven

点击Installations,此时还是用插件自带的Maven版本3.0.4,而且Global settings是空的我们需要添加自己安装的版本，点击Add,打开D:\apache-maven-3.2.1即可，最终结果如下：

此时Maven插件将会使用安装的Maven3.2.1版本

之后点击User Settings,可以看到如下结果

这里也许最让你迷惑的是这三个概念，Global Settings, User Settings,以及Local Repository。因为我也未深入理解，所以也只能在这里说说我的理解。简单来说，

Global Settings就是一些全局设置，设置了中央jar仓库的位置等等.

User Settings设置了用户私有jar仓库的位置等等.

Local Repository是本地jar仓库的位置.

假设你现在在开发一个应用，它需要使用一个jar,则Maven会先到Local Repository中寻找，如果没找到这个jar,则它会到User Settings中设置的用户私有jar仓库中查找，如果还是没找到，则到Global Settings设置的中央jar仓库中查找，如果还是没找到，Maven将报错，指示jar未找到。

网上还有介绍另外一种方法，也就是先去下载Eclipse的Maven插件，之后再将插件导入到Eclipse, 只是因为直接用URL的方法已经解决了安装问题，所以没有尝试。

6.Hello World例子

之后用《Maven by Example》中的一个例子来介绍安装介绍。命令行进入Eclipse工作目录，我这里是d:\workspace,执行以下命令

mvn archetype:generate -DgroupId=org.sonatype.mavenbook -DartifactId=simple -Dpackage=org.sonatype.mavenbook -Dversion=1.0-SNAPSHOT

之后敲几次回车，一个最简单的HelloWorld项目就建立好了。

之后cd simple进入simple目录，如果你有兴趣，可以看看Maven生成的内容，

其目录结构如下

simple/

simple/pom.xml

simple/src/main

simple/src/main/java

simple/src/test

simple/src/test/java

其中src/main存放源文件,src/test存放测试文件,pom.xml为Maven提供编译信息，

执行mvn install，编译,测试，打包项目

执行java -cp target/simple-1.0-SNAPSHOT.jar org.sonatype.mavenbook.App

看到输出的 Hello World！

事实上，在命令行中，一个困惑是如何选择新建项目的类型，命令行里一共列出了九百多种，而很难知道哪个编号对应的是哪一种项目类型。

关于Maven的更多内容可以去sonatype官网下载《Maven by Example》,绝对值得一看。

参考文章：

http://www.blogjava.net/fancydeepin/archive/2012/07/13/eclipse_maven3_plugin.html

联系作者

用select实现精确定时器

By robinjia

發表於 2013-12-26

之前为了找出Sphinx中index ‘test1’: search error: query too complex, not enough stack (thread_stack=1217498K or higher required)这个bug,大致看了一下Sphinx的源码，发现问题的原因是在计算线程使用的空间时出错，具体原因依然没有找到，还在努力当中。在这个过程中，看到以下这段程序

void sphSleepMsec ( int iMsec )
{
    if ( iMsec<0 )
        return;

#if USE_WINDOWS
    Sleep ( iMsec );

#else
    struct timeval tvTimeout;
    tvTimeout.tv_sec = iMsec / 1000; // full seconds
    tvTimeout.tv_usec = ( iMsec % 1000 ) * 1000; // remainder is msec, so *1000 for usec

    select ( 0, NULL, NULL, NULL, &tvTimeout ); // FIXME? could handle EINTR
#endif
}

其实就是一个毫秒定时器，《UNIX环境编程》第14章的习题就要求实现一个这样的函数。看这段程序，又是令人恶心的匈牙利命名，把它改为正常点的比较好。程序中的注释”//FIXME?could handle EINR”说的是select会被SIGINT信号中断，那么这个定时器也会因为这个原因而被中断信号中断，看看能否提供不被中断的方法。立刻就想到了忽略中断信号，试了一下，其实还是挺容易的。难道这种直接忽略中断信号还是存在问题？

#include <sys/select.h>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
void sleep_ms(int msec) {//睡眠msec毫秒
    if (msec < 0)
        return;
    signal(SIGINT, SIG_IGN);
    struct timeval tv; 
    tv.tv_sec = msec / 1000;//除以1000，得到秒数
    tv.tv_usec = (msec % 1000) * 1000;//得到剩余的毫秒数，之后乘以1000得到微秒数
    select(0, NULL, NULL, NULL, &tv);
}
int main() {
    printf("start sleeping\n");
    sleep_ms(4000);
    printf("finish sleeping\n");
    return 0;
}

联系作者

用epoll提供telnet服务的代码(续)

By robinjia

發表於 2013-12-26

最终的代码如下，这里修正了对nc命令无法处理的问题

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <fcntl.h>
#include <arpa/inet.h>
#include <sys/epoll.h>
#include <stdlib.h>
#include <netinet/tcp.h> 
#include <ctype.h>
#include <assert.h>
#define MAX_EVENTS 10
#define PORT 9999
//从buf中得到命令
void _get_command(char *buf, char *cmd) {
    int i = 0;
    int j = 0;
    while (!isalpha(buf[i]))
        i++;
    while (buf[i] != '\0' && buf[i] != ' ' && buf[i] != '\r' && buf[i] != '\n') {
        cmd[j++] = buf[i];
        i++;
    }
    cmd[j] = '\0';
}
// 返回成功发送的字节数
int Send(int sock, void *buffer, int size)
{
    int nsend = 0, total = 0;
    int err;
    if(NULL == buffer || 0 == size) {
        return 0;
    }
    while(size > 0) {
        nsend = write(sock, (char*)buffer + total, size);
        if(nsend == -1) {
            err = errno;
            if(EINTR == err) {
                printf("send data to socket[%d], error is %s[%d]\n", 
                            sock, strerror(err), err);
            } else {
                printf("Fail to send data to socket[%d], error is %s[%d]", 
                            sock, strerror(err), err);
                return -1;    
            }
        } else {
            total += nsend;
            size -= nsend;
        }
    }
    return total;
}
//处理重置命令
void process_reset(int sock){
    char mess[] = "reset successful\r\n";
    Send(sock, mess, strlen(mess));
    return;
}
//处理错误命令
void process_error(int sock) {
    char error[] = "ERROR\r\n";
    Send(sock, error, strlen(error));
    return;
}
void process_stats(int sock){
    char mess[] = "stats successful\r\n";
    Send(sock, mess, strlen(mess));
    return;
}

//处理退出命令
void process_quit(int sock) {
    close(sock);
}

int process_command(int sock, char *buf) {
    assert(buf != NULL);

    /*char cmd[BUFSIZ];
    _get_command(buf, cmd);    
    printf("command: %s\n", cmd);

    if (strcmp("stats",cmd) == 0) {
        process_stats(sock);
    } else if (strcmp("reset", cmd) == 0) {
        process_reset(sock);
    } else if (strcmp("quit", cmd) == 0){
        process_quit(sock);
    } else {
        process_error(sock);
    }*/
    Send(sock, buf, strlen(buf));

    return 0;
}

//设置socket为非阻塞
void setnonblocking(int sockfd) {
    int opts;
    opts = fcntl(sockfd, F_GETFL);
    if (opts < 0) {
        perror("fcntl(F_GETFL)\n");
        exit(1);
    }
    opts = (opts | O_NONBLOCK);
    if (fcntl(sockfd, F_SETFL, opts) < 0) {
        perror("fcntl(F_SETFL)\n");
        exit(1);
    }
}
int main() {
    int listenfd, conn_sock, epfd;
    char buf[BUFSIZ];
    socklen_t clilen;
    struct sockaddr_in cliaddr, servaddr;
    struct epoll_event ev, events[MAX_EVENTS];
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd < 0) {
        printf("create socket error\n");
        return -1;
    }
    int on = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on));
    setnonblocking(listenfd);
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(PORT);

    if(bind(listenfd,(struct sockaddr*)&servaddr,sizeof(struct sockaddr))<0){
        printf("bind error\n");
        close(listenfd);
        return -1;
    }

    if(listen(listenfd, 5) < 0) {
        printf("listen error\n");
        close(listenfd);
        return -1; 
    }
    epfd = epoll_create(MAX_EVENTS); //生成epoll专用的文件描述符
    if (epfd == -1) {
        printf("epoll_create\n");
        return -1;
    }
    ev.events = EPOLLIN | EPOLLET; //设置处理的事件类型,设置为边沿触发
    ev.data.fd = listenfd;
    if (epoll_ctl(epfd, EPOLL_CTL_ADD, listenfd, &ev) == -1) {
        printf("epoll_ctl add listen_sock fail\n");
        close(listenfd);
        return -1;
    }
    while (1) {
        int timeout = 1000; 
        int nfds = epoll_wait(epfd, events, MAX_EVENTS, timeout);
        if (nfds == -1) {
            printf("epoll_wait\n");
            return -1;
        }
        for (int i = 0;i < nfds; ++i) {
            int fd = events[i].data.fd;
            if (fd == listenfd) { //监听事件
                while ((conn_sock = accept(listenfd, NULL, NULL)) > 0) {//循环处理accept,这样可以处理多个连接在就绪队列中的情况
                    printf("accept %d\n", conn_sock);
                    setnonblocking(conn_sock);
                    ev.events = EPOLLIN | EPOLLET; //设置为边沿触发
                    ev.data.fd = conn_sock;
                    if (epoll_ctl(epfd, EPOLL_CTL_ADD, conn_sock, &ev) == -1) {
                        printf("epoll_ctl: add fail\n");
                        close(conn_sock);
                        return -1;
                    }
                }
            } else if (events[i].events & EPOLLIN) {//读事件，说明有数据从客户端发来
                int n = 0;
                int nread = 0;
                while ((nread = read(fd, buf + n, BUFSIZ - n)) > 0) {
                    n += nread;
                }
                //printf("n %d nread %d\n", n, nread);
                if (nread == -1 && errno != EAGAIN) {//读数据错误,关闭描述符
                    printf("read error\n");
                    close(fd); //关闭一个描述符，它会从epoll描述符集合中自动删除
                    continue;
                }
                if( n > 0) {
                    process_command(fd, buf);
                    memset(buf, 0, sizeof(buf));
                }
                if(nread == 0) { //客户端关闭连接，关闭相应的描述符
                    close(fd);
                    continue;
                }
            }
        }
    }
}

联系作者

用epoll提供telnet服务的代码

By robinjia

發表於 2013-12-25

这是之前写的用epoll提供telnet服务的代码。

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <fcntl.h>
#include <arpa/inet.h>
#include <sys/epoll.h>
#include <stdlib.h>
#include <netinet/tcp.h> 
#include <ctype.h>
#include <assert.h>
#define MAX_EVENTS 10
#define PORT 9999
//从buf中得到命令
void _get_command(char *buf, char *cmd) {
    int i = 0;
    int j = 0;
    while (!isalpha(buf[i]))
        i++;
    while (buf[i] != '\0' && buf[i] != ' ' && buf[i] != '\r' && buf[i] != '\n') {
        cmd[j++] = buf[i];
        i++;
    }
    cmd[j] = '\0';
}
// 返回成功发送的字节数
int Send(int sock, void *buffer, int size)
{
    int nsend = 0, total = 0;
    int err;
    if(NULL == buffer || 0 == size) {
        return 0;
    }
    while(size > 0) {
        nsend = write(sock, (char*)buffer + total, size);
        if(nsend == -1) {
            err = errno;
            if(EINTR == err) {
                printf("send data to socket[%d], error is %s[%d]\n", 
                            sock, strerror(err), err);
            } else {
                printf("Fail to send data to socket[%d], error is %s[%d]", 
                            sock, strerror(err), err);
                return -1;    
            }
        } else {
            total += nsend;
            size -= nsend;
        }
    }
    return total;
}
//处理重置命令
void process_reset(int sock){
    char mess[] = "reset successful\r\n";
    Send(sock, mess, strlen(mess));
    return;
}
//处理错误命令
void process_error(int sock) {
    char error[] = "ERROR\r\n";
    Send(sock, error, strlen(error));
    return;
}
void process_stats(int sock){
    char mess[] = "stats successful\r\n";
    Send(sock, mess, strlen(mess));
    return;
}

//处理退出命令
void process_quit(int sock) {
    close(sock);
}

int process_command(int sock, char *buf) {
    assert(buf != NULL);

    /*char cmd[BUFSIZ];
    _get_command(buf, cmd);    
    printf("command: %s\n", cmd);

    if (strcmp("stats",cmd) == 0) {
        process_stats(sock);
    } else if (strcmp("reset", cmd) == 0) {
        process_reset(sock);
    } else if (strcmp("quit", cmd) == 0){
        process_quit(sock);
    } else {
        process_error(sock);
    }*/
    Send(sock, buf, strlen(buf));

    return 0;
}

//设置socket为非阻塞
void setnonblocking(int sockfd) {
    int opts;
    opts = fcntl(sockfd, F_GETFL);
    if (opts < 0) {
        perror("fcntl(F_GETFL)\n");
        exit(1);
    }
    opts = (opts | O_NONBLOCK);
    if (fcntl(sockfd, F_SETFL, opts) < 0) {
        perror("fcntl(F_SETFL)\n");
        exit(1);
    }
}
int main() {
    int listenfd, conn_sock, epfd;
    char buf[BUFSIZ];
    socklen_t clilen;
    struct sockaddr_in cliaddr, servaddr;
    struct epoll_event ev, events[MAX_EVENTS];
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd < 0) {
        printf("create socket error\n");
        return -1;
    }
    int on = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on));
    setnonblocking(listenfd);
    struct linger {
        int l_onoff; /* 0 = off, nozero = on */
        int l_linger; /* linger time */
    }lin;
    lin.l_onoff = 1;
    lin.l_linger = 0;
    setsockopt(listenfd, SOL_SOCKET, SO_LINGER, (char*)&lin, sizeof(lin));
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(PORT);

    if(bind(listenfd,(struct sockaddr*)&servaddr,sizeof(struct sockaddr))<0){
        printf("bind error\n");
        close(listenfd);
        return -1;
    }

    if(listen(listenfd, 5) < 0) {
        printf("listen error\n");
        close(listenfd);
        return -1; 
    }
    epfd = epoll_create(MAX_EVENTS); //生成epoll专用的文件描述符
    if (epfd == -1) {
        printf("epoll_create\n");
        return -1;
    }
    ev.events = EPOLLIN | EPOLLET; //设置处理的事件类型,设置为边沿触发
    ev.data.fd = listenfd;
    if (epoll_ctl(epfd, EPOLL_CTL_ADD, listenfd, &ev) == -1) {
        printf("epoll_ctl add listen_sock fail\n");
        close(listenfd);
        return -1;
    }
    while (1) {
        int timeout = 1000; 
        int nfds = epoll_wait(epfd, events, MAX_EVENTS, timeout);
        if (nfds == -1) {
            printf("epoll_wait\n");
            return -1;
        }
        for (int i = 0;i < nfds; ++i) {
            int fd = events[i].data.fd;
            if (fd == listenfd) { //监听事件
                while ((conn_sock = accept(listenfd, NULL, NULL)) > 0) {//循环处理accept,这样可以处理多个连接在就绪队列中的情况
                    printf("accept %d\n", conn_sock);
                    setnonblocking(conn_sock);
                    ev.events = EPOLLIN | EPOLLET; //设置为边沿触发
                    ev.data.fd = conn_sock;
                    if (epoll_ctl(epfd, EPOLL_CTL_ADD, conn_sock, &ev) == -1) {
                        printf("epoll_ctl: add fail\n");
                        close(conn_sock);
                        return -1;
                    }
                }
            } else if (events[i].events & EPOLLIN) {//读事件，说明有数据从客户端发来
                int n = 0;
                int nread = 0;
                while ((nread = read(fd, buf + n, BUFSIZ - n)) > 0) {
                    n += nread;
                }
                if (nread == -1 && errno != EAGAIN) {//读数据错误,关闭描述符
                    printf("read error\n");
                    close(fd); //关闭一个描述符，它会从epoll描述符集合中自动删除
                    continue;
                }
                if(nread == 0) { //客户端关闭连接，关闭相应的描述符
                    close(fd);
                    continue;
                }
                if( n > 0) {
                    process_command(fd, buf);
                    memset(buf, 0, sizeof(buf));
                }
            }
        }
    }
}

联系作者

欧拉工程-问题58

By robinjia

發表於 2013-09-02

原题链接http://projecteuler.net/problem=58

Spiral primes

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ~ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

螺旋素数
从1开始以如下方式逆时针螺旋，可以得到一个大小为7的螺旋方块

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

有趣的是奇数的平方都在对角线的右下角，更有趣的是，13个位于对角线的数中，有8个是素数；比率是8/13 约等于 62%。

如果像上面的螺旋那样再加一层螺旋，将得到一个大小为9的螺旋方块。如果这个步骤一直持续下去，当螺旋方块的大小为多少时，对角线上的素数比率会小于10%？

解答：
表示对角线上的数与第28题相同，最难的部分是判定一个数是否是素数，用动态生成素数表的方法不行，太大了。最后找到了米勒-拉宾素数测试法，很快。等以后有空时专门写一篇关于素数判定方法。

联系作者

欧拉工程-问题57

By robinjia

發表於 2013-09-02

原题链接http://projecteuler.net/problem=57

Square root convergents

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

sqrt( 2) = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

平方根收敛

有可能将2的平方根表示成无限分数：

sqrt(2) = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

扩展这个式子的前四项，我们得到

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

之后的三项是99/70，239/169，和577/408，对于第八项，1393/985，是第一个分子中的数字个数超过分母中的数字个数的项

在前1000项中，一共有多少个分数是分子中的数字个数超过分母的？

解答：

就是如何表示分数，之后定义分数的加法，不难。

联系作者

欧拉工程-问题56

By robinjia

發表於 2013-08-25

原题链接http://projecteuler.net/problem=56

Powerful digit sum

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

幂方数字和
古戈尔 (10¹⁰⁰)是一个天文数字：1后面跟着100个零；100¹⁰⁰更是不可想象的大:1后面跟着200个零。尽管它们非常大，但是它们的数字和为1.

求幂方a^b中，a,b < 100,最大的数字和
解法：
暴力吧。

联系作者

欧拉工程-问题55

By robinjia

發表於 2013-08-25

原题链接http://projecteuler.net/problem=55

Lychrel numbers

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.
利克瑞尔数

如果我们取47，将它逆序并求和，47 + 74 = 121，是一个回文数。
并不是所有的数都可以这么快产生回文数。例如
349 + 943 = 1292，
1292 + 2921 = 4213
4213 + 3124 = 7337
也就是说，349用了3此迭代得到一个回文数。
虽然至今没有人证明，但是有猜想认为一些数，如196，永远不产生回文数。一个数通过逆序和迭代如果永远不产生回文数则称为利克瑞尔数。因为这些数的理论本质以及方便这个问题的目的，我们假设一个数是利克瑞尔数，直到证明不是。另外，对于每个小于10000的数，给定两种可能，它或者是(i)在小于50次迭代变成循环数(ii)没有一个人，在有限的计算能力下，能够将它迭代到一个回文数。事实上，10677是第一个超过50次迭代产生回文数：4668731596684224866951378664(53次迭代，28位数)
令人惊奇的是，有一些回文数自身也是利克瑞尔数，第一个例子是4994.
求10000以下一共有多少个利克瑞尔数？
注意：为了强调利克瑞尔数的理论一些性质，一些单词于2007.4.24更改

解答：
没什么，遍历。

联系作者

欧拉工程-问题54

By robinjia

發表於 2013-08-22

原题链接 http://projecteuler.net/problem=54

Poker hands

In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:

High Card: Highest value card.
One Pair: Two cards of the same value.
Two Pairs: Two different pairs.
Three of a Kind: Three cards of the same value.
Straight: All cards are consecutive values.
Flush: All cards of the same suit.
Full House: Three of a kind and a pair.
Four of a Kind: Four cards of the same value.
Straight Flush: All cards are consecutive values of same suit.
Royal Flush:Ten, Jack, Queen, King, Ace, in same suit.
The cards are valued in the order:
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.

Consider the following five hands dealt to two players:

Hand	Player 1	Player 2	Winner
1	5H 5C 6S 7S KD Pair of Fives	2C 3S 8S 8D TD Pair of Eights	Player 2
2	5D 8C 9S JS AC Highest card Ace	2C 5C 7D 8S QH Highest card Queen	Player 1
3	2D 9C AS AH AC Three Aces	3D 6D 7D TD QD Flush with Diamonds	Player 2
4	4D 6S 9H QH QC Pair of Queens Highest card Nine	3D 6D 7H QD QS Pair of Queens Highest card Seven	Player 1
5	2H 2D 4C 4D 4S Full House With Three Fours	3C 3D 3S 9S 9D Full House with Three Threes	Player 1

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1’s cards and the last five are Player 2’s cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player’s hand is in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?

扑克手牌

在扑克牌游戏中，一手牌由5张牌构成，有不同的等级，从最小到最大，规则如下：

大牌：牌中最大的

对子：两张相同的牌

两对：有两对对子

三条：三张相同的牌

顺子：所有的牌是连续的

同花：所有的牌是同一花色

葫芦：三条和一对

四条：四张相同的牌

同花顺：所有的牌连续且是同花

同花大顺：AKQJ10组成的同花顺

牌值的顺序如下：

2，3，4，5，6，7，8，9，10，J，Q，K，A

如果两个玩家有相同等级的牌，则值更大的那个赢，例如一对8赢一对5（如下例1），但是如果等级相同，例如两个玩家都有一对Q，那么将比较手牌中的最大值（如下例4），如果最大的依然相同，则比较次大的，重复如上步骤。

考虑如下5种两个玩家的对局情况：

局

玩家1

玩家2

赢家

5H 5C 6S 7S KD
一对5

2C 3S 8S 8D TD
一对8

玩家2

5D 8C 9S JS AC
最大牌A

2C 5C 7D 8S QH
最大牌Q

玩家1

2D 9C AS AH AC
3张A

3D 6D 7D TD QD
方块同花

玩家2

4D 6S 9H QH QC
一对Q
最大9

3D 6D 7H QD QS
一对Q
最大7

玩家1

2H 2D 4C 4D 4S
葫芦
三个四

3C 3D 3S 9S 9D
葫芦
三个三

玩家1

文件 poker.txt中包含一千次两个玩家的对局情况，每一行有10张牌（空格分开），前5张牌是玩家1的牌，后5张牌是玩家2的牌，你可以假设手牌都是有效的（没有无效字符和重复的牌），每个玩家的手牌都没有特殊顺序，并且每一对局一定有一个赢。

求玩家1共赢了多少次。

解答：

这题好麻烦啊，写的代码真是乱。就是按照扑克牌的规则比较大小，真是很麻烦，一度令我有放弃欧拉工程的冲动，还好坚持下来了。

阿龙的学习笔记

兼济天下则达,独善其身则穷

在C++的sort排序中永远让比较函数对相等的值返回false

联系作者

安装Maven

联系作者

用select实现精确定时器

联系作者

用epoll提供telnet服务的代码(续)

联系作者

用epoll提供telnet服务的代码

联系作者

欧拉工程-问题58

联系作者

欧拉工程-问题57

联系作者

欧拉工程-问题56

联系作者

欧拉工程-问题55

联系作者

欧拉工程-问题54

联系作者