練習 - Hangover

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)。
Math-1.4-2

輸入:輸入由一個或多個測試資料組成,最後一行使用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();
        	}
	}
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

*

驗證碼 * Time limit is exhausted. Please reload CAPTCHA.

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料