一个小学数学题的代码实现

综合讨论区 性能优化
1

今天一个朋友要去一个机构面试小学老师，发来的资料中的一道题，题目是：

有一些自然数，从它的第三个数字开始，每一个数字都是前两个数字之和，如101, 235, 2022,...
，求该类数字的最大值。

分析之后结果是 10112358。
我想的两种基本思路都是通过遍历求解：

  1. 使用digits()函数得到数字的每一位，然后进行计算。
  2. 使用string()函数得到数字字符串，利用parse()函数从Char恢复到整型计算后进行判断。
    主要代码：
julia> function test_use_digits()
	max_num = 0
	for num in 100:99_999_999
		digit = digits(num)
		len = length(digit)
	    for i in len:-1:3
			if digit[i-2] != digit[i-1] + digit[i]
				break
			else
				i==3 && num > max_num ? max_num = num : nothing
			end
		end
	end
	println(max_num)
end
test_use_digits (generic function with 1 method)

julia> function test_use_string()
	max_num = 0
	for num in 100:99_999_999
		str = string(num)
		len = length(str)
	    for i in 3:len
			if parse(Int,str[i]) != parse(Int,str[i-1]) + parse(Int,str[i-2])
				break
			else
				i == len && num > max_num ? max_num = num : nothing
			end
	    end
	end
	println(max_num)
end
test_use_string (generic function with 1 method)

用BenchMarkTools进行分析后结果如下:

julia> using BenchmarkTools

julia> @btime test_use_digits()
10112358
10112358
10112358
10112358
  16.322 s (100002154 allocations: 13.40 GiB)

julia> @btime test_use_string()
10112358
10112358
10112358
10112358
  7.503 s (199999809 allocations: 8.94 GiB)

两者时间和内存上都相差将近一倍，以前都是闷头写，没怎么做过测试，有没有老铁们给分析下原因，或者有什么更高效的实现思路也可以讲讲

2

穷举+生成

只枚举前两位，然后生成所需的数字，排序，取最大。

function f(num::Int)
    @assert num∈10:99 "num=$num ∉[10, 99]"
    i = num ÷ 10
    j = num % 10
    _num = string(num)
    while j <10
        num = _num
        i, j, _num = num3(i, j, num)
    end
    num
end

function num3(i::Int, j::Int, num::String)
    @assert i∈0:9 "i=$i ∉[1, 9]"
    @assert j∈0:9 "j=$j ∉[0, 9]"
    j, i+j, "$num$(i+j)"
end

function main()
    arr = [f(i) for i in 10:99]
    sort(arr)[1]
    # arr == sort(arr)
    # f(10)
end

main()
# "10112358"
# 44.000 μs (1229 allocations: 59.45 KiB)

test_use_digits 占用内存多估计是因为分配了 digit = digits(num) 这个数组。
纯粹是 digits 占用内存多而且慢

julia> @btime string(999_999_999)
  47.523 ns (2 allocations: 96 bytes)
"999999999"

julia> @btime digits(999_999_999)
  116.630 ns (1 allocation: 160 bytes)
9-element Array{Int64,1}:
 9
 9
 9
 9
 9
 9
 9
 9
 9
3 个赞
3

哇，我只会喊666了。
学会了好多，像写成几个函数，每个函数都有各自的功能，然后再进行函数嵌套这样看上去真的清晰。

4

因为要最大，所以自然数中从左到右每个数字的增长要尽量小，那么前两位和最小的开头是10，以此类推得到10 1 1 2 3 5 8