你有一架天平.现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 NNN 的正整数重量.
1=11=11=1;
2=6−42=6−42=6−4(天平一边放 666,另一边放 444);
3=4−13=4−13=4−1;
7=1+67=1+67=1+6;
少于 333 个砝码不可能称出 111 至 777 的所有重量.
根据[转载]由数据范围反推算法复杂度以及算法内容,这题 10910^9109 的数据范围一般需要做到 O(n)O(\sqrt{n})O(n ) 的时间复杂度才能通过,所以这题应该是有通项公式之类的数学方法解决的.
大概能找出规律:每多一个可用的砝码,能称出来的重量上限为上一级的 333 倍加 111.
所以写个循环递推找到 能称出任意小于等于 NNN 的正整数重量 在 最小多少砝码能称出的重量上限之内 即可.