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

回复
头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

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

帖子 rubyish »

假设有一个函数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
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

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

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

最近有点颓废了。
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

我的代码,很普通的思路,一千万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
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

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

帖子 rubyish »

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
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

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

帖子 rubyish »

# time ./split > ok

real 0m0.894s

# wc -l ok
5229 ok
$_
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

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

在线用户

正浏览此版面之用户: 没有注册用户 和 0 访客