中文XML论坛--求教一道题目

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> We choose to study algorithmic problems, not because they are easy, but because they are hard.

[返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『算法理论与分析』 → 求教一道题目

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 33326 个阅读者　　

*	贴子主题：求教一道题目	举报打印推荐 IE收藏夹
	本主题类别:

wcdxyl

  威望：4
  等级：大四(每天看1小时莱昂氏)(版主)
  文章：158
  积分：1145
  门派：IEEE.ORG.CN
  注册：2006/3/14

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第11楼

问题翻译过来大体是这样：有一个整数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编辑过]
----------------------------------------------
主页:http://wcdxyl.blogchina.com
MSN:wcdxyl@163.com

2006/10/23 15:26:00

wcdxyl

  威望：4
  等级：大四(每天看1小时莱昂氏)(版主)
  文章：158
  积分：1145
  门派：IEEE.ORG.CN
  注册：2006/3/14

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第12楼

我以前用ｊａｖａ写过一个算法，可以再改进，算法如下：
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;
}
----------------------------------------------
主页:http://wcdxyl.blogchina.com
MSN:wcdxyl@163.com

2006/10/23 15:52:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第13楼

我是用
while(x>0){
    if( x%10 == 1)
          sum++;
    x/=10;}
这样的方法算的。
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

2006/10/23 16:13:00

baibai

  等级：大一新生
  文章：1
  积分：61
  门派：XML.ORG.CN
  注册：2005/10/5

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第14楼

有思路，明天早上给答案

2006/11/6 22:49:00

lotusroots

  等级：大一新生
  文章：4
  积分：70
  门派：XML.ORG.CN
  注册：2006/11/6

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第15楼

看了一下，顺便计算了一下。发现这个题目是理论分析和编程结合（或许可以理论分析出来，只是我懒得费时间考虑了）的。
理论分析如下：
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;
}
}
代码借鉴了前面兄弟的代码,表示感谢.

2006/11/7 18:15:00

lotusroots

  等级：大一新生
  文章：4
  积分：70
  门派：XML.ORG.CN
  注册：2006/11/6

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第16楼

满足要求的所有值为：
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

2006/11/7 18:17:00

baibai

  等级：大一新生
  文章：1
  积分：61
  门派：XML.ORG.CN
  注册：2005/10/5

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第17楼

[quote]以下是引用lotusroots在2006-11-7 18:15:00的发言：
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);

2006/11/8 7:52:00

vingo555

  等级：大一(猛啃高等数学)
  文章：11
  积分：105
  门派：XML.ORG.CN
  注册：2006/10/11

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第18楼

535200001 不是最大de

2006/11/10 13:14:00

lonker

  等级：大一新生
  文章：0
  积分：54
  门派：IEEE.ORG.CN
  注册：2006/11/15

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第19楼

学习学习

2006/11/15 10:48:00

testlogic

  等级：大一新生
  文章：0
  积分：54
  门派：XML.ORG.CN
  注册：2006/11/21

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第20楼

以下是引用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;
又：（这里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;
  }
}
代码借鉴了前面兄弟的代码,表示感谢.

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

2006/11/21 19:13:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2025/8/13 10:46:53

本主题贴数22，分页： [1] [2] [3]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


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