0到300之间共出现多少个9?

hutule110

UID: 7208
帖子: 177
积分: 407
在线时间: 1 天 18 小时

1^# hutule110 发表于 2008-01-11 11:11

0到300之间共出现多少个9?

[Copy to clipboard] [ - ]

CODE:

use strict;
my $str = "";
for (my $i=9;$i<=299;$i++) {
$str .= $i;
}
my @str_arr = split(//,$str);
my @num_arr = grep {$_ == 9} @str_arr;
my $num = @num_arr;
print $num;

谁能給个更简单的算法么?

ly5066113

UID: 41125
帖子: 34
积分: 78
在线时间: 1 小时

2^# ly5066113 发表于 2008-01-11 11:37

for(0..300){$sum++ if /9/}

perljoker

UID: 30669
帖子: 88
积分: 202
在线时间: 10 小时

3^# perljoker 发表于 2008-01-11 11:39

[Copy to clipboard] [ - ]

CODE:

use strict;
my $num=0;
foreach(9..299){
$num+= $_=~s/9//g;
}
print $num;

Nosferatu

UID: 5185
帖子: 94
积分: 216
在线时间: 12 小时

4^# Nosferatu 发表于 2008-01-11 11:42

2楼是错的

$i = 0;
map { $i += tr/9// } (0 .. 300);
print $i;

p.s. 这样的代码写着玩可以，实际工作中用要挨骂了

hutule110

UID: 7208
帖子: 177
积分: 407
在线时间: 1 天 18 小时

5^# hutule110 发表于 2008-01-11 11:48

谢谢楼上的各位

rs1020545

UID: 16173
帖子: 2
积分: 4
在线时间: 10 分钟

6^# rs1020545 发表于 2008-01-11 12:00

对于连续的数字，每10个就有一个9（个位数），每100就有10个9（十位数），每1000……
就是：

print 300/10*1+300/100*10;

这种事情，就像是1+2+3+.....+99+100一样，用循环目的只是用来学习，真正算的时候肯定用公式。

perljoker

UID: 30669
帖子: 88
积分: 202
在线时间: 10 小时

7^# perljoker 发表于 2008-01-11 12:15

QUOTE:

原帖由 rs1020545 于 2008-1-11 12:00 发表
对于连续的数字，每10个就有一个9（个位数），每100就有10个9（十位数），每1000……
就是：

print 300/10*1+300/100*10;

这种事情，就像是1+2+3+.....+99+100一样，用循环目的只是用来学习，真正算的时 ...

呵呵，可是你这个算法不对啊，比如说299
再想想，改一下

CU_wanglijun

UID: 19952
帖子: 1
积分: 2
在线时间: 10 分钟

8^# CU_wanglijun 发表于 2008-01-11 13:19

6楼的想法很有启发性啊
确实是只有平时小问题第一反应是算法而不是语法才能有更大的进步
我就差的远呢

Lonki

UID: 21498
帖子: 1
积分: 2
在线时间: 10 分钟

9^# Lonki 发表于 2008-01-12 02:23

字符串方法就不说了.

递归/递推都行:
令f(a, b) (a<=b)表示从a到b中出现的9的总数

显然:
f(0, 300) = f(0, 99) + f(100, 199) + f(200, 299) + f(300, 300)
      = f(0, 99) * 3
而
f(0, 99) = f(0, 9) + f(10, 19) + ... + f(90, 99)
      = f(0, 9) * 10 + f(0, 9) * 10 ### 或 f(0, 9) * 9 + f(0, 9) * 10 + 1 = 20
      = 1 * 10 + 1 * 10
      = 20
所以f(0, 300) = f(0, 99) * 3 = 20 * 3 = 60

递归式:
考虑到f(a, b) = f(0, b) - f(0, a) 只需得出f(0, n)即可

To be continued...