有故障的打字机 — 编程爱好者社区

主题：有故障的打字机

ypyybbo [专家分：30] 发布于 2007-10-08 20:11:00

问题描述
    一台打字机准备将1到10^n的数依次打出。在打印过程中，这台打字机出现了一个故障：数字“3”打不出来。因此，所有含有数字“3”的数都没有被正确地打出。试问没有被正确打出的数一共有多少个。

输入数据
    输入一个正整数n。

输出数据
    输出从1到10^n这些数中不能被正确打印的数的个数。

输入样例
2

输出样例
19

时间限制
    各测试点1秒

内存限制
    你的程序将被分配32MB的运行空间

数据规模
    n<=1000

本帖地址： http://bbs.pfan.cn/post/253051.html

回复列表（共6个回复）

沙发

angwuy [专家分：2280] 发布于 2007-10-08 20:23:00

用数学方法

板凳

ypyybbo [专家分：30] 发布于 2007-10-08 20:30:00

说清楚一点！！！
拜托！！！

3 楼

ypyybbo [专家分：30] 发布于 2007-10-08 20:39:00

求助啊求助！！！拜托啊，各路神仙！！！

4 楼

punkrocker [专家分：720] 发布于 2007-10-09 16:40:00

我猜用字符串判断是否有“3”比较容易

5 楼

angwuy [专家分：2280] 发布于 2007-10-09 19:00:00

用排列与组合的方法：
某一位出现3的有9^(n-1)*n/1个
某两位出现3的有9^(n-2)*n*(n-1)/(1*2)个
某三位出现3的有9^(n-3)*n*(n-1)/(1*2*3)个
某三位出现3的有9^(n-3)*n*(n-1)*(n-2)/(1*2*3*4)个
某三位出现3的有9^(n-3)*n*(n-1)*(n-2)*(n-3)/(1*2*3*4*5)个
...
全部都是3的有9^(n-n)*n*(n-1)*...*1/(1*2*3*4*5*...n)个

再算总和就行了

6 楼

angwuy [专家分：2280] 发布于 2007-10-09 19:04:00

这题应该还需要用到高精度

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：有故障的打字机

回复列表（共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：有故障的打字机

回复列表 （共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共6个回复）