前几天参加百度的笔试纯粹是为了凑热闹，我这种平时不怎么关心数据结构和算法的人找软件的工作本来就难，何况是百度这种搞信息管理的公司。所以笔试的时候根本就没怎么动脑子。

后来想了想第1道程序题，发现没有想象的困难
原题大致是：
对一个非0自然数，进行如下操作：
若为偶数，则除以2；
若为奇数，则可+1或-1；
重复这两种操作直到最后得出1，计算需要的次数。

当时分析到奇数加减1影响运算次数后就没再往下想了，其实如果从二进制角度看，如果最低位为0（即偶数），必然进行移位（除以2）操作；如果最低位为1，所进行的操作跟最低为之前存在的连续1位数有关，如果只有两个及以下的1，并且与高位的1相隔2个以上的0（如110011），则减1操作比加更能减少1的个数和移位操作；如果相隔只有1个0，并且0以上的连续1大于2个，则应当加1（如11101，11011）；如果连续存在3个以上的1，也应该加1，其原理是减少1的个数超过了进位造成的移位次数增加的次数。

程序代码如下：

typedef unsigned int uint;
uint fcount(uint a)
{
if(a==0 || a==1)
return 0;
uint b=a;
uint n=0;
while(b!=1)
{
switch(b&0×07)
{
case 7 :
n++; b++;
break;
case 3:
if((b&0×8)==0×8) {n++;b++;break;}
else {n++;b–;break;}
case 5:
if((b&0×18)==0×18) {n++;b++;break;}
else {n++;b–;break;}
case 1:
n++;b–;
break;
default :
n++;b=b>>1;
break;
}
}
return n;
}

验证方法就是用递归算法硬算作比较，递归算法的函数如下：
uint fc(uint a)
{
uint n=0;
if(a==1) return n;
while(!(a&1) && a!=0)
{
a=a>>1;
n++;
}
if(a==1) return n;
n++;
uint n1=fc(a-1);
uint n2=fc(a+1);
return n+((n1 }

验证程序：
int main()
{
for(int i=1;i<=1000000;i++)
{
uint dd;
uint f=fc(i);
uint f1=fcount(i);
if(f!=f1) cout< }

return 0;
}

第2个检查IP的题，直接用C++的串操作拉倒吧

bool ipsearch(const string &f=” “,const string &filename=” “)
{
ifstream fin(filename.c_str());
bool fd=false;
if(!fin.is_open())
{
cout<<”no config file”< return false;
}
// 判断输入是否为有效IP格式，输出失败信息，返回失败
while(!fin.eof() && fd==false)
{
string str;
getline(fin,str);
if(str.find(‘ ‘)==-1)
{
if(f==str)
{
fd=true;
}
}
else
{
string::size_type c=str.find(‘ ‘);
string str1(str.begin(),str.begin()+c);
string str2(str.begin()+c+1,str.end());
// 判断是否为有效IP格式 否则输出失败信息，返回失败
if(f>=str1&&f<=str2)
{
fd=true;
}
}
}
return fd;
}

****