分页: 1 / 1
[问题] 计算出1 - N之内递归路径最长的数
发表于 : 2018年07月07日 19:56
由 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之内递归路径最长的数,并将其递归路径按以上格式打印出来,如果有并列最长的,则将多个并列最长的递归路径全部打印出来。
: 花了差不多
一天时间 算出
1千万 以内递归路径最长的数
[SOURCE]
http://bbs.chinaunix.net/forum.php?mod= ... peid%3D509
Re: [问题] 计算出1 - N之内递归路径最长的数
发表于 : 2018年07月09日 09:00
由 523066680
你现在的环境支持中文打字了吗?之前读拼音好辛苦
这个问题,需要大量同样的计算操作,如果用GPU并行编程,效率极高,就是我也不太会
最近有点颓废了。
Re: [问题] 计算出1 - N之内递归路径最长的数
发表于 : 2018年07月09日 11:07
由 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 ];
}
}
Re: [问题] 计算出1 - N之内递归路径最长的数
发表于 : 2018年07月09日 14:41
由 rubyish
v2:
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);
Re: [问题] 计算出1 - N之内递归路径最长的数
发表于 : 2018年07月09日 14:48
由 rubyish
# time ./split > ok
real 0m0.894s
# wc -l ok
5229 ok
Re: [问题] 计算出1 - N之内递归路径最长的数
发表于 : 2018年07月09日 15:24
由 523066680
C语言就是快,你的算法也很高效。