排它平方数
[i=s] 本帖最后由 ivor 于 2019-3-29 16:47 编辑 [/i]小明正看着 203879 这个数字发呆。
原来,203879 * 203879 = 41566646641
这有什么神奇呢?仔细观察,203879 是个6位数,并且它的每个数位上的数字都是不同的,并且它平方后的所有数位上都不出现组成它自身的数字。
具有这样特点的6位数还有一个,请你找出它!
再归纳一下筛选要求:
1. 6位正整数
2. 每个数位上的数字不同
3. 其平方数的每个数位不含原数字的任何组成数位
答案是一个6位的正整数。[code]$start=[System.DateTime]::Now
for($a=100001;$a -le 999999;$a++){
if ((([char[]]($a).ToString()| group).Length -eq 6) -and (([char[]][math]::Pow($a,2).ToString()).Where({$a.ToString().contains($_)}).Count -eq 0)){
Write-Host $a
}
}
([System.DateTime]::Now - $start).TotalSeconds[/code][code]
203879
639172
"耗时:"100.269806[/code]转载:[url]https://blog.csdn.net/u012027907/article/details/14157077[/url] [code]
from itertools import permutations
for digits in permutations((str(x) for x in range(10)), 6):
if digits[0] == '0':
continue
num = int("".join(digits))
square = num ** 2
if not set(str(square)) & set(digits):
print(num)
[/code]结果[code]
203879
639172
CPU times: user 304 ms, sys: 0 ns, total: 304 ms
Wall time: 304 ms
[/code]选 Python 主要是标准库里有 permutations, 省事儿 ( [i=s] 本帖最后由 523066680 于 2019-3-29 16:12 编辑 [/i]
[code]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\n", $num if $unique;
}
printf "time usage: %.2fs\n", time()-$ta;[/code][code]639172
203879
time usage: 0.40s[/code]强行优化,0 1 5 6 平方后末位与自身相同
my @repeat = map { ($_ * $_) =~ $_ ? 1 : 0 } (0 .. 9); [i=s] 本帖最后由 523066680 于 2019-3-29 17:12 编辑 [/i]
提速,在递归排列的每一层都做重复数的排查。
细节,例如当前累积到3位数,133*133 = 17689,那么只判断 689 是否与 133重合,而不考虑 17,因为 17 可能受到高位数的影响而变化。[code]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);
}
}
[/code]639172 408540845584
203879 41566646641
time usage: 0.05s 剪枝:
1:个位为0,1,5,6可以直接跳过。
2:只要发现某一位重复,跳过
附一下代码:[code]#include<bits/stdc++.h>
using namespace std;
int a[10],flag;
int main()
{
for(long long i=100000;i<=999999;++i)
{
for(int j=0;j<=9;++j)a[j]=0;
flag=0;
if(i%10==0||i%10==1||i%10==5||i%10==6)continue;
long long m=i*i;
a[i%10]=1;
if(a[i/10%10]==1)continue;
a[i/10%10]=1;
if(a[i/100%10]==1)continue;
a[i/100%10]=1;
if(a[i/1000%10]==1)continue;
a[i/1000%10]=1;
if(a[i/10000%10]==1)continue;
a[i/10000%10]=1;
if(a[i/100000%10]==1)continue;
a[i/100000%10]=1;
while(m>0)
{
if(a[m%10]==1)
{
flag=1;
break;
}
m/=10;
}
if(flag)continue;
for(int j=0;j<=9;++j)
{
if(a[j]>1)continue;
}
cout<<i<<"\n";
flag=0;
}
}[/code]耗时:0.1638s
是不是很快?C++就是快。
STL**好,退C转C++保平安。
页:
[1]