可递归次数的计算

bikkuri

大家好！
我有一个问题向大家请教。
假设有一个函数f(abc...n)=a*b*c*...*n，即函数值为变量的各数位数字的乘积，例如：
f(234)=2*3*4=24
继续以函数值为变量代入函数进行递归预算，可以得到f(24)=2*4=8;
而再次递归，可以得到f(8)=8;
当函数值等于变量时停止运算。
这样我们可以得到一条递归路径：
234 - 24 - 8
类似地我们可以计算出任何整数的函数递归路径：
678 - 336 - 54 - 20 - 0
1589 - 360 - 0
27893 - 3024 - 0
6393 - 486 - 192 - 18 - 8
88 - 64 - 24 - 8
78 - 56 - 30 - 0
-----------------------------------------
现在要求的是计算出1-100之内递归路径最长的数，并将其递归路径按以上格式打印出来，如果有并列最长的，则将多个并列最长的递归路径全部打印出来。
谢谢大家！

jason680

$ awk -f get_mul.awk
77 - 49 - 36 - 18 - 8


$ cat get_mul.awk

func get_path(str, path) {
  path = str
  while(length(str)>1) {
    str = get_mul(str);
    path = path " - " str
  }
  return path
}

func get_mul(str,  item, val, cnt, aStr) {
  item = split(str,aStr,"");
  val = 1;
  for (cnt=1; cnt<=item; cnt+=1)
    val *= aStr[cnt];
  return val;
}
BEGIN{
  for (cnt=0; cnt<=99 ;cnt+=1) {
    path = get_path(cnt);
    item = split(path, aPath, "-");
    if (max == item) {
      path_all = path_all "\n" path
    }
    if (max < item) {
      max = item
      path_all = path
    }
  }
  print path_all
}

wh7211

回复 1# bikkuri


<<<awk4.0+

1. seq 100|awk 'function w(x){a="";b++;l=split(x,t,"");if(l>1){for(i=1;i<=l;i++){a=a?a*t[i]:t[i]};c=c?c" - "a:$0" - "a;w(a)}else{d[b]=d[b]?d[b]"\n"c:c}}{b=c="";w($0)}END{PROCINFO["sorted_in"]="@ind_num_desc";for(i in d){print d[i];exit}}'

复制代码

输出：
77 - 49 - 36 - 18 - 8

bikkuri

谢谢大家的帮助！

rubyish

perl abc.pl

1. 77 - 49 - 36 - 18 - 8

复制代码

perl abc.pl 100

1. 77 - 49 - 36 - 18 - 8

复制代码

perl abc.pl 100000

1. 68889 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
2. 68898 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
3. 68988 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
4. 69888 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
5. 86889 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
6. 86898 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
7. 86988 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
8. 88689 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
9. 88698 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
10. 88869 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
11. 88896 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
12. 88968 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
13. 88986 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
14. 89688 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
15. 89868 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
16. 89886 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
17. 96888 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
18. 98688 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
19. 98868 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
    
20. 98886 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0

复制代码

abc.pl

1. #!/usr/bin/perl
   
2. # version 26, subversion 1 (v5.26.1)
   
3. use 5.010;
   
4. 
   
5. my $MAX = shift || 100; # default = 100
   
6. explore($MAX);
   
7. 
   
8. # ____________________SUB____________________
   
9. 
   
