1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
' Challenge 003
'
' Challenge #1
' Create a script to generate 5-smooth numbers, whose prime divisors are less
' or equal to 5. They are also called Hamming/Regular/Ugly numbers. For more
' information, please check this wikipedia.
' deque of integers
type ElemType
nValue as integer
pNext as ElemType ptr
end type
type QType
pFront as ElemType ptr
pBack as ElemType ptr
end type
function QEmpty(byref q as QType) as boolean
if q.pFront = 0 then
QEmpty = true
else
QEmpty = false
end if
end function
function QFront(byref q as QType) as integer
QFront = q.pFront->nValue
end function
function QBack(byref q as QType) as integer
QBack = q.pBack->nValue
end function
sub QPushBack(byref q as QType, nValue as integer)
dim pElem as ElemType ptr
pElem = callocate(1, sizeof(ElemType))
pElem->nValue = nValue
if q.pFront = 0 then
q.pFront = pElem
q.pBack = pElem
else
q.pBack->pNext = pElem
q.pBack = pElem
end if
end sub
sub QPopBack(byref q as QType)
dim pElem as ElemType ptr
if q.pFront = 0 then ' empty
elseif q.pFront = q.pBack then ' only one element
deallocate q.pFront
q.pFront = 0
q.pBack = 0
else ' more than one element
pElem = q.pFront
do while pElem->pNext <> q.pBack
pElem = pElem->pNext
loop
deallocate q.pBack
q.pBack = pElem
pElem->pNext = 0
end if
end sub
sub QPushFront(byref q as QType, nValue as integer)
dim pElem as ElemType ptr
pElem = callocate(1, sizeof(ElemType))
pElem->nValue = nValue
if q.pFront = 0 then
q.pFront = pElem
q.pBack = pElem
else
pElem->pNext = q.pFront
q.pFront = pElem
end if
end sub
sub QPopFront(byref q as QType)
dim pElem as ElemType ptr
if q.pFront = 0 then ' empty
elseif q.pFront = q.pBack then ' only one element
deallocate q.pFront
q.pFront = 0
q.pBack = 0
else ' more than one element
pElem = q.pFront
q.pFront = pElem->pNext
deallocate pElem
end if
end sub
function min(a as integer, b as integer) as integer
if a < b then
min = a
else
min = b
end if
end function
function min3(a as integer, b as integer, c as integer) as integer
min3 = min(a, min(b, c))
end function
' Hamming generator
dim shared q2 as QType
dim shared q3 as QType
dim shared q5 as QType
function next_hamming() as integer
dim n as integer
' init queues at start
if QEmpty(q2) then
QPushBack q2, 1
QPushBack q3, 1
QPushBack q5, 1
end if
' get the smallest of the queue heads
n = min3(QFront(q2), QFront(q3), QFront(q5))
' shift used multiples
if n = QFront(q2) then QPopFront q2
if n = QFront(q3) then QPopFront q3
if n = QFront(q5) then QPopFront q5
' push next multiples
QPushBack q2, 2*n
QPushBack q3, 3*n
QPushBack q5, 5*n
next_hamming = n
end function
' main
dim i as integer
for i=1 to val(command(1))
print next_hamming()
next i
|
