1237 . Binary Watch

題解  |  Anpig  |  2020-11-29  |  1.1k  |  4 Minutes

題目

二進位制手錶頂部有 4 個 LED 代表小時（0-11），
底部的 6 個 LED 代表分鐘（0-59）。
每個 LED 代表一個 0 或 1，最低位在右側。

例如，上面的二進位制手錶讀取 “3:25”。
上圖取自 leetcode Binary Watch，題目也是改自 leecode Binary Watch。

輸入說明

首先會是 1 個正整數 T（0 < T < 20），表示測資的數量。
接下來 T 行每行給定一個非負整數 n 代表當前 LED 亮著的數量。

輸出說明

針對每筆測資輸出所有可能的時間總和，並以分鐘為單位。
(不合理的時間請不要計算，像是”1:66”, “13:00”)

想法

這題主要是要我們窮舉n顆燈亮著的組合，
其他都是一些有的沒的處理，所以我們首先宣告一個陣列int led[11];，
代表那十顆燈，當它的值是0代表沒亮，1代表亮著，
我這裡是把第0~5顆當作分鐘的 1 ~ 32，6~9顆當作小時的 1 ~ 8。

然後開始建造遞迴函數。

首先給它兩個參數，分別是：

  1. n：現在要選第幾顆燈了
  2. chosen：總共已經選幾顆燈了

再來要給它中止點，可能的中止點有：

  1. 沒有燈可以選了（n > 10）
  2. 選到的燈數跟題目要求的一樣（chosen == on，其中on代表題目輸入）
1
2
3
4
5
6
if (n > 10) return;
if (chosen == on) {
    有的沒的處理;
    return;
}
return;

由於我們有設定中止點了，所以先放心地把第n顆 LED 打開（設成1）：
led[n] = 1;

再尋找下一顆打開的可能，由於我們選了第n顆，所以chosen要加 1：
dfs(n + 1, chosen + 1);

再來我們要試試看不選第n顆的可能，所以先讓第n顆熄滅（設成0）：
led[n] = 0;

再尋找下一顆打開的可能，由於我們沒選第n顆，所以chosen不加 1：
dfs(n + 1, chosen);

這樣遞迴的部分就完成了，接下來開始有的沒的處理。

題目要求不合理的時間不要計算，所以我們先檢查選這n顆燈代表的時間合不合理：
由於這隻錶是二進位錶，我宣告了一個變數pow，讓它先等於 1，
之後每換下一顆燈就再乘以 2。
由於led[i]會是0或1，所以+= led[i] * pow就只是代表會不會把pow加進去而已。

先算分鐘數，由於led[i]會是0或1，
所以min += led[i] * pow就代表會不會把pow加min而已，
超過 60 分鐘（>= 60）代表這是不合理的時間，所以不把它加進總和。

1
2
3
4
5
6
7
int min = 0;
int pow = 1;
for (int i = 0; i < 6; i++) {
    min += led[i] * pow;
    pow *= 2;
}
if (min >= 60) return;

再算小時數，由於led[i]會是0或1，
所以hr += led[i] * pow就代表會不會把pow加hr而已，
超過 12 小時（>= 12）代表這是不合理的時間，所以不把它加進總和。

1
2
3
4
5
6
7
int hr = 0;
pow = 1;
for (int i = 6; i < 10; i++) {
    hr += led[i] * pow;
    pow *= 2;
}
if (hr >= 12) return;

確保時間是合理的之後，就可以把它加進總和裡了。

1
2
sum += hr * 60 + min;
return;

遞迴函數：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void dfs(int n, int chosen) {
    if (n > 10) return;
    if (chosen == on) {
        int min = 0;
        int pow = 1;
        for (int i = 0; i < 6; i++) {
            min += led[i] * pow;
            pow *= 2;
        }
        if (min >= 60) return;
        int hr = 0;
        pow = 1;
        for (int i = 0; i < 4; i++) {
            hr += led[i + 6] * pow;
            pow *= 2;
        }
        if (hr >= 12) return;
        sum += hr * 60 + min;
        return;
    }
    led[n] = 1;
    dfs(n + 1, chosen + 1);
    led[n] = 0;
    dfs(n + 1, chosen);
    return;
}

遞迴函數寫完之後，把輸入輸出搞一搞這題就結束了。

完整程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
int sum, led[11], on;
void dfs(int n, int chosen) {
    if (n > 10) return;
    if (chosen == on) {
        int min = 0;
        int pow = 1;
        for (int i = 0; i < 6; i++) {
            min += led[i] * pow;
            pow *= 2;
        }
        if (min >= 60) return;
        int hr = 0;
        pow = 1;
        for (int i = 0; i < 4; i++) {
            hr += led[i + 6] * pow;
            pow *= 2;
        }
        if (hr >= 12) return;
        sum += hr * 60 + min;
        return;
    }
    led[n] = 1;
    dfs(n + 1, chosen + 1);
    led[n] = 0;
    dfs(n + 1, chosen);
    return;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &on);
        sum = 0;
        dfs(0, 0);
        printf("%d\n", sum);
    }
    return 0;
}
tags:  #Formosa OJ #遞迴 #DFS #Backtrack #窮舉
全部展開 回到頂部 移至底部