可用分押宝游戏火热进行中...	专题改版：Java Web 专题

今天的面试题，欢迎讨论

楼主coldcrane（清风明月）2005-04-04 00:21:41 在 C/C++ / C语言提问

1. 解二次方程:a*x*x+b*x+c
int Quadratic( double a,double b,double c,double& x1,double& x2);
返回值：解的个数

2. 最大公约数
DWORD Divisor( DWORD dwFirst, DWORD dwSecond );
返回值：最大公约数

3. 根据蒙特卡洛算法计算圆周率
double PI( DOWRD dwCount/*测试次数*/ )；
返回值：PI

4. 无符号整数乘法，乘数为32bit，结果为64bit
提示：32bit整数分解为16bit相乘
void Multiply( DWORD dwFirst, DWORD dwSecond, DWORD& dwHigh, DWORD& dwLower );

5. 链表排序(从小到大)
节点定义为：
struct Node{
int nValue;
struct Node* pNext;
};
最后一个节点的pNext = NULL.
Node* SortChain( Node* pHead );
返回值：链表头

问题点数：100、回复次数：49Top

1 楼coldcrane（清风明月）回复于 2005-04-04 00:24:44 得分 0

我的答案：
1.
int Quadratic( double a,double b,double c,double& x1,double& x2)
{
int ret = 0;
double e = 0.0000001;
if( a == 0 ){
if( b == 0 ){
ret = 0;
}
else{
ret = 1;
x1 = -c/b;
}
}
else{
double B = b*b;
double C = 4.0*a*c;
if( B<C+e && B>C-e ){
ret = 1;
x1 = -b/2/a;
}
else if( B<C ){
ret = 0;
}
else{
ret = 2;
x1 = (-b+sqrt(B-C))/2/a;
x1 = (-b-sqrt(B-C))/2/a;
}
}
return ret;
}

2.
DWORD Divisor( DWORD dwFirst, DWORD dwSecond )
{
DWORD a,b,tmp;
assert( dwFirst!=0 && dwSecond!=0 );
a = dwFirst;
b = dwSecond;
while( b != 0 )
{
tmp = a%b;
a = b;
b = tmp;
}
return a;
}

3.
double PI( DOWRD dwCount/*测试次数*/ )
{
double R = 32767.0;
DWORD count = 0;
srand( (unsigned)time( NULL ) ); // 这段代码当时没写，因为没有msdn，只记得一个rand()，连32767也是试出来的。
for( DWORD i=0;i<dwCount;i++ )
{
int x = rand();
int y = rand();
double r = sqrt( x*x + y*y );
if( r<R )
{
count++;
}
}
return 4.0*count/dwCount;
}

4.
void Multiply( DWORD dwFirst, DWORD dwSecond, DWORD& dwHigh, DWORD& dwLower )
{
DWORD ah,al,bh,bl
ah = dwFirst>>16;
al = dwFirst&0xffff;
bh = dwSecond>>16;
bl = dwSecond&0xffff;
dwHigh = ah*bh;
dwLower = al*bl;
DWORD tmp1 = ah*bl;
DWORD tmp2 = al*bh;
dwHigh += tmp1>>16;
dwHigh += tmp2>>16;
DWORD tmp3 = (tmp1&0xffff) + (tmp2&0xffff) + (dwLower>>16);
dwHigh += tmp3>>16;
dwLower &= 0xffff;
dwLower |= (tmp3&0xffff)<<16;
}

5.
Node* SortChain( Node* pHead )
{
DWORD dwNum == 0;
if( pHead = NULL )
{
return NULL;
}
Node* pChain = pHead;
dwNum = 1;
while( pChain->pNext != NULL )
{
dwNum++;
pChain = pChain->pNext;
}

for( DWORD i=0;i<dwNum-1;i++ )
{
pChain = pHead;
for( DWORD j=i;j<dwNum-1;j++ )
{
if( pChain->nValue > pChain->pNext->nValue )
{
DWORD tmp = pChain->nValue;
pChain->nValue = pChain->pNext->nValue;
pChain->pNext->nValue = tmp;
}
pChain = pChain->pNext;
}
}
retur pHead;
}

***********************************************************

第5题有点投机取巧了，感觉不太对路！

第1题总觉得有问题！Top

2 楼xxxdg（学习中）回复于 2005-04-04 00:30:20 得分 0

今天的作业题,欢迎帮忙Top

3 楼coldcrane（清风明月）回复于 2005-04-04 01:07:30 得分 0

to xxxdg(学习中):
你很幽默！但是别自作聪明！Top

4 楼xjp6688（大平/要做必须最好）回复于 2005-04-04 07:35:52 得分 0

