公告版位

目前分類:UVa Online Judge (7)

瀏覽方式: 標題列表 簡短摘要

一、目的:在電腦科學中有小部份的領域是使用電腦來產生證明和協助驗證,首先四色問題的證明就是完全

            依靠電腦程式的協助來完成並且目前已經確認成功的將高階語言轉換至低階的晶片。

            這個問題的計算量與部份的費瑪最後定理相關:

                    根據上述定理,  106img1.gif  ,當n>2 時沒有正整數解。

            (連結UVa online原文題庫)

 

二、問題說明:

     給一個正整數N, 寫一個程式計算右式的兩次方程式的解  一     106img2.gif

     這裡的x,y,z是限制正整數小於等於N,計算truple(x,y,z)的數量且x<y<z,並且它們是互質,

     (ie.,它們沒有共同的除算大於1)。並且另外計算0<p<=N的數量,這理的p不屬於任何truple

yunjuihuang 發表在 痞客邦 留言(0) 人氣()

一、目的:隨著高速繪圖工作站、CAD(電腦輔助設定)和其他領域(CAM,VLSI design)的出現讓電腦愈

            來愈具有影響力。其中之一的問題就是如何在繪圖時排除隱藏線(hidden lines)的問題而所謂

            的隱藏線即該線段必須被其他繪圖的部份所遮蔽。  (連結UVa online原文題庫)

 

二、問題說明:

     如何設計一個程式來幫助一位建築師從所給建築物在城市中的位置去繪製一個城市的天際線。

     為了讓這個問題更容易處理則所有的建築物形成都是矩形且它們都是在共同的底部。這個城市

     是一個二維度觀點,因此所有的建築物是由三個資料項(L,H,R)所定義。L、R表示建築物左、右的

     座標位置,H表示建築物的高度。 參考圖如下:

      圖左: (1,11,5),(2, 6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)

yunjuihuang 發表在 痞客邦 留言(0) 人氣()

一、目的:近來使用電腦在金融企業進行爭議的交易程序即是利用極小的價格波動來進行獲利已經被

             許多華爾街公司所禁止。計算機程式倫理是一個新興的領域並且包含許多棘手的問題。

             (連結UVa online原文題庫)

 

二、問題說明:

     套匯是指將一個國家的貨幣透過與其他國貨幣之間極小的差異進行交易並使其獲得利益。

     因此如何寫一個程式根據給定的交易表並依照上述的規則,計算出可獲得利益的套匯交易流程。

     例如:  1美金等於0.7英鎊 1英鎊等於9.5法朗 1法朗等於0.16美元

              1 x 0.7 x 0.95 x 0.16 = 1.064  - 1 = .064 (profit)

 

yunjuihuang 發表在 痞客邦 留言(0) 人氣()

一、目的: 在數學及計算機科學中某些觀念在一維或二維是很簡單,但是當擴展至任意維度時將會

              變的很複雜。例如解決數個維度中的不同方程式和分析n維度立方體的拓撲等問題;但是

              由於後者在不同的維度之間存在著一個明顯的關係,因此前者在高維度時比後者還要複雜。

              (連結UVa online原文題庫)

 

二、問題說明:

        多維度箱子的收納問題是如何讓一系列同維度但不同大小的箱子進行最大巢狀收納的方法。

        而在進行巢狀收納時有下列條件及規則:

                1、維度內的數值可以任意的對調。 EX: (2,6) => (6,2)

                2、排序後外部箱子中同位置的維度數值必須比內部箱子中同位置的維度數值還要大。

yunjuihuang 發表在 痞客邦 留言(0) 人氣()

一、目的:在固定的限制中進行裝箱或是依照重量放置物體到不同的箱子是歷史上有趣的問題,某些

            裝箱問題是NP-complete,但是可以使用動態規劃法 (Dynamic Programming)或是

            啟法式演算法(Heuristic)來解決這類型的問題。     (連結UVa online原文題庫)

 

二、問題說明:

     回收玻璃的問題主要是將回收的玻璃分成棕色(Brown)、綠色(Green)、透明(Clear)三種不同顏色

     的種類後將不同堆但是同顏色的玻璃瓶移至同一堆,但是處理過程中必須儘量減少玻璃瓶的移動數量。

     該問題在兩個條件下成立:

         (1) 可在同一堆中放置無限數量的玻璃瓶            (2)所有的玻璃瓶的數量小於2^31

 

yunjuihuang 發表在 痞客邦 留言(0) 人氣()

一、目的:許多的計算機科學領域是使用簡單,抽象的觀念來進行分析和實驗的研究。因此這個問題的

            目的是如何在特定的規則和條件下透過有限的命令來讓目標達成某種特定的狀態,而不是直

            接讓目標去達成某種特定的狀態。(連結UVa online原文題庫)

 

二、問題說明:

     解析一系列的命令來指示機器手臂如何去操作位於桌子上的區塊,初始時桌子上有n個區塊

      (編號為0~n-1)並且依編號由小而大依序排列,如下圖所示:

      101.jpg

     程式必須提供下列五種不同的命令來操作上述的區塊:

     1、move a onto b 一

yunjuihuang 發表在 痞客邦 留言(0) 人氣()

一、目的:計算機科學中常見的問題是將問題依照其特性進行分類,因此這個問題主要的目的是如何依照

            特定的演算法將所有未知的輸入資料進行分類。(連結UVa online原文題庫)

 

二、問題說明:

     考慮下列的演算法:

     100.jpg

    當輸入整數值22時則會依序輸出如右的數值序例:22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

    由於該演算法是假設對於輸入任何的整數會結束(n=1), 因此必須依照上述的演算法對於所有輸入的整數

    (0~1,000,000)進行驗證。驗證的方式為給一整數n 則可以決定輸出數值的數量,即是cycle-length of n.

    因此當輸入兩個數值時,程式必須輸出兩個數值區間的最大cycle-length值。(EX:n=22,cycle-length=16)

yunjuihuang 發表在 痞客邦 留言(0) 人氣()