作者:陈太汉
一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值
比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
算法 原理的思想是将大问题转换成小问题。
就{3,2,4,3,6}的操作步骤:
第一步:想将数组递减排序得{6,4,3,3,2},求出数组中所有数的和m=18,第一个最大的数b=6, m/b=3余数为0,
当除数为1,余数为0时终止。当余数不为0时,转到第三步。当余数为0时将数组划分为{6},{4,3,3,2}两个。把{4,3,3,2}看成一个新的数组。
第二步:先用{4,3,3,2}中的最大数与b=6比较,即4<b,所以再将4与最右边的数即2相加与b比较,
结果相等,则将这两个数从该数组中除去生成新的数组,转到第一步,现在的结果是{6},{4,2},{3,3},把{3,3}看成一个新的数组继续重复第二步。
第三步,将数组中最大的数与最小的数取出构成一个新数组Z,剩余的构成一个数组,然后,
判断m/Z中数字之和看是否余数为0,若为0,把b替换为Z中数字之和转第二步,若不为0,
继续从剩余的数字中取出最小值加入到Z中,再判断m/Z中数字之和看是否余数为0,直到为0,转第二步为止。
最后得到的结果是{6},{4,2},{3,3} 这时可以计算出m为3,也可以在程序中作记载。
在第二步工程过,若出现两个数相加大于上一次的b,则将程序转到第三步。
上面是别人的分析,我想很多人跟我一样看了相当晕,但看了我的代码你应该不至于晕。有时候用文字表达还真是繁琐,但是代码却简单明了。
大家都说算法和数据结构对程序员来说很重要,还说比的就是这个,我看未必,我觉得更重要的还是分析问题的能力,你要是能把问题分析得相当透彻,我相信你也能写出相应的代码。
很多问题看起来复杂,但是等你分析清楚了,还是相当简单的。这道算法面试题的代码是相当简单啊!
源代码
#include
<
iostream
>
using
namespace
std ;
class
FindMaxM
{
public
:
int
FindM(
int
arr[],
int
length)
{
if
(NULL
==
arr
||
length
<=
0
)
{
return
-
1
;
}
//
倒序排序
InsertSort(arr,length);
int
sum
=
0
;
//
数组的和
for
(
int
i
=
0
;i
<
length;i
++
)
{
sum
+=
arr[i];
}
int
end
=
length
-
1
;
int
subSum
=
arr[
0
];
while
(sum
/
subSum
>=
2
)
{
if
(sum
%
subSum
==
0
)
{
return
sum
/
subSum;
}
subSum
+=
arr[end
--
];
}
return
-
1
;
}
private
:
//
用数组实现插入排序
inline
void
InsertSort(
int
arr[],
int
length)
{
int
cur;
for
(
int
i
=
1
;i
<
length;i
++
)
{
cur
=
arr[i];
for
(
int
j
=
0
;j
<
i;j
++
)
{
if
(arr[j]
<
cur)
{
for
(
int
k
=
i;k
>
j;k
--
)
{
arr[k]
=
arr[k
-
1
];
}
arr[j]
=
cur;
break
;
}
}
}
}
//
用指针实现选择排序
inline
void
SelectSort(
int
*
ptArr,
int
n)
{
for
(
int
i
=
0
; i
<
n
-
1
; i
++
)
{
int
k
=
i;
for
(
int
j
=
i
+
1
; j
<
n; j
++
)
{
if
(
*
(ptArr
+
j)
>*
(ptArr
+
k))
{
k
=
j;
}
}
if
(k
!=
i)
{
int
tmp
=
*
(ptArr
+
k);
*
(ptArr
+
k)
=
*
(ptArr
+
i);
*
(ptArr
+
i)
=
tmp;
}
}
}
};
排序用了两种方实现。插入排序和选择排序就不多说了,大家都懂。
我要说的是用数组实现排序和用指针实现排序,个人认为指针排序速度要比数组排序快(没有测试),
指针直接访问元素的地址,而数组要先计算元素的偏移,才能得出元素的地址