函数习题（8)：分解一个整数的所有素数因子

将下列复合函数''分解”为基本初等函数:

将n个正整数存放于一个一维数组A[]中，试设计一个函数，将所有的奇数移动并存放于数组的前半部分，将所有的偶数移动并存放于数组的后半部分。要求尽可能少用临时存储单元并使计算时间达到O(n)。

试编写一个求解Josephus问题的函数。用整数序列1，2，3.….n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n=9，s=l，m=5，以及n=9，s=1，m=0，或者n=9，s=1，m=10作为输人数据，检你的程序的正确性和健壮性。

试证明下列函数是初等函数

(1)(f(i)是初等函数)

(2)(f(i)是初等函数)

(3)中不同质因子的个数"(相同的只算一个)

(4)中质因子的个数”(相同的重复计算)

(5)的最大公约数”

(6)的最小公倍数”

有n个整数，使前面各数顺序向后移m个位置，最后m个数变成最前面m个数，见图8.1。写一函数实现以上功能，在主函数中输入n个整数和输出调整后的n个数。

假定把关键码key散列到有m个表项(从0到m-1编址)的散列表中。对于下面的每一个函数Hash(key)(key为整数)，这些函数能够当作散列函数吗(即对于插入和查找，散列程序能正常工作吗)?如果能够，它是一个好的散列函数吗?请说明理由。设函数random(m)返回一个0到m-1之间的随机整数(包括0与m-1在内)。

(1)Hash(key)==key/m;

(2)Hash(key)=1;

(3)IIash(key)==(key+random(m))%rn;

(4)Hash(key)=key%p(m);其中p(m)是不大于m的最大素数。

两个正整数的最大公约数(Greatest Common Divisor，GCD) 是能够整除这两个整数的最大整数，请分别采用如下3种方法编写计算最大公约数的函数Ged()，在主函数中调用该函数计算并输出从键盘任意输入的两整数的最大公约数。

(1)穷举法 ，由于a阳的最大公约数不可能比a和b中的较小者还大，否则一定不能整除它，因此，先找到，a和b中中的较小者t，然后从t开始逐次减I尝试每种可能.即检验t到I之间的所有整数，第一个满足公约数条件的t就是和b的最大公约数。

(2)欧几里得算法，也称辗转相除法、对正整数a和b，连续进行求余运算，直到余数为0为止.此时非0的除数就是最大公约数。设r=a mod b表示a除以上的余数，若r≠0将b作为新的a，r作为新的b，即Ged(a，b)=Ged(b，r)，重复a mod b运算，直到r=0为止，此时b为所求的最大公约数。例如，50和15的最大公约数的求解过程可表示为：Ged(50，15)=Ged(15，5)=Ged(5，0) =5。

(3)递归方法。对正整数a和b，当a>b时，若a中含有与b相同的公约数，则a中去掉b后剩余的部分a-b中也应含有与b相同的公约数，对a-b和b计算公约数就相当于对a和b计算公约数。反复使用最大公约数的如下3条性质，直到a和b相等为止，这时，a或b就是它们的最大公约数。

性质1如果a>b， 则a和b与a-b和b的最大公约数相同， 即Ged(a，b)=Ged(a-b，b)

性质2如果b>a， 则a和b与a和b-a的最大公约数相同， 即Ced(a，b)=Ged(a，b-a)

性质3如果a=b， 则a和b的最大公约数与a值和b值相同， 即Ged(a，b)=a=b