天平称量假币

天平称量假币

有一个天平，需要在最少的次数中找到n个硬币中的一个假币.

分析.

1.天平两端放同样多的硬币才能进行判断

2.每次操作都将原有n个硬币分为leftn做盘硬币个数,rightn右盘硬币个数.lastn剩余硬币个数.

则的d[n]，表示有n个硬币时的最少称量次数.

d[n]=max{d[leftn],d[rightn],d[lastn]}+1;

可以动归

由于形势较为简单可以判断当

使得d[n]最小要求max{d[leftn],d[rightn],d[lastn]}，最小，经过尝试发现尽量将物品分为三份，

n/3,剩余的一定是0,1,2,则不剩余时则max为d[n/3],若剩余是1,max=d[n/3+1],否则剩余位2，时

leftn,rightn,lastn，找其中两个平摊剩余的两个，max=d[n/3+1](每个部分最少情况下最多有n/3+1)

4.显然当只有n=0||n==1是d[n]=1;

#include <iostream>

using namespace std;
int ansGeting(int n){int count=0;while(n!=0&&n!=1){n=n/3+(n%3==0?0:1);count++;}return count;
}
int main(){int n;memset(&d[4],-1,sizeof(d)-4);while(cin>>n)cout<<ansGeting(n)<<endl;return 0;
}