10. sub explore {
    
11.     my $end = shift;
    
12.     my ( $long, @the, @solu ) = 0;
    
13. 
    
14.     for my $numba ( 0 .. $end ) {
    
15.         my $next = 1;
    
16.         $next *= $_ for split '', $numba;
    
17.         my $path = $the[$numba] = 1 + ( $the[$next] // 0 );
    
18.         next if $path < $long;
    
19.         ( $long, @solu ) = $path if $path > $long;
    
20.         push @solu, $numba;
    
21.     }
    
22. 
    
23.     say join ' - ', @{ S_( $_, [] ) } for @solu;
    
24. }
    
25. 
    
26. sub S_ {
    
27.     my ( $num, $his ) = @_;
    
28.     return [ @$his, $num ] if $num < 10;
    
29.     my $next = 1;
    
30.     $next *= $_ for split '', $num;
    
31.     S_( $next, [ @$his, $num ] );
    
32. }
    
33. 
    
34. __DATA__
    
35. $_
    

复制代码

bikkuri

花了差不多一天时间算出1千万以内递归路径最长的数。

recursion10000000.txt (301.84 KB, 下载次数: 11)

2018-03-28 19:46 上传

点击文件名下载附件

523066680

回复 7# bikkuri

附件结果中有一行重复

1. 3768876 - 338688 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0
   
2. 3768876 - 338688 - 27648 - 2688 - 768 - 336 - 54 - 20 - 0

复制代码

----------------------------------------------分割线----------------------------------------------

回复 6# rubyish

rubyish 的代码在我的电脑上一千万内只需要19秒 （不含 printf 打印的时间）
代码有一处非常巧妙的地方，

my $path = $the[$numba] = 1 + ( $the[$next] // 0 );

@the 数组积累了从初始数字到当前数字的“可迭代次数”，反复利用，避免了对每个数字执行递归函数" S_() "。

christmas1102

1. seq 100 | awk 'func b(x){split(x,a,"");if(a[2]){x=a[1]*a[2];c=c?c"-"x:$0"-"x;b(x)}}{b($0);d=d?d"\n"c:c;e=length(c);max=max>e?max:e;c=""}END{split(d,f,"\n");for(i in f){if(length(f[i])==max){print f[i]}}}'
   
2. 执行结果：
   
3. 77-49-36-18-8

复制代码

reyleon

gawk 4.0+, 主要用到了 gawk 4.0+ 版本 asorti 函数排序的特性

[root@hk ~]# cat f.awk

function rec(n) {
    v=1;
    t=split(n,a,"");
    for(i=1;i<=t;i++) v*=a;
    if(v==n)return s;
    s=s?s" - "v:v;
    rec(v);
}

{
    for(k=1;k<=$1;k++){ s="";x=sprintf("%s - %s",k,rec(k));L=split(x,b);c[L]=c[L]?c[L]"\n"x:x }
    # 这里排序选最大长度
    asorti(c,d,"@ind_num_desc");
    print c[d[1]];
}


[root@hk ~]# echo 100 | awk -f f.awk
77 - 49 - 36 - 18 - 8
[root@hk ~]#
[root@hk ~]# echo 1000 | awk -f f.awk
679 - 378 - 168 - 48 - 32 - 6
688 - 384 - 96 - 54 - 20 - 0
697 - 378 - 168 - 48 - 32 - 6
769 - 378 - 168 - 48 - 32 - 6
796 - 378 - 168 - 48 - 32 - 6
868 - 384 - 96 - 54 - 20 - 0
886 - 384 - 96 - 54 - 20 - 0
967 - 378 - 168 - 48 - 32 - 6
976 - 378 - 168 - 48 - 32 - 6
[root@hk ~]# echo 10000 | awk -f f.awk
6788 - 2688 - 768 - 336 - 54 - 20 - 0
6878 - 2688 - 768 - 336 - 54 - 20 - 0
6887 - 2688 - 768 - 336 - 54 - 20 - 0
7688 - 2688 - 768 - 336 - 54 - 20 - 0
7868 - 2688 - 768 - 336 - 54 - 20 - 0
7886 - 2688 - 768 - 336 - 54 - 20 - 0
8678 - 2688 - 768 - 336 - 54 - 20 - 0
8687 - 2688 - 768 - 336 - 54 - 20 - 0
8768 - 2688 - 768 - 336 - 54 - 20 - 0
8786 - 2688 - 768 - 336 - 54 - 20 - 0
8867 - 2688 - 768 - 336 - 54 - 20 - 0
8876 - 2688 - 768 - 336 - 54 - 20 - 0
[root@hk ~]#


------------------------

代码重发下, 上面的代码 因为CU会隐藏掉[i ]:

[root@hk ~]# cat f.awk

function rec(n) {
    v=1;
    t=split(n,a,"");
    for(p=1;p<=t;p++) v*=a[p];
    if(v==n)return s;
    s=s?s" - "v:v;
    rec(v);
}

{
    for(k=1;k<=$1;k++){ s="";x=sprintf("%s - %s",k,rec(k));L=split(x,b);c[L]=c[L]?c[L]"\n"x:x }
    asorti(c,d,"@ind_num_desc");
    print c[d[1]];
}
------------------
再次更新, 以下是经过优化的代码, 一千万的计算大概花了 1分多钟, 比上面最原始的快了 NNNNNNN 倍... 基本上与3楼的代码 相当, 稍慢一丢丢

[root@hk ~]# time echo 10000000 | awk -f f.awk  > /tmp/1qw

real    1m35.637s
user    1m35.521s
sys     0m0.082s


[root@hk ~]# cat f.awk

function rec(n) {
    v=1;
    t=split(n,a,"");
    for(p=1;p<=t;p++) v*=a[p];
    if(v==n)return s;
    s=s?s" - "v:v;
    rec(v);
}

{
    for(k=1;k<=$1;k++){
        s="";x=sprintf("%s - %s",k,rec(k));L=split(x,b);c[L]=c[L]?c[L]"\n"x:x;
        asorti(c,d,"@ind_num_desc");
        var=c[d[1]];
        delete c;
        c[d[1]]=var;

    }
    print var;
}

[root@hk ~]# awk --version
GNU Awk 4.2.1, API: 2.0
Copyright (C) 1989, 1991-2018 Free Software Foundation.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
[root@hk ~]#