[Java] UVa 11636 Hello World!

題目連結

題意:
在 C 語言中，要印出一行 Hello World!
需要執行一行printf("Hello World!\n");

假設不透過迴圈的方式
要印出1行以上，就只能寫同樣數量的指令
而且只能由原本的指令複製貼上

題目每行代表一組測資
給定要印出的總行數 N，輸出所需最少"複製貼上"的次數(複製貼上算一個步驟)

例:
要 2 行，原本 1 行，複製貼上那 1 行 = 2，共貼上 1 次
要 4 行，用前一例的 2 行都複製貼上 = 4 ，共貼上 2 次
要 5 行，前一例再複製貼上任一行 = 5 ，共貼上 3 次


解法:
因為題目要求要貼上最少次
先判斷每次貼上最多可以產生多少行 (當下的全部複製)

由於都必須由 1 行開始

第 1 次複製得到 2 行

第 2 次複製 全部 得到共 4 行

第 3 次複製 全部 得到共 8 行

依此類推，2 的 n 次方行數最少就需 n 次複製

3 行可以在第2次複製1行時得到
5, 6, 7 行在第3次複製時同理

因此，建立 2 的指數陣列
將題目的總行數 N 依序比，當 N 比陣列值小
該 index 就是對應的貼上數

如 N = 5，5 < 8
index 3 就是輸出值

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int c = 0;
	int pow[] = new int[20];
	pow[0] = 1;
	for (int n = 1, i = 1; i < 20; i++) {
	n *= 2;
	pow[i] = n;
	}
	while (sc.hasNext()) {
	c++;
	int N = sc.nextInt();
	if (N < 0)
	break;
	int ans = 0;
	while (pow[ans] < N)
	ans++;
	System.out.println("Case " + c + ": " +ans);
	}
	}
	}

view raw UVa11636.java hosted with ❤ by GitHub