小明正看着 203879 这个数字发呆。
原来,203879 * 203879 = 41566646641
这有什么神奇呢?仔细观察,203879 是个6位数,并且它的每个数位上的数字都是不同的,并且它平方后的所有数位上都不出现组成它自身的数字。
具有这样特点的6位数还有一个,请你找出它!
再归纳一下筛选要求:
1. 6位正整数
2. 每个数位上的数字不同
3. 其平方数的每个数位不含原数字的任何组成数位
[puzzle]排他平方数
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
[puzzle]排他平方数
http://www.bathome.net/thread-52399-1-1.html
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
Re: [puzzle]排他平方数
Perl, 方案一
use Time::HiRes qw/time/; use Algorithm::Permute; my $ta = time(); my $iter = Algorithm::Permute->new ( [0..9], 6 ); my (@digits, @res); my ($num, $unique); # 尾数 0 1 5 6 相乘都产生与本身相同尾数的值 my @repeat = map { ($_ * $_) =~ $_ ? 1 : 0 } (0 .. 9); while ( @res = $iter->next ) { next if $res[0] == 0; next if $repeat[ $res[-1] ]; $num = join("", @res); @digits = (0)x10; $unique = 1; grep { $digits[$_] = 1 } @res; for ( split("", $num * $num )) { $unique = 0, last if $digits[$_] } printf "%d %d\n", $num, $num*$num if $unique; } printf "time usage: %.2fs\n", time()-$ta;
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
Re: [puzzle]排他平方数
加速版,在递归中逐层排除,减少冗余操作。
考虑低位的情况,比如个位数,0 1 5 6 ,它们的平方的末位数,和自身相同。所以个位可以排除这几个数字
然后是两位数的情况,13*13=169,只判断 69 和 13 是否有重合,因为只有69在下一层是肯定不变的。
以此类推,直到6位数时,判断所有位是否与因数重合。
203879 41566646641
time usage: 0.05s
考虑低位的情况,比如个位数,0 1 5 6 ,它们的平方的末位数,和自身相同。所以个位可以排除这几个数字
然后是两位数的情况,13*13=169,只判断 69 和 13 是否有重合,因为只有69在下一层是肯定不变的。
以此类推,直到6位数时,判断所有位是否与因数重合。
639172 408540845584use Time::HiRes qw/time/; my $ta = time(); our $maxlen = 6; permute([], [0..9], 0); printf "time usage: %.2fs\n", time() - $ta; sub permute { my ($a, $b, $lv) = @_; return if $lv > $maxlen; if ( $lv > 0 and $a->[0] != 0 ) { my $n = join("", @$a); my $mp = $n*$n; $mp = substr($mp, -$lv) if ($lv < $maxlen); for ( 0 .. $#$a ) { return if $mp =~ $a->[$_] } if ($lv == $maxlen) { printf "%d %d\n", $n, $mp; return; } } for ( 0 .. $#{$b} ) { permute( [ $b->[$_], @$a ] , [@{$b}[0..$_-1, $_+1..$#$b]], $lv+1); } }
203879 41566646641
time usage: 0.05s
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
Re: [puzzle]排他平方数
这个问题可以扩充到16进制版,0123456789abcdef,积累的位数往上加。对效率是种考验。
- rubyish
- 渐入佳境
- 帖子: 52
- 注册时间: 2018年04月23日 09:58
- 联系:
Re: [puzzle]排他平方数
My test.
代码: 全选
use 5.010;
perm ( 9876543210, 6, 0, 0 );
# ________________ SUB _______________
sub perm{
my ( $chars, $lev, $maybe, $exist ) = @_;
if (!$lev){
my $num = $maybe * $maybe;
my @num = split //, $num;
for (@num){
return if $exist & ( 1 << $_ );
}
say $maybe;
return;
}
my ( $head, $pick, $tail ) = ( $chars, 0, 0 );
my $i = 0;
while ($head){
$pick = $head % 10;
$head = int ( $head / 10 );
$tail = $chars % ( 10 ** $i );
my $may = $maybe * 10 + $pick;
perm (
$head * ( 10 ** $i ) + $tail,
$lev - 1,
$may,
$exist | ( 1 << $pick )
) if $may;
$i++;
}
}
__DATA__
203879 639172
$_
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
Re: [puzzle]排他平方数
Hi Rubyish,为啥注册一个这么明显的马甲 Rubyish2rubyish 写了:My test.
- rubyish
- 渐入佳境
- 帖子: 52
- 注册时间: 2018年04月23日 09:58
- 联系:
Re: [puzzle]排他平方数
v1: 6.325s
v2: 0.201s
3樓的加速方式果然 very fast~~
3Q~
v2: 0.201s
3樓的加速方式果然 very fast~~
3Q~
代码: 全选
use 5.010;
sub N() { 6 }
perm( 9876543210, N, 0, 0 );
# ________________ SUB _______________
sub perm {
my ( $chars, $lev, $maybe, $exist ) = @_;
if ( !$lev ) {
return if $maybe < 10**( N - 1 );
my $num = $maybe * $maybe;
$num = int( $num / ( 10**( N - 1 ) ) );
while ($num) {
my $c = $num % 10;
return if $exist & ( 1 << $c );
$num = int( $num / 10 );
}
say $maybe;
return;
}
my ( $head, $pick, $tail ) = ( $chars, 0, 0 );
my $i = 0;
my $more = 10**( N - $lev );
my $more10 = $more * 10;
while ($head) {
$pick = $head % 10;
$head = int( $head / 10 );
$tail = $chars % ( 10**$i );
my $may = $pick * $more + $maybe;
my $e = $exist | ( 1 << $pick );
my $num = ( $may * $may ) % $more10;
my $next = 1;
while ($num) {
my $n = $num % 10;
$next--, last if $e & ( 1 << $n );
$num = int( $num / 10 );
}
perm( $head * ( 10**$i ) + $tail, $lev - 1, $may, $e ) if $next;
$i++;
}
}
__DATA__
203879 639172
$_
- rubyish
- 渐入佳境
- 帖子: 52
- 注册时间: 2018年04月23日 09:58
- 联系:
Re: [puzzle]排他平方数
v3: 0.182s
代码: 全选
use 5.010;
sub N() { 6 }
perm( 9876543210, N, 0, 0, 0 );
# ________________ SUB _______________
sub perm {
my ( $chars, $lev, $maybe, $exist, $exist2 ) = @_;
if ( !$lev ) {
return if $maybe < 10**( N - 1 );
my $num = $maybe * $maybe;
$num = int( $num / ( 10**( N - 1 ) ) );
while ($num) {
my $c = $num % 10;
return if $exist & ( 1 << $c );
$num = int( $num / 10 );
}
say $maybe;
return;
}
my ( $head, $pick, $tail ) = ( $chars, 0, 0 );
my $i = 0;
my $more = 10**( N - $lev );
my $more10 = $more * 10;
while ($head) {
$pick = $head % 10;
$head = int( $head / 10 );
$tail = $chars % ( 10**$i );
goto NEXT if ( 1 << $pick ) & $exist2;
my $may = $pick * $more + $maybe;
my $num = ( $may * $may ) % $more10;
my $e = $exist | ( 1 << $pick );
my $e2 = $exist2 | ( 1 << int( $num / $more ) );
while ($num) {
my $n = $num % 10;
goto NEXT if $e & ( 1 << $n );
$num = int( $num / 10 );
}
perm( $head * ( 10**$i ) + $tail, $lev - 1, $may, $e, $e2 );
NEXT:
$i++;
}
}
__DATA__
203879 639172
$_
- rubyish
- 渐入佳境
- 帖子: 52
- 注册时间: 2018年04月23日 09:58
- 联系:
Re: [puzzle]排他平方数
這個寫法我想可能有問題。
答案正確也許只是巧合。
在Perlmonk 看過。
64位元的 perl int 是 int64。
在試圖解答 Puzzle15 的過程中,一個int64恰好可以儲存map.
4個bit. 0 - 15 ok
8/0.5 = 16 = 4 x 4
但是發現確實有些問題一時之間無法解決。
Maybe
答案正確也許只是巧合。
答案正確也許只是巧合。
在Perlmonk 看過。
64位元的 perl int 是 int64。
在試圖解答 Puzzle15 的過程中,一個int64恰好可以儲存map.
4個bit. 0 - 15 ok
8/0.5 = 16 = 4 x 4
但是發現確實有些問題一時之間無法解決。
Maybe
答案正確也許只是巧合。
$_
在线用户
正浏览此版面之用户: 没有注册用户 和 1 访客