-2

我想编写一个方法来返回最后一个未被删除的可用奇数位置。例如

Say the number inputted to function is 5 Then we can number as follows 1,2,3,4,5

After first pass, numbers left are - 2,4. 1,3,5 have been removed After second pass - 2 has been removed and so we are left with 4

The function should return 4. 在我的方法中，我创建了一个包含 n 个数字的数组。每个元素可能有一个值 0 或 1, 0 表示该元素没有被删除和 1 被删除。我的代码是

int findposition(int n)
{
int barr[n];
int count=0,i,begIndex=0;

for(i=0;i<n;i++)
    barr[i]=0;

while(n!=count+1)
{
    for(i=begIndex;i<n;i=i+2)
    {
        barr[i]=1;
    }


    for(i=0;i<n;i++)
    {
        if(barr[i]==0)
            begIndex=i;
    }

}

return (begIndex+1);
}

上述函数编译成功，但从 main 方法调用时不打印任何内容。另外，我认为我的方法有点笨拙。有没有更简洁的方法来做到这一点。

4

2 回答 2

1

如果您查看二进制位置符号中已删除对象的索引，您会发现在第一步中您删除了所有最后一位为 1 的数字。这给我们留下了 xxxx0 形式的数字，其中 xxxx 是某个范围内的所有二进制数字。所以你会得到001 0, 010 0, 011 0, 100 0。很明显，第二步删除了所有后缀为10的数字，你最终会得到01 00、10 00、11 00等。

显然，最后一个数字是尾随零最多的数字。

于 2012-07-19T17:34:22.773 回答
1

如果我正确理解了这个问题，则解决方案归结为找到输入数字的最高有效位。这只是k = 2 的约瑟夫斯问题。

于 2012-07-19T17:22:44.483 回答