7,763
社区成员
发帖
与我相关
我的任务
分享算法，又见算法，10个自然数，选中任意一个，列出和它最接近的5个数字， 高分求最快速的算法！！！！！！
如题： 10 个大于0的整数。 从中间任意取出一个来，用对快的速度得到和此数字最接近的5个数字。
大家动脑劲吧，偶老了，只想出排序等的方法，可是光排序就要用到2次循环，不是很满意。
喜欢研究算法的朋友们帮忙啦，偶老蔡开贴从来不会不结的。
大家动脑劲吧，偶老了，只想出排序等的方法，可是光排序就要用到2次循环，不是很满意。
喜欢研究算法的朋友们帮忙啦，偶老蔡开贴从来不会不结的。
...全文
请发表友善的回复…
发表回复
熊孩子开学喽 2006-11-02
- 打赏
- 举报
看了Dunzip的算法，确实比较快，因为结构简单，循环少。
缺点是代码不够灵活，如果是1000个数中找100个最近值的话，代码量就很可观了。
呵呵，纯粹找茬，稍微改动一下，其实只要把中间的SELECT中的东西用一个循环代替就好了。
只是速度也会下降一些。
好了，结贴了。
谢谢大家的参与和建议。
希望还有更多的问题能这样大家一起讨论。
缺点是代码不够灵活，如果是1000个数中找100个最近值的话，代码量就很可观了。
呵呵，纯粹找茬，稍微改动一下，其实只要把中间的SELECT中的东西用一个循环代替就好了。
只是速度也会下降一些。
好了，结贴了。
谢谢大家的参与和建议。
希望还有更多的问题能这样大家一起讨论。
heqq850 2006-10-28
- 打赏
- 举报
学习
xiagl311 2006-10-28
- 打赏
- 举报
study
guoguo1982 2006-10-28
- 打赏
- 举报
好象是学习过了，再学习！！
Rodensoft 2006-10-28
- 打赏
- 举报
1/Dunzip(路登软件,一路登先! / http://www.dunzip.com)
算法测试结果：
850 { 847 848 849 851 852 } Timer: 5.671875
10 { 7 8 9 11 12 } Timer: 3.53125
2/WallesCai(沧海明月一度,西风残阳无悔.)
算法测试结果：
850 { 847 849 851 848 852 } Timer: 7.140625
10 { 7 9 11 8 12 } Timer: 7.578125
3/测试平台C2.4,256M，ASUS Motherboard
4/经过测试发现：
A:WallesCai算法速度平均
B:Dunzip算法速度不平均，找前面的比找后面快.
算法测试结果：
850 { 847 848 849 851 852 } Timer: 5.671875
10 { 7 8 9 11 12 } Timer: 3.53125
2/WallesCai(沧海明月一度,西风残阳无悔.)
算法测试结果：
850 { 847 849 851 848 852 } Timer: 7.140625
10 { 7 9 11 8 12 } Timer: 7.578125
3/测试平台C2.4,256M，ASUS Motherboard
4/经过测试发现：
A:WallesCai算法速度平均
B:Dunzip算法速度不平均，找前面的比找后面快.
Dunzip 2006-10-28
- 打赏
- 举报
Option Explicit
Private TARGET(0 To 5) As Long
Private SOURCE(0 To 999) As Long
Private Sub Form_Load()
On Error Resume Next
Dim lNextLoop As Long
For lNextLoop = 0 To 999
SOURCE(lNextLoop) = lNextLoop
Next lNextLoop
End Sub
Private Sub AnalyseVicinalNumber(ByVal Reference As Long)
Dim TempTime As Single
Dim lNext As Long, lLoop As Long
TempTime = Timer
For lLoop = 0 To 10000
TARGET(0) = 0: TARGET(1) = 99995
TARGET(2) = 99996: TARGET(3) = 99997
TARGET(4) = 99998: TARGET(5) = 99999
For lNext = 0 To ALL - 1
Select Case Abs(SOURCE(lNext) - Reference)
Case Is <= Abs(TARGET(0) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = TARGET(3)
TARGET(3) = TARGET(2)
TARGET(2) = TARGET(1)
TARGET(1) = TARGET(0)
TARGET(0) = SOURCE(lNext)
Case Is <= Abs(TARGET(1) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = TARGET(3)
TARGET(3) = TARGET(2)
TARGET(2) = TARGET(1)
TARGET(1) = SOURCE(lNext)
Case Is <= Abs(TARGET(2) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = TARGET(3)
TARGET(3) = TARGET(2)
TARGET(2) = SOURCE(lNext)
Case Is <= Abs(TARGET(3) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = TARGET(3)
TARGET(3) = SOURCE(lNext)
Case Is <= Abs(TARGET(4) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = SOURCE(lNext)
Case Else
End Select
Next lNext
Next lLoop
Debug.Print "{"; TARGET(5); TARGET(4); TARGET(2); "[" & Reference & "]"; TARGET(1); TARGET(3); "}"
Debug.Print "Timer: " & CStr(Timer - TempTime)
End Sub
Private Sub Command1_Click()
AnalyseVicinalNumber 50
End Sub
循环10000次的耗时结果：
50:
{ 47 48 49 [50] 51 52 }
Timer: 1.625
980:
{ 977 978 979 [980] 981 982 }
Timer: 3.46875
我可以断定，在1000个数字内找5个靠近某个数字的代码，以上是比较快的了
Private TARGET(0 To 5) As Long
Private SOURCE(0 To 999) As Long
Private Sub Form_Load()
On Error Resume Next
Dim lNextLoop As Long
For lNextLoop = 0 To 999
SOURCE(lNextLoop) = lNextLoop
Next lNextLoop
End Sub
Private Sub AnalyseVicinalNumber(ByVal Reference As Long)
Dim TempTime As Single
Dim lNext As Long, lLoop As Long
TempTime = Timer
For lLoop = 0 To 10000
TARGET(0) = 0: TARGET(1) = 99995
TARGET(2) = 99996: TARGET(3) = 99997
TARGET(4) = 99998: TARGET(5) = 99999
For lNext = 0 To ALL - 1
Select Case Abs(SOURCE(lNext) - Reference)
Case Is <= Abs(TARGET(0) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = TARGET(3)
TARGET(3) = TARGET(2)
TARGET(2) = TARGET(1)
TARGET(1) = TARGET(0)
TARGET(0) = SOURCE(lNext)
Case Is <= Abs(TARGET(1) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = TARGET(3)
TARGET(3) = TARGET(2)
TARGET(2) = TARGET(1)
TARGET(1) = SOURCE(lNext)
Case Is <= Abs(TARGET(2) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = TARGET(3)
TARGET(3) = TARGET(2)
TARGET(2) = SOURCE(lNext)
Case Is <= Abs(TARGET(3) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = TARGET(3)
TARGET(3) = SOURCE(lNext)
Case Is <= Abs(TARGET(4) - Reference)
TARGET(5) = TARGET(4)
TARGET(4) = SOURCE(lNext)
Case Else
End Select
Next lNext
Next lLoop
Debug.Print "{"; TARGET(5); TARGET(4); TARGET(2); "[" & Reference & "]"; TARGET(1); TARGET(3); "}"
Debug.Print "Timer: " & CStr(Timer - TempTime)
End Sub
Private Sub Command1_Click()
AnalyseVicinalNumber 50
End Sub
循环10000次的耗时结果：
50:
{ 47 48 49 [50] 51 52 }
Timer: 1.625
980:
{ 977 978 979 [980] 981 982 }
Timer: 3.46875
我可以断定，在1000个数字内找5个靠近某个数字的代码，以上是比较快的了
jcyluck 2006-09-11
- 打赏
- 举报
我觉得最简单 的办法就是放到数据库里，一排序，取前面两个和后面三个，代码最简单了，
熊孩子开学喽 2006-09-11
- 打赏
- 举报
TO cxjddd(又是花开时)
谢谢你的提醒，找了很多资料看，没有找到原代码，只有一些接口说明。
所以没有办法用VB实现。
看来只能用自己的办法了。
谢谢你的提醒，找了很多资料看，没有找到原代码，只有一些接口说明。
所以没有办法用VB实现。
看来只能用自己的办法了。
熊孩子开学喽 2006-09-11
- 打赏
- 举报
to jcyluck(VB 2005 QQ群：26096739)
代码简单不等于速度快，用数据库的话，前面的任何一个算法都要比它快100倍以上。你可以自己测试一下。
代码简单不等于速度快，用数据库的话，前面的任何一个算法都要比它快100倍以上。你可以自己测试一下。
purdue 2006-09-08
- 打赏
- 举报
TO WallesCai:
然后求这个数组中最小的若干个数
-------又回到排序上来了,就是这个最慢
从n个数中找第k小的是k-selection问题，最好的算法是O(n).
找到第k小的数后在遍历一次树祖，可以得到最小的k个数。（如果有重复的数，最多遍历两次）。
所以整个问题的复杂度在最坏情况下是O(n)，和k的大小无关。
很长时间没用过basic了，所以写不出程序。:(
不过你可以很容易google到k-selection的算法。
然后求这个数组中最小的若干个数
-------又回到排序上来了,就是这个最慢
从n个数中找第k小的是k-selection问题，最好的算法是O(n).
找到第k小的数后在遍历一次树祖，可以得到最小的k个数。（如果有重复的数，最多遍历两次）。
所以整个问题的复杂度在最坏情况下是O(n)，和k的大小无关。
很长时间没用过basic了，所以写不出程序。:(
不过你可以很容易google到k-selection的算法。
熊孩子开学喽 2006-09-08
- 打赏
- 举报
空间效率不考虑，但是不要太离谱就行
唐竹 2006-09-08
- 打赏
- 举报
突然想到一个问题
考虑不考虑空间效率？
考虑不考虑空间效率？
guoguo1982 2006-09-08
- 打赏
- 举报
study!
东方冉 2006-09-08
- 打赏
- 举报
mark
学习~~
学习~~
yimins 2006-09-08
- 打赏
- 举报
来一个用对象的方法，纯粹开阔一下思路，无需考虑效率。（大约比楼主的慢100倍）
Private Sub FSort2(ByVal Test As Long)
Dim A(9) As Long
Dim D(9) As Long
Dim I As Long
Dim J As Long
Dim C1 As New Collection
Dim ExitBool As Boolean
A(0) = 3: A(1) = 3: A(2) = 1: A(3) = 6: A(4) = 2
A(5) = 7: A(6) = 5: A(7) = 8: A(8) = 9: A(9) = 7
Dim Num(4) As Long
Dim GG As Long
T = timeGetTime
For GG = 0 To 1000000
Set C1 = Nothing
Set C1 = New Collection
For I = 0 To 9
D(I) = Abs(A(I) - Test)
Next I
C1.Add D(0)
For I = 1 To 9
For J = C1.Count To 1 Step -1
If D(I) > C1(J) Then
C1.Add CStr(I), , , J
ExitBool = True
Exit For
End If
Next J
If ExitBool = False Then
C1.Add CStr(I), , J + 1
Else
ExitBool = False
End If
Next I
For J = 0 To 4
Num(J) = A(C1(J + 1))
Next J
Next GG
For I = 0 To 4
Me.Print Num(I)
Next
Me.Print timeGetTime - T
End Sub
Private Sub FSort2(ByVal Test As Long)
Dim A(9) As Long
Dim D(9) As Long
Dim I As Long
Dim J As Long
Dim C1 As New Collection
Dim ExitBool As Boolean
A(0) = 3: A(1) = 3: A(2) = 1: A(3) = 6: A(4) = 2
A(5) = 7: A(6) = 5: A(7) = 8: A(8) = 9: A(9) = 7
Dim Num(4) As Long
Dim GG As Long
T = timeGetTime
For GG = 0 To 1000000
Set C1 = Nothing
Set C1 = New Collection
For I = 0 To 9
D(I) = Abs(A(I) - Test)
Next I
C1.Add D(0)
For I = 1 To 9
For J = C1.Count To 1 Step -1
If D(I) > C1(J) Then
C1.Add CStr(I), , , J
ExitBool = True
Exit For
End If
Next J
If ExitBool = False Then
C1.Add CStr(I), , J + 1
Else
ExitBool = False
End If
Next I
For J = 0 To 4
Num(J) = A(C1(J + 1))
Next J
Next GG
For I = 0 To 4
Me.Print Num(I)
Next
Me.Print timeGetTime - T
End Sub
cxjddd 2006-09-08
- 打赏
- 举报
可以参考 C++ STL 的 nth_element 算法：）
xxelement 2006-09-07
- 打赏
- 举报
??????
这个怎么和俺面试时做的题很像?先排序,然后求差值之间的关系.
这个怎么和俺面试时做的题很像?先排序,然后求差值之间的关系.
熊孩子开学喽 2006-09-07
- 打赏
- 举报
to 楼上:
先变换一下，得到数字与目标数的差值的绝对值的数组
--------没错,这个是必需的
然后求这个数组中最小的若干个数
-------又回到排序上来了,就是这个最慢
先变换一下，得到数字与目标数的差值的绝对值的数组
--------没错,这个是必需的
然后求这个数组中最小的若干个数
-------又回到排序上来了,就是这个最慢
cxjddd 2006-09-07
- 打赏
- 举报
先变换一下，得到数字与目标数的差值的绝对值的数组
然后求这个数组中最小的若干个数
然后求这个数组中最小的若干个数
熊孩子开学喽 2006-09-07
- 打赏
- 举报
TO zswang(伴水清清)(专家门诊清洁工)
不是20次，是100次
TO Modest(塞北雪貂)·(偶最欣赏楼主的分)
请仔细想想，先排序再取临近值肯定不是最快的。并且在取“临近值”的时候还是存在一个插值排序的过程，这样更慢了。
不是20次，是100次
TO Modest(塞北雪貂)·(偶最欣赏楼主的分)
请仔细想想，先排序再取临近值肯定不是最快的。并且在取“临近值”的时候还是存在一个插值排序的过程，这样更慢了。
加载更多回复（33）
用连续自然数之和来表达整数【华为OD机试JAVA题解】一个整数可以由连续的自然数之和来表示。给定一个整数，计算该整数有几种连续自然数之和的表达式，且打印出每种表达式。 输入描述： 一个目标整数T (1
