微软面试题 --- 时钟三针重合问题

FreddyMusic

微软面试题：
http://www.simwe.com/forum/thread-768074-1-1.html

问题：

第一组 第7题

在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？

答案：24 小时内，共 24 次三针重合

12 小时内，共 12 次三针重合

分别是：

00:00:00
01:05:05
02:10:10
03:16:16
04:21:21
05:27:27
06:32:32
07:38:38
08:43:43
09:49:49
10:54:54
11:59:59

==============================================

注释：

你们可以使用windows 自带的时钟验证这一结果。

解题思路：见 Mathematica 版 附件是原创程序：

关键点：

是把握

1. 三重循环定时器
2. 时针 每 12 分钟 进一小格 0.2

[ 本帖最后由 FreddyMusic 于 2007-7-29 22:48 编辑 ]

FreddyMusic

I forget to make a stamping.

FreddyMusic's Patent No.0021
Location: Mathematica
Description: A triplicate loop for time counting?
http://www.simwe.com/forum/thread-780882-1-1.html

pcqsl

** Since all three hands are overlapped, there must be a single loop algorithm instead of three nested loop one **

For[k = 0, k < 60,
  h = 5*Floor[k/5] + Floor[k/12];
  m = (k - 5*Floor[k/5])*12;
  
  If[k == h && k >= m &&
    k < m + 12, Print[Floor[k/5], ":", k, ":", k]];
  
  k++];

[ 本帖最后由 pcqsl 于 2007-5-30 13:54 编辑 ]

FreddyMusic

pcqsl

Good Job. Simple is the best.

Your algorithm is more economic.

My algorithm is more physical.

FreddyMusic

pcqsl

我又有了另一个好的主意。
也许可以把你我的优势合并在一起。

有关代码可以这样。

单个循环 次数 60 * 60 *12  （ 12 小时内的秒数，即时间）

======================================

循环内变量定义

1. 数字显示时间，秒钟
2. 数字显示时间，分钟
3. 数字显示时间，小时

======================================

4. 指针指示时间，秒钟
5. 指针指示时间，分钟
6. 指针指示时间，小时

判断条件.....

======================================

作图显示，两种时钟和结果。

======================================

这样我就开发了一种具有更广泛意义的功能性的小程序，
它可以帮助我们判断，除三针重合外的其他条件。
例如，三针间隔角度都相等，都是 120 度 ，有几次等。

大伙有兴趣，都可以来玩玩，周末我来玩玩。

[ 本帖最后由 FreddyMusic 于 2007-5-31 09:23 编辑 ]

huahua2005

24小时好像只有22次哦，当中有二个重复时间~~

[ 本帖最后由 huahua2005 于 2007-5-31 12:14 编辑 ]

FreddyMusic

00:00:00
01:05:05
02:10:10
03:16:16
04:21:21
05:27:27
06:32:32
07:38:38
08:43:43
09:49:49
10:54:54
11:59:59
12:00:00
13:05:05
14:10:10
15:16:16
16:21:21
17:27:27
18:32:32
19:38:38
20:43:43
21:49:49
22:54:54
23:59:59

因该是 24 次。如果以24小时，数字显示计时的话。

FreddyMusic

我改进了一下代码。

1. 
   
