【问题】$K 的 INDEX 是几？

jason680

回复 9# pitonas

[ 问题的限制 ] : 不能使用穷举法 <==不是不能使用，是在数值很大时......太慢了......
（这跟（破）解码一样，不是不能用暴力解，但如果暴力解
要花好几年，几十年，上百年，上千年，上万年....这个解，有解跟没解是一样的....）

所以我们要找出方法，用产生出来的....
例：K =4，N =200  

W=1,有
1,10,100

W=2
101, 11, 110
2, 20, 200

W=3
102, 111, 12, 120
201(X), 21, 210(X)
3, 30, 300(X)

W=4
103, 112, 121, 13, 130
202(X), 211(X), 22, 220(X)
301(X), 31, 310(X)
4, 40, 400(X)

Note: for (X), the length match the N(Number 200) and summary match the W, but value is over than Number(200)
ex: 201(X)
1. the length is 3 and match the length of Number(200)
2. and summary(2+0+1=3) is matched the W=3,
3. but value(201) is over than 200

---------------------------------------------
$ cat nk.pl
#!/usr/bin/perl
use strict;
use warnings;

my $sCnt;
my $X=0;
my $sMatch = 0;
my $sCount_str = "";
my $sLocation  = "";
while (<DATA>) {
  my ( $sK, $sN ) = split;

  $sCnt = 0;
  kn($sK, $sN);  

}

sub kn{
  my($sK, $sN, $sW, $sStr, $sSum) = @_;
  
  my $sDigit = int(log($sN)/log(10)+1);

  if(!defined $sW){
    foreach(1 .. $sK){
      kn($sK, $sN, $_);
    }
    return;
  }
  if(!defined $sStr){
    my $sStart = ($sW>9 ? 9 : $sW);
    foreach(1 .. $sStart){
      kn($sK, $sN, $sW, $_, $_);
    }
    return;
  }
  my $sLen = length($sStr);
  return if($sLen > $sDigit);

  my $sDiff = $sW - $sSum;
  print STDERR "debug K=$sK, N=$sN($sDigit), W=$sW, str=$sStr($sLen), Sum=$sSum,Diff=$sDiff\n";
  return if($sN < $sStr);
  #exit if($X++ > 20000);
  if($sDiff > 0){
    if($sDigit - $sLen > 1){
      foreach(0 .. ($sDiff>9?9:$sDiff)){
        last if($sW < $sSum+$_);
        kn($sK, $sN, $sW, "$sStr$_", $sSum+$_);
      }
    }
    elsif($sDigit - $sLen == 1){
      
      print STDERR "$sK, $sN, $sW, $sStr$sDiff, " . ($sSum+$sDiff) ."\n";
      kn($sK, $sN, $sW, "$sStr$sDiff", $sSum+$sDiff);
    }
    return;
  }
  if($sDiff == 0 ){
    foreach( 0 .. $sDigit - $sLen){
      if($sStr <= $sN){
        ++$sCnt;
        print STDERR "***match $sCnt: $sK, $sN, $sW, $sStr, $sSum\n";
        printf("\nmatch %2d: ",$sCnt) if($sCnt %10 == 1);
        print sprintf( "%5d, ",$sStr);
        if($sCnt == $sK){
           $sCount_str = "\n count $sK is number $sStr\n";
          ++$sMatch;
        }
        if($sStr == $sK){
          $sLocation = "\n the number $sStr is on $sCnt\'th\n";
          ++$sMatch;
        }  
        if($sMatch == 2){
          print "$sCount_str $sLocation";
          exit;
        }
        $sStr .= "0";
      }
    }
      
  }
}

__DATA__
4 200

$ perl nk.pl 2> nk.log

match  1:     1,    10,   100,   101,    11,   110,     2,    20,   200,   102,
match 11:   111,    12,   120,    21,     3,    30,   103,   112,   121,    13,
match 21:   130,    22,    31,     4,
count 4 is number 101

the number 4 is on 24'th

Note: please check the nk.log for detail information...


   

afukada

回复 41# jason680

膜拜@jason680大

學習了

pitonas

我读到，但看起来不是那么容易，
谢谢你, my $师傅，我读它，一次 + 一次

回复 41# jason680