这个估计不能当做面试题.上一行是n值,下一行是第一个要猜的数.1 21 23 4 5 6 7 82 3 4 5 6 79~246~2125~6018~5361~7450~6375~10060~85
■网友
这道题没说是平均还是最坏情况，姑且按最坏情况计算。
设1-N的最小Cost总数为cost(1,N)
cost(1,N)=min =min
cost(1,0)=0;
cost(1,1)=1;
【这道猜数字面试题的窍门在哪里】 cost(1,2)=3
依次计算，这就是一个动态规划问题，复杂度为O（n^2)

■网友
没想出特别的好办法，以下是一个难点：

----------------------------------------------------------------------------------------------------写了一段代码，代码算法很乱、排版很乱、亦未优化，但速度还行（当然了，是否正确，我没办法验证，因为手工计算量太大）#include \u0026lt;iostream\u0026gt;#include \u0026lt;utility\u0026gt;#include \u0026lt;vector\u0026gt;#include \u0026lt;cassert\u0026gt;class foo{public: foo() { buf_.push_back( std::vector\u0026lt;branch_\u0026gt;(1,branch_(0,0,0)) ); buf_.push_back( std::vector\u0026lt;branch_\u0026gt;(1,branch_(1,1,1)) ); // 对于{x+1}而言，只有1种分割方式，即从1开始分，总cost为1*x+1 // 对于 x+1 到 x+8 这8个数，有两种可能的最小分割方法： // 若以 { {无 x+1 x+2} x+3 {x+4 x+5 {x+6 x+7 x+8}} } 方式分割，总cost = 22*x + 92 // 若以 { {x+1 x+2 x+3} x+4 {x+5 x+6 {无 x+7 x+8}} } 方式分割，总cost = 21*x + 93 } unsigned bar( unsigned n ) { buf_.reserve( n+1 ); for( unsigned i=buf_.size(); i\u0026lt;n+1; ++i ) { buf_.push_back( std::vector\u0026lt;branch_\u0026gt;() ); for( unsigned j=1; j!=i; ++j ) append_branchs_( buf_.back(), j, cost_(1,j-1,formula_(1,j)), formula_(1,j), cost_(j+1,i,formula_(1,j)) ); } unsigned cost; printmiddle_( 1, n, cost ); printf( "(cost = %u)\", cost ); return cost; }private: struct formula_ { unsigned k, b; formula_( unsigned k_, unsigned b_ ) : k(k_), b(b_) { } }; struct branch_ { unsigned middle; formula_ fml; branch_( unsigned middle_, unsigned k_, unsigned b_ ) : middle(middle_), fml(k_,b_) { } }; std::vector\u0026lt; std::vector\u0026lt;branch_\u0026gt; \u0026gt; buf_; std::vector\u0026lt;formula_\u0026gt; cost_( unsigned a, unsigned b, formula_ base ) const { if( a \u0026gt; b ) return std::vector\u0026lt;formula_\u0026gt;(1,formula_(0,0)); std::vector\u0026lt;formula_\u0026gt; ret; ret.reserve( buf_.size() ); for( size_t i=0; i!=buf_.size(); ++i ) { // 对于这b-a+1个数而言，总cost = kx + b // 则对于这b-a+1个数而言，总cost = k(x+a-1) + b = kx + (k*(a-1)+b) formula_ f = buf_.fml; f.b += f.k * (a-1); f.k += (b-a+1)*base.k; f.b += (b-a+1)*base.b; bool bignore = false; for( std::vector\u0026lt;formula_\u0026gt;::iterator itor=ret.begin(); !bignore \u0026amp;\u0026amp; itor!=ret.end(); ) { if( f.k\u0026gt;=itor-\u0026gt;k \u0026amp;\u0026amp; f.b\u0026gt;=itor-\u0026gt;b ) bignore = true; else if( f.k\u0026lt;=itor-\u0026gt;k \u0026amp;\u0026amp; f.b\u0026lt;=itor-\u0026gt;b ) itor = ret.erase( itor ); else ++itor; } if( !bignore ) ret.push_back( f ); } return ret; } static void append_branchs_( std::vector\u0026lt;branch_\u0026gt;\u0026amp; all, unsigned middle, const std::vector\u0026lt;formula_\u0026gt;\u0026amp; a, const formula_\u0026amp; b, const std::vector\u0026lt;formula_\u0026gt;\u0026amp; c ) { for( size_t i=0; i!=a.size(); ++i ) { for( size_t j=0; j!=c.size(); ++j ) { formula_ f( a.k+b.k+c.k, a.b+b.b+c.b ); bool bignore = false; for( std::vector\u0026lt;branch_\u0026gt;::iterator itor=all.begin(); !bignore \u0026amp;\u0026amp; itor!=all.end(); ) { if( f.k\u0026gt;=itor-\u0026gt;fml.k \u0026amp;\u0026amp; f.b\u0026gt;=itor-\u0026gt;fml.b ) bignore = true; else if( f.k\u0026lt;=itor-\u0026gt;fml.k \u0026amp;\u0026amp; f.b\u0026lt;=itor-\u0026gt;fml.b ) itor = all.erase( itor ); else ++itor; } if( !bignore ) all.push_back( branch_(middle,f.k,f.b) ); } } } unsigned getmiddle_( unsigned a, unsigned b, unsigned\u0026amp; cost ) const { const size_t n = b-a+1; unsigned middle = buf_.middle + (a-1); cost = (a-1) * buf_.fml.k + buf_.fml.b; for( size_t i=1; i!=buf_.size(); ++i ) { unsigned cost_ = (a-1) * buf_.fml.k + buf_.fml.b; if( cost_ \u0026lt; cost ) { middle = buf_.middle + (a-1); cost = cost_; } } return middle; } unsigned printmiddle_( unsigned a, unsigned b, unsigned\u0026amp; cost ) const { if( a == b ) { cost = a; return a; } unsigned cost_m; unsigned middle_m = getmiddle_( a, b, cost_m ); cost = cost_m; unsigned cost_l=0, middle_l = 0; if( middle_m \u0026gt; a ) middle_l = printmiddle_( a, middle_m-1, cost_l ); unsigned cost_r=0, middle_r=0; if( middle_m \u0026lt; b ) middle_r = printmiddle_( middle_m+1, b, cost_r ); printf( "", middle_l, middle_m, middle_r ); assert( cost_m == cost_l + cost_r + (b-a+1)*middle_m ); return middle_m; }};#include \u0026lt;ctime\u0026gt;int main(){ clock_t t1 = clock(); foo f; f.bar( 100 ); //f.bar( 100 ); // 耗时 0.015 秒 //f.bar( 200 ); // 耗时 0.062 秒 //f.bar( 300 ); // 耗时 0.234 秒 //f.bar( 500 ); // 耗时 1.453 秒 //f.bar( 1000 ); // 耗时 27.046 秒 clock_t t2 = clock(); printf( " ---- %ld.%03ld ---\", (t2-t1)/CLOCKS_PER_SEC, (t2-t1)%CLOCKS_PER_SEC ); return 0;}