用VBA解欧拉计划题目（315）

grf1973 · 发表于 2017-11-18 12:09

这是一个很有意思的题目，可是我算了半天怎么也算不对。

第315题：数根时钟

（左：萨姆的钟；右：马克斯的钟；下：在本题中钟面上的数字样式）

萨姆和马克斯被要求将两个数字时钟改装成两个“数根”时钟。
所谓数根时钟就是迭代计算数字根的数字时钟。

当时钟接收到一个数时，它会先显示这个数，然后开始计算，期间展示所有的中间值，直到它得到结果。
例如，如果时钟接收到的数是137，它会显示：”137“ → “11“ → “2“，然后它会黑屏，等待接收下一个数。

每个数字在钟面上用七段数码管显示：三根水平数码管（上、中、下）和四根竖直数码管（左上、右上、左下、右下）。
显示数字”1“需要点亮右上和右下的竖直数码管，显示数字”4“需要点亮中间的水平数码管和左上、右上、右下的竖直数码管，显示数字”8“则需要点亮所有的数码管。

只有在数码管打开或关闭时时钟才消耗能量。
因此，显示”2“需要5次转换，而”7“则只需要4次转换。

萨姆和马克斯制作了两个不同的时钟。

如果萨姆的时钟接收到一个数，比如说137：时钟先显示”137“，然后全部关掉，然后显示下一个数(“11“)，再全部关掉，然后显示最后一个数(“2“)，过一段时间后再全部关掉。
在这个例子中，接收到137后，萨姆的时钟需要消耗：

“137“

:(2 + 5 + 4) × 2 = 22次转换（显示和关闭”137“）。
“11“:(2 + 2) × 2 = 8次转换（显示和关闭”11“）。
“2“:(5) × 2 = 10次转换（显示和关闭”2“）。

总计需要40次转换。

马克斯的时钟运作的方式略有不同。它会很聪明地只关掉那些显示下一个数时不再用到的数码管，而不是全部关掉。
接收到137后，马克斯的时钟需要消耗：

“137“

:2 + 5 + 4 = 11次转换（显示”137“ on）
7次转换（关闭显示”11“不需要的数码管）。
“11“:0次转换（”11“已经正确显示）
3次转换（关闭第一个”1“和第二个”1“的下半部分；
上半部分保留用于显示”2“)。
“2“:4次转换（显示”2“的剩余部分）
5次转换（关闭”2“）。

总计需要30次转换。

显然，马克斯的时钟比萨姆的时钟更节能。
这两个时钟随后依次接收到在A = 10^7和B = 2×10^7之间的所有质数。
求萨姆的时钟和马克斯的时钟所需要的转换次数的差。

grf1973 · 发表于 2017-11-18 12:19

我的思路是给每个数字一个编码，按相同次序对应7根管子。
比如：
'以左竖为起点，上半圈顺时针，下半圈逆时针给7个管子做标记，每个数一个特殊的排列
arr(0) = "1110111"
arr(1) = "0010001"
arr(2) = "0111110"
arr(3) = "0111011"
arr(4) = "1011001"
arr(5) = "1101011"
arr(6) = "1101111"
arr(7) = "1110001"
arr(8) = "1111111"
arr(9) = "1111011"
然后两个数字之间的转换就可以看成编码之间的转换，只要对应位置不相同，那么转换次数+1
比如：0-->1，等同于 "1110111"--> "0010001"，有4个位置不同，所以[01]=4。同理[10]=4。
有了这个模型之后就很好计算了。

grf1973 · 发表于 2017-11-20 09:01

思路没错，结果终于算出来了。
最多开关次数： 63424722 ，聪明做法开关次数： 49799480，两者差值： 13625242 ，运行时间3.671875s

大灰狼1976 · 发表于 2017-11-20 16:13

不好意思，想问两个问题：
1、运行时间内有无包含生成素数的时间；
2、两次素数计算之间，是否会全灭，还是保留无变化的管子。

grf1973 · 发表于 2017-11-27 19:20

大灰狼1976 发表于 2017-11-20 16:13
不好意思，想问两个问题：
1、运行时间内有无包含生成素数的时间；
2、两次素数计算之间，是否会全灭，还 ...

