【问题】$K 的 INDEX 是几？

pitonas

同样的问题 ~
http://bbs.chinaunix.net/thread-4150152-1-1.html

1. __DATA__
   
2. 24  20000
   
3. 31  100000
   
4. 54  5000000
   
5. 690  400000

复制代码

1. while (<DATA>){
   
2.     my ( $K, $N ) = split;
   
3.     my ( $index, $num );
   
4.     dosomething;
   
5.     say "$K\t$N\t$index\t$num";
   
6. }

复制代码

DATA:

$N: ( 第 1 个 char 正整数 1 .. 9 ) , 其余是 0 ....
$K: 1 < $K < $N

问题:

• $K 的 INDEX 是几？
• INDEX $K 的数是几？
  

INDEX 的算法:

1. my @a = 1 .. $N;
   
2. my @b = map { $_->[0] }
   
3.         sort { $a->[1] <=> $b->[1] || $a->[0] cmp $b->[0] } # cmp !!
   
4.         map { [ $_, SUM($_) ] } @a;
   
5.         
   
6. sub SUM {
   
7.     my ( @chars, $sum ) = split //, shift;
   
8.     $sum += $_ for @chars;
   
9.     return $sum;
   
10. }

复制代码

$K 的 INDEX 是几？ =>
find $index: $b[$index] == $K
INDEX $K 的数是几？ =>
$num = $b[$K]

这是说，INDEX 是 数组 @b 的 index, 不是 数组 @a 的 index
保持数组 @b 在头脑内, 但不把它写进代码中

计算出这个 $index, $num


这个问题的限制 !!

不能使用穷举法 sort 出这个array @b

1. my @b = map { $_->[0] }
   
2.         sort { $a->[1] <=> $b->[1] || $a->[0] cmp $b->[0] }
   
3.         map { [ $_, SUM($_) ] } @a;

复制代码

算出这个 $index, $num !


$K 的 INDEX 是几？
INDEX $K 的数是几？

q1208c

what are you saying ?

pitonas

http://bbs.chinaunix.net/thread-4150152-1-1.html
same question ~ {:2_168:}

回复 2# q1208c


   

q1208c

回复 3# pitonas

很多人觉得, 程序写得越简单, 越是高手. 我同意.
因为我永远成不了高手, 注定只是个 coder.

我永远不会在Perl程序中使用默认变量. 也不会使用未声明的变量.

我是个完美主义者, 虽然做不到, 但我一直努力让别人可以看懂我的code.



楼主的, code, 我实在看不懂. 我匿了.

afukada

這個題目有意思

應該可以使用divide and conquer來做

不過我最近沒時間

所以先不要讓這個帖沉下去

pitonas

支持你 ~ {:2_168:}

回复 5# afukada


   

pitonas

大神~ 这个只是婴儿等级代码啊。
a sort : Schwartzian transform
a sub: SUM
~~ {:2_170:}

回复 4# q1208c


   

pitonas

my $师傅, 我有一个问题，
一般我写这个问题代码是这样写的:
( 更少的代码更容易理解, 一点点优化代码在下一楼 )

1. sub SUM {
   
2.     my $sum;
   
3.     $sum += $_ for split //, shift;
   
4.     $sum;
   
5. }
   
6. 
   
7. while (<DATA>) {
   
8.     my ( $K, $N ) = split;
   
9.     my @mind = sort { $a->[1] <=> $b->[1] || $a->[0] cmp $b->[0] }
   
10.       map { [ $_, SUM($_) ] } 1 .. $N;
    
11.     my $index;
    
12.     for my $i ( 0 .. $#mind ) {
    
13.         if ( $mind[$i][0] == $K ) { $index = $i; last }
    
14.     }
    
15.     my $number = $mind[$K][0];
    
16.     say join "\t", $K, $N, $index, $number;
    
17. }
    
18. __DATA__
    
19. 24  20000
    
20. 31  100000
    
21. 54  5000000
    
22. 690  400000

复制代码

但你说：程序写得越简单, 越是高手

我尽我所能写我的代码如下: 我是非常满意的! {:2_168:}
我, 尽我所能的放弃了 perl 语言的特性, 让别人可以看懂我的 代码.

1. sub SUM {
   
2.     my ($number) = @_;
   
3.     my $len = length $number;
   
4.     my @chars;
   
5.     for ( my $i = 0 ; $i < $len ; $i++ ) {
   
6.         my $char = substr $number, $i, 1;
   
7.         push @chars, $char;
   
8.     }
   
9.     my $sum = 0;
   
10. 
    
11.     for my $c (@chars) {
    
12.         $sum = $sum + $c;
    
13.     }
    
14. 
    
15.     return $sum;
    
16. }
    
17. 
    
18. while ( my $line = <DATA> ) {
    
19.     chomp $line;
    
20.     my ( $K, $N ) = split /\t/, $line;
    
21.     my @wait_for_sort = ();
    
22. 
    
23.     for ( my $n = 1 ; $n <= $N ; $n++ ) {
    
24.         my $sum       = SUM($n);
    
25.         my @two_elems = ();
    
26.         push @two_elems, $n;
    
27.         push @two_elems, $sum;
    
28.         push @wait_for_sort, [@two_elems];
    
29.     }
    
30. 
    
31.     my @Semi_products =
    
32.       sort { $a->[1] <=> $b->[1] || $a->[0] cmp $b->[0] } @wait_for_sort;
    
33.     my @array_in_mind = ();
    
34. 
    
35.     for my $semi (@Semi_products) {
    
36.         my @two_elems = @{$semi};
    
37.         my ( $number, $sum ) = @two_elems;
    
38.         push @array_in_mind, $number;
    
39.     }
    
40. 
    
41.     my $index;
    
42.     my $counter1 = 0;
    
43. 
    
44.     for my $num (@array_in_mind) {
    
45.         if ( $num == $K ) {
    
46.             $index = $counter1;
    
47.         }
    
48.         $counter1 = $counter1 + 1;
    
49.     }
    
50. 
    
51.     my $number;
    
52.     my $counter2 = 0;
    
53. 
    
54.     for my $num (@array_in_mind) {
    
55.         if ( $counter2 == $K ) {
    
56.             $number = $num;
    
57.         }
    
58.         $counter2 = $counter2 + 1;
    
59.     }
    
60. 
    
61.     say "$K\t$N\t$index\t$number";
    
62. 
    
63. }
    
64. 
    
65. __DATA__
    
66. 24        20000
    
67. 31        100000

复制代码

这行，我很好奇， 我们是否可以更简单写它 ? 让别人可以看懂 ?

1. my @Semi_products =
   
2.       sort { $a->[1] <=> $b->[1] || $a->[0] cmp $b->[0] } @wait_for_sort;

复制代码

可否给点思路 or 代码 呢？谢谢师傅!

回复 4# q1208c


   

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. 24  20000
    
36. 31  100000
    
37. 54  5000000
    
38. 690  400000
    

复制代码

ssfjhh

赞一个

但是每次看到perl的代码真的很崩溃，其它语言写的代码至少我能看出算法是什么，perl写的，算法都看不明白。