[puzzle]排他平方数

回复
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

[puzzle]排他平方数

帖子 523066680 »

http://www.bathome.net/thread-52399-1-1.html
小明正看着 203879 这个数字发呆。

原来,203879 * 203879 = 41566646641

这有什么神奇呢?仔细观察,203879 是个6位数,并且它的每个数位上的数字都是不同的,并且它平方后的所有数位上都不出现组成它自身的数字。

具有这样特点的6位数还有一个,请你找出它!

再归纳一下筛选要求:
1. 6位正整数
2. 每个数位上的数字不同
3. 其平方数的每个数位不含原数字的任何组成数位
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

Re: [puzzle]排他平方数

帖子 523066680 »

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
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

Re: [puzzle]排他平方数

帖子 523066680 »

加速版,在递归中逐层排除,减少冗余操作。
考虑低位的情况,比如个位数,0 1 5 6 ,它们的平方的末位数,和自身相同。所以个位可以排除这几个数字
然后是两位数的情况,13*13=169,只判断 69 和 13 是否有重合,因为只有69在下一层是肯定不变的。
以此类推,直到6位数时,判断所有位是否与因数重合。
use 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); } }
639172 408540845584
203879 41566646641
time usage: 0.05s
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

Re: [puzzle]排他平方数

帖子 523066680 »

这个问题可以扩充到16进制版,0123456789abcdef,积累的位数往上加。对效率是种考验。
头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

Re: [puzzle]排他平方数

帖子 rubyish »

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
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

Re: [puzzle]排他平方数

帖子 523066680 »

rubyish 写了:My test.
Hi Rubyish,为啥注册一个这么明显的马甲 Rubyish2 :speechless3
头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

Re: [puzzle]排他平方数

帖子 rubyish »

:crazylaugh4 login kunnan.
$_
头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

Re: [puzzle]排他平方数

帖子 rubyish »

v1: 6.325s
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]排他平方数

帖子 rubyish »

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]排他平方数

帖子 rubyish »

這個寫法我想可能有問題。
答案正確也許只是巧合。
在Perlmonk 看過。
64位元的 perl int 是 int64。

在試圖解答 Puzzle15 的過程中,一個int64恰好可以儲存map.
4個bit. 0 - 15 ok
8/0.5 = 16 = 4 x 4
但是發現確實有些問題一時之間無法解決。
Maybe
答案正確也許只是巧合。 :exciting4 :exciting4
$_
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 1 访客