練習 － 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)。

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