Board logo

标题: 排它平方数 [打印本页]

作者: ivor    时间: 2019-3-29 11:25     标题: 排它平方数

本帖最后由 ivor 于 2019-3-29 16:47 编辑

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

    原来,203879 * 203879 = 41566646641

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

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

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

答案是一个6位的正整数。
  1. $start=[System.DateTime]::Now
  2. for($a=100001;$a -le 999999;$a++){
  3. if ((([char[]]($a).ToString()| group).Length -eq 6) -and (([char[]][math]::Pow($a,2).ToString()).Where({$a.ToString().contains($_)}).Count -eq 0)){
  4.     Write-Host $a
  5. }
  6. }
  7. ([System.DateTime]::Now - $start).TotalSeconds
复制代码
  1. 203879
  2. 639172
  3. "耗时:"100.269806
复制代码
转载:https://blog.csdn.net/u012027907/article/details/14157077
作者: bailong360    时间: 2019-3-29 12:17

  1. from itertools import permutations
  2. for digits in permutations((str(x) for x in range(10)), 6):
  3.     if digits[0] == '0':
  4.         continue
  5.     num = int("".join(digits))
  6.     square = num ** 2
  7.     if not set(str(square)) & set(digits):
  8.         print(num)
复制代码
结果
  1. 203879
  2. 639172
  3. CPU times: user 304 ms, sys: 0 ns, total: 304 ms
  4. Wall time: 304 ms
复制代码
选 Python 主要是标准库里有 permutations, 省事儿 (
作者: 523066680    时间: 2019-3-29 13:04

本帖最后由 523066680 于 2019-3-29 16:12 编辑
  1. use Time::HiRes qw/time/;
  2. use Algorithm::Permute;
  3. my $ta = time();
  4. my $iter = Algorithm::Permute->new ( [0..9], 6 );
  5. my (@digits, @res);
  6. my ($num, $unique);
  7. # 尾数 0 1 5 6 相乘都产生与本身相同尾数的值
  8. my @repeat = map { ($_ * $_) =~ $_ ? 1 : 0  } (0 .. 9);
  9. while ( @res = $iter->next )
  10. {
  11.     next if $res[0] == 0;
  12.     next if $repeat[ $res[-1] ];
  13.     $num = join("", @res);
  14.     @digits = (0)x10;
  15.     $unique = 1;
  16.     grep { $digits[$_] = 1 } @res;
  17.     for (split("", $num * $num )) {
  18.         $unique = 0, last if $digits[$_]
  19.     }
  20.     printf "%d\n", $num if $unique;
  21. }
  22. printf "time usage: %.2fs\n", time()-$ta;
复制代码
  1. 639172
  2. 203879
  3. time usage: 0.40s
复制代码
强行优化,0 1 5 6 平方后末位与自身相同
my @repeat = map { ($_ * $_) =~ $_ ? 1 : 0  } (0 .. 9);
作者: 523066680    时间: 2019-3-29 16:01

本帖最后由 523066680 于 2019-3-29 17:12 编辑

提速,在递归排列的每一层都做重复数的排查。
细节,例如当前累积到3位数,133*133 = 17689,那么只判断 689 是否与 133重合,而不考虑 17,因为 17 可能受到高位数的影响而变化。
  1. use Time::HiRes qw/time/;
  2. my $ta = time();
  3. our $maxlen = 6;
  4. permute([], [0..9], 0);
  5. printf "time usage: %.2fs\n", time() - $ta;
  6. sub permute
  7. {
  8.     my ($a, $b, $lv) = @_;
  9.     return if $lv > $maxlen;
  10.     if ( $lv > 0 and $a->[0] != 0 )
  11.     {
  12.         my $n = join("", @$a);
  13.         my $mp = $n*$n;
  14.         $mp = substr($mp, -$lv) if ($lv < $maxlen);
  15.         for ( 0 .. $#$a ) { return if $mp =~ $a->[$_] }
  16.         if ($lv == $maxlen)
  17.         {
  18.             printf "%d %d\n",  $n, $mp;
  19.             return;
  20.         }
  21.     }
  22.     for ( 0 .. $#{$b} ) {
  23.         permute( [ $b->[$_], @$a ] , [@{$b}[0..$_-1, $_+1..$#$b]], $lv+1);
  24.     }
  25. }
复制代码
639172 408540845584
203879 41566646641
time usage: 0.05s
作者: liujingcheng    时间: 2020-4-19 16:54

剪枝:
1:个位为0,1,5,6可以直接跳过。
2:只要发现某一位重复,跳过
附一下代码:
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[10],flag;
  4. int main()
  5. {
  6. for(long long i=100000;i<=999999;++i)
  7. {
  8. for(int j=0;j<=9;++j)a[j]=0;
  9. flag=0;
  10. if(i%10==0||i%10==1||i%10==5||i%10==6)continue;
  11. long long m=i*i;
  12. a[i%10]=1;
  13. if(a[i/10%10]==1)continue;
  14. a[i/10%10]=1;
  15. if(a[i/100%10]==1)continue;
  16. a[i/100%10]=1;
  17. if(a[i/1000%10]==1)continue;
  18. a[i/1000%10]=1;
  19. if(a[i/10000%10]==1)continue;
  20. a[i/10000%10]=1;
  21. if(a[i/100000%10]==1)continue;
  22. a[i/100000%10]=1;
  23. while(m>0)
  24. {
  25. if(a[m%10]==1)
  26. {
  27. flag=1;
  28. break;
  29. }
  30. m/=10;
  31. }
  32. if(flag)continue;
  33. for(int j=0;j<=9;++j)
  34. {
  35. if(a[j]>1)continue;
  36. }
  37. cout<<i<<"\n";
  38. flag=0;
  39. }
  40. }
复制代码
耗时:0.1638s
是不是很快?C++就是快。
STL**好,退C转C++保平安。




欢迎光临 批处理之家 (http://bbs.bathome.net/) Powered by Discuz! 7.2