先來個只計算分割數的版本
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 閱讀(1494)
評論(0) 編輯 收藏 引用 所屬分類:
面試小算法