每周一题“问这本书有多少页?”
为了给一本厚书的各页标上页码，印刷工人用了2989个数字，
问这本书有多少页? 先给个For循环:zishu = 2989;
yeshu =
For[j = 1; yeshu = 0, True, j++,
yeshu += Length@IntegerDigits@j;
If[yeshu >= zishu,
If[yeshu > zishu,
Print["Err"]; Break[],
Print; Break[]
]
]
]
1024 Module[{n = 1, p := Length@Flatten] &},
While < 2989, n++]; n] 本帖最后由 ggggwhw 于 2010-3-15 12:43 编辑
jimogsh 的代码虽短,但是效率还不如我在2楼的For循环效率呢,而且还大量占用内存.
既然FreddyMusic 是要考验效率的,那么我想我下面的代码效率应该是最高的了,几乎不占内存.
In:=
zishu = 3725742742586314258657243585712425381245752124385742165;
For[j = 1; k = 0, True, j++, h = k; k = h + j*9*10^(j - 1);
If];];
If[IntegerQ@jieguo, jieguo,
"输入的字数" <> ToString <> "有误,\n最接近的两种情况是:" <> "\n当字数:" <>
ToString <>
"时,\n页数是:" <> ToString <> ".\n当字数:" <>
ToString <>
"时,\n页数是:" <> ToString <> "."]
Out= 70506676484857082448459522581576160233148362933902891
下面是用Module封存后的表达式,我想效率应该是相同的.
In:=
zishu = 3725742742586314258657243585712425381245752124385742165;
Remove@yeshu;
yeshu := Module[{j, k, h, jieguo},
For[j = 1; k = 0, True, j++,
h = k; k = h + j*9*10^(j - 1);
If];];
If[IntegerQ@jieguo, jieguo,
"输入的字数" <> ToString <> "有误,\n最接近的两种情况是:" <> "\n当字数:" <>
ToString <>
"时,\n页数是:" <> ToString <> ".\n当字数:" <>
ToString <>
"时,\n页数是:" <> ToString <> "."]
];
yeshu
Out= 70506676484857082448459522581576160233148362933902891
如果2楼的是O(n)那么4楼的就是O(10^n)了 Length + IntegerDigits = IntegerLength
计算效率和代码整洁两者都要，但是前者优先级高。 本帖最后由 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
我的程序是以前面的初值为基础算的,后来复制时忘了改一下初值. waynebuaa 在10楼的代码经过我的测试,在天文数字方面的所花时间是我的代码所花时间的50%,每次看到你的代码总能让我感到以外,看着咱们两个代码的差别很小的,效率却总是你的高.
至于11楼的纠正我也接受,那是我对O这个函数的定义不太理解.
再顺便说一声:10楼的代码还是有问题的,问题出在了循环的判断上,比如你想当然的认为9*10^页数*页数 <=字数,但是对于小数字你的判断是有问题的,比如页数6,则字数6到了你的判别式却是错误的.其它的小数字出错的情况也比较多,比如135,我为了取得页数的上限,曾经拿页数与字数的比值进行过研究,发现比值一直减小,所以无法从字数直接判断页数的数量级.
所以我在判断语句里写的是True这也是我比Table更加喜欢For的一个原因了,因为它会自己根据Break判断退出的.
容错代码我以前也用的是和你的代码一样的形式,后来改成了现在的形式,为了让我更快的找到满足条件的zishu用来检验输入满足条件的zishu时的运算结果. 本帖最后由 lin2009 于 2010-3-16 16:41 编辑
分析一下方法更简单
数的范围 1~9 10~99100~9991000~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#有误，为了不使楼塌掉，就不删除了） k = 1时 页码为9 + (page-xyz)/(k+1)
k = 2时 页码为99 + (page-xyz)/(k+1)
k = 3时 页码为999 + (page-xyz)/(k+1)
...
也可以写成统一的表达式 10^(k+1)-1 +(page-xyz)/(k+1) 下面是我把10楼waynebuaa 的代码重新写了一遍,当然
13楼lin2009 的思路和10楼waynebuaa是一样的.
zishu = 37257427425863142586572435857124253812457521243857400;
Remove@z;
z := (1/9 - 10^n/9 + 10^n n);
n = 0;
While <= zishu, n++]; n--;
tmp = (zishu - z);
jieguo = tmp/(n + 1) - 1 + 10^n;
If[IntegerQ@jieguo, jieguo,
"输入的字数" <> ToString <> "有误,\n最接近的两种情况是:" <> "\n当字数:" <>
ToString*(n + 1) + z] <> "时,\n页数是:" <>
ToString <> ".\n当字数:" <>
ToString*(n + 1) + z] <>
"时,\n页数是:" <> ToString <> "."]
Out[]= 732716441901455954856540136632065978893502595195460
下面的方程能否直接求出
((9/10)*10^(n+1)*(n+1)-10^(n+1)+1)/9 <= zishu，求最大的整数n。(源自10楼)
我试了Maple，算不出来。 page :=
Module[{n = 1}, While;
n = n - 1;
Return[x /.
Solve[n 10^n - (10^n - 1)/9 + (n + 1) (x - 10^n + 1) == t,
x][]]]page 代码变量要么用中文，要么用英文， 拼音歧义非上策。
你们谁呢最后给个，一个字符也改不了的代码？ 本帖最后由 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 7# ggggwhw
(total-((9/10)*10^(k+1)*(k+1)-10^(k+1)+1)*(1/9))/(k+1) 的余数为213，
所以给出的总字数37257427425....是个不合适的数，即不可能的数。 接受23楼lin2009 的说法,我将总字数改成了37257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537253725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574216537257427425863142586572435857124253812457521243857421637257427425863142586572435857124253812457521243857421653725742742586314258657243585712425381245752124385742165372574274258631425865724358571242538124575212438574497
看了后面那么多算法后,发现其实速度并没有提高哦,当然maple的算法我没有测试.
但是我发现其实只有我考虑了如果总字数有问题时,如何获得与所给总字数最接近的两个正确总字数.换句话说,只有我为用户想的更多了.其实如果将程序写完了,谁还会在意你是写了多少行呢?程序本身并不占太多硬盘空间的,而界面,所占内存和运行速度才是最重要的.
以上是我对好程序的理解. 本帖最后由 ggggwhw 于 2010-3-16 18:43 编辑
对于21楼FreddyMusic的说法我很不满意
拼音岐义非上策.
那么英文就没有岐义吗?中文就没有岐义吗?你不喜欢在论坛上写中文嫌慢,但是你至少不用换输入法啊,我也不喜欢在代码中写代码因为那样要不停地换输入法.写英文实在不好意思,我不爱国但是我更不喜欢外语.
我不喜欢在代码中写汉语,但是我也不强迫别人看我的拼音,所以我的输出界面还是用的汉语提示.这说明我还是能克制自己的想法又能照顾用户的心理的. 很久以前, 我的好友 aba 同志,就告诉我 我写得 Mathematica 书字体太小.
我那时狂那, 目空一切, 为此还和他吵了一架, 说他是老古董.
现在我后悔不已, 悔不该当时不停他的忠言, 现在麻烦的要命. 本帖最后由 chyanog 于 2013-8-19 19:53 编辑
RuleBased：i = 0; 0 //. p_ /; p < 2989 :> p + IntegerLength@++i; i
0 //. i_ /; Length] < 2989 :> i + 1
页:
[1]