Hangover
題目:使一疊在桌子上的卡片向桌子外伸出多遠?如果是一張卡片,這張卡片最多可以向桌子外伸出卡片的一半長度(卡片需以直角伸出桌子)。如果有兩張卡片,就讓上面一張卡片向外伸出下面那張卡片的一半長度,而下面那張卡片伸出桌子卡片的三分之一長度,所以兩張卡片總向外延伸為1/2 + 1/3 = 5/6卡片長度,依此類推,n張卡片向外延伸1/2 + 1/3 + 1/4 + … + 1/(n + 1)卡片長度,最上面的向外延伸1/2 第二張向外延伸1/3,第三張向外延伸1/4,…,最下面一張向外延伸1(n + 1)。
輸入:輸入由一個或多個測試資料組成,最後一行使用0表示輸入結束,每個測試資料佔據一行,是一個3位的正浮點數c,最小值0.01,最大值5.20。
輸出:對每個測試資料c,輸出要至少伸出超過c的卡片長度所最少要用的卡片的數目。
import java.util.Scanner; public class Hangover { final static int maxn = 300; //設定len陣列容量 final static double delta = 1e-8; //設定精度 public static int zero(double x) //在精度delta的範圍內,若x是小於負精度的為負實數,則返回-1;若x是大於正精度的為正實數,則返回1;若x在精度區間,則返回0。 { if(x < -delta) return -1; else if(x > delta) return 1; return 0; } public static void main(String[] args) { double len[] = new double[maxn]; int total; len[0] = 0.0; for(total = 1; zero(len[total - 1] - 5.20) < 0; total++) //直接計算出截止長度不超過5.20所需的最少卡片數 len[total] = len[total - 1] + 1.0 / (total + 1); double x; Scanner scanIn = new Scanner(System.in); //輸入下一個資料 x = scanIn.nextDouble(); while(zero(x) > 0){ //用二元法在len表中搜尋不小於x的最少卡片數 int l, r; l = 0; //設定搜尋區間的左右指標 r = total; while(l + 1 < r){ int mid = (l + r) / 2; //計算搜尋區間的中間指標,若中間元素值少於x,則在右區間搜尋;不則在左區間搜尋 if(zero(len[mid] - x) < 0) l = mid; else r = mid; } System.out.printf("%d card(s)", r); //輸出至少伸出x長度最少要用的卡片數 scanIn = new Scanner(System.in); //輸入下一組資料 x = scanIn.nextDouble(); } } }
鏈結到這頁!