中文XML论坛 - 专业的XML技术讨论区--显示贴子

以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『算法理论与分析』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  求教一道题目  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=38289)

--  作者：datoubaicai
--  发布时间：9/25/2006 10:12:00 PM

--  求教一道题目
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

--  作者：Logician
--  发布时间：9/25/2006 11:18:00 PM

--
我觉得f(n)=n只有两个解：1和0。

[此贴子已经被作者于2006-10-11 18:32:58编辑过]

--  作者：datoubaicai
--  发布时间：9/26/2006 9:02:00 PM

--
这个据说是GOOGLE的笔试题目

--  作者：Logician
--  发布时间：9/26/2006 9:09:00 PM

--
汗……
我觉得分析“1”出现的频率，可以证明，不会有大于1的解……

--  作者：phoenixinter
--  发布时间：9/30/2006 8:54:00 PM

--
how can it be possible that f(n)=n?

--  作者：vingo555
--  发布时间：10/11/2006 6:12:00 PM

--
so many such whole number,  But how to prove it is largest in theory ?

--  作者：Logician
--  发布时间：10/11/2006 6:32:00 PM

--
应该只有0和1啊。
你能举出第三个吗？

--  作者：vingo555
--  发布时间：10/12/2006 10:52:00 AM

--
OK: Index = 199981, Result is == 199981
OK: Index = 199982, Result is == 199982
OK: Index = 199983, Result is == 199983
OK: Index = 199984, Result is == 199984
OK: Index = 199985, Result is == 199985
OK: Index = 199986, Result is == 199986
OK: Index = 199987, Result is == 199987
OK: Index = 199988, Result is == 199988
OK: Index = 199989, Result is == 199989
OK: Index = 199990, Result is == 199990
OK: Index = 200000, Result is == 200000
OK: Index = 200001, Result is == 200001

--  作者：DavidPotter
--  发布时间：10/18/2006 9:47:00 AM

--
在网上搜一下，应该有一个计算f(n)的程序的。
不过通过仅对数字进行分析没有什么思路。。。

--  作者：Logician
--  发布时间：10/18/2006 12:15:00 PM

--
果然有很多……

0
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998
35000000
35000001
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199988
35199989
35199990
35200000
35200001
117463825

这个……
还真有点难……

--  作者：wcdxyl
--  发布时间：10/23/2006 3:26:00 PM

--
问题翻译过来大体是这样：有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问此后最大的f(n)=n的n是什么？
f(13)=6是因为1,2,3,4,5,6,7,8,9,10,11,12,13.中'1'的个数，正好是6.

[此贴子已经被作者于2006-10-23 15:58:26编辑过]

--  作者：wcdxyl
--  发布时间：10/23/2006 3:52:00 PM

--
我以前用ｊａｖａ写过一个算法，可以再改进，算法如下：
public int Func(int n){
  int m = 0;
  for(int i=0;i<=n;i++){
   String a = String.valueOf(i);
   for(int j=0;j<a.length();j++){
    String b = a.substring(j,j+1);
    if(b.equals("1")) m++;
   }
  }
  return m;
}

--  作者：Logician
--  发布时间：10/23/2006 4:13:00 PM

--
我是用
while(x>0){
    if( x%10 == 1)
          sum++;
    x/=10;}
这样的方法算的。

--  作者：baibai
--  发布时间：11/6/2006 10:49:00 PM

--
有思路，明天早上给答案

--  作者：lotusroots
--  发布时间：11/7/2006 6:15:00 PM

--
看了一下，顺便计算了一下。发现这个题目是理论分析和编程结合（或许可以理论分析出来，只是我懒得费时间考虑了）的。

理论分析如下：

f(10^n - 1) = 10*f(10^(n-1) -1) + 10^(n-1);
f(10^n) = f(10^n - 1) + 1;

推出：
f(10^n-1)=n*10^(n-1);
f(10^n) = n*10^(n-1) + 1;

