[问题] 计算出1 - N之内递归路径最长的数

头像
rubyish
初来炸道
初来炸道
帖子: 6
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 2 times
Been thanked: 2 times
联系:

[问题] 计算出1 - N之内递归路径最长的数

帖子 #1 rubyish » 2018年07月07日 19:56

假设有一个函数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-N之内递归路径最长的数,并将其递归路径按以上格式打印出来,如果有并列最长的,则将多个并列最长的递归路径全部打印出来。


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

[SOURCE] http://bbs.chinaunix.net/forum.php?mod= ... peid%3D509
$_

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

Re: [问题] 计算出1 - N之内递归路径最长的数

帖子 #2 523066680 » 2018年07月09日 09:00

你现在的环境支持中文打字了吗?之前读拼音好辛苦 :speechless3

这个问题,需要大量同样的计算操作,如果用GPU并行编程,效率极高,就是我也不太会 :shy

最近有点颓废了。

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

Re: [问题] 计算出1 - N之内递归路径最长的数

帖子 #3 523066680 » 2018年07月09日 11:07

我的代码,很普通的思路,一千万30秒
还未做详细优化

num_iter.pl
use List::Util qw/product/;
#use Data::Dump qw/dump/;

our $times = 0;
our @array;
my  $iter = 0;

while ( $iter++ <= 1000000 )
{
    count($iter);
}

#dump @array;
grep {  print join(" - ", @$_ ), "\n"  } @array;
exit;

sub count
{
    our @array;
    my $num = shift;
    my @record;

    while (1)
    {
        my @nums = split("", $num);
        $res = product(@nums);
        push @record, $num;
        last if ( $res == $num );
        if ( $res =~/0/ ) { push @record, ($res, 0); last; }
        $num = $res;
    }

    if ( $#record + 1 > $times ) 
    {
        @array = ( [ @record ] );
        $times= $#record + 1;
    }
    elsif ( $#record + 1 == $times )
    {
        push @array, [ @record ];
    }

头像
rubyish
初来炸道
初来炸道
帖子: 6
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 2 times
Been thanked: 2 times
联系:

Re: [问题] 计算出1 - N之内递归路径最长的数

帖子 #4 rubyish » 2018年07月09日 14:41

v2: :crazylaugh4
split.c:

代码: 全选

# include "util.h"

int main (int numa, char **para){
    my $MAX = 10000000;
    //my $MAX  = atoi (para[1]);
    explore ($MAX);
}

/* _____________________ SUB _____________________ */

void explore (int $n){

    my $path = new (int, $n + 1);

    $path[0] = 1;
    for (my $i = 1; $i < 10; $i++) $path[$i] = 0;

    my $num   = new (int, $n);
    my $indes = 0;
    my $max   = 0;

    for (my $i = 1; $i <= $n; $i++) {
        my $numba = $path[$i] = 1 + $path[split ($i)];
        if ($numba < $max) next;
        if ($numba > $max) $indes = 0, $max = $numba;
        $num[$indes++] = $i;
    }

    for (my $i = 0; $i < $indes; $i++) display ($num[$i]);

}

void display (int $n){
    while ($n > 9) {
        printf ("%d - ", $n);
        $n = split ($n);
    }
    printf ("%d\n", $n);
}

int split (int $n){
    my $nest = 1;

    while ($n && $nest) {
        $nest *= $n % 10;
        $n    /= 10;
    }
    return $nest;
}


util.h:

代码: 全选

# include <stdio.h>
# include <stdlib.h>
# define my   __auto_type
# define new(T, N) (T *)malloc ((N)*sizeof(T))
# define next continue

int split (int);
void display (int);
void explore (int);
上次由 rubyish 在 2018年07月09日 14:58,总共编辑 1 次。
$_

头像
rubyish
初来炸道
初来炸道
帖子: 6
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 2 times
Been thanked: 2 times
联系:

Re: [问题] 计算出1 - N之内递归路径最长的数

帖子 #5 rubyish » 2018年07月09日 14:48

# time ./split > ok

real 0m0.894s

# wc -l ok
5229 ok
$_

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

Re: [问题] 计算出1 - N之内递归路径最长的数

帖子 #6 523066680 » 2018年07月09日 15:24

C语言就是快,你的算法也很高效。


回到 “算法和编码”

在线用户

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