發表新討論
#42102: python 可以使用 itertools 的 permutations


sam851015@gmail.com (多挖鼻孔有益身心健康)

學校 : 不指定學校
編號 : 277705
來源 : [123.192.228.253]
最後登入時間 ：
2024-11-09 20:16:56
d299. 程式設計師的面試問題 -- 某科技公司的面試問題 | From: [123.192.228.253] | 發表日期 : 2024-09-27 00:39

對，我知道可以直接輸出答案，不用寫一長串的 code，當成 hello world 做題(或益智解謎遊戲?)，但畢竟這裡是 zerojudge ，還是老老實實寫吧

至少......不需要推半天，然後發現自己智慧不足，做出來的答案是錯的，甚至做不出來，最後直接抄

 

這題就是要你窮舉，讓程式去遍歷所有可能的狀況，判斷哪一個狀況是正解

根據題意，題目提供 10 個不同的字母，每個字母都代表 0-9 中不同的數字，不重複

 

這剛好就是 itertools 的 permutations 的功能：窮舉一切可能的排列組合

簡單的像下面這樣寫就可以得到答案，非常優雅，不需要動太多腦，但是會吃 TLE

from itertools import permutations


char = ['F', 'O', 'R', 'T', 'Y', 'E', 'N', 'S', 'I', 'X']
for i in permutations(char):
    ans = {j:i for i, j in enumerate(i)}

    forty = sum((ans['F'] * 10000, ans['O'] * 1000, ans['R'] * 100, ans['T'] * 10, ans['Y']))
    ten = sum((ans['T'] * 100, ans['E'] * 10, ans['N']))
    sixty = sum((ans['S'] * 10000, ans['I'] * 1000, ans['X'] * 100, ans['T'] * 10, ans['Y']))

    if forty + ten * 2 == sixty:
        print(f'{forty} + {ten} + {ten} = {sixty}')
        break

 

這是因為如果真的要窮舉的話，一共會有 10! = 3,628,800 種組合

每一種都這樣檢查會吃 TLE 不奇怪，所以需要剪枝，有兩個方向可以處理

  1. 對於明顯就是錯誤的答案，直接略過
  2. 對於答案很明顯的字母，直接設定固定的值

例如:

  1. F, T, S 這三個字母絕對不可能是 0
  2. N 和 E 這兩個字母只可能是 0 或 5
  3. O 很明顯就一定是 9，這樣才能進位，讓 F 和 S 變成 2 個不同的數字
  4. ......(後面自己想)

實際不需要真的那麼多 if ，一定有某些方法，可以用很優雅的方式去掉很大一部分不可能的答案

 

我的作法: github 

 

 

 
ZeroJudge Forum