2. For[k = 0, k < 43200,
   
3.    
   
4.     s = Mod[k, 60];
   
5.     m = Mod[(k - s)/60, 60];
   
6.     h = (k - s - m*60)/(60*60);
   
7.    
   
8.     PS = 0.2*s;
   
9.     PM = 0.2*m;
   
10.     PH = h + 0.2*Floor[m/12];
    
11.    
    
12.     If[PS == PM && PH == PM, Print["Show Time = ", h, ":
    
13.     ", m, ":", s, " -> Point Scale = ", PH, ":", PM, ":", PS],];
    
14.    
    
15.         k++];
    
16. 
    

复制代码

这样更好点。见附件。

下一步考虑如何 plot。

huahua2005

11:59:59
12:00:00

00:00:00
23:59:59
这两个好像是重复的，跟计算精度有关~~

FreddyMusic

1. 
   
2. For[k = 0, k < 43200,
   
3.    
   
4.     (* Define Show Time *)
   
5.     s = Mod[k, 60];
   
6.     m = Mod[(k - s)/60, 60];
   
7.     h = (k - s - m*60)/(60*60);
   
8.    
   
9.     (* Define Point Scale  *)
   
10.     PS = 0.2*s;
    
11.     PM = 0.2*m;
    
12.     PH = h + 0.2*Floor[m/12];
    
13.    
    
14.     If[PS == PM && PM == PH && PH == PS,
    
15. 
    
16.       Print["Show Time = ", h, ":", m, ":", s, " -> Point Scale = ", PH, ":", PM, ":", PS];
    
17.       
    
18.       Show[
    
19.                    Graphics[{
    
20.             
    
21.                                           Thickness[0.01],
    
22.                                         (* construction Scale and circles *)
    
23.                                         Circle[{0, 0}, 1, {0, 2π}],
    
24.                                          Text["9", {-1.1, 0}, {-1.1, 0}],
    
25.                                          Text["3", {1.1, 0}, {1.1, 0}],
    
26.                                          Text["12", {0, 1.05}, {0, -1.05}],
    
27.                                          Text["6", {0, -1.05}, {0, 1.05}],
    
28.             
    
29.                                         (* Replot 3 Arms *)
    
30.                                          Thickness[0.01], Hue[0.5],   
    
31.                                          Line[{{0, 0}, {0.9*Cos[90° - PS*30°], 0.9*Sin[90° - PS*30°]}}],
    
32.                                          Thickness[0.02], Hue[0.7],   
    
33.                                          Line[{{0, 0}, {0.6*Cos[90° - PM*30°], 0.6*Sin[90° - PM*30°]}}],
    
34.                                          Thickness[0.03], Hue[0.9],   
    
35.                                          Line[{{0, 0}, {0.3*Cos[90° - PH*30°], 0.3*Sin[90° - PH*30°]}}]
    
36.                                     }],
    
37.                                  AspectRatio -> Automatic, PlotRange -> All
    
38.                  ],
    
39.          ];
    
40.    
    
41.         k++];
    
42. 
    

复制代码

[ 本帖最后由 FreddyMusic 于 2007-5-31 14:41 编辑 ]

huahua2005

刚刚算了一下，其实只有00:00:00和12:00:00两个时间点是完全准确的，比如1：05：05
这个时间点时针距十二点的角度是32.5度而秒针则在30度上，其余的也类似~~

huahua2005

用MATHCAD解的时候这样的解是有的，但是是小数，呵呵
时   分   秒
0        0        0
1        5.363636363636363        5.454545454545454
2        10.727272727272727        10.909090909090908
3        16.09090909090909        16.363636363636363
4        21.454545454545453        21.818181818181817
5        26.818181818181817        27.27272727272727
6        32.18181818181818        32.72727272727273
7        37.54545454545455        38.18181818181818
8        42.90909090909091        43.63636363636363
9        48.272727272727266        49.090909090909086
10        53.63636363636363        54.54545454545454
11        59        59.99999999999999
12        0        0
13        5.36363636363636        5.454545454545453
14        10.727272727272734        10.909090909090907
15        16.090909090909093        16.36363636363636
16        21.454545454545453        21.818181818181813
17        26.818181818181813        27.272727272727266
18        32.18181818181817        32.72727272727272
19        37.54545454545455        38.18181818181817
20        42.90909090909091        43.636363636363626
21        48.272727272727266        49.09090909090908
22        53.63636363636364        54.54545454545453
23        59        59.999999999999986

FreddyMusic

huahua2005 mm不用那么精确吧！:D

一秒为最小刻度就可以了。

看我把钟给画出来了。

huahua2005

不是我弄的，是方程解出来的:lol

FreddyMusic

原帖由 pcqsl 于 2007/5/30 13:43 发表
** Since all three hands are overlapped, there must be a single loop algorithm instead of three nested loop one **

pcqsl ，

One question for a single loop algorithm and nested loop.

If we have three variables which is related, a single loop is better ?

If we have three variables which is NOT related, a nested loop is better ?

What's your opinion ? Any comments ?

pcqsl

It really depends on your interests.  I am interesting in the fastest algorithm.  If you are interesting in the problem itself, you may have different idea.

To justify how fast an algorithm is, we are normally using the computational complexity, in the form O(f(n)).  Intuitively, it represents the required computational steps vs.  the data size up to a scale.  Discrete Fourier transform, for example, has natual computational complexity O(n^2).  And the revolution is that people develop an O(n *log_2(n) ) algorithm, called FFT.

原帖由 FreddyMusic 于 2007-6-1 12:10 发表


pcqsl ，

One question for a single loop algorithm and nested loop.

If we have three variables which is related, a single loop is better ?

If we have three variables which is NOT rela ...

pcqsl

It depends on how these three variables are defined.  In the OP's post, all are discrete variables.  And they have a uniform timer for updating.

If we assume all three are pure analog variables, I would like to conjecture that 0:0:0 is the only solution for 12 hour case.

原帖由 huahua2005 于 2007-5-31 12:07 发表
24小时好像只有22次哦，当中有二个重复时间~~

FreddyMusic

pcqsl

I just evaluate your loop algorithm and mine. Your timing is good. :)
The less defined variables inside small loop is the advantage.
It worth a simwe +1 technical score either. huahua2005,  please help.

Another question. you mention about in the form O(f(n)).
I am confusing, How can we best evaluate the algorithm by Mathematica ?
We have Timing [] and MemoryInUse[] , Dose those two functions related each other.
I think Timing has included Memory. Any comments ? What is your experience ?

pcqsl

FreddyMusic:

I would claim that both single loop algorithms are the same in the sense of computational complexity.  Because I look at the part in the loop as a unit, the computational complexity is O(n).  In other words, if we increase the data size, the number of executing the unit will increase linearly.  Instead of 60 levels, for example, if we decide to have 360 levels, we need roughly 6 times of computational power.  On the other hand, in the three loop algorithm, if we want to compute the case of 360 levels, we need 6^3 times of the computational power.  Therefore, this is an O(n^3) algorithm.  And O(n^3) algorithm will be much faster than O(n) algorithm to become unfeasible when we increase n.  

Actually, I am quite new to Mathematica although I know it long long time ago.  But I would say that both functions are not designed for evaluating the computational complexity.  They should be tools for enhancing the performance of implementation.

FreddyMusic

pcqsl,

Thank you for the explaination.
That helps me to understand computational complexity much better.

You are most welcome in Mathematica room.