这道题有什么好思路？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

这道题有什么好思路？

这道题有什么好思路？# Programming - 葵花宝典

s*r2006-02-17 08:02

1 楼

Input Output
1 0,1,2,..,9
2 0,1,2,...,98,99
3 0,1,2,...,999
......
不能用整数打印， 2^32 (Int32) 最多用到9或10，当input=11时会溢出。
据说用recursive algorithm
那位大侠给个思路。。。

t*t2006-02-17 08:02

2 楼

sub bt
{
my $i=shift;
my $prefix=shift;
for my $k (0..9) {
if ($i==1) {
print "$prefix$k\n";
} else {
bt ($i-1, ($prefix || $k) ? "$prefix$k" : "");
}
}
}
but do you really want to print those number literally?
if input=11, then it's 10^11 numbers.
O i like perl.

【在 s******r 的大作中提到】

: Input Output
: 1 0,1,2,..,9
: 2 0,1,2,...,98,99
: 3 0,1,2,...,999
: ......
: 不能用整数打印， 2^32 (Int32) 最多用到9或10，当input=11时会溢出。
: 据说用recursive algorithm
: 那位大侠给个思路。。。

s*r2006-02-17 08:02

3 楼

Thanks.
I don't know Perl. What is shift, my?
Could you translate it into C code?
thanks again.

【在 t****t 的大作中提到】

: sub bt
: {
: my $i=shift;
: my $prefix=shift;
: for my $k (0..9) {
: if ($i==1) {
: print "$prefix$k\n";
: } else {
: bt ($i-1, ($prefix || $k) ? "$prefix$k" : "");
: }

o*g2006-02-17 08:02

4 楼

private void print(String h,int n,int l)
{
if (l==0)
{
System.out.print(h);
System.out.println(n);
return;
}
for (int i=0;i<10;i++)
{
print(h+new Integer(n).toString(),i,l-1);
}
}
public void run(int input)
{
for (int i=0;i<10;i++)

【在 t****t 的大作中提到】

: sub bt
: {
: my $i=shift;
: my $prefix=shift;
: for my $k (0..9) {
: if ($i==1) {
: print "$prefix$k\n";
: } else {
: bt ($i-1, ($prefix || $k) ? "$prefix$k" : "");
: }

o*g2006-02-17 08:02

5 楼

递归算法本身的计算顺序是一个树的深度搜索
每一个节点都相同的method就好了（情况复杂的可能是有多个method的相互嵌套）
根节点的地方可以有硬编码
叶子的地方一定要能返回
这个例子我们可以这样安排这些数（如果i=3）
000-999
000-099 100-199 ..... 900- 999 （10个节点）
000-009 010-019.................................. 990-999 （100个节点）
000 001 002 ...................................998 999 （1000个节点）
从这个树能够发现规律，每一个节点上的数都是这样组成的：
开头的一段都是一样的，然后有一个数是固定的，后面若干位都是完全待定的
比如010-019，"0"是开头的,"1"是固定的，最后一位是待定的
再比如200-299，""是开头的，"2"是固定的，最后两位是待定的
所以，递归的method有三个参数，就这个意思
到叶子的时候，待定的