无限循环的算法，以匹配时钟运行在不同的速度

我正在尝试解决这个问题:

两个时钟，使用24小时制以小时和分钟显示时间，运行在不同的位置速度。每个时钟都是每小时快的精确分钟数。两个时钟开始显示相同的时间(00:00)，每小时(一小时后开始)由精确计时员定时检查一次。第一次检查时，两个时钟显示的时间是一样的?注:对于这个问题，我们只关心时钟在检查时是否匹配。例如，假设第一个时钟快1分钟(每小时)，第二个时钟快31分钟快(每小时)。•当一小时后第一次检查时钟时，第一个时钟显示01:01，第二个时钟显示01:01将显示01:31;•当两个小时后检查时钟时，它们会显示02:02和03:02;•48小时后，时钟将显示00:48。

下面是我的代码:

def add_delay(min,hash)
    hash[:minutes] = (hash[:minutes] +  min)
    if hash[:minutes] > 59 
        hash[:minutes] %= 60
        if min < 60 
            add_hour(hash)
        end
    end
    hash[:hour] += (min / 60) 
    hash
end
def add_hour(hash) 
    hash[:hour] += 1
    if hash[:hour] > 23
        hash[:hour] %= 24
    end
    hash
end
def compare(hash1,hash2)
    (hash1[:hour] == hash2[:hour]) && (hash1[:minutes] == hash2[:minutes])
end


#-------------------------------------------------------------------
first_clock = Integer(gets) rescue nil
second_clock = Integer(gets) rescue nil

#hash1 = if first_clock < 60 then {:hour => 1,:minutes => first_clock} else {:hour => 1 + (first_clock/60),:minutes => (first_clock%60)} end
#hash2 = if second_clock < 60 then {:hour => 1,:minutes => second_clock} else {:hour => 1 + (second_clock/60),:minutes => (second_clock%60)} end
hash1 = {:hour => 0, :minutes => 0}
hash2 = {:hour => 0, :minutes => 0}
begin 
    hash1 = add_hour(hash1)
    hash1 = add_delay(first_clock,hash1)
    hash2 = add_hour(hash2)
    p hash2.to_s
    hash2 = add_delay(second_clock,hash2)
    p hash2.to_s
end while !compare(hash1,hash2)
#making sure print is good
if hash1[:hour] > 9
    if hash1[:minutes] > 9
        puts hash1[:hour].to_s + ":" + hash1[:minutes].to_s
    else
        puts hash1[:hour].to_s + ":0" + hash1[:minutes].to_s
    end
else
    if hash1[:minutes] > 9
        puts "0" + hash1[:hour].to_s + ":" + hash1[:minutes].to_s
    else
        puts "0" + hash1[:hour].to_s + ":0" + hash1[:minutes].to_s
    end
end
#-------------------------------------------------------------------

对于1和31，代码按预期运行。对于更大的数，如5和100，它似乎进入了无限循环，我不知道bug在哪里。出了什么问题?

您的add_delay函数中的逻辑有缺陷。

def add_delay(min,hash)
    hash[:minutes] = (hash[:minutes] +  min)
    if hash[:minutes] > 59 
        hash[:minutes] %= 60
        if min < 60 
            add_hour(hash)
        end
    end
    hash[:hour] += (min / 60) 
    hash
end

如果hash[:minutes]大于60，无论如何都应增加小时数。注意，小于60的增量会导致分钟溢出。

另外，如果增量超过60分钟，您可能必须将小时增加不止一次。

最后，做hash[:hour] += (min / 60)是错误的，因为min不一定超过60，因为你已经做了add_hour(hash)。

下面是该函数的更正版本:

def add_delay(minutes, time)
    time[:minutes] += minutes
    while time[:minutes] > 59  # If the minutes overflow,
        time[:minutes] -= 60   # subtract 60 minutes and
        add_hour(time)         # increment the hour.
    end                        # Repeat as necessary.
    time
end

您可以将这个函数插入到您现有的代码中。我只是擅自将min重命名为minutes，将hash重命名为time。

您的代码

让我们看看你的代码，同时做一些小的改进。

add_delay将给定的分钟数加到哈希中，将分钟数转换为小时数和分钟数，然后将小时数转换为一天内的小时数。一个问题是，如果时钟每小时增加59分钟以上，您可能必须将小时增加不止1个小时。试试这样写它和add_hours:

def add_delay(min_to_add, hash)
  mins = hash[:minutes] + min_to_add
  hrs, mins = mins.divmod 60
  hash[:minutes] = mins
  add_hours(hash, hrs)
end
def add_hours(hash, hours=1)
  hash[:hours] = (hash[:hours] + hours) % 24
end

我们不必关心这两个方法的返回值，因为它们修改了实参hash。

