Re: [閒聊] 程設作業

[game0416 (鳳狼)]

結果我決定今天寫，不然明天又沒時間摸魚發呆念點書(?)

新的學期新的開始，新的JAVA號稱語法簡便卻跟這句話一樣多點類別就長的不可思議




反正語言這種東西一回事，能明確表達想講的東西都是好語言

所以程設就是這樣一句

「用腦袋模擬程式運作，用程式模擬腦袋思維。」
                                     by 大神 allenown



--

進入正題，這次的作業叫因數分解...也就是把一個數切成數個質數的乘積


如果完全沒有頭緒去寫，那可以先想「如果要進行因數分解需要些什麼、要做些什麼」

因為要把某數分解為質數乘積，所以首先需要的是 1."有哪些數是質數"

有了質數之後，那再來就對傳入的數值進行處理...2."這個數會被那些質數除盡"

進而有 3."這個數會被除幾次"

最後，只要照格式輸出這個結果就完成題目要求了
當然，這是一種比較去省時間的做法...簡化的話在文末會提一下


嚴格說起來，這個題目最難/最簡單都是在 1. 的部分

寫出個質數表說簡單倒也不簡單這樣...下頁就從 1."有哪些數是質數"繼續說明


--

建質數表方法很多...顧及撰寫時間與程式執行速度
在可預知範圍的前提下大概是這招最為有效與合理 (?) http://tinyurl.com/29x9nvv

int prime[]=new int[]={2,3,5...........};


不過只講這招這文倒也寫不下去，因為顧及分數，所以手動刻一份表是非常合情合理的

質數的判斷很簡單 "一個不會被1與自己除盡的數"

因此，不顧及時間，最直覺的方法就是 把這個數一直試除取餘數看看

比方說..
for (int i=2;i<input;i++)
  if (input%i == 0)
    System.out.println(input+" is a prime number.")

像是這樣的直覺爆解法，然後只要把判斷出來的質數丟進去陣列放著就是質數表啦


--

再稍微經過一點數學推論

"能整除一個數的數，一定小於某數開根號"
就可以對這段code小小加速成


for (int i=2;i<Math.sqrt(input);i++)
  if (input%i == 0)
    System.out.println(input+" is a prime number.")


再進一步的方法就會是"只用之前判斷出是質數的數來除"

以及"減少使用取餘數與除法的次數"


不過那堆東西寫寫出來就能直接抄下去了，這樣不太好，至少對我成績來說(y)
有興趣的可以拿寫一半一類的狀況另外來問...
這部分觀念就請另外gooooooooogle關鍵字"質數 篩法"來思考

--

取得質數表後，就能進入作業本體的部分
一個層面來說，跟前面取質數的做法很接近
反正就是一直拿質數來測試能不能除盡

這部分應該是只提像是 8 = 2^3怎麼解決就好

照理論上腦袋已經建好的流程圖來說，最前頭是for loop跑質數
以input=8為例


for (int i=0;prime[i]<Math.sqrt(8);i++)
  if (8%prime[i]==0){
    ...
  }


寫到這一步應該要做得出來才對？
不然就得套用一下王老大發言了


--

除了input，在這裡其實還需要另建一個temp變數，就暫時叫tmp好了
tmp = input

在這個if (8%prime[i]==0)裏頭
事實上是做一個while去嘗試這個input可以被現在找到這個質數除幾次
我的作法大概會像是

while (tmp %prime[i] ==0){
  power++
  tmp/=prime[i]
}

從此來計算次方數，再利用得到這個次方與底數
就直接能輸出現在這個底數共有幾次方
System.out.print(prime+"^"+power)

說質數只要取到1000底下，則是因為如果把1000底下所有質數都除過除不盡了
那表示最後剩下的數字"也會是質數" 這樣

殘餘針對一次方不輸出/其他格式上的問題就請多利用if做幾個處理就能得到完整作業啦
--

前頭說好不建表又能得到作業的好方法(?)

就是利用爆解質數的方法跟最後這段檢查次方去直接跑，因為
"如果是合數，一定會先被該合數的質因數除盡"
所以可以在不做建表的前提下，直接得到分解的答案



然而，如果你到作業死線錢還沒搞懂，或是還沒開始做
我會推薦你聊勝於無的評分標準  2. 可寫成兩個數的乘積           (+30%)

這就很簡單啦...開個foooooooooooooooooor loooooooooooooooooooop
找到哪個數可以把現在這個數除盡，就把除數跟商數print出來就好
這樣至少有個程式可以交代你的分數這樣

--
  所恐懼的，不是沒有知識的大眾　          所憎恨的，不是深沉幽暗的人心
      而是自以為是的思考之聲                    而是自恃甚高的執法者

  所毀滅的，不是溫馨和諧的世界       這是我最後的期許，沒有憤怒、沒有悔恨
      而是自欺欺人的夢境                      只剩下，渾沌的死亡呼吸
                            　　　　　　　　　　　　　　 節自　新月神話－弒王者

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 115.43.50.239
推 CaptainWill:強大
推 jerry771210:JACA?
推 jerry771210:input int a, output "1*"+a   XDD
推 Arashinoon:新語法 JACA 語法強度跟安邦JOKE語法有得比
推 j2612280:樓上洗爹考
※ 編輯: game0416        來自: 220.130.128.171      (10/18 15:52)