Poj1013解题心得

October 28, 2013 21:17


好久没做题了,这两天回家略无聊,没心情玩游戏了,于是又开始来拿poj上的题目来练练了。

这题目,以前看过一会,后来没做了,昨天才开始拿起来解,由于昨天没怎么想,直接就动手, 用了1个多小时没解出来就去睡觉了,今天又花了一个小时的样子,还是乱摸,呃好吧, 确实一下弄不出来,于是把笔和纸来画了,思路如下:

首先,天平有三次比较数据,每次比较有三种结果,我采用了排除法来确实哪个是假的硬币, 有如下情况:

比较结果是 even, 那么所有比较的硬币一定为真 比较结果非 even, 那么没在天平上的所有硬币一定为真(只有一个假的嘛) 如果一个硬币两次位置不变,但是天平的结果确变了,那这个硬币一定是真的 如果一个硬币两次位置不一样,但是天平的结果确是一样的,那么这个硬币一定是真的 依据以上判断,非平衡状态下最后两个判断的的比较代码:

// coin.loca 是上一次位置, loca是coin的当前位置
// coin.weight 表示天平位置,或硬币是否为真
// status 是当前的天平状态
if (coin.loca == loca && coin.weight != status ) {
  coin.weight = GOOD;
  continue;
}

if (coin.loca != loca && coin.weight == status) {
  coin.weight = GOOD;
  continue;
}

// 如果不确定真假,就设置一下硬币位置,天平状态
coin.loca = loca;
coin.weight = status;

前面两个判断最好写的,这个就不多说了,最后显示假的硬币

for (int i = 0; i < COINS_COUNT; i++) {
  if (coins[i].weight != GOOD) {
    Coin &coin = coins[i];
    cout<<char(i + 65)<<" is the counterfeit coin and it is ";

    if (coin.loca == LEFT) {
      cout<<(coin.weight == DOWN ? "light" : "heavy")<<".\n";
    } else {
      cout<<(coin.weight == UP ? "light" : "heavy")<<".\n";
    }
  }
}

再用题目讨论中的测试数据一下,基本上没问题了。最后题目 源代码

Comments: