是什么导致错误的第一个函数，似乎看起来类似于第二个函数?

Question

下面的函数给出不同的结果。它们之间的区别是什么导致了不同的输出。例如，n=30和k=417219134分别给出输出0和1。

函数1(错误的):

int kthGrammar(int n, int k) {
if (n==1){
return 0;
}
int parent_node = kthGrammar(n-1, ceil(float(k)/2));
int isKodd = k%2;
if (isKodd){
return parent_node;}
else{
return parent_node==0?1:0;}
}

功能2(右):

int kthGrammar(int n, int k){
if (n==1){
return 0;
}
int isKodd = k%2;
if (isKodd){
return kthGrammar(n-1, (k+1)/2);}
else{
return (kthGrammar(n-1, k/2)==0?1:0);}
}

Answer 1

int-417219134不能用float完美地表示。

float  f = 417219134;
double d = 417219134;
std::cout << std::fixed
<< f << 'n'   // 417219136.000000
<< d << 'n';  // 417219134.000000

这解释了为什么ceil(float(k)/2)在k = 417219134.

时返回的数字比预期的少+1。我会在函数中转换为double:

int parent_node = kthGrammar(n-1, ceil(k / 2.));