找回密码
 注册
Simdroid-非首页
查看: 407|回复: 19

[基础概念] 每周一题“问这本书有多少页?”

[复制链接]
发表于 2010-3-14 15:58:38 | 显示全部楼层 |阅读模式 来自 上海宝山区
为了给一本厚书的各页标上页码,
印刷工人用了2989个数字,
问这本书有多少页?
发表于 2010-3-14 18:42:14 | 显示全部楼层 来自 北京
Simdroid开发平台
先给个For循环:
  1. zishu = 2989;
  2. yeshu =
  3. For[j = 1; yeshu = 0, True, j++,
  4.   yeshu += Length@IntegerDigits@j;
  5.   If[yeshu >= zishu,
  6.    If[yeshu > zishu,
  7.     Print["Err"]; Break[],
  8.     Print[j]; Break[]
  9.     ]
  10.    ]
  11.   ]


  12. 1024
复制代码

评分

1

查看全部评分

回复 不支持

使用道具 举报

发表于 2010-3-14 22:41:17 | 显示全部楼层 来自 北京海淀
  1. Module[{n = 1, p := Length@Flatten[IntegerDigits /@ Range[#]] &},
  2. While[p[n] < 2989, n++]; n]
复制代码

评分

1

查看全部评分

回复 不支持

使用道具 举报

发表于 2010-3-15 07:08:53 | 显示全部楼层 来自 北京
本帖最后由 ggggwhw 于 2010-3-15 12:43 编辑

jimogsh 的代码虽短,但是效率还不如我在2楼的For循环效率呢,而且还大量占用内存.
既然FreddyMusic 是要考验效率的,那么我想我下面的代码效率应该是最高的了,几乎不占内存.

  1. In[1]:=
  2. zishu = 3725742742586314258657243585712425381245752124385742165;
  3. For[j = 1; k = 0, True, j++, h = k; k = h + j*9*10^(j - 1);
  4.   If[zishu <= k, jieguo = (zishu - h)/j + 10^(j - 1) - 1; Break[]];];
  5. If[IntegerQ@jieguo, jieguo,
  6. "输入的字数" <> ToString[zishu] <> "有误,\n最接近的两种情况是:" <> "\n当字数:" <>
  7.   ToString[1/10 (10 h + 10 j - 10^j j + 10 j*Floor@jieguo)] <>
  8.   "时,\n页数是:" <> ToString[Floor@jieguo] <> ".\n当字数:" <>
  9.   ToString[1/10 (10 h + 10 j - 10^j j + 10 j*Ceiling@jieguo)] <>
  10.   "时,\n页数是:" <> ToString[Ceiling@jieguo] <> "."]
  11. Out[3]= 70506676484857082448459522581576160233148362933902891
复制代码
下面是用Module封存后的表达式,我想效率应该是相同的.

  1. In[4]:=
  2. zishu = 3725742742586314258657243585712425381245752124385742165;
  3. Remove@yeshu;
  4. yeshu[zishu_] := Module[{j, k, h, jieguo},
  5.    For[j = 1; k = 0, True, j++,
  6.     h = k; k = h + j*9*10^(j - 1);
  7.     If[zishu <= k, jieguo = (zishu - h)/j + 10^(j - 1) - 1; Break[]];];
  8.    If[IntegerQ@jieguo, jieguo,
  9.     "输入的字数" <> ToString[zishu] <> "有误,\n最接近的两种情况是:" <> "\n当字数:" <>
  10.      ToString[1/10 (10 h + 10 j - 10^j j + 10 j*Floor@jieguo)] <>
  11.      "时,\n页数是:" <> ToString[Floor@jieguo] <> ".\n当字数:" <>
  12.      ToString[1/10 (10 h + 10 j - 10^j j + 10 j*Ceiling@jieguo)] <>
  13.      "时,\n页数是:" <> ToString[Ceiling@jieguo] <> "."]
  14.    ];
  15. yeshu[zishu]

  16. Out[7]= 70506676484857082448459522581576160233148362933902891

复制代码
如果2楼的是O(n)那么4楼的就是O(10^n)了
回复 不支持

使用道具 举报

 楼主| 发表于 2010-3-15 08:32:35 | 显示全部楼层 来自 上海
Length + IntegerDigits = IntegerLength

计算效率和代码整洁两者都要,但是前者优先级高。
回复 不支持

使用道具 举报

发表于 2010-3-15 12:58:41 | 显示全部楼层 来自 北京
本帖最后由 ggggwhw 于 2010-3-16 18:26 编辑

6楼的waynebuaa 真是专家说了一句外行话,
写程序的目的只在于为懒人服务.让你写一套程序再来打印一个表格,你会觉得先写程序,再打表格还没有直接拿笔画表格快呢,但是随着表格数量的增加,直接画拿笔表格所用的时间差不多与表格数量的关系可以写成t=k*n的形式,而程序做表格的时间可以写成t=a+b*n的形式.b<n时,总存在一个数目n使得后者的时间小于前者的时间的.
那么你用笔可能算该题目给出的数字时比较快,但是如我在4层给出的总数字3725742742586314258657243585712425381245752124385742165时,你能说你快吗?假定你还是快,那么对于下面的总数字你还快吗?37257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537253725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537257427425863142586572435857124253812457521243857421637257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216
我的代码在1秒内给出的结果是是: 75442385702377031776687342040962277173215854969571928673758813469023128278883309102881652818536160395742617968590456245687737929102905809073590383068190938359686898073613030068529751873218154564163610397757807415456471362907861711306416482868374160869802335322339445999088431837344875584082943833396120540421529078792649053350138730259855341167964076311100297506549321707628810435158973208171768934610172813296264568468697352949115861329662503003411711274782463515861274660634917481146403946731

后面有人说我给的初值有问题,那么我接受后面的说法,将初值改成
zishu=
37257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537253725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537257427425863142586572435857124253812457521243857421637257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574497
我的程序是以前面的初值为基础算的,后来复制时忘了改一下初值.
回复 不支持

使用道具 举报

发表于 2010-3-15 17:01:56 | 显示全部楼层 来自 北京
waynebuaa 在10楼的代码经过我的测试,在天文数字方面的所花时间是我的代码所花时间的50%,每次看到你的代码总能让我感到以外,看着咱们两个代码的差别很小的,效率却总是你的高.

至于11楼的纠正我也接受,那是我对O这个函数的定义不太理解.
再顺便说一声:10楼的代码还是有问题的,问题出在了循环的判断上,比如你想当然的认为9*10^页数*页数 <=字数,但是对于小数字你的判断是有问题的,比如页数6,则字数6到了你的判别式却是错误的.其它的小数字出错的情况也比较多,比如135,我为了取得页数的上限,曾经拿页数与字数的比值进行过研究,发现比值一直减小,所以无法从字数直接判断页数的数量级.
所以我在判断语句里写的是True这也是我比Table更加喜欢For的一个原因了,因为它会自己根据Break判断退出的.

容错代码我以前也用的是和你的代码一样的形式,后来改成了现在的形式,为了让我更快的找到满足条件的zishu用来检验输入满足条件的zishu时的运算结果.
回复 不支持

使用道具 举报

发表于 2010-3-15 20:53:20 | 显示全部楼层 来自 湖南湘潭
本帖最后由 lin2009 于 2010-3-16 16:41 编辑

分析一下方法更简单

数的范围   1~9   10~99  100~999  1000~9999      ...
数的字数    1         2           3                     4          ...
数的个数    9        90         900               9000         ...
总的字数  1*9      2*90      3*900          4*9000     9*n*10^(n-1)


题设的总字数为 zishu
设 xyz = Sigma (9*n*10^(n-1), n = 1..k) = ((9/10)*10^(k+1)*(k+1)-10^(k+1)+1)/9, k为xyz<=zishu时最大的整数。

页码page为:
page =  10^k-1 +  (zishu-xyz) / (k+1)

公式推导如下
k = 0时       1<page<9          page =  0 + (zishu-xyz) /1
k = 1时     10<page<99        page =  9 + (zishu-xyz) /2
k = 2时    100<page<999     page =  99 + (zishu-xyz) /3
...
k  = k时  10^k-1<page<10^(k+1)-1     page =  10^k-1+ (zishu-xyz) /(k+1)


于是题目变成求解最大整数k的问题。
(另,14#,15#有误,为了不使楼塌掉,就不删除了)

评分

1

查看全部评分

回复 不支持

使用道具 举报

发表于 2010-3-15 20:56:05 | 显示全部楼层 来自 湖南湘潭
k = 1时 页码为  9 + (page-xyz)/(k+1)
k = 2时 页码为  99 + (page-xyz)/(k+1)
k = 3时 页码为  999 + (page-xyz)/(k+1)
...
也可以写成统一的表达式
回复 不支持

使用道具 举报

发表于 2010-3-15 21:18:07 | 显示全部楼层 来自 湖南湘潭
10^(k+1)-1 +  (page-xyz)/(k+1)
回复 不支持

使用道具 举报

发表于 2010-3-15 22:46:13 | 显示全部楼层 来自 北京
下面是我把10楼waynebuaa 的代码重新写了一遍,当然
13楼lin2009 的思路和10楼waynebuaa是一样的.

  1. zishu = 37257427425863142586572435857124253812457521243857400;
  2. Remove@z;
  3. z[n_] := (1/9 - 10^n/9 + 10^n n);
  4. n = 0;
  5. While[z[n] <= zishu, n++]; n--;
  6. tmp = (zishu - z[n]);
  7. jieguo = tmp/(n + 1) - 1 + 10^n;
  8. If[IntegerQ@jieguo, jieguo,
  9. "输入的字数" <> ToString[zishu] <> "有误,\n最接近的两种情况是:" <> "\n当字数:" <>
  10.   ToString[Quotient[tmp, (n + 1)]*(n + 1) + z[n]] <> "时,\n页数是:" <>
  11.   ToString[Floor@jieguo] <> ".\n当字数:" <>
  12.   ToString[Quotient[tmp + n + 1, (n + 1)]*(n + 1) + z[n]] <>
  13.   "时,\n页数是:" <> ToString[Ceiling@jieguo] <> "."]

  14. Out[]= 732716441901455954856540136632065978893502595195460
复制代码
回复 不支持

使用道具 举报

发表于 2010-3-16 09:47:09 | 显示全部楼层 来自 湖南湘潭
下面的方程能否直接求出
((9/10)*10^(n+1)*(n+1)-10^(n+1)+1)/9 <= zishu,求最大的整数n。(源自10楼)
我试了Maple,算不出来。
回复 不支持

使用道具 举报

发表于 2010-3-16 12:47:22 | 显示全部楼层 来自 美国
  1. page[t_] :=
  2. Module[{n = 1}, While[n 10^n - 1/9 (10^n - 1) < t, n = n + 1];
  3.   n = n - 1;
  4.   Return[x /.
  5.     Solve[n 10^n - (10^n - 1)/9 + (n + 1) (x - 10^n + 1) == t,
  6.       x][[1]]]]
复制代码
  1. page[2989]
复制代码

评分

1

查看全部评分

回复 不支持

使用道具 举报

 楼主| 发表于 2010-3-16 16:49:32 | 显示全部楼层 来自 江苏苏州
代码变量要么用中文,要么用英文, 拼音歧义非上策。

你们谁呢最后给个,一个字符也改不了的代码?
回复 不支持

使用道具 举报

发表于 2010-3-16 16:53:01 | 显示全部楼层 来自 湖南湘潭
本帖最后由 lin2009 于 2010-3-16 21:21 编辑

用修改后的13#算法,采用maple计算,验证了6# ggggwhw 的例子。程序如下,仅供参考。
restart;
total := 37257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537253725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537257427425863142586572435857124253812457521243857421637257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216;
fsolve(log10(((9/10)*10^(k+1)*(k+1)-10^(k+1)+1)*(1/9)) = log10(total));
k = floor(%);
page = 10^k-1+(total-((9/10)*10^(k+1)*(k+1)-10^(k+1)+1)*(1/9))/(k+1)
evalf(page);

返回答案:page = 7.544238570*10^493
回复 不支持

使用道具 举报

发表于 2010-3-16 17:37:14 | 显示全部楼层 来自 湖南湘潭
7# ggggwhw

(total-((9/10)*10^(k+1)*(k+1)-10^(k+1)+1)*(1/9))/(k+1) 的余数为213,
所以给出的总字数37257427425....是个不合适的数,即不可能的数。
回复 不支持

使用道具 举报

发表于 2010-3-16 18:35:41 | 显示全部楼层 来自 北京
接受23楼lin2009 的说法,我将总字数改成了37257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537253725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537257427425863142586572435857124253812457521243857421637257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574497
看了后面那么多算法后,发现其实速度并没有提高哦,当然maple的算法我没有测试.
但是我发现其实只有我考虑了如果总字数有问题时,如何获得与所给总字数最接近的两个正确总字数.换句话说,只有我为用户想的更多了.其实如果将程序写完了,谁还会在意你是写了多少行呢?程序本身并不占太多硬盘空间的,而界面,所占内存和运行速度才是最重要的.
以上是我对好程序的理解.
回复 不支持

使用道具 举报

发表于 2010-3-16 18:41:15 | 显示全部楼层 来自 北京
本帖最后由 ggggwhw 于 2010-3-16 18:43 编辑

对于21楼FreddyMusic的说法我很不满意
拼音岐义非上策.
那么英文就没有岐义吗?中文就没有岐义吗?你不喜欢在论坛上写中文嫌慢,但是你至少不用换输入法啊,我也不喜欢在代码中写代码因为那样要不停地换输入法.写英文实在不好意思,我不爱国但是我更不喜欢外语.
我不喜欢在代码中写汉语,但是我也不强迫别人看我的拼音,所以我的输出界面还是用的汉语提示.这说明我还是能克制自己的想法又能照顾用户的心理的.
回复 不支持

使用道具 举报

 楼主| 发表于 2010-3-17 09:09:42 | 显示全部楼层 来自 江苏苏州
很久以前, 我的好友 aba 同志,就告诉我 我写得 Mathematica 书字体太小.
我那时狂那, 目空一切, 为此还和他吵了一架, 说他是老古董.
现在我后悔不已, 悔不该当时不停他的忠言, 现在麻烦的要命.
回复 不支持

使用道具 举报

发表于 2013-8-19 19:48:37 | 显示全部楼层 来自 北京
本帖最后由 chyanog 于 2013-8-19 19:53 编辑

RuleBased:
  1. i = 0; 0 //. p_ /; p < 2989 :> p + IntegerLength@++i; i

  2. 0 //. i_ /; Length[Join @@ IntegerDigits@Range[i]] < 2989 :> i + 1
复制代码

评分

1

查看全部评分

回复 不支持

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|小黑屋|联系我们|仿真互动网 ( 京ICP备15048925号-7 )

GMT+8, 2024-3-29 19:40 , Processed in 0.077263 second(s), 19 queries , Gzip On, MemCache On.

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表