2014年10月 的存档

Ugly Numbers

n=2^i*3^j*5^k,ijk是自然数。可以得到n序列 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
求此序列第N个数是多少。
一般的人会这样:
把可能的数都算出来,去重,再排序,得到序列

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main()
{
    set<int> s;
    s.insert(1);
    set<int>::iterator it = s.begin();
    //此处使用1600而非1500,是为了防止类似*it*5 > *(++it)*2的情况出现而导致循环结束时较小的丑数仍未插入容器
    while(s.size()<=1600)
    {
        s.insert(*it*2);
        s.insert(*it*3);
        s.insert(*it*5);
        it++;
    }
    int n;
    while(cin>>n&&n)
    {
        it = s.begin();
        int i = n;
        while(--i){
            ++it;
        }
        cout<<"The "<<n<<"th ugly number is "<<*it<<"."<<endl;
    }
    return 0;
}

明白一些的人思路是这个:http://online-judge.uva.es/board/viewtopic.php?f=22&t=26972
引用原文代码是:

int main(void)
{
   int N;
   while(scanf("%d", &N)){
      if(N <= 0) continue;
      int v, p, temp;
      v = 1; p = 1;
      while(p < N){
         v++;
         temp = v;
         while(temp % 2 == 0) temp /= 2;
         if(temp == 1) { p++; continue;}
         while(temp % 3 == 0) temp /= 3;
         if(temp == 1) { p++; continue;}
         while(temp % 5 == 0) temp /= 5;
         if(temp == 1) { p++; continue;}
      }
      printf("%d\n", v);
   }
   return 0;
}

数小还可以,数大了就会很慢了
然后算法更精一些的人还可以这样:http://www.2cto.com/kf/201306/222203.html
引用原文代码是:

#include<stdio.h>  
int main(void) 
{ 
    int un[1505]={0}; 
    int m2=0,m3=0,m5=0,n,t; 
    un[0]=1; 
    for(n=1;n<1500;n++) 
    { 
        if(2*un[m2]>3*un[m3]) 
            t=un[m3]*3; 
        else 
            t=un[m2]*2; 
        if(t>un[m5]*5) 
            t=un[m5]*5;
        if(t == 2*un[m2]) m2++; 
        if(t == 3*un[m3]) m3++; 
        if(t == 5*un[m5]) m5++;
        un[n]=t; 
    } 
    printf("The 1500'th ugly number is %d.\n",un[1499]); 
    return 0; 
}

算法思路就是先定义一个集合,该集合中有元素1,如果x在集合中,并且y是x的下一个丑数,那么x*2,x*3,x*5也在集合中,其它数不再集合中,这三个数中必定是2x最小,因此首先放入数组中,而此时*2最小的应该是x的下一个丑数y*2,此时应该找出y*2,x*3,x*5中最小的数放入数组,以此类推,具体操作如下:
1
*2
*3
*5

选出乘积最小的,加入到结果集中,相应指针右移
1 2
*3 *2
*5

选出乘积最小的,加入到结果集中,相应指针右移
1 2 3
*5 *2
*3

选出乘积最小的,加入到结果集中,相应指针右移
1 2 3 4
*5 *3 *2

选出乘积最小的,加入到结果集中,相应指针右移
1 2 3 4
*3 *2
*5

以此类推,直到获得足够长的结果集
嗯。算是空间换时间吧。目的下标不确定的话需要自己处理数组空间。不过速度与前者比较那是相当的快啊。
不知道还有没有更好的解法。

为什么ping对方ip会返回重复回应包呢?

ping同一个序号的ICMP包却收到了多个回应:

root@test:/var/www/db# ping mail.corp.qihoo.net
PING mail.corp.qihoo.net (220.181.158.203) 56(84) bytes of data.
64 bytes from 220.181.158.203: icmp_req=1 ttl=114 time=158 ms
64 bytes from 220.181.158.203: icmp_req=1 ttl=114 time=158 ms (DUP!)
64 bytes from 220.181.158.203: icmp_req=2 ttl=114 time=157 ms
64 bytes from 220.181.158.203: icmp_req=2 ttl=114 time=157 ms (DUP!)
64 bytes from 220.181.158.203: icmp_req=3 ttl=114 time=157 ms
64 bytes from 220.181.158.203: icmp_req=3 ttl=114 time=157 ms (DUP!)
^C
— mail.corp.qihoo.net ping statistics —
3 packets transmitted, 3 received, +3 duplicates, 0% packet loss, time 2002ms
rtt min/avg/max/mdev = 157.363/157.646/158.133/0.338 ms

man ping 这样说:

ping will report duplicate and damaged packets. Duplicate packets
should never occur, and seem to be caused by inappropriate link-level
retransmissions. Duplicates may occur in many situations and are
rarely (if ever) a good sign, although the presence of low levels of
duplicates may not always be cause for alarm.

首先重复的数据包确实是不应该出现的,然后如此稳定的重复现象也不像是“inappropriate link-level retransmissions”,多方搜索下来前辈们的意见是有这么几种可能:
1.网络中存在环路路由,static route
2.双机HA
3.两台虚拟机使用了相同MAC地址
4.HUB问题
5.ICMP REDIRECT
6./etc/tcp里面的配置手动改过,改错了,广播地址改成了你所要ping的ip地址
阅读更多…

为邮件服务器设置域名DNS SPF记录

SPF用于辅助过滤垃圾邮件,描述哪些ip是此域名的合法发送者,当然不满足测试条件的ip发送的邮件就很有可能是有人恶意仿冒发送方发送的垃圾邮件了。
SPF 的 TXT 记录
SPF 记录包含在一个 TXT 记录之中,格式如下:
v=spf1 [[pre] type [ext] ] … [mod]
每个参数的含义如下表所示: 参数 描述
v=spf1 SPF 的版本。如果使用 Sender ID 的话,这个字段就应该是 v=spf2
pre 定义匹配时的返回值。
可能的返回值包括: 返回值 描述
+ 缺省值。在测试完成的时候表示通过。
– 表示测试失败。这个值通常是 -all,表示没有其他任何匹配发生。
~ 表示软失败,通常表示测试没有完成。
? 表示不置可否。这个值也通常在测试没有完成的时候使用。
type 定义使用的确认测试的类型。
可能的值包括: 候选值 描述
include 包含一个给定的域名的测试
以 include:domain 的形式书写。
all 终止测试序列。
比如,如果选项是 -all,那么到达这条记录也就意味着测试失败了。但是如果无法确定,可以使用”?all”来表示,这样,测试将被接受。
实例比如:
“v=spf1 ip4:220.181.12.0/22 ip4:202.108.9.128/25 ip4:202.108.5.0/24 ~all”
再比如QQ邮箱是
“v=spf1 include:spf.mail.qq.com ~all”
再再比如163邮箱是
“v=spf1 include:spf.163.com -all”
再再再比如de3eb.cn是(QQ企业邮箱加两台vps,include在后)
“v=spf1 ip4:209.141.61.51 ip4:203.195.248.238 include:spf.mail.qq.com -all”
详细参见
http://www.openspf.org/SPF_Record_Syntax