有些算法不熟悉了，自己翻番书Top

5 楼YFY（天易）回复于 2005-04-04 08:24:33 得分 0

帮顶。Top

6 楼zengwujun（月之海为linux入门奋斗100天）回复于 2005-04-04 08:27:25 得分 0

upTop

7 楼pcboyxhy（-273.15℃）回复于 2005-04-04 08:40:06 得分 10

1 double a; if(a==0) ????

5 使用链表的冒泡排序效率不好
不如用插入排序

Top

8 楼coldcrane（清风明月）回复于 2005-04-04 09:02:03 得分 0

to pcboyxhy(-273.15℃) :
1 double a; if(a==0) ????
应该是：
if( a>-e && a<e )
做这题时有点心烦意乱，因为有提示说：要注意相近的数不能相减，相差太大的数不能相加。但这一规则不知如何运用才好。感觉很失败！

5 使用链表的冒泡排序效率不好
不如用插入排序
确实是生疏了！Top

9 楼AtaLoss0202（星空天宇）回复于 2005-04-04 09:37:12 得分 30

#include "stdio.h"
#include "math.h"

int Quadratic(double a, double b, double c, double& x1, double& x2)
{
double delta = b*b-4*a*c;
double sqrtRootOfDelta = sqrt(delta);
x1 = (b-sqrtRootOfDelta)/2*a;
x2 = (b+sqrtRootOfDelta)/2*a;
if(delta > 0)
return 2;
else if(!delta)
return 1;
else
return 0;
}

这是第一道题我的解法.后面的懒得做了.要上课了.Top

10 楼xxxdg（学习中）回复于 2005-04-04 10:49:11 得分 0

55555555555555
俺一点也不想聪明

俺只是说，
找本书，作业里头都有...Top

11 楼coldcrane（清风明月）回复于 2005-04-04 12:39:11 得分 0

to AtaLoss0202(星空天宇):
>>
>>else if(!delta)
>> return 1;
>>
对于浮点运算，这样的判断是不对的！可以参考前面的代码。

to xxxdg(学习中):
对我来说，做作业是n年前的事了。

Top

12 楼MagicCarmack（MagiC++）回复于 2005-04-04 12:46:37 得分 0

作业里头都有...

哪天,我也把作业发上来让同志们帮我一下!
Top

13 楼coldcrane（清风明月）回复于 2005-04-04 12:48:12 得分 0

呵呵，刚接到那家公司的电话，觉得我挺合适！搞定！Top

14 楼AtaLoss0202（星空天宇）回复于 2005-04-04 12:55:11 得分 0

恭喜!我测试过了,if(!delta)可以,即使delta=0.0000001也是测试通过,即是说,只要delta不等于0,c就不会把它当0.Top

15 楼AtaLoss0202（星空天宇）回复于 2005-04-04 12:56:21 得分 0

另外,偶发上BBS的所有程序都是经过自己测试通过的.Top

16 楼yelang771（牧野流星）回复于 2005-04-04 13:15:20 得分 0

恭喜~~﹗Top

17 楼playmud（(猪头流氓)(抵制日货)(热烈庆祝火箭输球)）回复于 2005-04-04 13:41:37 得分 0

学习Top

18 楼javaJeff（华子）回复于 2005-04-04 16:11:37 得分 0

我怎么看不懂那个求圆周率的蒙特卡罗算法呢,能不能解释一下?Top

19 楼coldcrane（清风明月）回复于 2005-04-04 16:34:09 得分 0

to AtaLoss0202(星空天宇):
需要注意这样一个问题：delta理论上为0，但实际可能不为0！
举个例子：
double a=100000000000.0,b=1.0,c=0.0000000000025;
double delta = b*b-4*a*c;
你会发现delta并不等于0！

to javaJeff(华子):
蒙特卡罗算法的原理是：考虑一个正方形和它的内切圆。在正方形随机取一点，其落在园内的概率应该是二者的面积比。
我的算法是取R=32767,在第一象限做采样。Top

20 楼wugaojun（）回复于 2005-04-04 16:47:44 得分 0

恭喜恭喜!面试还考这题目呀,看来平时是该注意一点细节问题呀Top

21 楼tianhxk（c++<>_JAVA(拒绝回答中文作为字段的问题)）回复于 2005-04-04 16:58:47 得分 20

DWORD Divisor( DWORD dwFirst, DWORD dwSecond )
{
DWORD a,b,tmp;
assert( dwFirst!=0 && dwSecond!=0 );
a = dwFirst;
b = dwSecond;
while( a != 0 && b != 0 )
{
if( a > b)
a %= b;
else
b %= a;
}
if( a)
return a;
return b;
}
个人感觉楼主的第四题考虑的非常周到，并且思路也很巧妙，我想了好几种方法都会出现加法的溢出，pfTop

