用python来做这个题目,还真好玩!

pitonas

这个题目 n = 100000
穷举不到半秒搞定还是可以接受的

i have a idea: count
呵呵，程序没还做出来

k在第几个位置？
example: k = 21 => 3
count 1 => total a个
count 2 => total b个

count k in 3 => c
k在第 a + b + c 的位置

效率: 没程序还没测试 ~ {:2_168:}

icymirror

个人理解：这个原始题目的目的不是说不允许穷举，毕竟当数据量不是那么大的时候，穷举还是可以解决不少问题的。
所以，原始题目特意指定数据的量是在10^18的范围，来使穷举变得不那么合算。
题目的意思应当是：
让我们通过一个合适的递归分解，来解决一个数可能有哪些排列方式。
比如：当数据在100000内的时候，如果是w(data) = 1，那可能的方式就只有：
1, 10, 100, 1000, 10000, 100000,　（共５个）
w(data)=2，可能的方式有：
2, 11, 101, 110......
从而让我们把问题转向数的可能的排列方式以及相应个数的递归分析上，然后，再应用第二条规则，找出第k个位置上的数是谁。

我想，这个是题目希望我们做的。  

ssfjhh

回复 12# icymirror


    你说的这个方法我考虑过，但是如果楼主给一个2897575896这样的数字，而不是整数的时候，这个方法就复杂多了。

icymirror

回复 13# ssfjhh
针对这个题目来说，没有特定的最好解决方案。
比如：就您刚刚给出的数字，如果数字的范围在0~3000000000 （2897575896快到结尾了）。
因为在枚举可能的排列时，要从1开始，除去列出所有可能组合之外，还需要记数当前一共出现了多少个排列。
这时，穷举反而不会在效率上比枚举所有可能的排列组合慢多少，反而更有可能是比较快的方法。
所以，我的说法只是针对题目的期望，并不是说什么样的方法是好的，呵呵。

pitonas

呵呵，程序没还做出来,
but i have a 穷举法的优化代码!
come here!

http://bbs.chinaunix.net/forum.p ... id=4150973#lastpost
ssfjhh:

1. 10000000, 10000 == 1m53.790s
   
2. 100000, 10000     == 0m0.994s

复制代码

pitonas:

1. 10000 10000000  == 0m47.963s
   
2. 10000 100000   == 0m0.443s

复制代码

pitonas

这时，穷举法的优化:
比如：就 k, n = 22, 100 来说
22      100     11      24

1 .. 100 generate a new ARRAY

ARRAY
index0: undef
index1
1 10 100

index2
2 11 20

index3
3 12 21 30

index4
4 13 22 31 40

22 ( 2 + 2 = 4 ) => index4
index1 ~ index3 = 3 + 3 + 4 => 10
[SORT!!] index4 [ 13 22 31 4 40 ]
22 's index = 1
10 + 1 = [ index = 11 ]

index5
5 14 23 32 41 50

index1 ~ index5
3 + 3 + 4 + 5 + 6 = 21 ( 21 < 22 )
index1 ~ index6
21 + 7 = 28 ( 28 > 22 )
22 IN index6
[SORT!!] index6

index6
15 24 33 42 51 6 60 [SORTED!!]

index 22 = count 21 + index6[1]
index6[1] => [ number = 24 ]

......

pitonas

因此，这是我的代码 ；

1. #!/usr/bin/perl
   
2. 
   
3. while (<DATA>) {
   
4.     my ( $K, $N ) = split;
   
5.     my ( $K_sum, @mind );
   
6.     $K_sum += $_ for split //, $K;
   
7. 
   
8.     for my $i ( 1 .. $N ) {
   
9.         my $sum;
   
10.         $sum += $_ for split //, $i;
    
11.         push @{ $mind[$sum] }, $i;
    
12.     }
    
13. 
    
14.     my $index = 0;
    
15.     $index += @$_ for @mind[ 1 .. $K_sum - 1 ];
    
16. 
    
17.     for my $n ( sort { $a cmp $b } @{ $mind[$K_sum] } ) {
    
18.         last if $K == $n;
    
19.         $index++;
    
20.     }
    
21. 
    
22.     my ( $INDEX, $I );
    
23. 
    
24.     for my $i ( @mind[ 1 .. $#mind ] ) {
    
25.         last if $INDEX > $K;
    
26.         $I++;
    
27.         $INDEX += @$i;
    
28.     }
    
29. 
    
30.     $mind[$I] = [ sort { $a cmp $b } @{ $mind[$I] } ];
    
31.     my $number = $mind[$I][ $K - $INDEX ];
    
32.     print join( "\t", $K, $N, $index, $number ), "\n";
    
33. }
    
34. __DATA__
    
35. 10000 100000

复制代码

change it for speed test
__DATA__
10000 10000000

r2007

等楼主放代码

substr函数

我想等楼主来放代码

bskay

回复 10# ssfjhh


那请你计算一下1到109999999999999999产生权中的第 7684342753的位置和第7684342753个位置的权是哪个数产生的
不知你没有看问题还是思维有问题啊，题目很明白的说明不要用穷举
当然机器好一点可以掩盖一些低劣的算法，也能让IT的门槛降低，退潮后就知道谁在裸泳了

我的电脑很破，是80年代产的古董，算到10万就吃不消了