算法题：三针重叠问题

Nov 27th, 2018

Posted by CaiKnife

Nov 27th, 2018实战, 算法, 编程

经典问题——三针重叠问题。

在时针走满一圈的情况下，也就是12小时内，时针、分针、秒针会重合多少次？

分析一下：秒针60s走完一整圈，每秒的旋转角度是6度，分针速度是秒针的1/60，每s的旋转角度是1/10度，时针速度是分针的1/12，每s的旋转角度是1/120度。那么就需要计算出12个小时的时间内，也就是12*3600秒内，每秒钟三个指针的位置即可。如果度数相同，那么就认为三针重合。

更简单地来说，假设把时针的最小步长定位1，那么分针的步长就是12，而秒针的步长就是720。再针对各自一圈的步长取模，就可以得到每秒时每个位置的偏移量，如果三个偏移量相等的话，

编写程序如下：

(clock.php) download

<?php
/**
 * Created by PhpStorm.
 * User: caiknife
 * Date: 2018/11/27
 * Time: 10:51
 */

namespace App\Cron;


class Time
{
    const TOTAL_TIME = 12 * 60 * 60;

    protected $_hourNeedle   = 0;
    protected $_minuteNeedle = 0;
    protected $_secondNeedle = 0;

    protected $_nextMinuteNeedle = 0;

    public function __construct()
    {
        date_default_timezone_set('Asia/Shanghai');
    }

    public function main()
    {
        $baseTime = strtotime('2018-01-01 00:00:00');

        for ($i = 0; $i <= static::TOTAL_TIME; $i++) {
            // 求时针的偏移量
            $this->_hourNeedle = (1 * $i) % static::TOTAL_TIME;
            // 求分针的偏移量
            $this->_minuteNeedle = (12 * $i) % static::TOTAL_TIME;
            // 求秒针的偏移量
            $this->_secondNeedle = (720 * $i) % static::TOTAL_TIME;

            if ($this->_hourNeedle == $this->_minuteNeedle
                && $this->_minuteNeedle == $this->_secondNeedle) {
                echo $i . PHP_EOL;
                echo date("H:i:s", $baseTime + $i) . PHP_EOL;
            }
        }
    }
}

所以，在12个小时内，三针重合只有在0点和12点的时候才会出现。这个时候是真正的停止重合。

而在其他的条件下，时针和分针只会出现划过重合，不会出现停止重合。

下面更新一个Golang写的版本，了解一下Golang时间处理的奇葩……

(clock.go) download

package main

import (
  "fmt"
  "time"
)

const (
  TotalTime = 12 * 60 * 60
  FDateTime = "2006-01-02 15:04:05" // 奇葩的时间点，格式化必须是这个格式……
  FDate     = "2006-01-02"
  FTime     = "15:04:05"
  StartTime = "2018-01-01 00:00:00" // 我们设置的起点时间
)

func main() {
  fmt.Println(time.Now().Format(FDate)) // 先试试格式化日期
  fmt.Println(time.Now().Format(FTime)) // 再试试格式化时间
  // 下面定个时间起点
  fromDate, _ := time.ParseInLocation(FDateTime, StartTime, time.Local)

  for i := 0; i <= TotalTime; i++ {
      hourNeedle := (i * 1) % TotalTime
      minuteNeedle := (i * 12) % TotalTime
      secondNeedle := (i * 720) % TotalTime

      if hourNeedle == minuteNeedle && minuteNeedle == secondNeedle {
          fmt.Println("Three needles get together!")
          fmt.Println(time.Unix(fromDate.Unix()+int64(i), 0).Format(FTime))
      }
  }
}