华为C笔试题目

最开始以为是编程题就写了个函数：

bool f(int x)

{

while(x%2==0) //判断是否为奇数

x/=2; //为追求效率可以用x>>=1

return !(x>1);

}

为了追求更高点点的效率可以把除法运算用右移代替，判断用位运算代替，就有下面代码：

bool f(int x)

{

while((x&1)==0)//就是判断x的末位是否为1

x>>=1;

return !(x>1);

}

后来发觉这题其实有更简单的方法，请看下面问题：

如何求一个数的二进制表示中1的个数？

int func(x)

{

int count=0;

while(x)

{

count++;

x+=x&(x-1);//这个操作能使x的二进制表示中的1的个数减1

}

return count;

}

这样判断一个数是不是2的幂代码就很简单了：（也就是判断它里面只有一个1，哈哈）

bool f(int x)

{

return !(x&(x-1));

}

2 字符串逆置（腾讯面试）

题目本身简单，但是有的是要求不能malloc新的内存空间，这样的话你就得在原来的串上进行操作就像下面的代码：

void reverse(char* ch)

{

int i, len;

char tmp;

len = strlen( ch );

for ( i = 0; i < len / 2; i++ )

{

tmp = ch[ i ];

ch[ i ] = ch[ len - i - 1 ];

ch[ len - i - 1 ] = tmp;

}

}

有的则是要求逆置到另外一段内存空间里，这样你就需用malloc了，而且注意函数的声明形式：

如果用纯c语言，恭喜你，你得用到指针的指针了：

int reserve(char** a, char** b)//返回值代表操作成功与否

c++的话就可以用引用：

int reserve(char*& a, char*& b)

3背包问题、约瑟夫问题、有序表合并（华为第4面机测）

从一摞摞数里比如从20个数{12，24，22，58，47，11，19，28，33，67，81，34，27，41，50，36，88，51，21，14}中挑选出若干个数使它们的和等于100.输出所有可能的选法。

解法：20个数放到a[20]数组里，然后b[20]数组里面放0或者1.然后再

sum=a[0]*b[0]+a[1]*b[1]+...+a[19]*b[19]

当b=1时，说明下标为i的那个数a被选中了，否则说明a这个数没有被选中

于是用一个20位的二进制数k来表示b[]数组，然后将k从0...0（20个0）到1...1（20个1）遍历一遍（for循环），穷举出所有解法。代码如下：

#include

using namespace std;

const int N=20;

const int M=100;

void main()

