设f(k)= y其中k是非负整数递增序列中的第y个数,其二进制表示中的数目为1,与k相同,例如f(0)= 1,f(1)= 1,f(2)= 2,f(3)= 1,f(4)= 3,f(5)= 2,f(6)= 3,依此类推。 给定k> = 0,计算f(k)
我们很多人都看过这个问题
1这个问题的解决方案是根据1的数量对数字进行分类然后找到rank.i确实找到了一些模式,但这将是一个漫长的过程。 有谁能建议我一个更好的解决方案?
这是一个计数问题。 我认为,如果你考虑到这一点,你可以做得比在字面上枚举值和检查它们有多少位要好得多。
考虑数字17.二进制表示是10001.1的数量是2.我们可以得到两个1的较小数字(在这种情况下)将1重新分配给四个低位中的任何一个。 4选择2是6,所以17应该是第7个数字,在二进制表示中有2个。 我们可以查一下……
0 00000 - 1 00001 - 2 00010 - 3 00011 1 4 00100 - 5 00101 2 6 00110 3 7 00111 - 8 01000 - 9 01001 4 10 01010 5 11 01011 - 12 01100 6 13 01101 - 14 01110 - 15 01111 - 16 10000 - 17 10001 7
我们是对的。 推广这个想法,你应该得到一个有效的函数,你只需计算 k的等级。
编辑:提示一般化17的特殊之处在于,如果不考虑高阶位,则数字的等级为1; 也就是说,f(z)= 1其中z是除高阶位之外的所有内容。 对于不是这种情况的数字,您如何解释这样一个事实:您可以在不移动高位的情况下获得更小的数字?
f(k)是小于或等于k的整数,其二进制表示中具有与k相同数量的1。
例如,k需要m比特,即k = 2^(m-1) + a
,其中a < 2^(m-1)
。 选择小于2^(m-1)
且与k具有相同位数的整数的数量choose(m-1, bitcount(k))
,因为您可以在m-1
最低有效位中自由地重新分配。
大于或等于2 ^(m-1)的整数具有与k(其为1)相同的最高有效位,因此存在f(k - 2^(m-1))
。 这意味着f(k) = choose(m-1, bitcount(k)) + f(k-2^(m-1))
。
请参阅“有效枚举集合的子集” 。 请看表3,“银行家序列”。 这是一种精确生成所需序列的方法(如果反转位顺序)。 只需用K位运行K迭代。 该文件中包含生成它的代码。
需要了解更多c/c++开发分享根据1的数量查找数字的等级,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享根据1的数量查找数字的等级相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979067.html