22 楼xxmv99（喜欢你```所以学你```Cc）回复于 2005-04-04 16:58:54 得分 0

长见识...Top

23 楼MagicCarmack（MagiC++）回复于 2005-04-04 17:00:36 得分 0

长见识...
Top

24 楼liwei6797（对倒二五条）回复于 2005-04-04 17:28:13 得分 0

强人Top

25 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-04-04 17:28:42 得分 0

難啊。Top

26 楼liwei6797（对倒二五条）回复于 2005-04-04 17:58:41 得分 0

第4题没看明白-_-!!Top

27 楼soft_leer（softwind）回复于 2005-04-04 21:09:33 得分 0

是不错的公司吧？！面试题跟数学还结合得如此紧密。Top

28 楼coldcrane（清风明月）回复于 2005-04-04 21:50:57 得分 0

面试题有8道VC的(涉及MFC,socket,thread),一道算法的。
没有msdn，VC的题我就没辙了，只能做算法题。Top

29 楼coldcrane（清风明月）回复于 2005-04-04 21:58:50 得分 0

按 pcboyxhy(-273.15℃) 的建议，用插入排序重做了第5题，不知理解的对不对！
呵呵，写这个花的时间可比我当时写的那个多多了！

struct Node* NewSortChain( struct Node *pHead )
{
struct Node *pNewHead = NULL; // 新构造的链表
struct Node *pOldChain = NULL; // 用于遍历旧的链表
struct Node *pOldChainNext = NULL; // 用于临时存放pOldChain的pNext

pOldChain = pHead;

while( pOldChain != NULL )
{
pOldChainNext = pOldChain->pNext; // 保存pOldChain->pNext
if( pNewHead == NULL )
{
pNewHead = pOldChain;
pNewHead->pNext = NULL;
}
else
{
if( pOldChain->nValue <= pNewHead->nValue )
{
pOldChain->pNext = pNewHead;
pNewHead = pOldChain;
}
else
{
struct Node *pNewChain = pNewHead; // 用于遍历新的链表，寻找插入点
while( pNewChain != NULL )
{
if( pNewChain->pNext == NULL || pOldChain->nValue <= pNewChain->pNext->nValue )
{
pOldChain->pNext = pNewChain->pNext;
pNewChain->pNext = pOldChain;
break;
}
pNewChain = pNewChain->pNext;
}
}
}
pOldChain = pOldChainNext;
}
return pNewHead;
}

//************************************************************************************

一直没弄清楚的是第1题，不知道如何才能体现出：
“注意相近的数不能相减，相差太大的数不能相加”Top

30 楼opec（狂风基督）回复于 2005-04-04 22:02:49 得分 0

达人！！我来学习一下，看看自己可以做多少出来，顺便顶上去Top

31 楼AtaLoss0202（星空天宇）回复于 2005-04-04 22:58:17 得分 20

#include "stdio.h"
#include "math.h"
#include "iostream"
using namespace std;

int Quadratic(double a, double b, double c, double& x1, double& x2)
{
double delta = b*b-4*a*c;
double sqrtRootOfDelta = sqrt(delta);
x1 = (b-sqrtRootOfDelta)/2*a;
x2 = (b+sqrtRootOfDelta)/2*a;
printf("delta=%f\n",delta);
cout << "b*b=" << b*b << endl;
cout << "a*c=" << a*c << endl;
cout << "4*a*c=" << 4*a*c << endl;
cout << "delta.cout=" << b*b-4*a*c << endl;
if(delta > 0)
return 2;
else if(!delta)
return 1;
else
return 0;
}

void main()
{
double x1,x2;
int n=Quadratic(100000000000.0,1.0,0.0000000000025,x1,x2);
printf("n=%d x1=%f x2=%f\n", n,x1,x2);
}

输出:
delta=0.000000
b*b=1
a*c=0.25
4*a*c=1
delta.cout=1.11022e-016
n=2 x1=49999999473.164391 x2=50000000526.835609
Press any key to continue

刚刚调试了下,得出的结论正如楼主所说,是我没有考虑到实际情况,不过,我也确实不知道存在这个问题.你对问题的提出让我有不小的收获.真的很谢谢你.如果用printf()函数来输出是找不到问题所在的,我用了COUT输出流才发现确实会导致你所说的问题.不过,我还是不明白为什么会产生这个问题,因为从上面的输出可以看出分步计算b*b和4*a*c都是正确的,只有在最后执行两者的差运算时会出错,这点我暂时想不通.请指教.Top