{

int a[N]={12,24,22,58,47,11,19,28,33,67,81,34,27,41,50,36,88,51,21,14};

int b[N];//放的0，1...

int c[N];//掩码

int k,sum;

//下面是让c[i]里面保存的数第i位为1, 其他位都为0

c[0]=1;

for (int i=1;i{

c[i]=c[i-1]<<1;

}

k=(c[N-1]<<1)-1;//也就是说k等于111...111（一共20个1）

for (;k>0;k--)

{

sum=0;

for (int j=0;j{

b[j]=((c[j]&k)>0)?1:0;

sum+=a[j]*b[j];

}

if (sum==M)

{

cout<<"以下数字相加和为"<f

or (int m=0;m{

if (b

==1)

{

cout<<<' ';

}

}

cout<}

}

}

约瑟夫问题在我的另一日志里讲的很清楚，有序表合并算法也很简单，这里不多说，呵呵

4爱立信

老实说爱立信的笔试题目最诡异，技术面试也诡异-_-!

（1）下面程序运行结果是什么：

#include "stdio.h"

class test

{

public:

test(){}

void hello(){ printf("hello\

");}

};

void main()

{

test* p=new test();

p=NULL;

p->hello();

}

事实是输出了hello，虽然在调用p->hello();之前已经给p赋值为NULL了（即0值），但是p依然可以调用test类的函数。我对此的解释是只要是test类的成员函数和成员变量放在不同的存储区（事实上也是如此），只要是test类型的指针就能调用test的成员函数，前提是函数里没有涉及到成员变量。比如下面的代码编译无误但运行会报错：

#include "stdio.h"

class test

{

private:

int i;

public:

test(){i=1;}

void hello(){printf("%d\

进制的数先转换为十进制数，然后再转换为b进制的数

int fun_A_to_B(int xa, int a, int b)

{

int power=1;

int x10=0;//用来存储十进制数

int xb=0;

while (xa)

{

x10+=(xa%10)*power;

power*=a;

xa/=10;

}

//接下来将十进制的x10转为b进制xb

power=1;

while (x10)

{

xb+=(x10%b)*power;

power*=10;

x10/=b;

}

return xb;

、欧几里德算法和扩展欧几里德算法

欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：(a,b) = (b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b

假设d是a,b的一个公约数，则有

d|a, d|b，而r = a - kb，因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则

d | b , d |r ，但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为：

void swap(int & a, int & b)

{

int c = a;

a = b;

b = c;

}

int (int a,int b)

{

if(0 == a )

{

return b;

}

if( 0 == b)

{

return a;

}

if(a > b)

{

swap(a,b);

}

int c;

for(c = a % b ; c > 0 ; c = a % b)

{

a = b;

b = c;

}

return b;

}

2、Stein算法

欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。

考虑现在的硬件平台，一般整数最多也就是位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。

Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。

为了说明Stein算法的正确性，首先必须注意到以下结论：

(a,a) = a，也就是一个数和他自身的公约数是其自身

(ka,kb) = k (a,b)，也就是最大公约数运算和倍乘

运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除

C++/java 实现

// c++/java stein 算法

int (int a,int b){

if(ab{

int temp = a;

a = b;

b=temp;

}

if(0==b)//the base case

return a;

if(a%2==0 && b%2 ==0)//a and b are even

return 2*(a/2,b/2);

if ( a%2 == 0)// only a is even

return (a/2,b);

if ( b%2==0 )// only b is even

return (a,b/2);

return ((a+b)/2,(a-b)/2);// a and b are odd

}

另外：两个数x,y的最小公倍数等于x*y/(x,y)

（转）C++的const和static关键字

305444126 发表于2009年06月04日 15:18 阅读(loading...) 评论(0)

分类： 计算机学习 举报

用好const关键字, 可以使你的C++程序更加健壮

用好static关键字, 可以使你的C++程序更加高效

今天详细研究了下const和static的用法, 查了不少资料, 贴在下面, 如有不足, 还望高手们不吝赐教:)

const使用详解

出自：康建东

一 const基础

如果const关键字不涉及到指针，我们很好理解，下面是涉及到指针的情况：

int b = 500;

const int* a = &b; [1]

int const *a = &b; [2]

int* const a = &b; [3]

const int* const a = &b; [4]

如果你能区分出上述四种情况，那么，恭喜你，你已经迈出了可喜的一步。不知道，也没关系，我们可以参考《Effective c++》Item21上的做法，如果const位于星号的左侧，则const就是用来修饰指针所指向的变量，即指针指向为常量；如果const位于星号的右侧，const就是修饰指针本身，即指针本身是常量。因此，[1]和[2]的情况相同，都是指针所指向的内容为常量（const放在变量声明符的位置无关），这种情况下不允许对内容进行更改操作，如不能*a = 3 ；[3]为指针本身是常量，而指针所指向的内容不是常量，这种情况下不能对指针本身进行更改操作，如a++是错误的；[4]为指针本身和指向的内容均为常量。

另外const 的一些强大的功能在于它在函数声明中的应用。在一个函数声明中，const 可以修饰函数的返回值，或某个参数；对于成员函数，还可以修饰是整个函数。有如下几种情况，以下会逐渐的说明用法：

A& operator=(const A& a);

void fun0(const A* a );

void fun1( ) const; // fun1( ) 为类成员函数

const A fun2( );

二 const的初始化

先看一下const变量初始化的情况

1) 非指针const常量初始化的情况：

A b;

const A a = b;

2) 指针(引用)const常量初始化的情况：

A* d = new A();

const A* c = d;

或者：const A* c = new A();

引用：

A f;

const A& e = f; // 这样作e只能访问声明为const的函数，而不能访问一般的成员函数；

三 作为参数和返回值的const修饰符

其实

，不论是参数还是返回值，道理都是一样的，参数传入时候和函数返回的时候，初始化const变量

1 修饰参数的const，如 void fun0(const A* a ); void fun1(const A& a);

调用函数的时候，用相应的变量初始化const常量，则在函数体中，按照const所修饰的部分进行常量化，如形参为const A* a，则不能对传递进来的指针的内容进行改变，保护了原指针所指向的内容；如形参为const A& a，则不能对传递进来的引用对象进行改变，保护了原对象的属性。

[注意]：参数const通常用于参数为指针或引用的情况;

2 修饰返回值的const，如const A fun2( ); const A* fun3( );

这样声明了返回值后，const按照"修饰原则"进行修饰，起到相应的保护作用。

const Rational operator*(const Rational& lhs, const Rational& rhs)

{

return Rational(lhs.numerator() * rhs.numerator(),

lhs.denominator() * rhs.denominator());

}

返回值用const修饰可以防止允许这样的操作发生:

Rational a,b;

Radional c;

(a*b) = c;

一般用const修饰返回值为对象本身（非引用和指针）的情况多用于二目操作符重载函数并产生新对象的时候。

[总结] 一般情况下，函数的返回值为某个对象时，如果将其声明为const时，多用于操作符的重载。通常，不建议用const修饰函数的返回值类型为某个对象或对某个对象引用的情况。

原因如下：

如果返回值为某个对象为const（const A test = A 实例）或某个对象的引用为const（const A& test = A实例） ，则返回值具有const属性，则返回实例只能访问类A中的公有（保护）数据成员和const成员函数，并且不允许对其进行赋值操作，这在一般情况下很少用到。

四 类成员函数中const的使用

一般放在函数体后，形如：void fun() const;

如果一个成员函数的不会修改数据成员，那么最好将其声明为const，因为const成员函数中不允许对数据成员进行修改，如果修改，编译器将报错，这大大提高了程序的健壮性。

五 使用const的一些建议

1 要大胆的使用const，这将给你带来无尽的益处，但前提是你必须搞清楚原委；

2 要避免最一般的赋值操作错误，如将const变量赋值，具体可见思考题；

3 在参数中使用const应该使用引用或指针，而不是一般的对象实例，原因同上；

4 const在成员函数中的三种用法（参数、返回值、函数）要很好的使用；

5 不要轻易的将函数的返回值类型定为const;

6 除了重载操作符外一般不要将返回值类型定为对某个对象的const引用;

static关键字

static关键字是C, C++中都存在的关键字, 它主要有三种使用方式, 其中前两种只指在C语言中使用, 第三种在C++中使用(C,C++中具体细微操作不尽相同, 本文以C++为准).

(1)

局部静态变量

(2)外部静态变量/函数

(3)静态数据成员/成员函数

下面就这三种使用方式及注意事项分别说明

一、局部静态变量

在C/C++中, 局部变量按照存储形式可分为三种auto, static, register

(谭浩强, 第174-175页)

与auto类型(普通)局部变量相比, static局部变量有三点不同

1. 存储空间分配不同

auto类型分配在栈上, 属于动态存储类别, 占动态存储区空间, 函数调用结束后自动释放, 而static分配在静态存储区, 在程序整个运行期间都不释放. 两者之间的作用域相同, 但生存期不同.

2. static局部变量在所处模块在初次运行时进行初始化工作, 且只操作一次

3. 对于局部静态变量, 如果不赋初值, 编译期会自动赋初值0或空字符, 而auto类型的初值是不确定的. (对于C++中的class对象例外, class的对象实例如果不初始化, 则会自动调用默认构造函数, 不管是否是static类型)

特点: static局部变量的”记忆性”与生存期的”全局性”

所谓”记忆性”是指在两次函数调用时, 在第二次调用进入时, 能保持第一次调用退出时的值.

示例程序一

#include

using namespace std;

void staticLocalVar()

{

static int a = 0; // 运行期时初始化一次, 下次再调用时, 不进行初始化工作

cout<<"%u.%u.%u.%u

⑦, 静态存储区的内容是192.168.168.168. 当再调度到A执行时, 从⑥继续执行, 由于strBuff的全局唯一性, 内容已经被B线程冲掉, 此时返回的将是192.168.168.168字符串, 不再是10.10.9.11字符串.

二、外部静态变量／函数

在C中static有了第二种含义：用来表示不能被其它文件访问的全局变量和函数。, 但为了全局变量/函数的作用域, 函数或变量前加static使得函数成为静态函数。但此处“static”的含义不是指存储方式，而是指对函数的作用域仅局限于本文件(所以又称内部函数)。注意此时, 对于外部(全局)变量, 不论是否有static, 它的存储区域都是在静态存储区, 生存期都是全局的. 此时的static只是起作用域作用, 限定作用域在本模块(文件)内部.

使用内部函数的好处是：不同的人编写不同的函数时，不用担心自己定义的函数，是否会与其它文件中的函数同名。

示例程序三:

//file1.cpp

static int varA;

int varB;

extern void funA()

{

……

}

static void funB()

{

……

}

//file2.cpp

extern int varB; // 使用file1.cpp中定义的全局变量

extern int varA; // 错误! varA是static类型, 无法在其他文件中使用

extern vod funA(); // 使用file1.cpp中定义的函数

extern void funB(); // 错误! 无法使用file1.cpp文件中static函数

三、静态数据成员／成员函数(C++特有)

C++重用了这个关键字，并赋予它与前面不同的第三种含义：表示属于一个类而不是属于此类的任何特定对象的变量和函数. 这是与普通成员函数的最大区别, 也是其应用所在, 比如在对某一个类的对象进行计数时, 计数生成多少个类的实例, 就可以用到静态数据成员. 在这里面, static既不是限定作用域的, 也不是扩展生存期的作用, 而是指示变量/函数在此类中的唯一性. 这也是”属于一个类而不是属于此类的任何特定对象的变量和函数”的含义. 因为它是对整个类来说是唯一的, 因此不可能属于某一个实例对象的. (针对静态数据成员而言, 成员函数不管是否是static, 在内存中只有一个副本, 普通成员函数调用时, 需要传入this指针, static成员函数调用时, 没有this指针. )

请看示例程序四((影印版)第59页)

class EnemyTarget {

public:

EnemyTarget() { ++numTargets; }

EnemyTarget(const EnemyTarget&) { ++numTargets; }

~EnemyTarget() { --numTargets; }

static size_t numberOfTargets() { return numTargets; }

bool destroy(); // returns success of attempt to destroy EnemyTarget object

private:

static size_t numTargets; // object counter

};

// class statics must be defined outside the class;

// initialization is to 0 by default

size_t EnemyTarget::numTargets;

在这个例子中, 静态数据成员numTargets就是用来计数产生的对象

象个数的.

另外, 在设计类的多线程操作时, 由于POSIX库下的线程函数pthread_create()要求是全局的, 普通成员函数无法直接做为线程函数, 可以考虑用Static成员函数做线程函数.

C++内存的两小问题？？？

彭海 发表于2009年05月21日 16:14 阅读(86) 评论(4)

分类： 计算机学习 举报

1. 文本常量区中的两个常量值如果相等，编译器会只保留一个副本（这是一种优化机制）

const char* a="abcd";

const char* b="abcd";

那么这时&a和&b是相等的，他们指向同一个内存地址

2. 一个程序分配几个栈的问题。

开始的时候觉得应该是一个作用域分配一个栈，这样的话在此域中申请的变量将先进后出的方式释放。但是后来仔细想想，整个程序分配一个栈也能满足要求。但是在VC上测试一下，又发生了意想不到的结果：

#include

void f()

{

int i;

int j;

printf("&i=%d &j=%d\

std;

const int N=8;

const int M=3;

static int a[N]={0,1,2,3,4,5,6,7};

typedef struct LNode

{

int data;

LNode *next;

}*List;

int CreateList(List& L,int *a, int n)

{ //带头结点的循环链表

if(n<=0)return 0;

L=(LNode*)malloc(sizeof(LNode));//头结点不存储任何数据

L->next=L;

LNode *p,*q;

p=L;

for (int i=0;i{

q=(LNode*)malloc(sizeof(LNode));

q->data=a[i];

q->next=L; //指向头结点

p->next=q;

p=q;

}

return 1;

}

void DestroyList(List& L)

{

LNode *q;

while ( L->next != L)//每次释放第一节点，就是头结点后面的那个节点

{

q=L->next;

L->next=q->next;

delete q;

}

}

void OutputList(List& L)

{

if (L->next==L)

return;

LNode* p = L->next;

while(p != L)

{

printf("%d\

t;

printf("%d

态和虚函数机制的哦！！

　　这种情况我们叫覆盖(override)！覆盖指的是派生类的虚拟函数覆盖了基类的同名且参数相同的函数！

　　在这里，我要强调的是，这种覆盖，要满足两个条件

　(a)有virtual关键字，在基类中函数声明的时候加上就可以了

　(b)基类CB中的函数和派生类CD中的函数要一模一样，什么叫一模一样，函数名，参数，返回类型三个条件。

　　有人可能会对(b)中的说法质疑，说返回类型也要一样？？

　　是，覆盖的话必须一样，我试了试，如果在基类中,把f的声明改成virtual int f(int)，编译出错了

　　error C2555: 'CD::f' : overriding virtual function differs from 'CB::f' only by return type or calling convention

　　所以，覆盖的话，必须要满足上述的(a)(b)条件

　　那么如果基类CB中的函数f有关键字virtual　，但是参数和派生类CD中的函数f参数不一样呢，

实例三:

#include "stdafx.h"

#include

class CB

{

　public:

　　 virtual void f(int)

　　 {

　　　　 cout << "CB::f(int)" << endl;

　　 }

}

;

class CD : public CB

{

public:

　　 void f(int，int)

　　{

　　　 cout << "CD::f(int，int)" << endl;

　　}

　　void test()

　　{

　　　　 f(1);

　　}

}

;

int main(int argc, char* argv[])

{

return 0;

}

编译出错了，

error C2660: 'f' : function does not take 1 parameters

　　咦？？好面熟的错？？对，和实例一中的情况一样哦，结论也是基类中的函数被隐藏了。

　　通过上面三个例子，得出一个简单的结论

如果基类中的函数和派生类中的两个名字一样的函数f

满足下面的两个条件

(a)在基类中函数声明的时候有virtual关键字

(b)基类CB中的函数和派生类CD中的函数一模一样，函数名，参数，返回类型都一样。

那么这就是叫做覆盖(override)，这也就是虚函数，多态的性质

那么其他的情况呢？？只要名字一样，不满足上面覆盖的条件，就是隐藏了。

下面我要讲最关键的地方了，好多人认为，基类CB中的f(int)会继承下来和CD中的f(int,int)在派生类CD中构成重载，就像实例一中想像的那样。

　　对吗？我们先看重载的定义

　　重载(overload):

　　必须在一个域中,函数名称相同但是函数参数不同,重载的作用就是同一个函数有不同的行为,因此不是在一个域中的函数是无法构成重载的,这个是重载的重要特征

　　必须在一个域中，而继承明显是在两个类中了哦，所以上面的想法是不成立的，我们测试的结构也是这样，派生类中的f(int,int)把基类中的f(int)隐藏了

　　所以，相同的函数名的函数，在基类和派生类中的关系只能是覆盖或者隐藏。

　　在文章中

，我把重载和覆盖的定义都给了出来了，但是一直没有给隐藏的定义，在最后，我把他给出来，这段话是网上google来的，比较长，你可以简单的理解成，在派生类域中，看不到基类中的那个同名函数了，或者说，是并没有继承下来给你用，呵呵，如实例一　那样。

隐藏(hide):

指的是派生类的成员函数隐藏了基类函数的成员函数.隐藏一词可以这么理解:在调用一个类的成员函数的时候,编译器会沿着类的继承链逐级的向上查找函数的定义,如果找到了那么就停止查找了,所以如果一个派生类和一个基类都有同一个同名(暂且不论参数是否相同)的函数,而编译器最终选择了在派生类中的函数,那么我们就说这个派生类的成员函数"隐藏"了基类的成员函数,也就是说它阻止了编译器继续向上查找函数的定义