先来个只计算分割数的版本
int
Compute(
int
number,
int
maximum)
{
if
(number
==
1
||
maximum
==
1
)
return
1
;
else
if
(number
<
maximum)
return
Compute(number, number);
else
if
(number
==
maximum)
return
1
+
Compute(number, maximum
-
1
);
else
return
Compute(number, maximum
-
1
)
+
Compute(number
-
maximum, maximum);
}
int
IntPartionNo(
int
n)
{
return
Compute(n, n);
}
打印所有分割版本
int
IntegerPartition(
int
n)
{
int
*
partition
=
new
int
[n]();
int
*
repeat
=
new
int
[n]();
partition[
1
]
=
n;
repeat[
1
]
=
1
;
int
count
=
1
;
int
part
=
1
;
int
last, smaller, remainder;
printf(
"
%3d
"
, partition[
1
]);
do
{
last
=
(partition[part]
==
1
)
?
(repeat[part
--
]
+
1
) :
1
;
smaller
=
partition[part]
-
1
;
if
(repeat[part]
!=
1
)
--
repeat[part
++
];
partition[part]
=
smaller;
repeat[part]
=
1
+
last
/
smaller;
if
((remainder
=
last
%
smaller)
!=
0
)
{
partition[
++
part]
=
remainder;
repeat[part]
=
1
;
}
++
count;
printf(
"
\n
"
);
for
(
int
i
=
1
; i
<=
part;
++
i)
for
(
int
j
=
1
; j
<=
repeat[i];
++
j)
printf(
"
%3d
"
, partition[i]);
}
while
(repeat[part]
!=
n);
if
(partition)
{
delete [] partition;
partition
=
0
;
}
if
(repeat)
{
delete [] repeat;
repeat
=
0
;
}
return
count;
}
没有时间把解释写出来，自己根据变量名结合网上原理凑合看吧，真是对不起观众啊
posted on 2006-12-06 17:59
Charles 阅读(1451)
评论(0) 编辑 收藏 引用 所属分类:
面试小算法