[puzzle]排他平方数

头像
523066680
Administrator
Administrator
帖子: 464
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 51 times
Been thanked: 91 times
联系:

[puzzle]排他平方数

帖子 #1 523066680 » 2019年03月29日 19:44

http://www.bathome.net/thread-52399-1-1.html

小明正看着 203879 这个数字发呆。

原来,203879 * 203879 = 41566646641

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

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

再归纳一下筛选要求:
1. 6位正整数
2. 每个数位上的数字不同
3. 其平方数的每个数位不含原数字的任何组成数位

头像
523066680
Administrator
Administrator
帖子: 464
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 51 times
Been thanked: 91 times
联系:

Re: [puzzle]排他平方数

帖子 #2 523066680 » 2019年03月29日 19:45

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
帖子: 464
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 51 times
Been thanked: 91 times
联系:

Re: [puzzle]排他平方数

帖子 #3 523066680 » 2019年03月29日 21:09

加速版,在递归中逐层排除,减少冗余操作。
考虑低位的情况,比如个位数,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
帖子: 464
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 51 times
Been thanked: 91 times
联系:

Re: [puzzle]排他平方数

帖子 #4 523066680 » 2019年03月29日 21:11

这个问题可以扩充到16进制版,0123456789abcdef,积累的位数往上加。对效率是种考验。

头像
rubyish
崭露头角
崭露头角
帖子: 24
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 16 times
Been thanked: 13 times
联系:

Re: [puzzle]排他平方数

帖子 #5 rubyish » 2019年04月25日 14:43

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
帖子: 464
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 51 times
Been thanked: 91 times
联系:

Re: [puzzle]排他平方数

帖子 #6 523066680 » 2019年04月28日 15:21

rubyish 写了:My test.


Hi Rubyish,为啥注册一个这么明显的马甲 Rubyish2 :speechless3

头像
rubyish
崭露头角
崭露头角
帖子: 24
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 16 times
Been thanked: 13 times
联系:

Re: [puzzle]排他平方数

帖子 #7 rubyish » 2019年04月28日 16:40

:crazylaugh4 login kunnan.
$_

头像
rubyish
崭露头角
崭露头角
帖子: 24
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 16 times
Been thanked: 13 times
联系:

Re: [puzzle]排他平方数

帖子 #8 rubyish » 2019年04月28日 16:53

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
崭露头角
崭露头角
帖子: 24
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 16 times
Been thanked: 13 times
联系:

Re: [puzzle]排他平方数

帖子 #9 rubyish » 2019年04月29日 19:55

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
崭露头角
崭露头角
帖子: 24
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 16 times
Been thanked: 13 times
联系:

Re: [puzzle]排他平方数

帖子 #10 rubyish » 2019年05月02日 11:48

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

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


回到 “算法和编码”

在线用户

用户浏览此论坛: 没有注册用户 和 4 访客