[已解决]求从1加到999999999的高效算法

3mile

回复 15# thesnow
哦，的确是这样。怎么忘了还有4开头和7开头的数了呢？

yarsye

牛人 啊 佩服

psp7456

$num在6位数以下还能勉强算出结果，也能保证正确性，但一旦上了7位数，就变成漫长的等待......
不知道换成其他语言比如C语言，运行速度能否更快一些。

local $i,$j
local $num=999999;题目要求的是999999999
for $i=1 to $num
        if stringregexp($i,"4|7") then
                continueloop
        else
                $j=$j+$i
        endif
next
MsgBox(4096, "答案", $j)

thesnow

回复 18# psp7456


    也许会快一点.但是穷举快不到哪里去(因为需要先把数字转换为字符串,然后查找字符串"4"或者"7")
如果快的话,应该不是用的穷举.而且还有精度问题...
想法是:
枚举可能出现的字符串,然后相加.(这样计算量小得多)
比如:
一位
     4
二位
   14
   24
   34
   44
   54
   64
   74
   84
   94
三位
104
114
124
134
等等...
需要一个算法来枚举出来不需要的.

用前面的公式算出总量后减去.

3mile

问题的关键是没有规律可言啊。
如34，41，42.....49,54.....

auto

这个有点难度,数学兼算法

xyold1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
...
999999999

数有9列
共999999999行
我想每一列都有规律吧

ivanpg

如果4和7不参与运算的话，我想应该很难找出规律。。


个人想法。。。。

C.L

很有意思的题目,我也写了一个算法，算1-999999999（除去含4和7的数）相加的耗时为 4MS 左右，Input框只能输入数字为9的数，如：99，9999，99999999,输入其他非9组成的数，不保证结果正确

local $num = InputBox ('叠加1-999*','只能输入数字9','')
Local $result = ""
local $i,$j
Local $timer = TimerInit ()
for $i=1 to 99
        if Not stringregexp($i,"4|7") then
                $j=$j+$i
        endif
        If $i = 9 Then
                $one = $j
        Else
                $two = $j
        EndIf
next

$len = StringLen ($num)
If $len < 2 Then
        $result = $one
Else 
        $result = $two
EndIf

$pe = ""
For $i=1 To $len-2
        For $j=1 To $i-1
                $pe &= "0"
        Next
        $p = '80.'&$pe&'72'&$pe&'72'&$pe&'72'&$pe&'72'
        $result = Round($result * $p)
        $pe = ""
Next
MsgBox (0,"耗时："&TimerDiff ($timer),"1-"&$num &" 相加的数是："&$result)

netegg

大家看这样行不行，把带4和7的算出来，然后减呢，哪个快些？

afan

很有意思的题目,我也写了一个算法，算1-999999999（除去含4和7的数）相加的耗时为 4MS 左右，Input框只能输 ...
C.L 发表于 2010-8-3 22:34

    太NB了… 难以理解你的思路

psp7456

回复 24# C.L

这个太牛了，认真研究一下，附上注释就更好了。

ebhb

回复 24# C.L

这个算法牛。

3mile

很有意思的题目,我也写了一个算法，算1-999999999（除去含4和7的数）相加的耗时为 4MS 左右，Input框只能输 ...
C.L 发表于 2010-8-3 22:34

$p = '80.'&$pe&'72'&$pe&'72'&$pe&'72'&$pe&'72';请教下，这句是什么意思呢？

C.L

回复 29# 3mile

1-999 = (1-99结果)*80.72727272...
1-9999 = (1-999结果)*80.072072072072...
1-99999 =(1-9999结果)*80.0072007200720072...
依次累推