百科问答小站 logo
百科问答小站 font logo



一个数减去各位数字之和需要多少次减为 0? 第1页

  

user avatar   qzane 网友的相关建议: 
      

一脸懵逼,随手又画了个k=63的图发现比值下降了,虽然不知道极限存不存在,但这说明在63进制下n / log n 可能不再是上界了,这个问题提的好啊...

============================

不严谨的回答一下,令func(n, k)代表n这个数字在k进制下减到0需要的次数,讨论关于n的增长率的时候k为常数。

因为一共只有log(n,k)位,而每一位最大的值为k,所以每一次减去的数不超过log(n,k)*k,所以我们有了这个函数增长率的下界:func(n,k) = Ω(n / log n)

关于上界的话,暂时没想到好的证明方法,但是我把n/log2 n与func(n,2)的比值画出来了,可以看出来比值是越来越大的,说明n / log n应该也是这个函数增长率的上界,我猜这个结论在其它进制下也是成立的。

补个n / log3 n 与 func(n, 3)之比的图,看起来结论在三进制下依然成立:


user avatar   ling-jian-94 网友的相关建议: 
      

估算一个上界。思路是每一轮都寻求一条最短线段,将当前包含天使的多边形,按面积等分成两个新的子多边形。再假设天使的运气足够好,每次都瞬移到等分效率较低的子多边形。

直观看出,取平行于正三角形一条边的线段来等分其面积,等分效率最高。令此线段长度 ,三角形边长 ,则:

这样,初始正三角形被分成一个新的小正三角形和一个等腰梯形,易见等腰梯形的等分效率远高于新的小正三角形,于是根据假设,天使将瞬移到新的小正三角形当中。如此循环,至于无穷,天使将被锁定在初始正三角形的一个顶点。计算魔鬼走过的耗时路程:

记魔鬼速度 ,则捉住天使的时间:

这个题目如此离散,不借助于数值离散优化不易得到全局最优解,建议大家来改进这个上界吧。


按照 @yyx 说的圆弧线等分正三角形以及后续的扇形,上界可以改进为:




  

相关话题

  请问B项和D项有什么区别吗? 
  减一个负数,为什么是加这个数的相反数呢? 
  直角三角形内知道两个锐角的角平分线长度,怎么求斜边? 
  有哪些数学上的定理让你感觉「这不显然吗,这还用证明」? 
  如何比较 √2与log3(5)的大小? 
  数学家是怎样思考问题的? 
  数学专业的学生的毕业论文是怎样的? 
  我这个数有葛立恒数的大吗? 
  为什么会有 i 这一虚数?可以求出 i 的值吗? 
  李群的伴随表示如何理解? 

前一个讨论
刘备伐吴的决策是完全错误吗?
下一个讨论
大学不加入社团和任何学生组织有影响吗?





© 2025-04-03 - tinynew.org. All Rights Reserved.
© 2025-04-03 - tinynew.org. 保留所有权利