TELK
OMNIKA
Indonesian
Journal
of
Electrical
Engineering
V
ol.
12,
No
.
8,
A
ugust
2014,
pp
.
6338
6345
DOI:
10.11591/telk
omnika.v12.i8.5198
6338
A
Complete
Combinatorial
Solution
f
or
a
Coins
Chang
e
Puzzle
and
Its
Computer
Implementation
Daxin
Zhu
and
Xiaodong
W
ang*
Quanzhou
Nor
mal
Univ
ersity
362000
Quanzhou,
Fujian,
China
*Corresponding
author
,
e-mail:
w
angxiaodong@qztc.edu.cn
Abstract
In
this
paper
,
w
e
study
a
combinator
ial
prob
lem
encountered
in
monetar
y
systems
.
The
prob
lem
concer
ned
is
to
find
an
optimal
solution
R
(
k
;
n
)
of
a
combinator
ial
prob
lem
f
or
some
positiv
e
integers
k
and
n
.
T
o
the
authors’
kno
wledge
,
there
is
no
efficient
solutions
f
or
this
prob
lem
in
the
liter
atures
so
f
ar
.
W
e
first
sho
w
ho
w
to
find
an
efficient
recursiv
e
constr
uction
algor
ithm
based
on
the
bac
ktr
ac
king
search
str
ategy
.
Fur
ther
more
,
w
e
can
giv
e
an
e
xplicit
f
or
m
ula
f
or
finding
the
maximal
elements
of
the
solution.
Our
ne
w
techniques
ha
v
e
impro
v
ed
the
time
comple
xities
of
the
search
algor
ithm
dr
amatically
.
K
e
yw
or
ds:
Coins
Change
Puzzle
,
combinator
ial
solution,
linear
time
,
optimal
algor
ithm
Cop
yright
c
2013
Univer
sitas
Ahmad
Dahlan.
All
rights
reser
ved.
1.
Intr
oduction
In
this
paper
,
w
e
consider
the
f
ollo
wing
combinator
ial
prob
lem
encountered
in
monetar
y
systems
.
Suppose
C
(
k
)
is
a
monetar
y
system
that
divides
the
currency
denomination
into
k
+
1
decimal
le
v
els:
f
1
;
2
;
5
g
;
f
10
;
20
;
50
g
;
;
f
10
i
;
2
10
i
;
5
10
i
g
;
;
f
10
k
g
:
F
or
e
xample
,
China’
s
currency
system
(RMB)
can
be
classified
as
C
(4)
.
Notation:
c
(
i;
j
)
;
0
i
k
;
0
j
2
denote
the
le
v
els
of
monetar
y
v
alues
.
The
monetar
y
v
alue
of
le
v
el
i
can
be
wr
itten
as
c
i
=
(
c
(
i;
0)
;
c
(
i;
1)
;
c
(
i;
2))
>
;
0
i
k
.
In
par
ticular
,
when
i
=
k
,
c
k
=
(10
k
;
0
;
0)
>
.
F
or
an
y
integer
n
2
I
+
w
e
can
ob
viously
e
xpress
n
b
y
the
abo
v
e
currency
system
as
f
ollo
ws
n
=
k
X
i
=0
2
X
j
=0
a
(
i;
j
)
c
(
i;
j
)
(1)
where
a
(
i;
j
)
2
I
+
;
0
i
k
;
0
j
2
.
Denote
a
i
=
(
a
(
i;
0)
;
a
(
i;
1)
;
a
(
i;
2))
>
;
g
(
a
i
;
c
i
)
=
a
>
i
c
i
;
0
i
k
and
a
=
(
a
0
;
a
1
;
;
a
k
)
>
.
Then,
the
integer
n
can
be
e
xpressed
b
y
n
=
k
X
i
=0
a
>
i
c
i
=
k
X
i
=0
g
(
a
i
;
c
i
)
,
f
(
k
;
a
)
(2)
F
or
a
giv
en
n
2
I
+
,
the
abo
v
e
representation
is
ob
viously
not
unique
in
gener
al.
The
diff
erent
v
alues
of
a
satisfying
(1)
will
giv
e
diff
erent
representations
of
the
positiv
e
integer
n
.
Set
A
(
k
;
n
)
=
f
a
j
f
(
k
;
a
)
=
n
g
constitutes
all
representations
of
a
positiv
e
integer
n
in
the
giv
en
currency
system.
F
or
e
xample
,
when
k
=
4
;
n
=
3
w
e
ha
v
e
A
(4
;
3)
=
8
>
>
>
>
<
>
>
>
>
:
0
B
B
B
B
@
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
C
C
C
C
A
;
0
B
B
B
B
@
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
C
C
C
C
A
9
>
>
>
>
=
>
>
>
>
;
Receiv
ed
No
v
ember
24,
2013;
Re
vised
March
5,
2014;
Accepted
March
26,
2014
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
2302-4046
6339
Definition
1.
Let
a
and
b
be
tw
o-dimensional
arr
a
ys
.
b
a
if
and
only
if
b
(
i;
j
)
a
(
i;
j
)
,
0
i
k
,
and
0
j
2
;
b
<
a
if
and
only
if
both
b
a
and
b
6
=
a
.
Definition
2.
Let
s
(
k
;
a
)
=
f
f
(
k
;
b
)
j
f
(
k
;
a
)
=
n;
0
<
b
a
g
(3)
Set
s
(
k
;
a
)
is
defined
as
an
implication
set
of
the
positiv
e
integer
n
,
which
is
the
collection
of
all
the
mone
y
under
the
representation
a
.
F
or
e
xample
,
when
a
=
0
B
B
B
B
@
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
C
C
C
C
A
2
A
(4
;
3)
w
e
ha
v
e
s
(4
;
a
)
=
f
1
;
2
;
3
g
.
Definition
3.
Set
R
(
k
;
n
)
=
\
a
2
A
(
k
;n
)
s
(
k
;
a
)
(4)
is
defined
to
be
an
accur
ate
implication
set
of
the
positiv
e
integer
n
in
the
giv
en
currency
system[1].
F
or
an
y
x
2
R
(
k
;
n
)
,
regardless
of
the
kind
of
par
v
alue
of
the
currency
that
composes
the
positiv
e
integer
n
,
it
cer
tainly
contains
x
.
F
or
e
xample
,
suppose
the
currency
system
is
in
RMB
.
A
person
has
mone
y
$5.27
(
n
=
527
).
If
his
mone
y
is
composed
of
one
$5
piece
(
c
(2
;
2)
=
500
),
one
2
angle
piece
(
c
(1
;
1)
=
20
)
,
one
5
cent
coin
(
c
(0
;
2)
=
5
),
and
one
2
cent
coin
(
c
(0
;
1)
=
2
).
In
our
definition,
k
=
4
and
a
=
0
B
B
B
B
@
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
1
C
C
C
C
A
2
A
(4
;
527)
:
In
this
case
,
he
cannot
come
up
with
$0.17.
Tha
t
is
,
17
62
s
(4
;
a
)
.
Ho
w
e
v
er
,
regardless
of
the
kind
of
par
v
alue
of
the
currency
,
he
can
cer
tainly
tak
e
out
$0.02
because
without
one
2
cent
coin
or
tw
o
1
cent
coins
he
cannot
scr
ape
together
$5.27.
In
other
w
ords
,
2
2
R
(4
;
527)
.
In
addition
to
$0.02,
he
can
cer
tainly
tak
e
out
$5.00,
$0.2,
$0.07,
$5.2,
$0.27,
and
so
on.
These
amounts
of
mone
y
,
as
the
y
are
called,
are
cer
tainly
tak
en
out
of
the
$5.27.
The
main
prob
lem
concer
ned
in
this
paper
is
f
or
the
giv
en
positiv
e
integers
k
and
n
,
ho
w
to
find
the
corresponding
accur
ate
implication
set
R
(
k
;
n
)
efficiently
.
T
o
the
authors’
kno
wledge
,
there
is
no
solutions
f
or
the
prob
lem
in
the
liter
atures
so
f
ar
.
A
preliminar
y
conf
erence
v
ersion
of
this
paper
w
as
presented
at
Adv
ances
in
Inf
or
mation
T
echnology
and
Education
Comm
unications
in
Computer
and
Inf
or
mation
Science[2].
I
n
this
paper
the
correctness
and
comple
xities
are
pro
v
ed
r
igorously
,
b
ut
not
just
stated
in
intuitiv
ely
.
More
e
xper
iment
details
are
descr
ibed
in
this
v
ersion
of
the
paper
.
2.
Bac
ktrac
king
Algorithm
2.1.
A
Simple
Bac
ktrac
king
Algorithm
According
to
Definition
3,
the
accur
ate
implication
set
of
the
giv
en
positiv
e
integers
k
and
n
in
the
currency
system
C
(
k
)
can
be
f
or
m
ulated
as
(4).
In
the
algor
ithm
descr
iption,
w
e
use
oper
ations
+
and
-
f
or
a
set
U
and
a
positiv
e
integer
v
defined
as
f
ollo
ws
U
+
v
=
f
x
+
v
j
x
2
U
g
;
U
v
=
f
x
v
j
x
2
U
and
x
v
g
Based
on
this
f
or
m
ula
w
e
can
design
a
s
i
mple
bac
ktr
ac
king
algor
ithm
[
?
,
3,
4]
to
find
R
(
k
;
n
)
as
f
ollo
ws
.
Initially
,
R
=
f
1
;
2
;
;
n
g
and
S
=
;
.
A
recursiv
e
function
call
B
ack
tr
ack
(
n
)
will
compute
the
set
R
=
R
(
k
;
n
)
.
A
Complete
Combinator
ial
Solution
f
or
a
Coins
Change
Puzzle
and
Its
Computer
...
(D
.
Zhu)
Evaluation Warning : The document was created with Spire.PDF for Python.
6340
ISSN:
2302-4046
Algorithm
1
Bac
ktr
ac
k(
t
)
1:
if
t
=
0
then
2:
R
R
T
S
3:
return
R
4:
else
5:
f
or
all
c
(
i;
j
)
2
C
(
k
)
such
that
c
(
i;
j
)
t
do
6:
S
S
+
c
(
i;
j
)
7:
Bac
ktr
ac
k(
t
c
(
i;
j
)
)
8:
S
S
c
(
i;
j
)
9:
end
f
or
10:
end
if
11:
return
R
2.2.
Bac
ktrac
k
Pruning
If
par
v
alue
1,
2,
and
5
are
used
to
compose
the
mone
y
,
then
positiv
e
integer
10
can
be
one
of
the
f
ollo
wing
10
diff
erent
representations
.
T
ab
le
1.
Representations
of
10
e
1
=
(10
;
0
;
0)
e
2
=
(8
;
1
;
0)
e
3
=
(6
;
2
;
0)
e
4
=
(4
;
3
;
0)
e
5
=
(2
;
4
;
0)
e
6
=
(0
;
5
;
0)
e
7
=
(5
;
0
;
1)
e
8
=
(3
;
1
;
1)
e
9
=
(1
;
2
;
1)
e
10
=
(0
;
0
;
2)
Let
E
=
f
e
i
;
i
=
1
;
;
10
g
.
Lemma
1.
F
or
the
positiv
e
integers
m
=
10
,
m
=
1
2
and
m
14
,
if
m
=
g
(
a
0
;
c
0
)
=
2
X
j
=0
a
(0
;
j
)
c
(0
;
j
)
,
then
there
m
ust
be
an
integer
d
2
E
such
that
d
a
0
.
Lemma
2.
F
or
an
y
a
2
A
(
k
;
n
)
w
e
ha
v
e
,
(1)
(
a;
i
)
2
A
(
k
;
n
)
;
0
i
k
.
(2)
s
(
k
;
(
a;
i
))
s
(
k
;
a
)
;
0
i
k
.
Theorem
3.
Let
S
0
=
f
1
;
2
;
3
;
4
;
5
;
6
;
7
;
8
;
9
;
11
;
13
g
,
B
(
k
;
n
)
=
f
a
2
A
(
k
;
n
)
j
(
a;
i
)
=
a;
0
i
k
g
,
F
(
k
;
n
)
=
f
a
2
B
(
k
;
n
)
j
a
>
i
c
0
2
S
0
g
.
Then,
R
(
k
;
n
)
=
T
a
2
A
(
k
;n
)
s
(
k
;
a
)
=
T
a
2
B
(
k
;n
)
s
(
k
;
a
)
T
a
2
F
(
k
;n
)
s
(
k
;
a
)
.
By
making
use
of
the
constr
aints
of
F
(
k
;
n
)
in
Theorem
3,
w
e
can
add
pr
uning
condition
in
the
bac
ktr
ac
king
algor
ithm
to
impro
v
e
the
searching
speed
as
f
ollo
ws
[5].
Algorithm
2
Bac
ktr
ac
k(
t
)
1:
if
t
=
0
then
2:
R
R
T
S
3:
return
R
4:
else
5:
f
or
all
c
(
i;
j
)
2
C
(
k
)
and
c
(
i;
j
)
t
and
a
>
i
c
0
2
S
0
do
6:
S
S
+
c
(
i;
j
)
7:
Bac
ktr
ac
k(
t
c
(
i;
j
)
)
8:
S
S
c
(
i;
j
)
9:
end
f
or
10:
end
if
11:
return
R
TELK
OMNIKA
V
ol.
12,
No
.
8,
A
ugust
2014
:
6338
6345
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
2302-4046
6341
2.3.
Recur
sive
Constructing
Algorithm
Definition
5.
div
(
x;
y
)
=
x
y
;
mo
d(
x;
y
)
=
x
y
x
y
:
Lemma
4.
Let
G
1
(
k
;
n
)
=
f
a
2
F
(
k
;
n
)
j
a
T
0
c
0
=
mo
d(
n;
10)
g
G
2
(
k
;
n
)
=
f
a
2
F
(
k
;
n
)
j
a
T
0
c
0
=
10
+
mo
d(
n;
10)
g
(1)
If
mo
d(
n;
10)
=
2
f
1
;
3
g
,
then
F
(
k
;
n
)
=
G
1
(
k
;
n
)
.
(2)
If
mo
d(
n;
10)
2
f
1
;
3
g
,
then
F
(
k
;
n
)
=
G
1
(
k
;
n
)
S
G
2
(
k
;
n
)
:
Theorem
5.
(1)
If
mo
d(
n;
10)
=
2
f
1
;
3
g
,
then
R
(
k
;
n
)
=
T
a
2
G
1(
k
;n
)
s
(
k
;
a
)
:
(2)
If
mo
d(
n;
10)
2
f
1
;
3
g
,
then
R
(
k
;
n
)
=
T
a
2
G
1(
k
;n
)
s
(
k
;
a
)
T
T
a
2
G
2(
k
;n
)
s
(
k
;
a
)
:
Pr
oof
.
It
can
be
readily
pro
v
ed
b
y
Theorem
3
and
Lemma
4.
Lemma
6.
Let
s
0
(
k
;
a
)
=
f
f
(
k
;
b
)
j
0
<
b
a;
b
i
=
0
;
0
i
k
g
;
s
1
(
k
;
a
)
=
f
f
(
k
;
b
)
j
0
<
b
a;
b
0
=
0
g
;
s
2
(
k
;
a
)
=
s
(
k
;
a
)
s
0
(
k
;
a
)
s
1
(
k
;
a
)
:
Then
F
or
an
y
a
2
G
1
(
k
;
n
)
S
G
2
(
k
;
n
)
,
w
e
ha
v
e
s
(
k
;
a
)
=
s
0
(
k
;
a
)
S
s
1
(
k
;
a
)
S
s
2
(
k
;
a
)
;
T
a
2
G
1
(
k
;n
)
s
(
k
;
a
)
=
1
S
1
S
1
;
T
a
2
G
2
(
k
;n
)
s
(
k
;
a
)
=
2
S
2
S
2
.
where
1
=
\
a
2
G
1
(
k
;n
)
s
0
(
k
;
a
)
;
2
=
\
a
2
G
2
(
k
;n
)
s
0
(
k
;
a
)
1
=
\
a
2
G
1
(
k
;n
)
s
1
(
k
;
a
)
;
2
=
\
a
2
G
2
(
k
;n
)
s
1
(
k
;
a
)
1
=
\
a
2
G
1
(
k
;n
)
s
2
(
k
;
n
)
;
2
=
\
a
2
G
2
(
k
;n
)
s
2
(
k
;
n
)
Definition
6.
Let
U
and
V
be
tw
o
sets
of
integer
.
The
circle
plus
oper
ation
f
or
sets
U
and
V
is
defined
as
U
V
=
f
x
+
y
j
x
2
U
;
y
2
V
g
:
The
m
ultiplication
of
a
set
U
b
y
an
integer
m
is
defined
as
m
U
=
f
mx
j
x
2
U
g
:
Definition
7.
T
0
=
R
(
k
;
mo
d(
n;
10));
T
1
=
10
R
(
k
1
;
div
(
n;
10));
T
2
=
\
a
2
G
2
(
k
;n
)
s
0
(
k
;
a
);
T
3
=
10
R
(
k
1
;
div
(
n;
10)
1);
T
4
=
R
(
k
;
10
+
mo
d(
n;
10))
:
Lemma
7.
\
a
2
G
1
(
k
;n
)
s
0
(
k
;
a
)
=
T
0
(5)
\
a
2
G
1
(
k
;n
)
s
1
(
k
;
a
)
=
T
1
(6)
\
a
2
G
1
(
k
;n
)
s
2
(
k
;
a
)
=
T
0
T
1
(7)
\
a
2
G
2
(
k
;n
)
s
1
(
k
;
a
)
=
T
3
(8)
A
Complete
Combinator
ial
Solution
f
or
a
Coins
Change
Puzzle
and
Its
Computer
...
(D
.
Zhu)
Evaluation Warning : The document was created with Spire.PDF for Python.
6342
ISSN:
2302-4046
\
a
2
G
2
(
k
;n
)
s
2
(
k
;
a
)
=
T
2
T
3
(9)
Lemma
8.
Let
k
>
1
,
x
2
R
(
k
;
n
)
and
mo
d(
x;
10)
>
0
,
then
mo
d(
x;
10)
2
R
(
k
;
mo
d(
n;
10))
:
Theorem
9.
(1)
If
mo
d(
n;
10)
=
2
f
1
;
3
g
,
then
R
(
k
;
n
)
=
T
0
S
T
1
S
(
T
0
T
1
)
(2)
If
mo
d(
n;
10)
2
f
1
;
3
g
,
then
R
(
k
;
n
)
=
(
T
0
S
T
1
S
(
T
0
T
1
))
T
(
T
3
S
T
4
S
(
T
3
T
4
))
:
(3)
R
(0
;
n
)
=
f
1
;
2
;
;
n
g
:
Pr
oof
.
(1)
It
f
ollo
ws
from
Theorem
5
and
Lemma
7
that
if
mo
d(
n;
10)
=
2
f
1
;
3
g
,
then
R
(
k
;
n
)
=
\
a
2
G
1
(
k
;n
)
s
(
k
;
a
)
=
T
0
[
T
1
[
(
T
0
T
1
)
:
(2)
It
f
ollo
ws
from
Theorem
5,
Lemma
6
and
Lemma
7
that
if
mo
d(
n;
10)
2
f
1
;
3
g
,
then
R
(
k
;
n
)
=
(
T
0
[
T
1
[
(
T
0
T
1
))
\
(
T
3
[
T
2
[
(
T
3
T
2
))
:
If
k
>
1
and
mo
d(
n;
10)
=
1
,
then
R
(
k
;
11)
=
f
11
g
f
2
;
4
;
5
;
6
;
7
;
9
;
11
g
=
T
a
2
G
2
(
k
;n
)
s
0
(
k
;
a
)
=
T
2
If
k
>
1
and
mo
d(
n;
10)
=
3
,
then
R
(
k
;
13)
=
f
2
;
11
;
13
g
f
2
;
4
;
5
;
6
;
7
;
8
;
9
;
10
;
11
;
13
g
=
T
a
2
G
2
(
k
;n
)
s
0
(
k
;
a
)
=
T
2
Theref
ore
,
T
4
=
R
(
k
;
10
+
mo
d(
n;
10))
T
2
and
thus
,
T
3
S
T
4
S
(
T
3
T
4
)
T
3
S
T
2
S
(
T
3
T
2
)
:
It
f
ollo
ws
that
(
T
0
S
T
1
S
(
T
0
T
1
))
T
(
T
3
S
T
4
S
(
T
3
T
4
))
(
T
0
S
T
1
S
(
T
0
T
1
))
T
(
T
3
S
T
2
S
(
T
3
T
2
))
=
R
(
k
;
n
)
On
the
other
hand,
f
or
an
y
x
2
R
(
k
;
n
)
,
w
e
ha
v
e
x
2
T
3
S
T
2
S
(
T
3
T
2
)
:
If
mo
d(
x;
10)
=
0
,
then
x
2
T
3
.
If
mo
d(
x;
10)
>
0
,
then
x
2
T
2
S
(
T
3
T
2
)
.
It
f
ollo
ws
from
Lemma
8
that
mo
d(
x;
10)
2
R
(
k
;
mo
d(
n;
10))
.
(2.1)
If
mo
d(
n;
10)
=
1
,
then
R
(
k
;
mo
d(
n;
10))
=
f
1
g
.
If
x
2
T
2
,
then
x
2
f
11
g
=
R
(
k
;
11)
=
T
4
;
If
x
2
T
3
T
2
,
then
x
=
11
+
y
,
y
2
T
3
and
thus
,
x
2
T
3
T
4
.
Theref
ore
,
x
2
T
4
S
(
T
3
T
4
)
.
(2.2)
If
mo
d(
n;
10)
=
3
,
then
R
(
k
;
mo
d(
n;
10))
=
f
1
;
2
;
3
g
.
If
x
2
T
2
,
then
x
2
f
2
;
11
g
=
R
(
k
;
13)
=
T
4
;
If
x
2
T
3
T
2
,
then
x
=
y
+
z
,
y
2
T
4
,
z
2
T
3
and
thus
,
x
2
T
3
T
4
.
Theref
ore
,
x
2
T
4
S
(
T
3
T
4
)
.
It
f
ollo
ws
from
the
arbitr
ar
iness
of
x
that
R
(
k
;
n
)
(
T
0
[
T
1
[
(
T
0
T
1
))
\
(
T
3
[
T
4
[
(
T
3
T
4
))
:
In
summar
y
,
w
e
ha
v
e
R
(
k
;
n
)
=
(
T
0
[
T
1
[
(
T
0
T
1
))
\
(
T
3
[
T
4
[
(
T
3
T
4
))
:
(3)
R
(0
;
n
)
=
f
1
;
2
;
;
n
g
is
ob
vious
.
According
to
Theorem
9,
w
e
can
design
a
recursiv
e
constr
ucting
algor
ithm
R
ecur
C
onst
(
k
;
n
)
f
or
computing
R
(
k
;
n
)
as
f
ollo
ws
[4].
In
the
algor
ithm
descr
iption
abo
v
e
,
the
sub-algor
ithm
D
ir
ec
t
(
k
;
n
)
compute
the
set
R
(
k
;
n
)
directly
b
y
a
pre-computed
solution
tab
le
.
TELK
OMNIKA
V
ol.
12,
No
.
8,
A
ugust
2014
:
6338
6345
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
2302-4046
6343
Algorithm
3
RecurConst(
k
;
n
)
1:
if
k
=
0
or
n
<
14
then
2:
return
D
ir
ect
(
k
;
n
)
3:
end
if
4:
T
0
D
ir
ect
(
k
;
mo
d(
n;
10))
5:
T
1
R
ecur
C
onst
(
k
1
;
div
(
n;
10))
6:
R
T
0
S
T
1
S
(
T
0
T
1
)
7:
if
k
=
0
or
n
<
14
then
8:
T
3
D
ir
ect
(
k
;
10
+
mo
d(
n;
10))
9:
T
4
R
ecur
C
onst
(
k
1
;
div
(
n;
10)
1)
10:
R
R
T
(
T
3
S
T
4
S
(
T
3
T
4
))
11:
end
if
12:
return
R
3.
Finding
the
Maximal
Elements
Definition
8.
g
(
k
;
n
)
=
max
1
i
n
fj
R
(
k
;
i
)
jg
;
h
(
k
;
n
)
satisfying
g
(
k
;
n
)
=
j
R
(
k
;
h
(
k
;
n
))
j
[4].
Lemma
10.
g
(0
;
n
)
=
n
;
h
(0
;
n
)
=
n
.
Pr
oof
.
It
f
ollo
ws
from
R
(0
;
n
)
=
f
1
;
2
;
;
n
g
.
Lemma
11.
If
div
(
n;
10
k
)
1
and
m
k
,
then
R
(
k
;
n
)
=
R
(
m;
n
)
.
Pr
oof
.
It
f
ollo
ws
from
div
(
n;
10
k
)
1
that
f
or
an
y
a
2
A
(
k
;
n
)
,
w
e
ha
v
e
n
=
f
(
k
;
a
)
=
k
X
i
=0
a
>
i
c
i
;
div
(
n;
10
k
)
=
div
(
a
>
k
c
k
;
10
k
)
=
a
>
k
c
0
1
,
and
thus
,
A
(
k
;
1)
=
A
(
k
;
2)
=
0
.
If
m
k
,
then
f
or
an
y
a
2
A
(
m;
n
)
,
w
e
ha
v
e
n
=
f
(
m;
a
)
=
m
X
i
=0
a
>
i
c
i
;
div
(
n;
10
k
)
=
div
(
a
>
k
c
k
;
10
k
)
1
,
and
thus
,
a
i
=
0
f
or
all
i
>
k
;
A
(
k
;
1)
=
A
(
k
;
2)
=
0
.
Theref
ore
,
R
(
k
;
n
)
=
R
(
m;
n
)
.
Theorem
12.
If
div
(
n;
10
k
)
1
,
then
(1)
If
n
40
,
then
g
(
k
;
n
)
=
6
g
(
k
;
div
(
n
+
1
;
10)
1)
+
5
(10)
(2)
If
n
>
3
,
then
g
(
k
;
n
)
3
2
g
(
k
;
n
1)
+
1
2
(11)
Pr
oof
.
The
theorem
will
be
pro
v
ed
b
y
mathematical
induction.
F
or
m
ula
(2)
can
be
v
er
ified
directly
if
3
<
n
40
.
Induction
h
ypothesis:
F
or
all
40
m
<
n
,
w
e
ha
v
e
g
(
k
;
m
)
=
6
g
(
k
;
div
(
m
+
1
;
10)
1)
+
5;
F
or
all
3
<
m
<
n
,
w
e
ha
v
e
g
(
k
;
m
)
3
2
g
(
k
;
m
1)
+
1
2
:
(1)
W
e
first
pro
v
e
F
or
m
ula
(1)
b
y
induction.
(1.1)
The
case
of
mo
d(
n;
10)
=
9
.
In
this
case
,
div
(
n
+
1
;
10)
1
=
div
(
n;
10)
.
Let
g
(
k
;
div
(
n;
10))
=
j
R
(
k
;
m
)
j
.
Then,
f
or
an
y
40
i
n
,
w
e
ha
v
e
j
R
(
k
;
i
)
j
6
j
R
(
k
1
;
div
(
i;
10)
j
+
5
:
It
f
ollo
ws
from
div
(
n;
10
k
)
1
and
i
<
n
that
div
(div(
i;
10)
;
10
k
1
)
=
d
iv
(
i;
10
k
)
div
(
n;
10
k
)
1
:
F
rom
Lemma
11,
w
e
kno
w
R
(
k
1
;
div
(
i;
10)
=
R
(
k
;
div
(
i;
10)
.
Theref
ore
,
j
R
(
k
;
i
)
j
6
j
R
(
k
1
;
div
(
i;
10)
j
+
5
6
g
(
k
;
div
(
n;
10))
+
5
On
the
other
hand,
from
m
div
(
n;
10)
,
w
e
kno
w
10
m
+
9
n
.
Thus
,
j
R
(
k
;
10
m
+
9)
j
=
6
j
R
(
k
1
;
m
)
j
+
5
=
6
g
(
k
;
div
(
n;
10))
+
5
Theref
ore
,
g
(
k
;
n
)
=
6
g
(
k
;
div
(
n;
10))
+
5
=
6
g
(
k
;
div
(
n
+
1
;
10)
1)
+
5
.
A
Complete
Combinator
ial
Solution
f
or
a
Coins
Change
Puzzle
and
Its
Computer
...
(D
.
Zhu)
Evaluation Warning : The document was created with Spire.PDF for Python.
6344
ISSN:
2302-4046
(1.2)
The
case
of
mo
d(
n;
10)
6
=
9
.
In
this
case
,
div
(
n
+
1
;
10)
1
=
div
(
n;
10)
1
.
F
or
an
y
10div
(
n;
10)
i
n
,
w
e
ha
v
e
j
R
(
k
;
i
)
j
4
j
R
(
k
1
;
div
(
i;
10)
j
+
3
=
4
j
R
(
k
;
div
(
i;
10)
j
+
3
4
g
(
k
;
div
(
n;
10)
+
3
:
It
f
ollo
ws
from
n
40
that
div
(
n;
10)
4
>
3
.
By
induction
h
ypothesis
,
g
(
k
;
div
(
n;
10))
3
2
g
(
k
;
div
(
n;
10)
1)
+
1
2
.
It
f
ollo
ws
that
j
R
(
k
;
i
)
j
4
3
2
g
(
k
;
div
(
n;
10)
1)
+
1
2
+
3
=
6
g
(
k
;
div
(
n;
10)
1)
+
5
:
F
or
an
y
1
i
<
10div
(
n;
10)
,
let
g
(
k
;
div
(
n;
10)
1)
=
j
R
(
k
;
m
)
j
,
then
j
R
(
k
;
i
)
j
6
j
R
(
k
;
div
(
i;
10))
j
+
5
:
In
this
time
,
w
e
ha
v
e
div
(
i;
10)
div
(
n;
10)
1
.
Thus
,
j
R
(
k
;
i
)
j
6
g
(
k
;
div
(
n;
10)
1)
+
5
.
On
the
other
hand,
fr
om
m
div
(
n;
10)
1
,
w
e
kno
w
10
m
+
9
n
.
Thus
,
j
R
(
k
;
10
m
+
9)
j
=
6
j
R
(
k
1
;
m
)
j
+
5
=
6
g
(
k
;
div
(
n;
10))
+
5
.
g
(
k
;
n
)
=
6
g
(
k
;
div
(
n;
10)
1)
+
5
=
6
g
(
k
;
div
(
n
+
1
;
10)
1)
+
5
.
Theref
ore
,
F
or
m
ula
(1)
is
held
b
y
induction.
(2)
W
e
no
w
pro
v
e
F
or
m
ula
(2)
b
y
induction.
F
rom
F
or
m
ula
(1),
w
e
kno
w
g
(
k
;
n
)
=
6
g
(
k
;
div
(
n
+
1
;
10)
1)
+
5
;
g
(
k
;
n
1)
=
6
g
(
k
;
div
(
n;
10)
1)
+
5
.
(2.1)
The
case
of
mo
d(
n;
10)
=
9
.
In
this
case
,
div
(
n
+
1
;
10)
1
=
div
(
n;
10)
.
By
induction
h
ypothesis
,
g
(
k
;
div
(
n;
10))
3
2
g
(
k
;
div
(
n;
10)
1)
+
1
2
.
It
f
ollo
ws
that
g
(
k
;
n
)
6
3
2
g
(
k
;
div
(
n;
10)
1)
+
1
2
+
5
=
9
g
(
k
;
div
(
n;
10)
1)
+
8
=
3
2
(6
g
(
k
;
div
(
n;
10)
1)
+
5)
+
1
2
=
3
2
g
(
k
;
n
1)
+
1
2
(2.2)
The
case
of
mo
d(
n;
10)
6
=
9
.
In
this
case
,
div
(
n
+
1
;
10)
1
=
div
(
n;
10)
1
.
F
rom
F
or
m
ula
(1),
w
e
kno
w
g
(
k
;
n
)
=
g
(
k
;
n
1)
3
2
g
(
k
;
n
1)
+
1
2
.
Theref
ore
,
F
or
m
ula
(2
)
is
held
b
y
induction.
Theorem
13.
Suppose
m;
n
2
I
+
;
n
=
P
m
i
=0
a
i
10
i
;
and
p
=
8
<
:
n
1
m
=
0
div
(
n
+
1
;
10
m
1
)
1
1
m
k
;
a
k
1
100
k
<
m
or
k
=
m;
a
k
>
1
.
Then,
h
(
k
;
n
)
=
8
>
>
>
>
>
>
>
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
:
1
0
p
1
3
2
p
7
9
p
=
8
10
m
1
9
p
16
18
10
m
1
1
17
p
18
2
10
m
1
19
p
36
38
10
m
1
1
37
p
38
4
10
m
1
39
p
98
n
p
=
99
div
(
n
+
1
;
10
k
)
10
k
1
p
=
100
(12)
g
(
k
;
n
)
=
8
>
>
>
>
>
>
>
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
:
1
0
p
1
3
2
p
7
5
p
=
8
6
m
1
9
p
16
8
6
m
1
1
17
p
18
2
6
m
1
19
p
36
16
6
m
1
1
37
p
38
4
6
m
1
39
p
98
6
m
1
p
=
99
div
(
n
+
1
;
10
k
)
6
k
1
p
=
100
(13)
Pr
oof
.
If
m
1
,
w
e
can
compute
the
v
alues
of
h
(
k
;
n
)
and
g
(
k
;
n
)
directly
as
sho
wn
in
T
ab
le
2.
(1)
The
case
of
m
=
0
corresponds
to
1
n
9
,
0
p
8
,
and
can
thus
be
computed
directly
from
T
ab
le
2.
If
1
m
k
and
a
k
1
,
then
from
Theorem
12,
w
e
kno
w
that
if
n
40
,
TELK
OMNIKA
V
ol.
12,
No
.
8,
A
ugust
2014
:
6338
6345
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
2302-4046
6345
T
ab
le
2.
v
alues
of
h
(
k
;
n
)
and
g
(
k
;
n
)
n
1-2
3-8
9-16
17-18
19-36
37-38
39-98
99
h
(
k
;
n
)
1
3
9
17
19
37
39
99
g
(
k
;
n
)
1
3
5
7
11
15
23
35
then
h
(
k
;
n
)
=
10
h
(
k
;
div
(
n
+
1
;
10)
1)
+
9;
g
(
k
;
n
)
=
6
g
(
k
;
div
(
n
+
1
;
10)
1)
+
5
:
In
this
w
a
y
,
w
e
can
compute
recursiv
ely
that
h
(
k
;
n
)
=
10
m
1
h
(
k
;
div
(
n
+
1
;
10
m
1
)
1)
+
9
m
2
X
i
=0
10
i
=
10
m
1
h
(
k
;
div
(
n
+
1
;
10
m
1
)
1)
+
10
m
1
1
=
10
m
1
h
(
k
;
div
(
n
+
1
;
10
m
1
)
1)
+
1
1;
g
(
k
;
n
)
=
6
m
1
g
(
k
;
div
(
n
+
1
;
10
m
1
)
1)
+
5
m
2
X
i
=0
6
i
=
6
m
1
g
(
k
;
div
(
n
+
1
;
10
m
1
)
1)
+
6
m
1
1
=
6
m
1
g
(
k
;
div
(
n
+
1
;
10
m
1
)
1)
+
1
1
:
No
w
,
w
e
ha
v
e
9
p
=
div
(
n
+
1
;
10
m
1
)
1
99
.
The
v
alues
of
h
(
k
;
n
)
and
g
(
k
;
n
)
can
no
w
be
computed
directly
from
T
ab
le
2.
By
substituting
the
v
alues
into
the
abo
v
e
f
or
m
ula,
w
e
get
the
results
.
(2)
If
m
<
k
or
m
=
k
and
a
k
>
1
,
then
from
the
recursiv
e
f
or
m
ula
of
h
(
k
;
n
)
and
g
(
k
;
n
)
,
w
e
kno
w
h
(
k
;
n
)
=
10
k
h
(0
;
div
(
n
+
1
;
10
k
)
1)
+
9
P
k
1
i
=0
10
i
,
h
(0
;
div
(
n
+
1
;
10
k
)
1)
=
di
v
(
n
+
1
;
10
k
)
1
.
It
f
ollo
ws
from
Lemma
10
that
h
(0
;
div
(
n
+
1
;
10
k
)
1)
=
div
(
n
+
1
;
10
k
)
1
,
g
(0
;
div
(
n
+
1
;
10
k
)
1)
=
div
(
n
+
1
;
10
k
)
1
.
By
substituting
them
into
the
abo
v
e
f
or
m
ula
w
e
get
h
(
k
;
n
)
=
10
k
(div
(
n
+
1
;
10
k
)
1)
+
9
k
1
X
i
=0
10
i
=
10
k
(div
(
n
+
1
;
10
k
)
1)
+
10
k
1
=
div
(
n
+
1
;
10
k
)
10
k
1;
g
(
k
;
n
)
=
6
k
(div
(
n
+
1
;
10
k
)
1)
+
5
k
1
X
i
=0
6
i
=
6
k
(div
(
n
+
1
;
10
k
)
1)
+
6
k
1
=
d
iv
(
n
+
1
;
10
k
)6
k
1
The
proof
is
completed.
Ac
kno
wledgment
This
w
or
k
w
as
suppor
ted
b
y
the
Natur
al
Science
F
oundation
of
Fujian
under
Gr
ant
No
.2013J01247,
Fujian
Pro
vincial
K
e
y
Labor
ator
y
of
Data-Intensiv
e
Computing
and
Fujian
Univ
ersity
Labor
ator
y
of
Intelligent
Computing
and
Inf
or
mation
Processing.
Ref
erences
[1]
R.
Bird.
P
ear
ls
of
Functional
Algor
ithm
Design.
Cambr
idge
Univ
ersity
Press
.
2010:258-274.
[2]
Xiaodong
W
ang.
Gener
ation
and
En
umer
ation
of
Implication
Sets
.
Adv
ances
in
Inf
or
mation
T
echnology
and
Education
Comm
unications
in
Computer
and
Inf
or
mation
Science
.
2011;
201:
87-92.
[3]
TH
Cor
men
,
CE
Leiserson,
RL
Riv
est.
Introduction
to
Algor
ithms
.
MIT
Press
,
Cambr
idge
,
MA,
2001:
429-433.
[4]
DL
Kreher
and
D
Stinson.
Combinator
ial
Algor
ithms:
Gener
ation,
En
umer
ation
and
Search,
CRC
Press
,
1998:
125-133.
[5]
D
Zhu,
X
W
ang.
A
Pr
actical
Algor
ithm
and
Data
Str
uctures
f
or
Range
Select
ion
Quer
ies
.
TELK
OMNIKA
Indonesian
Jour
nal
of
Electr
ical
Engineer
ing
.
2014;
12(3):
2406-2413.
A
Complete
Combinator
ial
Solution
f
or
a
Coins
Change
Puzzle
and
Its
Computer
...
(D
.
Zhu)
Evaluation Warning : The document was created with Spire.PDF for Python.