我该如何解决这个鳕鱼问题！ [英] How do I solve this codility problem!!!

问题描述

[ ^ ]



我不知道如何解决这个问题。请有人带我一个简单的解决方案因为我是编程新手。



谢谢

解决方案

考虑数字的二进制表示并计算相邻的零。

提示：这可能是 SHIFT 和（按位） AND 任务。

要系统地解决问题，您可以使用状态机。

例如首先将 max_len 和 gap_len 初始化为 0 ， 状态到 Init ，然后按照下表所示的状态和操作一个接一个地处理：

< td rowspan =2>计数

当前状态	当前位	下一个状态	动作
Init	0	Init
	1	计数
0	计数	gap_len ++;
1	计数	max_len = max（max_len，gap_len）; gap_len = 0;

最后返回结果 max_len 值。

这是功能正确但可能不是最佳的。例如。 max_len 更新甚至 gap_len 为零等等。但这仅在速度相关时才有意义。在这种情况下，更多的状态可能会提高状态机复杂性的成本。不过，这仍然是运动。 ;-)



现在，状态机转换成如下内容：



已更改从define到enum [/ EDIT]

 ... 
  enum  {Init，Count} state = Init; 
 ... 
  int  n = ... 
  int  max_len =  0 ; 
  int  gap_len =  0 ; 
  for （ int  bit =  1 ; bit; bit<< =  1 ）{ //  只要掩码中有移动位就运行 
  int  one = n&位; 
  switch （state）{
  case 初始值：
  //  条件状态更改 
 如果 （一）{
 state = Count; 
} 
 
  //  无行动 
 < span class =code-keyword> break ; 
  case 计数：
  //  没有状态变化 
 
  //  有条件的行动 
  if （one）{
  if （max_len< gap_len）max_len = gap_len; 
 gap_len =  0 ; 
}  else  {
 gap_len ++; 
} 
  break ; 
 默认：
断言（！ 意外状态）; 
  break ; 
} 
} 

干杯

Andi

你想学点东西。因此，为您提供解决方案会适得其反。但我可以给出一些提示：



不要认为'十进制'。请记住，值已经在二进制表示中。因此，您可以通过对值应用掩码来检查单个位。



很明显，使用相应的掩码检查所有可能的位将是低效的。是不是有一个可以移动的操作？



剩下的任务只是计算和确定最大值。值。

[^]

I have no idea how to solve this problem. Please can someone walk me through a simple solution because I'm a programming novice.

Thanks

解决方案

Consider the binary representation of the number and count adjacent zeroes.
Hint: this could be a SHIFT and (bitwise) AND task.

To tackle the problem systematically, you might employ a state machine.
E.g. you start by initializing the max_len and gap_len to 0, the State to Init and then process one bit after the other by following the states and actions as shown in this table:

Current State	Current Bit	Next State	Action
Init	0	Init	;
	1	Count	;
Count	0	Count	gap_len++;
	1	Count	max_len = max(max_len, gap_len); gap_len = 0;

Finally you return the resulting max_len value.
This is functional correct but maybe not optimal. E.g. max_len is updated even gap_len is zero, etc. But this is only relevant if speed is relevant. In such a case, more states might improve speed for the cost of complexity of the state machine. This is left as exercise, though. ;-)

Now, the state machine translates into something like this:

[EDIT] changed from define to enum [/EDIT]

...
enum { Init, Count } state = Init;
...
int n = ...
int max_len = 0;
int gap_len = 0;
for(int bit = 1; bit; bit<<=1) { // run as long as there is a moving bit in the mask
    int one = n & bit;
    switch(state) {
    case Init:
        // conditional state change
        if (one) {
            state = Count;
        }

        // no action
        break;
    case Count:
        // no state change

        // conditional action
        if (one) {
            if (max_len < gap_len) max_len = gap_len;
            gap_len = 0;
        } else {
            gap_len++;
        }
        break;
    default:
        assert(!"Unexpected State");
        break;
    }
}

Cheers
Andi

You want to learn something. So it would be counterproductive to give you a solution. But I can give some hints:

Don't think 'decimal'. Just remember that values are already in their binary representation. So you can check single bits by applying a mask to the value.

It is obvious that checking all possible bits with corresponding masks would be inefficient. Isn't there an operation that can move bit wise?

The remaining tasks are just counting and determining a max. value.

这篇关于我该如何解决这个鳕鱼问题！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！