1、素数生成是用筛选法。香川提供了一种最快捷的筛法。
2、两次素数之间，浪费的做法素数1全明--素数1全暗--素数2全明--素数1全暗，
精明的做法是素数1全明（从素数0部分暗过来）--素数1部分暗--素数2全明--素数2部分暗（以待素数3全明）

grf1973 · 发表于 2017-11-27 19:23

贴上我的代码。家里的破电脑运行了16秒。

Dim Light '公共数组，Light(0-9)分别记录0-9点亮的管数
'P315：萨姆和马克斯被要求将两个数字时钟改装成两个“数根”时钟。
'所谓数根时钟就是迭代计算数字根的数字时钟。'
'当时钟接收到一个数时，它会先显示这个数，然后开始计算，期间展示所有的中间值，直到它得到结果。
'例如，如果时钟接收到的数是137，它会显示：”137“ → “11“ → “2“，然后它会黑屏，等待接收下一个数。
'
'每个数字在钟面上用七段数码管显示：三根水平数码管（上、中、下）和四根竖直数码管（左上、右上、左下、右下）。
'显示数字”1“需要点亮右上和右下的竖直数码管，显示数字”4“需要点亮中间的水平数码管和左上、右上、右下的竖直数码管，显示数字”8“则需要点亮所有的数码管。
'
'萨姆和马克斯制作了两个不同的时钟。
'如果萨姆的时钟接收到一个数，比如说137：时钟先显示”137“，然后全部关掉，然后显示下一个数(“11“)，再全部关掉，然后显示最后一个数(“2“)，过一段时间后再全部关掉。
'马克斯的时钟运作的方式略有不同。它会很聪明地只关掉那些显示下一个数时不再用到的数码管，而不是全部关掉。'
'显然，马克斯的时钟比萨姆的时钟更节能。
'这两个时钟随后依次接收到在A = 10^7和B = 2×10^7之间的所有质数。
'求萨姆的时钟和马克斯的时钟所需要的转换次数的差。
Sub problem315() '最多开关： 63424722 节省做法： 49799480 结果是： 13625242 运行：3.609375s
tm = Timer
Light = Array(6, 2, 5, 5, 4, 5, 6, 4, 7, 6) '0-9点亮的管数
Dim arr$(9), brr%(99)
Dim p&, p1&, i&, m&, s1#, s2#
Dim cp$, cpp$, phead$, ptail$, Lp%, Lpp%
'以左竖为起点，上半圈顺时针，下半圈逆时针给7个管子做标记，每个数一个特殊的排列
arr(0) = "1110111"
arr(1) = "0010001"
arr(2) = "0111110"
arr(3) = "0111011"
arr(4) = "1011001"
arr(5) = "1101011"
arr(6) = "1101111"
arr(7) = "1110001"
arr(8) = "1111111"
arr(9) = "1111011"
For k = 0 To 9 '数字k-->kk需开关的次数
For kk = 0 To 9
x = 10 * k + kk
If k = kk Then
brr(x) = 0
Else
For i = 1 To 7
If Mid(arr(k), i, 1) <> Mid(arr(kk), i, 1) Then brr(x) = brr(x) + 1
Next
End If
Next
Next
Dim crr(10 To 64) '预处理：从2位数亮的状态-->1位数灭的状态节省做法开关数
Dim drr(10 To 64) '同上，浪费做法开关数
For pa = 10 To 64 '2*10^7内各位数之和最大为19999999=1+7*9
p = pa
While p >= 10
p1 = p \ 10: p2 = p Mod 10
drr(pa) = drr(pa) + Light(p1) + Light(p2) '前数关
pp = p1 + p2 '下一个数字(当前数字各位之和）
If pp < 10 Then
x = p2 * 10 + pp '前一数字的个位与下一个数字转换
crr(pa) = crr(pa) + Light(p1) + brr(x)
drr(pa) = drr(pa) + Light(pp) '后数开（1位）
Else
pp1 = pp \ 10: pp2 = pp Mod 10
x1 = p1 * 10 + pp1: x2 = p2 * 10 + pp2
crr(pa) = crr(pa) + brr(x1) + brr(x2)
drr(pa) = drr(pa) + Light(pp1) + Light(pp2) '后数开（2位）
End If
p = pp
Wend
crr(pa) = crr(pa) + Light(p) '最后单数关掉
drr(pa) = drr(pa) + Light(p) '后数关
Next
PrimeArr = GetPrimeArray(2 * 10 ^ 7)
For i = 1 To UBound(PrimeArr)
If PrimeArr(i) > 10 ^ 7 Then Exit For
Next
For m = i To UBound(PrimeArr)
p = PrimeArr(m)
s1 = s1 + 2 * TurnOn(p) ''浪费做法：第一个P开关一次
s2 = s2 + TurnOn(p) ''节省做法：开第一个P
pp = SumDgts(p) '各位数之和
If pp < 10 Then '如果是个位数，直接结束
s1 = s1 + 2 * Light(pp) '浪费做法：最后一个数开关一次
p1 = p \ 10: p2 = p Mod 10
x = p2 * 10 + pp '转换：从质数的最后一位到个位数
s2 = s2 + TurnOn(p1) + brr(x) + Light(pp)
Else '否则计算到2位数亮起的步数，之后已预处理
pp1 = pp \ 10: pp2 = pp Mod 10
s1 = s1 + Light(pp1) + Light(pp2) '浪费做法：2位数直接亮起
p1 = p \ 100: p2 = p Mod 100 '节省做法：把质数分成前后两段，前段关闭，后段转换
p21 = p2 \ 10: p22 = p2 Mod 10
x1 = p21 * 10 + pp1: x2 = p22 * 10 + pp2 'p21-->pp1,p22-->pp2
s2 = s2 + TurnOn(p1) + brr(x1) + brr(x2)
s1 = s1 + drr(pp) '浪费做法：加上预处理的结果
s2 = s2 + crr(pp) '节省做法：加上预处理的结果
End If
Next
Debug.Print "最多开关："; s1, "节省做法："; s2, "结果是："; s1 - s2, "运行：" & Timer - tm & "s"
End Sub
Function SumDgts%(p&) '求各位之和
x = p
While x > 0
SumDgts = SumDgts + x Mod 10
x = x \ 10
Wend
End Function
Function TurnOn(p&) '求p开(关)一次点亮的管数
x = p
While x > 0
TurnOn = TurnOn + Light(x Mod 10)
x = x \ 10
Wend
End Function
Function GetPrimeArray(n&) 'by kagawa
Dim i&, j&, k&, m&
m = Int((n - 1) / 2): ReDim a(1 To m) As Byte
For i = 1 To Sqr(n) \ 2
If a(i) = 0 Then
For j = i * 3 + 1 To m Step i * 2 + 1
a(j) = 1
Next
End If
Next
ReDim b&(1 To m): b(1) = 2: k = 1 '当a(i)=0时，2i+1是质数
For i = 1 To m
If a(i) = 0 Then k = k + 1: b(k) = i * 2 + 1
Next
ReDim Preserve b&(1 To k)
GetPrimeArray = b
End Function

复制代码

02761752696 · 发表于 2017-11-27 20:12

grf1973 发表于 2017-11-27 19:23
贴上我的代码。家里的破电脑运行了16秒。

最多开关： 63424722 节省做法： 49799480 结果是： 13625242 运行：7.664063s

老师有示例文件吗？
怎么用的啊

grf1973 · 发表于 2017-11-28 10:19

直接贴到模块里运行就行了。要什么示例文件？

大灰狼1976 · 发表于 2017-12-5 12:50

其实我的方法还要简单一点，不必算出每一步的点灭次数再计算差，而是直接计算两者不同的地方，比如8位数的数字根肯定不会大于2位数，那么就不需要计算8位数了，直接计算最后2位数之间的差就行了，但是我的代码效率也并没有高多少，所以就不贴出来了。

		自动登录	找回密码
密码			注册

[VBA] 用VBA解欧拉计划题目（315）

本帖子中包含更多资源

浏览过的版块