又：（这里m = a1*10^(n-1) + a2*10^(n-2) +...+ an;）
f(m) = f(a1,a2,a3,a4,,,,an)=a1*f(10^(n-1) - 1) + 10^(n-1) + f(a2,a3,a4,,,an) + (a1 == 1)*(a2,a3,a4,,,,an) >= a1*n*10^(n-2) + 10^(n-1) > a1*n*10^(n-2) + (a2,a3,a4,,,an);
当n大于等于10时，有：
a1*n*10^(n-2) + (a2,a3,a4,,,an) >= a1*10^(n-1) + (a2,a3,a4,,,an) = (a1,a2,a3,a4,,,an) = m;
所以，当n大于等于10的时候，都是不可能发生f(m) = m的情况的，这些时候，f(m)均大于m。

那么，我们仅仅需要测试0-999999999这些情况了。

结果是：
535200001

java代码如下：
public class Calor {
public static void main(String[] args) {
  int pre = 0;
  for (int i = 1; i < 1000000000; i++) {
   pre += f(i);
   if (pre == i)
    //System.out.println(i + ":" + pre);
    System.out.println(pre);
  }
}

public static int f(int n) {
  int m = 0;
  while (n > 0) {
   if (n % 10 == 1)
    m++;
   n /= 10;
  }
  return m;
}
}

代码借鉴了前面兄弟的代码,表示感谢.

--  作者：lotusroots
--  发布时间：11/7/2006 6:17:00 PM

--
满足要求的所有值为：

1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998
35000000
35000001
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199988
35199989
35199990
35200000
35200001
117463825
500000000
500000001
500199981
500199982
500199983
500199984
500199985
500199986
500199987
500199988
500199989
500199990
500200000
500200001
501599981
501599982
501599983
501599984
501599985
501599986
501599987
501599988
501599989
501599990
502600000
502600001
513199998
535000000
535000001
535199981
535199982
535199983
535199984
535199985
535199986
535199987
535199988
535199989
535199990
535200000
535200001

--  作者：baibai
--  发布时间：11/8/2006 7:52:00 AM

--
[quote]以下是引用lotusroots在2006-11-7 18:15:00的发言：

f(10^n-1)=n*10^(n-1);
f(10^n) = n*10^(n-1) + 1;

这两个答案是没有错的，但是下边的呢，这个式子感觉不大对了

--  作者：vingo555
--  发布时间：11/10/2006 1:14:00 PM

--
535200001 不是最大de

--  作者：lonker
--  发布时间：11/15/2006 10:48:00 AM

--
学习学习

--  作者：testlogic
--  发布时间：11/21/2006 7:13:00 PM

--

以下是引用lotusroots在2006-11-7 18:15:00的发言：
看了一下，顺便计算了一下。发现这个题目是理论分析和编程结合（或许可以理论分析出来，只是我懒得费时间考虑了）的。

理论分析如下：

f(10^n - 1) = 10*f(10^(n-1) -1) + 10^(n-1);
f(10^n) = f(10^n - 1) + 1;

推出：
f(10^n-1)=n*10^(n-1);
f(10^n) = n*10^(n-1) + 1;

那么，我们仅仅需要测试0-999999999这些情况了。

结果是：
535200001

java代码如下：
public class Calor {
  public static void main(String[] args) {
   int pre = 0;
   for (int i = 1; i < 1000000000; i++) {
    pre += f(i);
    if (pre == i)
     //System.out.println(i + ":" + pre);
     System.out.println(pre);
   }
  }

  public static int f(int n) {
   int m = 0;
   while (n > 0) {
    if (n % 10 == 1)
     m++;
    n /= 10;
   }
   return m;
  }
}

代码借鉴了前面兄弟的代码,表示感谢.

不要自以为是,我的程序算到1111111110这个结果,花了比较多时间就是了

--  作者：xiaoyou8519
--  发布时间：7/27/2008 12:21:00 AM

--
我代码不写了。就说一下我的一点认识把。
（0）n位数共含有n*10^(n-1)个1
（1）由n位数到n+1位数增加(n+1)*10^n - n*10^(n-1)个1
（2）对于n+1位数分两种情况讨论：首位为1；首位不为1
（3）此题显然有上界

--  作者：xiaoyou8519
--  发布时间：7/27/2008 12:24:00 AM

--
lotusroots 兄的代码我没看，但估计思路差不多。
问一下，lotusroots兄现在在做什么？

W 3 C h i n a ( since 2003 ) 旗下站点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》

101.563ms