Placeholder Image

字幕列表 影片播放

  • Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.


  • It's the only thing between them and the tower

    [地點:198 森林]

  • that houses the second of three powerful artifacts.

    [第六集 裂谷]

  • They've got a brief window of time to get across before the guards return.

    艾希克、海吉、奧特薇雅 站在無底深谷的邊緣。

  • With Hedge's fuel gauge on empty he won't be able to fly Ethic across,


  • so the only option is to make a bridge.

    三個強大工藝品中的 第二個就在這座塔內。

  • Fortunately, the floating stacks of stones nearby are bridge components

    他們在守衛回來之前, 還有一點時間可以設法越過深谷。

  • invented by Octavia herselfcalled hover-blocks.

    海吉的燃料已經快用盡, 他無法帶艾希克飛過去。

  • Activate a pile with a burst of energy,


  • and they'll self-assemble to span the ravine as Ethic walks across.

    幸運的是,附近有一疊疊的浮石, 是可造橋的元件——

  • But there is, of course, a catch.

    它們是奧特薇雅自己的發明 ——叫做懸浮塊。

  • The hover-blocks are only stable when they're perfectly palindromic.


  • Meaning they have to form a sequence

    它們就會自行組合,跨越深谷, 讓艾希克可以走過去。

  • that's the same when viewed forwards and backwards.


  • The stacks start in random orders,

    懸浮塊只有在完全 對稱的時候才會穩定。

  • but will always put themselves into a palindromic configuration


  • if they can.

    順著看跟逆著看 都要完全一樣才行。

  • If they get to a point where a palindrome isn't possible,


  • the bridge will collapse,

    但在可以的情況下, 都會自行排成對稱的形式。

  • and whoever's on it will fall into the ravine.


  • Let's look at an example.


  • This stack would make itself stable.


  • First the A blocks hold themselves in place.


  • Then the B's.


  • And finally the C would nestle right between the B's.

    A 懸浮塊會先就位。再到 B。

  • However, suppose there was one more A.

    最後是 C,在兩個 B 之間。

  • First two A blocks form up, then two B's,

    然而,如果有再多一個 A,

  • but now the remaining C and A have nowhere to go,

    兩個 A 會先排好, 接著是兩個 B,

  • so the whole thing falls apart.

    但,現在就剩下一個 C 及一個 A,無處可去,

  • The Node of Power enables Hedge to energize a single stack of blocks.


  • What instructions can Ethic give Hedge to allow him to efficiently find

    力量球會讓海吉能夠 用能量激發其中一疊懸浮塊。

  • and power a stable palindromic stack?

    艾希克要給海吉什麼樣的指令, 才能讓他有效率地找到

  • Pause now to figure it out for yourself.

    一疊穩定的對稱懸浮塊, 並用能量激發它們?

  • Examples of palindromes include ANNA, RACECAR, and MADAM IM ADAM.


  • Counting the number of times a given letter appears in a palindrome


  • will reveal a helpful pattern.

    計算一個字母出現在 對稱排列中的次數,

  • Pause now to figure it out for yourself.


  • Let's first look at a naïve solution to this problem.


  • A naïve solution is a simple, brute-force approach that isn't optimized

    針對這個問題,咱們先來 看一個天真的解決方案。

  • but will get the job done.

    天真的解決方案是簡單、 用蠻力、沒有最佳化的方式——

  • Naïve solutions are helpful ways to analyze problems,


  • and work as stepping stones to better solutions.

    天真的解決方案 可以協助分析問題,

  • In this case, a naïve solution is to approach a pile of blocks,

    且可以當作墊腳石, 以想出更好的解決方案。

  • try all the arrangements,


  • and see if one is a palindrome by reading it forward and then backwards.

    先選一疊懸浮塊, 嘗試所有的排列組合,

  • The problem with this approach

    再透過正向及逆向閱讀的方式, 看看是否有一種組合是對稱的。

  • is that it would take a tremendous amount of time.

    這個方法的問題 是要花很大量的時間。

  • If Hedge tried one combination every second,

    假設海吉嘗試一種 組合需要一秒鐘,

  • a stack of just 10 different blocks would take him 42 days to exhaust.

    若一疊中有十種不同的懸浮塊, 就要花四十二天試盡所有組合。

  • That's because the total time is a function of the factorial


  • of the number of blocks there are.


  • 10 blocks have over 3 million combinations.


  • What this naïve solution shows is that we need a much faster way

    天真的解決方案告訴我們, 我們需要一種更快的方法,

  • to tell whether a pile of blocks can form a palindrome.

    來辨別哪一疊懸浮塊 能夠形成對稱排列。

  • To start, it may be intuitively clear that a pile of all different blocks

    一開始,直覺上很清楚, 一疊懸浮塊中,

  • will never form one.

    若每塊的字母都不同, 就不可能形式對稱排列。為什麼?

  • Why?

    若沒有重覆的字母,第一個 和最後一個懸浮塊就不會相同。

  • The first and last blocks can't be the same if there are no repeats.

    所以,什麼情況下一疊懸浮塊 能夠形成對稱的排列?

  • So when can a given sequence become a palindrome?

    找出答案的方式之一, 就是分析幾個既有的對稱排列。

  • One way to figure that out is to analyze a few existing palindromes.

    在 ANNA 中, 有兩個 A、兩個 N。

  • In ANNA, there are 2 A's and 2 N's.

    RACECAR 有兩個 R、 兩個 A、兩個 C、一個 E。

  • RACECAR has 2 R's, 2 A's, 2 C's, and 1 E.

    MADAM IM ADAM 有四個 M、

  • And MADAM IM ADAM has 4 M's, 4 A's, 2 D's, and 1 I.

    四個 A、兩個 D、一個 I。

  • The pattern here is that most of the letters occur


  • an even number of times,


  • and there's at most 1 that occurs just once.

    最多只有一個字母會出現一次。 是這樣嗎?

  • Is that it?

    如果 RACECAR 有三個 E, 而不是一個呢?

  • What if RACECAR had 3 E's instead of 1?

    我們可以把新增加的兩個 E 補在兩端,仍然會對稱,

  • We could tack the new E's onto the ends and still get a palindrome,


  • so 3 is ok.

    但如果有三個 E 和三個 C,

  • But make that 3 E's and 3 C's, and there's nowhere for the last C to go.

    最後一個 C 就沒地方放了。

  • So the most generalized insight is that


  • at most one letter can appear an odd number of times,

    最多只能有一個字母 出現的次數是單數,

  • but the rest have to be even.


  • Hedge can count the letters in each stack and organize them into a dictionary,

    海吉可以去計算每一疊懸浮石 當中的字母數,整理成字典,

  • which is a tidy way of storing information.


  • A loop could then go through and count how many times odd numbers appear.

    接著可以用迴圈來計算 單數出現了幾次。

  • If there are less than 2 odd characters, the stack can be made into a palindrome.

    若一疊當中的單數字母不到兩個, 它就可以形成對稱排列。

  • This approach is much, much faster than the naïve solution.

    這個方法比天真的 解決方案快非常多。

  • Instead of factorial time, it takes linear time.

    需要的時間不是 階乘的,是線性的。

  • That's where the time increases

    也就是說,需要的時間 和懸浮塊的數目成正比。

  • in proportion to the number of blocks there are.

    現在只要為海吉寫一個迴圈, 讓他分別接近每一疊懸浮塊。

  • Now write a loop for Hedge to approach the piles individually,

    在他找到可用的一疊之後就停止, 這樣你就可以準備出發了。

  • and stop when he finds a good one, and you'll be ready to go.


  • Here's what happens:

    海吉動作很快,但有太多疊了, 他花了很長的時間。

  • Hedge is fast, but there are so many piles it takes a long time.


  • Too long.


  • Ethic and Hedge are safe.


  • But Octavia is not so lucky.

Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.



影片操作 你可以在這邊進行「影片」的調整,以及「字幕」的顯示

B1 中級 中文 美國腔 TED-Ed 對稱 字母 排列 天真 方案

裂縫|像編碼員一樣思考,第6集------------------。 (The Chasm | Think Like A Coder, Ep 6)

  • 26 0
    ally.chang 發佈於 2021 年 01 月 14 日