2010-12-04 102 views
3

的問題是如下:問題98 - 項目歐拉

通過分別用1,2,圖9和6替換單詞CARE每個字母,我們形成正方形數:1296 = 36 ^( 2)。值得注意的是,通過使用相同的數字替換,字謎RACE也形成一個平方數:9216 = 96 ^(2)。我們將呼叫CARE(和RACE)一個方形字謎字對,並進一步指定不允許前導零,不同的字母也不能與另一個字母具有相同的數字值。

使用words.txt(右鍵單擊和「Save Link/Target As ...」),一個包含近兩千個常用英語單詞的16K文本文件,找到所有正方形anagram字對(迴文單詞不是被認爲是自己的一個字謎)。

這樣一對的任何成員形成的最大方號是多少?

注意:所有形成的anagrams必須包含在給定的文本文件中。

我不明白CARE到1296的映射嗎?這是如何運作的?或者是否意味着要嘗試的所有置換映射,即所有1-9的字母?

回答

3

總之:是的,所有的排列都需要嘗試。

+3

好的,這是有道理的,措辭不佳的問題國際海事組織。 – dominic 2010-12-04 20:52:26

5

允許所有字母數字賦值。所以C = 1,A = 2,R = 3,E = 4將是一個可能的任務...除了1234不是正方形,所以這將是不好的。

也許另一個例子有助於說清楚嗎?如果我們分配A = 6,E = 5,T = 2,則TEA = 256 = 16 2和EAT = 625 = 25。所以(TEA = 256,EAT = 625)是一個正方形的anagram字對。

(只是因爲所有字母數字的賦值都是允許的,並不意味着實際嘗試所有這樣的賦值是解決問題的最佳方式,也可能有其他更聰明的方法來實現。)

1

如果測試所有替代字母數字,比你正在尋找對廣場與性能:

  • 具有相同的長度
  • 有發生次數相同的數字作爲輸入字符串。

找到所有這些正方形對更快。有68個正方形,長度爲4,216個正方形,長度爲5,...通過上面的屬性過濾所有相同長度的正方形將生成「小」數對,這是您正在尋找的解決方案。

這些數據是'靜態'的,不依賴於輸入字符串。它可以計算一次並用於所有輸入字符串。

1

嗯。如何把這個。把歐拉項目放在一起的人們承諾,每個問題都有一分鐘的解決方案,而且我認爲只有一個問題可能會失敗,但事實並非如此。

是的,你可以對數字進行排列,並對所有方塊嘗試所有排列,但這將是一個非常大的搜索空間,根本不可能是(TM)正確的東西。一般來說,當你看到你對問題的「看」會產生一個需要很長時間的搜索時,你需要搜索其他的東西。

贊,假設你被要求確定什麼數字是1和1之間的兩個素數相乘的結果。你可以將每個數字都計算在1到1億之間,但將兩個素數的所有組合乘以它們可能會更快。既然你在看組合,你可以從兩個開始,直到你的結果太大,然後用三個等等,相比之下,這應該快得多 - 你不必乘以所有的數字你可以把所有素數記錄下來,然後添加它們並找出每個素數的限制,給你一個你可以加起來的數字列表。

有許多創新的解決方案,但您首先想到的一個 - 特別是您在Project Euler描述問題時所考慮的問題,可能是錯誤的。

那麼,你如何解決這個問題呢?可能有太多的排列組合,但也許你可以找出映射和比較映射的東西?

(試圖避免全部消失。)