原文地址:http://blog.csdn.net/wangyuling1234567890/article/details/38565239
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: intmain() { inti,n=20; for(i=0;i<n;n--) printf("*"); return0; } 解法2: intmain() { inti,n=20; for(i=0;i<n;i++) printf("*"); return0; }
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层的尝试), 依据我们的递归,easy得到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跟等长的筷子,要求组成四个等边三角形,不同意折断或者弯曲筷子。
正四面体就可以。
9、交换两个整形变量的值,不使用第三个变量
解法1: 把两个整形数放到数轴上,如图(吐槽一下,博客中不能绘图,真不方便,能够考虑添加简单绘图的功能): <span style="color:#000099;">-----<span style="color:#FF0000;">|</span>-------------<span style="color:#FF0000;">|</span>------></span> a <span style="color:#FF0000;"><-- b-a --></span> b 于是有 a=b-a //a为a、b之间距离 b=b-a //b减去a、b之间距离,等于之前a的值 a=b+a //如今的b加上a、b之间距离,等于之前b的值 解法2: 依据异或运算符性质,a=a^b^b: a=a^b //a' = a^b, b' = b b=b^a //b' = a , a' = a^b a=b^a //b' = a, a' = b 解法3: 指针运算,原理同1
10、不使用比較运算符求两个数中较大者
还是数轴原理
#define max(a, b) ( ( (a) + (b) + abs((a) - (b)) ) / 2 )
11、洗牌算法
解法1
a、定义一个54整数数组poker[54],分别赋值1~54
b、生成两个随机数:m=rand()%54 + 1, n=rand()%54 + 1
c、交换pocker[m]与pocker[n]的值
d、反复b、c动作N次,N值越大越平均,但须要考虑效率。
解法2
使用集合,如vector或list
vector pocker; //未洗牌的一幅扑克,顺序为1~54 vector orderd; //已洗牌的扑克集合,初始为空 while(pocker.size()) { p = rand() % pocker.size(); orderd.push_back(pocker[p]); pocker.erase(pocker.begin() + p); }
12、有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一仅仅蚂蚁。木杆非常细,不能同一时候通过两仅仅蚂蚁。開始时,蚂蚁头朝向随意(左或右),它们仅仅会朝前或掉头,不会后退。当随意两仅仅蚂蚁碰头是,两仅仅蚂蚁会同一时候调头朝反向走。如果蚂蚁每秒走1厘米,编敲代码,求全部蚂蚁都离开木杆的最短时间和最长时间。(来自《编程之美》)
解法1
蛮力解法(brute force),枚举各蚂蚁的初始朝向,模拟每一个蚂蚁的运动规律来解决。
解法2
考虑,尽管两仅仅蚂蚁碰头后都掉头往相反的方向,可是,能够看作是是两仅仅蚂蚁相遇后,擦肩而过了(看到这里的时候可能非常多人就有一种恍然大悟的感觉了吧)。也就是说能够觉得蚂蚁的运动独立的,是否有碰头并非问题的中重点。这样尽管每一个蚂蚁的运动轨迹都与原来的不一样了。可是全部的蚂蚁离开木杆的最短的时间和最长时间是不变的。仅仅须要分别计算每一个蚂蚁离开木杆的时间,就可以求出全部蚂蚁离开木杆的时间了。
这样,程序仅仅须要遍历全部的蚂蚁,把每一个蚂蚁走出木杆的最长时间(蚂蚁朝离自己较远的一端走去),最短时间(蚂蚁朝离自己较近的一端走去)分别求出来,就算出最大值,这两个最大值就是全部蚂蚁离开木杆的最长时间和最短时间。