1、写一个高效C语言程序,计算一个无符号整数中1的个数。
for(count=0; x ; count++) x &= x-1;
同理,计算0的位数:
for(count=32; x ; count--) x &= x-1;
2、给定字符串S1和S2,写程序判断S2是否能由S1旋转而来,要求只能调用一次strstr系统函数。
void main()
{
char *str1 = "wang";
char *str2 = "angw";
char *tmp = (char*)malloc(2*strlen(str1) + 1);
sprintf(tmp, "%s%s", str1, str1);
if (strstr(tmp, str2))
cout<<"yes"<<endl;
getchar();
}
3、IF条件中填入什么东西,能能让下面的程序打印出HelloWorld?
- if(<condition>)
- printf ("Hello");
- else
- printf("World");
if (!printf("Hello"))
printf("Hello");
else
printf("World");
4、只修改或添加一个字符,使下面的程序打印出20个*号。(至少有3种解法)
- int main()
- {
- int i, n = 20;
- for (i = 0; i < n; i--)
- printf("*");
- return 0;
- }
解法1:
int
main
(
)
{
int
i
,
n
=
20
;
for
(
i
=
0
;
i
<
n
;
n
--
)
printf
(
"*"
)
;
return
0
;
}
解法2:
int
main
(
)
{
int
i
,
n
=
20
;
for
(
i
=
0
;
i
<
n
;
i++
)
printf
(
"*"
)
;
return
0
;
}
5、写一个算法,反转字符串中的单词顺序。
例如:Hi Welcome to cricode 反转成 cricode to Welcome Hi
void main()
{
string str("Hi Welcome to cricode");
stack<char> cstack;
stack<char> tmp;
int index = 0;
for (index = 0; index < str.size(); index++)
{
cstack.push(str[index]);
}
index = 0;
while(!cstack.empty())
{
if (' ' == cstack.top()) //实验代码,未对标点符号做判断
{
while(!tmp.empty())
{
str[index++] = tmp.top();
tmp.pop();
}
str[index++] = ' ';
cstack.pop();
}
else
{
tmp.push(cstack.top());
cstack.pop();
}
}
while(!tmp.empty())
{
str[index++] = tmp.top();
tmp.pop();
}
cout<<str<<endl;
getchar();
}
6、100层楼,给你两个球,球的特性如下:如果你从这栋楼的某一小于X的楼层扔下这个球,球不会碎,如果你从大于等于X的楼层扔下,则球必定会碎。假设你能重复使用没有摔碎的球,请给定一个算法,用最少的扔球次数找出边界楼层X.
如果是两个玻璃球,最少次数m确定楼高为N的哪一层开始能使这个玻璃球摔碎这个问题,等价于求最小的m,使得 1+2+...+m >= N 。
假设N正好等于1+2+...+m,那么我觉得最优的策略就是第一个玻璃球扔在第m层,如果碎了,显然需要剩下的m-1层从底往上一一尝试,最坏情况就是m;假设m处没有碎,问题等价于楼高N'=1+2+...+(m-1)的地方同样的问题需要的次数m'+1 (1就是第一次在m层的尝试),根据我们的递归,容易得到N'对应需要的次数正好是m-1次,因此总次数也是m。
我们的二分应该倾向于不管失败还是成功,两种情况的总检测次数相等。因此这应该是最优的算法。
当然,当N不能表示成1+2+...+m使,我们只能找最小的m作为需要测试的次数。
至于100层楼,显然m=14,我们的第一次扔球应该分别在第14, 如果没碎继续在14+13=27,再没有碎则扔在第27+12=39层,以此类推。
7、A、B两座城市相距1000Km,我们有3000个香蕉要从A城市运往B城市,已知一头大象一次最多能运1000个香蕉,而且大象每次走1Km要吃掉一个香蕉,如果香蕉被吃完了,大象就不能再继续往前走。请问,你最终最多能运多少香蕉到B城市?
1000米设置一个回头点,是不可行的。1000米设置两个回头点A,B,也就是将1000米分成3段。设每段长度为从起点到A点X1,A点到B点X2,B点到终点X3,
X1+X2+X3=1000
在A点需要来回5次才能将3000的香蕉运到A点。那么A点有3000-5*X1的香蕉,
通过推理,3000-5*X1小于等于2000,
这样到B点 3000-5*X1-3*X2,这个值小于等于1000,
终点剩下3000-5*X1-3*X2-X3,根据上面的判断,如果都取等于的话:
X1=200;X2=334
最终剩下532。
注:其实X2取333,这时候剩余533个,注意这种情况下需要丢弃一根香蕉。
8、给你6跟等长的筷子,要求组成四个等边三角形,不允许折断或者弯曲筷子。
正四面体即可。