32 楼lobatt（网络爬虫）回复于 2005-04-04 23:00:15 得分 0

赞tianhxk(天涯海角&近在天涯) 的最大公约数算法
王道啊...Top

33 楼coldcrane（清风明月）回复于 2005-04-04 23:51:40 得分 0

to AtaLoss0202(星空天宇):
浮点数很少是精确的，比如0.1，不可能用浮点数精确的表示出来。在浮点运算中，很可能出现舍入误差。

BTW:
你的代码有点小问题，应该是：
x1 = (b-sqrtRootOfDelta)/(2*a);
x2 = (b+sqrtRootOfDelta)/(2*a);Top

34 楼coldcrane（清风明月）回复于 2005-04-04 23:58:08 得分 0

呵呵，应该是：
x1 = (-b-sqrtRootOfDelta)/(2.0*a);
x2 = (-b+sqrtRootOfDelta)/(2.0*a);
Top

35 楼jinder22（jinder22）回复于 2005-04-05 00:24:24 得分 0

upTop

36 楼owsxo（owsxo（阿松））回复于 2005-04-05 12:26:28 得分 0

楼主你去的是什么公司呀怎么连数值分析都考啊....
唉当年没学好郁闷看来得重新学一下数学了......Top

37 楼AtaLoss0202（星空天宇）回复于 2005-04-05 12:44:04 得分 0

to coldcrane:
对,2*a少了括号是我的失误,而b前少了减号则是因为我把具体的求根公式给忘记了...谢谢你指出我的错误.

引用:浮点数很少是精确的，比如0.1，不可能用浮点数精确的表示出来。在浮点运算中，很可能出现舍入误差。

是不是说浮点数据类型的位长限制导致精确度无法很高?Top

38 楼AtaLoss0202（星空天宇）回复于 2005-04-05 12:57:36 得分 20

#include "stdio.h"
#include "math.h"
#include "iostream"
using namespace std;

int Quadratic(double a, double b, double c, double& x1, double& x2)
{
double b2=b*b;
double fourac=4*a*c;
double delta = double(b2+1) - double(fourac+1);
double sqrtRootOfDelta = sqrt(delta);
x1 = (-b-sqrtRootOfDelta)/(2*a);
x2 = (-b+sqrtRootOfDelta)/(2*a);
printf("delta=%f\n",delta);
cout << "b*b=" << b*b << endl;
cout << "a*c=" << a*c << endl;
cout << "4*a*c=" << 4*a*c << endl;
cout << "delta.cout=" << delta << endl;
cout << "b2 fourac " << b2 << " " << fourac << endl;
if(delta > 0)
return 2;
else if(!delta)
return 1;
else
return 0;
}

void main()
{
double x1,x2;
int n=Quadratic(100000000000.0,1.0,0.0000000000025,x1,x2);
printf("n=%d x1=%f x2=%f\n", n,x1,x2);
cout << "cout: x1=" << x1 << " x2=" << x2 << endl;
}

输出:
delta=0.000000
b*b=1
a*c=0.25
4*a*c=1
delta.cout=0
b2 fourac 1 1
n=1 x1=-0.000000 x2=-0.000000
cout: x1=-5e-012 x2=-5e-012
Press any key to continue

终于换了一种方法解决了上面的问题了...Top

39 楼coldcrane（清风明月）回复于 2005-04-05 13:50:28 得分 0

关于浮点运算的误差分析，与其我在这一知半解的瞎解释，还不如认真参考一下数值分析等相关书籍。Top

40 楼dllcyy（）回复于 2005-04-05 14:05:04 得分 0

高手真多
学习
顶一下
Top

41 楼coldcrane（清风明月）回复于 2005-04-05 16:36:13 得分 0

今天正式辞职Top

42 楼bitzilla（桃之夭夭）回复于 2005-04-05 17:18:39 得分 0

楼主应聘的公司是做什么的阿，对数据处理的算法要求好高啊！！！

佩服佩服Top

43 楼AtaLoss0202（星空天宇）回复于 2005-04-05 17:23:01 得分 0

倒...你不是吧?为什么辞职啊?Top

44 楼coldcrane（清风明月）回复于 2005-04-05 17:33:36 得分 0

to AtaLoss0202(星空天宇):
呵呵，换工作啊Top

45 楼qq911110（）回复于 2005-04-05 22:08:58 得分 0

顶一下Top

46 楼AtaLoss0202（星空天宇）回复于 2005-04-05 22:27:09 得分 0

哦，我理解错了．我以为你把这个面试所得到的工作辞了．嘿嘿．．．好好加油！Top

47 楼MagicCarmack（MagiC++）回复于 2005-04-06 00:35:53 得分 0