> ==>發信人: Ying-Chun Liu <PaulLiu.bbs@bbs.cis.nctu.edu.tw>, 信區: programming
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 快樂研究生 wrote:
> > 看到那個算200階的題目那麼多人討論
> > 不如現在大家逆向來思考
> > 一樣是用200著個簡單的數字 不過這次是要大家出題
> > 命題的要求是 形式越簡單越好 但是電腦卻要算很久或是無法在有生之年解出
> > 例如: 最接近10^200 的質數
> > pi 的小數第 200 位數
就照他講的那一題試試看:
假設有 200 個 node 標為 1-200 , 先用亂數產生彼此可能的 edge link 組
成一個 graph , 再假設亂接的 grap 有 200 種. 求這 200 種不同 graph
下, 從 node 1 出發以接近一筆畫的方式可以拜訪每個點, 最終回到 node 1
, 對每個 graph 列出路徑次序使經過的 edge cost (可假設為每個 edge
weight = 1) 總數為最少.
最笨的方法就是窮舉列出, 求所有可能的最小值.
> 這兩題目前電腦都是很快就跑出來
> import java.math.*;
> import java.lang.*;
> import java.io.*;
> public class HW1 {
> public static void main(String args[]) {
> BigInteger n = (new BigInteger("10")).pow(200);
> BigInteger ret = n;
> int i;
> for (i=0 ; !ret.isProbablePrime(200) ; i++)
> ret=n.add(new BigInteger(Integer.toString((i/2)*((i%2)*2-1))));
> System.out.println(ret.toString());
> }
> }
> 求 π 的, 網路上有個只有幾行的 C 程式就超過 200 位啦
> - --
> PaulLiu(劉穎駿)
--
◎ Origin: 中央松濤站□bbs.csie.ncu.edu.tw From: 140.115.6.234