【机智题？】【Vijos】【天平称量】

天平称量

题目！

其实这并不是一道太难的题，但如何做需要细细分析。

 其实这里有一个重要的思想：
 
 正常情况下，对数据进行划分搜索效率，很明显： 3分>2分。( 就如 log3 < log2 )
  
 但由于代码实现和运行效率的原因，在实际的程序中效率：3分<2分。 

　　

（但其实我也不知道怎么证明，比心吧，据说来源是一道数学题。）　　

题解中有这样一个人：Nightingalelyy，他给出了他的想法：

对于3k的情况毫无疑问答案是a[k]+1,因为分成3个k称一次之后就跟k的情况相同


对于3k+1和3k+2，分别分成k，k，k+1和k，k+1，k+1，运气最差的情况就是那个重的在k+1的堆里，那么答案就是a[k+1]+1.

　　

然后就是代码了:

#include<iostream>
using namespace std;

int n;

int Calc (int num) {
    
    if (num==1) return 0;
    else if (num==2||num==3) return 1;
    else
      if (num%3==0) return Calc(num/3)+1;    
        else return Calc(num/3+1)+1;
    
} 

int main () {
    
    cin>>n;
    cout<<Calc(n)<<endl;
    
  return 0;    
    
} 

　　

如果有大神还知道更多的东西，欢迎直接赐我贵言，就算是喷也无妨！