[puzzle]排他平方数

头像
523066680
Administrator
Administrator
帖子: 453
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 46 times
Been thanked: 77 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
帖子: 453
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 46 times
Been thanked: 77 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
帖子: 453
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 46 times
Been thanked: 77 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
帖子: 453
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 46 times
Been thanked: 77 times
联系:

Re: [puzzle]排他平方数

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

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


回到 “算法和编码”

在线用户

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