題目描述
給出 n 個(gè)金幣痹栖，每個(gè)金幣重 10g辣恋，但是有一個(gè)金幣的重量是 11g。現(xiàn)在有一個(gè)能夠精確稱重的天平羔沙，問最少稱幾次躺涝，能夠確保找出那一個(gè)重量 11g 的金幣？
思路點(diǎn)撥
根據(jù)貪心的思想扼雏，每次盡可能大地縮小下次稱量金幣的個(gè)數(shù)坚嗜。故每次可以將金幣盡可能均勻地分成三份：若 n % 3 = 0夯膀，則分成 n/3、n/3苍蔬、n/3诱建，任意取兩份進(jìn)行比較。若 n % 3 = 1碟绑，則分成 n/3俺猿、n/3、 n/3 + 1格仲，取個(gè)數(shù)為 n/3 的兩份進(jìn)行比較押袍。若 n % 3 = 2，則分成 n/3 + 1凯肋、n/3谊惭。
考點(diǎn)分析
本題為簡(jiǎn)單的熱身題，主要考察貪心的思想否过，做到 bug free 即可午笛。
參考程序
https://www.jiuzhang.com/solution/weighing-problem/
/**
* 本參考程序來自九章算法，由 @華助教 提供苗桂。版權(quán)所有药磺，轉(zhuǎn)發(fā)請(qǐng)注明出處。
* - 九章算法致力于幫助更多中國(guó)人找到好的工作煤伟，教師團(tuán)隊(duì)均來自硅谷和國(guó)內(nèi)的一線大公司在職工程師癌佩。
* - 現(xiàn)有的面試培訓(xùn)課程包括：九章算法班，系統(tǒng)設(shè)計(jì)班便锨，算法強(qiáng)化班围辙，Java入門與基礎(chǔ)算法班，Android 項(xiàng)目實(shí)戰(zhàn)班放案，
* - Big Data 項(xiàng)目實(shí)戰(zhàn)班姚建，算法面試高頻題班, 動(dòng)態(tài)規(guī)劃專題班
* - 更多詳情請(qǐng)見官方網(wǎng)站：http://www.jiuzhang.com/?source=code
*/
public class Solution {
/**
* @param n: The number of coins
* @return: The Minimum weighing times int worst case
*/
public int minimumtimes(int n) {
// Write your code here
int ans;
ans = 0;
if (n % 3 == 0 ) {
n = n - 1;
}
while (n > 0) {
n = n / 3;
ans++;
}
return ans;
}
}
