[分享]百度武大笔试题

程序设计一：设计一个函数int func(unsigned)实现：输入n，若n为偶数，则除以2，若为奇数，则可以作加1或减1操作。知道n变为1，函数返回操作的最少次数。
举例：n=7，7->8->4->2->1,最少次数为4。
我当时程序这样写的，回来调试了一下，通过了；
#include <stdio.h>
int main()
{
int func(unsigned);
int n;
printf("输入一个数:");
scanf("%d",&n);
printf("最少次数为%d\n",func(n));
return 0;
}
int func(unsigned n)
{
if(n==1)
return 0;
else
if(n%2==0)
return(func(n/2)+1);
else
return(func(n+1)<func(n-1)?func(n+1)+1:func(n-1)+1);
}
程序设计题二：
ip.txt中存放ip地址，一行包含一个ip，可能是一个ip地址（192.168.0.1），也可能是一个ip段（192.168.0.10 192.168.0.100）ip段的范围不超过一个B类，行数不超过10万，现有ip入侵，如果入侵ip在文件中则输出“Y”，否则输出“N”
我的程序如下，应该还有很多优化的地方，大家提哈意见；
#include <stdio.h>
int main()
{
FILE *fp;
int i,a[4],b[4],c[4];//c存放入侵地址，ab分别存放首尾地址
char d;
printf("入侵IP:");
scanf("%d.%d.%d.%d",&c[0],&c[1],&c[2],&c[3]);
while((fp=fopen("d:\\ip.txt","r"))==NULL)
{
printf("打开文件失败!\n");
exit(1);
}
while(!feof(fp))
{
for(i=0;i<4;i++)
{
fscanf(fp,"%d",&a[i]);
d=fgetc(fp);
}
if(d=='\n') //该行为ip地址
{
for(i=0;i<4;i++)
if(a[i]==c[i])
continue;
else
break;
if(i==4&&a[4]==c[4]) //匹配成功
{
printf("Y\n");
return 0;
}
}
else //该行为ip段
{
for(i=0;i<4;i++)
{
fscanf(fp,"%d",&b[i]);
d=fgetc(fp);
}
if(a[2]==b[2])
if(c[2]==a[2]&&c[3]>=a[3]&&c[3]<=b[3])
{
printf("Y\n");
return 0;
}
else
;
else
{
if(c[2]>a[2]&&c[2]<b[2])
{
printf("Y\n");
return 0;
}
if(c[2]==a[2]&&c[3]>=a[3]||c[2]==b[2]&&c[3]<=b[3])
{
printf("Y\n");
return 0;
}
}
}
}
fclose(fp);
printf("N\n");
return 0;
}
比较那里写的很乱，考试时写的。数据结构没学，算法考前抱了下佛脚，现在才开始学C一个月，就这水平了！

[此贴子已经被作者于2007-9-20 13:17:27编辑过]

今天下午百度就要来我们学校了，哈哈！期待中..

怎么不来我们学校`````

这么简单的笔试题？

不知道有没有什么简单方法``能一步就把一个偶数``直接弄成奇数```

10000->5000->2500->1250->625``好麻烦啊```

要是可以直接把10000弄成625就好了```

简单DP，比那个3n+1还要好做些



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

楼主代码没错，但时间复杂度太高了。。。
baidu考的题应该不会这样简单的算法就能解决。
这是我写的代码，但还没自习考虑，不确定有没有bug：

程序代码：

[此贴子已经被作者于2007-9-20 12:52:03编辑过]

DP...
时间复杂度应该是O（n）吧？
如果把输入改成unsigned long long 就够呛了。。

不是O(logn)?



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

才学了一个月的C，没考虑那么多。算法大三上学的，全忘了！以前没认真学，现在后悔莫及啊！