免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12345下一页
最近访问板块 发新帖
查看: 7335 | 回复: 42

【问题】$K 的 INDEX 是几? [复制链接]

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2014-08-19 15:29 |显示全部楼层
本帖最后由 pitonas 于 2014-08-19 09:25 编辑

同样的问题 ~
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 的数是几?

论坛徽章:
33
荣誉会员
日期:2011-11-23 16:44:17天秤座
日期:2014-08-26 16:18:20天秤座
日期:2014-08-29 10:12:18丑牛
日期:2014-08-29 16:06:45丑牛
日期:2014-09-03 10:28:58射手座
日期:2014-09-03 16:01:17寅虎
日期:2014-09-11 14:24:21天蝎座
日期:2014-09-17 08:33:55IT运维版块每日发帖之星
日期:2016-04-17 06:23:27操作系统版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-24 06:20:0015-16赛季CBA联赛之天津
日期:2016-05-06 12:46:59
发表于 2014-08-19 15:42 |显示全部楼层
what are you saying ?

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2014-08-19 15:46 |显示全部楼层
http://bbs.chinaunix.net/thread-4150152-1-1.html
same question ~ {:2_168:}

回复 2# q1208c


   

论坛徽章:
33
荣誉会员
日期:2011-11-23 16:44:17天秤座
日期:2014-08-26 16:18:20天秤座
日期:2014-08-29 10:12:18丑牛
日期:2014-08-29 16:06:45丑牛
日期:2014-09-03 10:28:58射手座
日期:2014-09-03 16:01:17寅虎
日期:2014-09-11 14:24:21天蝎座
日期:2014-09-17 08:33:55IT运维版块每日发帖之星
日期:2016-04-17 06:23:27操作系统版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-24 06:20:0015-16赛季CBA联赛之天津
日期:2016-05-06 12:46:59
发表于 2014-08-19 16:34 |显示全部楼层
回复 3# pitonas

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

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

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



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

论坛徽章:
0
发表于 2014-08-19 17:01 |显示全部楼层
這個題目有意思

應該可以使用divide and conquer來做

不過我最近沒時間

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

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2014-08-19 17:08 |显示全部楼层
支持你 ~ {:2_168:}

回复 5# afukada


   

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2014-08-19 17:16 |显示全部楼层
大神~ 这个只是婴儿等级代码啊。
a sort : Schwartzian transform
a sub: SUM
~~ {:2_170:}

回复 4# q1208c


   

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2014-08-20 17:47 |显示全部楼层
my $师傅, 我有一个问题,
一般我写这个问题代码是这样写的:
( 更少的代码更容易理解, 一点点优化代码在下一楼 )
  1. sub SUM {
  2.     my $sum;
  3.     $sum += $_ for split //, shift;
  4.     $sum;
  5. }

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

  13.     return $sum;
  14. }

  15. while ( my $line = <DATA> ) {
  16.     chomp $line;
  17.     my ( $K, $N ) = split /\t/, $line;
  18.     my @wait_for_sort = ();

  19.     for ( my $n = 1 ; $n <= $N ; $n++ ) {
  20.         my $sum       = SUM($n);
  21.         my @two_elems = ();
  22.         push @two_elems, $n;
  23.         push @two_elems, $sum;
  24.         push @wait_for_sort, [@two_elems];
  25.     }

  26.     my @Semi_products =
  27.       sort { $a->[1] <=> $b->[1] || $a->[0] cmp $b->[0] } @wait_for_sort;
  28.     my @array_in_mind = ();

  29.     for my $semi (@Semi_products) {
  30.         my @two_elems = @{$semi};
  31.         my ( $number, $sum ) = @two_elems;
  32.         push @array_in_mind, $number;
  33.     }

  34.     my $index;
  35.     my $counter1 = 0;

  36.     for my $num (@array_in_mind) {
  37.         if ( $num == $K ) {
  38.             $index = $counter1;
  39.         }
  40.         $counter1 = $counter1 + 1;
  41.     }

  42.     my $number;
  43.     my $counter2 = 0;

  44.     for my $num (@array_in_mind) {
  45.         if ( $counter2 == $K ) {
  46.             $number = $num;
  47.         }
  48.         $counter2 = $counter2 + 1;
  49.     }

  50.     say "$K\t$N\t$index\t$number";

  51. }

  52. __DATA__
  53. 24        20000
  54. 31        100000
复制代码
这行,我很好奇, 我们是否可以更简单写它 ? 让别人可以看懂 ?
  1. my @Semi_products =
  2.       sort { $a->[1] <=> $b->[1] || $a->[0] cmp $b->[0] } @wait_for_sort;
复制代码
可否给点思路 or 代码 呢?谢谢师傅!

回复 4# q1208c


   

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2014-08-20 18:00 |显示全部楼层
本帖最后由 pitonas 于 2014-08-21 12:12 编辑

[ 问题的限制 ] : 不能使用穷举法
这个是穷举法的优化代码:
  1. #!/usr/bin/perl

  2. while (<DATA>) {
  3.     my ( $K, $N ) = split;
  4.     my ( $K_sum, @mind );
  5.     $K_sum += $_ for split //, $K;

  6.     for my $i ( 1 .. $N ) {
  7.         my $sum;
  8.         $sum += $_ for split //, $i;
  9.         push @{ $mind[$sum] }, $i;
  10.     }

  11.     my $index = 0;
  12.     $index += @$_ for @mind[ 1 .. $K_sum - 1 ];

  13.     for my $n ( sort { $a cmp $b } @{ $mind[$K_sum] } ) {
  14.         last if $K == $n;
  15.         $index++;
  16.     }

  17.     my ( $INDEX, $I );

  18.     for my $i ( @mind[ 1 .. $#mind ] ) {
  19.         last if $INDEX > $K;
  20.         $I++;
  21.         $INDEX += @$i;
  22.     }

  23.     $mind[$I] = [ sort { $a cmp $b } @{ $mind[$I] } ];
  24.     my $number = $mind[$I][ $K - $INDEX ];
  25.     print join( "\t", $K, $N, $index, $number ), "\n";
  26. }
  27. __DATA__
  28. 24  20000
  29. 31  100000
  30. 54  5000000
  31. 690  400000
复制代码

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2014-08-20 20:14 |显示全部楼层
赞一个

但是每次看到perl的代码真的很崩溃,其它语言写的代码至少我能看出算法是什么,perl写的,算法都看不明白。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会 限时8.5折

【架构革新 高效可控】2020年8月17日~19日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP