给定整数0-9的库存，在用完某个整数之前，我能写的最后一个数字是什么？
正如标题所述，给定整数0-9的存量，在用完某个整数之前，我能写的最后一个数字是什么？
所以，如果给我一个股票，比如说从0到9的每一个数字10，在我用完某个数字之前，我能写的最后一个数字是多少。例如，如果股票是2，我可以写数字1. 10：
%1%2%3%4%5%6%7%8%9 10
此时我的股票是0，我不能写11。还请注意，如果给我一个股票3，我仍然只能写数字1. 10，因为11将花费我两个1，这将使我的股票在-1。
到目前为止，我得出的结论是：
public class Numbers {
public static int numbers(int stock) {
int[] t = new int[10];
for (int k = 1; ; k++) {
int x = k;
while (x > 0) {
if (t[x % 10] == stock) return k-1;
t[x % 10]++;
x /= 10;
}
}
}
public static void main(String[] args) {
System.out.println(numbers(4));
}
}有了这个，我可以得到正确的答案，相当大的股票规模。当库存大小为10^6时，代码在大约2秒内完成，而库存为10^7的数字则需要整整27秒。这还不够好，因为我正在寻找一个可以处理10^16的库存大小的解决方案，所以我可能需要一个O(log(n))解决方案。
这是一份像作业一样的作业，所以我很长一段时间没有和这个泡菜搏斗而来到这里。我没能通过谷歌搜索出类似的东西，wolfram不认识这给出的任何模式。
到目前为止，我得出的结论是，所有的都会先用完。我没有证据，但事实如此。
有人能提点建议吗？非常感谢。
编辑：
我想出并实现了一种有效的方法来找到数字1.n的成本，多亏了btilly的指示(见他的帖子和下面的评论)。也被标记为解决方案)。在实现了二进制搜索之后，我将进一步阐述这一点，以找到您今天晚些时候可以用给定的股票编写的最后一个数字。
编辑2:解决方案
我完全忘记了这篇文章，所以我很抱歉之前没有在我的解决方案中进行编辑。不过，我不会复制实际的实现。
我的代码用于查找一个数字的成本，其代码如下：
首先，让我们选择一个数字，例如9999。现在，我们将通过将每一个数字的成本相加得到成本，如下所示：
9 9 9 9
^ ^ ^ ^
^ ^ ^ roof(9999 / 10^1) * 10^0 = 1000
^ ^ roof(9999 / 10^2) * 10^1 = 1000
^ roof(9999 / 10^3) * 10^2 = 1000
roof(9999 / 10^4) * 10^3 = 1000因此，9999的成本是4000。
256人的情况相同：
2 5 6
^ ^ ^
^ ^ roof(256 / 10^1) * 10^0 = 26
^ roof(256 / 10^2) * 10^1 = 30
roof(256 / 10^3) * 10^2 = 100因此，256的成本是156。
用这种思想实现将使程序只对没有数字1或0的数字工作，这就是为什么需要进一步的逻辑。让我们调用上面解释的方法C(n，d)，其中n是我们获得成本的数字，d是我们目前正在使用的nE 212的d'th数字。我们还定义了一个方法E 113D(n，d)E 214/code>，它将从E 115de 216从E 117nE 218返回E 115dE 216>E 218，然后应用以下逻辑：
sum = C(n, d)
if D(n, d) is 1:
for each k < d, k >= 0 :
sum -= ( 9 - D(n, k) ) * 10^(k-1);
else if D(n, d) is 0:
sum -= 10^(d-1)这样，程序将有效地计算出一个数字的正确成本。在此之后，我们只需应用二进制搜索来找到具有正确成本的数字。
回答 2
Stack Overflow用户
发布于 2014-09-09 18:32:46
步骤1.编写一个有效的函数来计算需要使用多少股票才能将所有的数字写入N。(提示:使用公式计算用于在最后一个数字中写出数字的所有内容，然后使用递归计算其他数字中使用的所有数字。)
第二步，进行二进制搜索，找出你可以用你的股票量写的最后一个数字。
Stack Overflow用户
发布于 2014-09-12 02:39:14
我们可以直接计算出答案。递归公式可以确定从1到10减1幂的数字需要多少股票：
f(n, power, target){
if (power == target)
return 10 * n + power;
else
return f(10 * n + power, power * 10, target);
}
f(0,1,1) = 1 // a stock of 1 is needed for the numbers from 1 to 9
f(0,1,10) = 20 // a stock of 20 is needed for the numbers from 1 to 99
f(0,1,100) = 300 // a stock of 300 is needed for the numbers from 1 to 999
f(0,1,1000) = 4000 // a stock of 4000 is needed for the numbers from 1 to 9999当我们的计算出现在上述系数的第一个倍数之后时，就需要计算额外的1；例如，在10 (11-19)的第二个倍数上，我们需要对每个数字增加一个1。
JavaScript代码：
function f(stock){
var cs = [0];
var p = 1;
function makeCoefficients(n,i){
n = 10*n + p;
if (n > stock){
return;
} else {
cs.push(n);
p *= 10;
makeCoefficients(n,i*10);
}
}
makeCoefficients(0,1);
var result = -1;
var numSndMul = 0;
var c;
while (stock > 0){
if (cs.length == 0){
return result;
}
c = cs.pop();
var mul = c + p * numSndMul;
if (stock >= mul){
stock -= mul;
result += p;
numSndMul++;
if (stock == 0){
return result;
}
}
var sndMul = c + p * numSndMul;
if (stock >= sndMul){
stock -= sndMul;
result += p;
numSndMul--;
if (stock == 0){
return result;
}
var numMul = Math.floor(stock / mul);
stock -= numMul * mul;
result += numMul * p;
}
p = Math.floor(p/10);
}
return result;
}输出：
console.log(f(600));
1180
console.log(f(17654321));
16031415
console.log(f(2147483647));
1633388154https://stackoverflow.com/questions/25751327
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号