使用非常方便的方法Fixnum#divmod将分钟转换为小时和分钟。

(注:有些Ruby不使用hash作为变量名，因为它也是Ruby方法的名称)

接下来，compare确定两个键为:hour和:minutes的哈希是否相等。不需要检查小时和分钟是否匹配，只需查看哈希值是否相等:

def compare(hash1, hash2)
  hash1 == hash2
end

得到时钟快的每小时分钟数:

first_clock  = Integer(gets) rescue nil
second_clock = Integer(gets) rescue nil

，现在初始化散列，逐小时逐级，直到找到匹配，然后返回散列:

def find_matching_time(first_clock, second_clock)
  hash1 = {:hours => 0, :minutes => 0}
  hash2 = {:hours => 0, :minutes => 0} 
  begin 
    add_delay(first_clock, hash1)
    add_hours(hash1)
    add_delay(second_clock, hash2)
    add_hours(hash2)
  end until compare(hash1, hash2)
  hash1
end

让我们试一试:

find_matching_time(1, 31)
  # => {:hours=>0, :minutes=>48} 
find_matching_time(5, 100)
  #=> {:hours=>0, :minutes=>0}
find_matching_time(5, 5)
  #=> {:hours=>1, :minutes=>5} 
find_matching_time(0, 59)
  #=> {:hours=>0, :minutes=>0}

这些结果与我下面用另一种方法得到的结果相匹配。在时间相同之前，您不会返回从现在开始的小时数，但您可能不需要这样做。

我还没有确定为什么你会得到无限循环，但也许通过这个分析，你将能够找到它。

我建议还有两个小的变化:1)将add_hours合并到add_delay中并重新命名后者，2)摆脱compare，因为它太简单了，只在一个地方使用:

def add_hour_and_delay(min_to_add, hash)
  mins = hash[:minutes] + min_to_add
  hrs, mins = mins.divmod 60
  hash[:minutes] = mins
  hash[:hours] = (hash[:hours] + 1 + hrs) % 24
end
def find_matching_time(first_clock, second_clock)
  hash1 = {:hours => 0, :minutes => 0}
  hash2 = {:hours => 0, :minutes => 0} 
  begin 
    add_hour_and_delay(first_clock, hash1)
    add_hour_and_delay(second_clock, hash2)
  end until hash1 == hash2
  hash1
end

替代方法

这里是编写该方法的另一种方式。让:

f0:分钟每小时第一个时钟快
f1:分钟每小时第二个时钟快

然后我们可以计算下一次它们显示相同时间的时间，如下所示:

MINS_PER_DAY = (24*60)
def find_matching_time(f0, f1)
  elapsed_hours = (1..Float::INFINITY).find { |i|
    (i*(60+f0)) % MINS_PER_DAY == (i*(60+f1)) % MINS_PER_DAY }
  [elapsed_hours, "%d:%02d" % ((elapsed_hours*(60+f0)) % MINS_PER_DAY).divmod(60)]
end

find_matching_time(1, 31)
  #=> [48, "0:48"]

在48小时后，两个时钟将显示时间为"0:48"。

find_matching_time(5, 100)
  #=> [288, "0:00"]
find_matching_time(5, 5)
  #=> [1, "1:05"] 
find_matching_time(0, 59)
  #=> [1440, "0:00"]

在i小时过去后，两个时钟将分别显示一天内的分钟数:

(i*(60+f0)) % MINS_PER_DAY # clock 0
(i*(60+f1)) % MINS_PER_DAY # clock 1

当这两个值相等时，使用

Enumerable#find来确定第一个经过的小时数i。我们不知道这需要多长时间，所以我枚举了所有以1开头的正整数。(我猜它可能不超过59小时，所以我可以写(1..n).find..，其中n是比58大的任何整数。)find返回的值被赋给变量elapsed_hours。

两个时钟将在elapsed_hours之后显示相同的时间，因此我们可以计算两个时钟将显示的时间。我选择为时钟0这样做。对于第一个例子(f0=1, f1=31)

elapsed_hours #=> 48

mins_clock0_advances = elapsed_hours*(60+1)
  #=> 2928
mins_clock_advances_within_day = mins_clock0_advances % MINS_PER_DAY
 #=> 48

然后将其转换为小时和分钟:

mins_clock_advances_within_day.divmod(60)
  #=> [0, 48]

，然后我们可以使用String#%方法来适当地格式化结果:

"%d:%02d" % mins_clock_advances_within_day.divmod(60)
  #=> "0:48"

请参阅Kernel#sprintf了解使用%时的格式化信息。在"%02d"中，d表示"decimal"，2表示字段宽度，0表示左空格为0。

相关内容

最新更新

热门标签：