习题2.8
假设需要生成前N个自然数的一个随机置换。例如，{4,1,2,5,2} 和 {3,1,4,2,5} 就是合法的置换，但 {5,4,1,2,1} 却不是，因为数1出现了两次而数 3 缺没有。这个程序常常用于模拟一些算法。我们假设存在一个随机数生成器 randInt(i, j) ，它以相同的概率生成 i 和 j 之间的一个整数。
下面是三个算法：
1.如下填入a[0]到a[N-1]的数组a;为了填入a[i],生成随机数直到它不同于已经生成的a[0],a[1], ... ,a[i-1]时,再将其填入a[i]。
2.同算法1,但是要保存一个附加的数组,称之为Used（用过的）数组。当一个随机ran最初被放入数组a的时候,置Used[ran]=1。这就是说，当用一个随机数填入 a[i] 时，可以用一步来测试是否该随机数已经被使用，而不是像第一个算法那样（可能）进行 i 步测试。
3.填写该数组使得 A[i] = i + 1。然后
for(i = 1; i < N; i++)
swap(&A[i], &A[randInt(0, i)]);
/**
* @description: 假设需要生成前N个整数的一个随机置换。例如，{4，3，1，5，2}和{3，1，4，2，5}就是合法的置换，但{5，4，1，2，1}却不是，因为数1出现两次而数3却没有。
* @author:
* @date: 2018/7/24
*/
public class RandomReplace {
/**
* 随机数生成器randInt(i,j)，它以相同的概率生成i和j之间的一个整数。
*
* @param i
* @param j
* @return
*/
private int randInt(int i,int j){
Random rand = new Random();
// 生成区间[i,j]的随机数
return rand.nextInt(j-i + 1) + i;
}
/**
* 方法一：填入从a[0]到a[n-1]的数组a，为了填入a[i]，生成随机数直到它不同于已经生成的a[0],a[1],...,a[i-1]时，再将其填入a[i]。
*
* 时间复杂度为O(N^2)
* @param a
*/
public int[] randFun1(int[] a){
for(int i = 0; i < a.length; i++){
a[i] = randInt(1,a.length);
for(int j = 0; j < i; j++){
if(a[i] == a[j]){
a[i] = randInt(1,a.length);
j = -1;
}
}
}
return a;
}
/**
* 方法二：同方法一，但是要保存一个附加的数组，称为used数组。当一个随机数ran最初被放入数组a的时候，置used[ran] = true。
* 这就是说，当用一个随机数填入a[i]时，可以用一步来测试是否该随机数已经被使用。
*
* 时间复杂度为O(N)
* @param a
* @return
*/
public int[] randFun2(int[] a){
int[] used = new int[a.length + 1];
for(int i = 0; i < a.length; i++){
a[i] = randInt(1,a.length);
while(used[a[i]] != 0){
a[i] = randInt(1,a.length);
}
used[a[i]] = 1;
}
return a;
}
/**
* 方法三：填写该数组使得a[i]=i+1。然后for(i=1; i<n; i++)
* swapReferences(a[i], a[randInt(0,i)]);
* @param a
* @return
*/
public int[] randFun3(int[] a){
for(int i = 0; i < a.length; i++){
a[i] = i + 1;
}
//随机交换位置
for(int i = 1; i < a.length; i++){
swapReferences(a,i,randInt(0,i));
}
return a;
}
private void swapReferences(int[] arr,int a,int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* 打印数组
*
* @param arr
*/
private static void printArr(int[] arr){
for(int i =0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
RandomReplace rand = new RandomReplace();
System.out.println(rand.randInt(0,2));
int[] a = new int[5];
// rand.randFun1(a);
// rand.randFun2(a);
rand.randFun3(a);
printArr(a);
}
}
习题2.16
基于下列各式编写另外的gcd算法（其中a>b）
gcd(a，b)=2gcd(a/2，b/2)若a和b均为偶数。
gcd(a，b)=gcd(a/2，b)若a为偶数， b为奇数。
gcd(a，b)=gcd(a，b/2)若a为奇数， b为偶数。
gcd(a，b)=gcd((a+b)/2，(a-b)/2)若a和b均为奇数。
/**
* 最大公约数（欧几里得算法）
* 假设M ≥ N，如果N < M，则循环的第一次迭代将它们互换。
*
* @param m
* @param n
* @return
*/
public long gcd(long m,long n){
while(n != 0){
long rem = m % n;
m = n;
n = rem;
}
return m;
}
public long gcd2(long m,long n){
// a和b均为偶数
if((m&1) == 0 && (n&1) == 0){
return 2 * gcd(m/2,n/2);
}
//a为偶数， b为奇数。
else if((m&1) == 0 && (n&1) != 0){
return gcd(m/2,n);
}
//a为奇数， b为偶数
else if((m&1) != 0 && (n&1) == 0){
return gcd(m,n/2);
}
//a和b均为奇数
else {
return gcd((m+n)/2,(m-n)/2);
}
}
/**
* 最小公倍数（两个数乘积除以最大公约数）
*
* @param m
* @param n
* @return
*/
public long lcm(long m,long n){
long gcd = gcd(m, n);
return m * n / gcd;
}
习题2.17
给出有效的算法
a.求最小子序列和。
b.求最小的正子序列和。
c.求最大子序列乘积。
1.求最小子序列和。
/**
* 最小子序列和
*
* @param arr
* @return
*/
public static int getMinSeq(int[] arr) {
int minSum = 0;
if(arr != null && arr.length > 0){
minSum = arr[0];
int thisSum = 0;
for (int i = 0; i < arr.length; i++) {
thisSum += arr[i];
if (thisSum < minSum) {
minSum = thisSum;
} else if (thisSum > 0) {
thisSum = 0;
}
}
}
return minSum;
}
2.求最小的正子序列和。
/**
* 最小正子序列和：1.连续子序列，2.序列和为正且最小
* 思路：
* (1)先求出数组的前缀数组之和，例如：2,-3,-3,7,5=>前缀数组和为2,-1,-4,3,8（它们的索引0 1 2 3 4）
* (2)对前缀数组进行排序得到：-4,-1,2,3,8
* (3)则最小值一定是在：-4,1,2,3,8（结果一定在当前项减去前面一项，同时满足索引大于前一项的索引）
*
* @param arr
* @return
*/
public static int getMinPositiveSeq(int[] arr) {
int minPosSum = 0;
int len = arr.length;
int[] newArr = new int[len];
for(int i = 0; i < len; i++){
minPosSum += arr[i];
newArr[i] = minPosSum;
}
// 快速排序
quickSort(newArr,0,len - 1);
int min = newArr[0] >= 0 ? newArr[0] : newArr[len - 1];
for(int i = 1; i < len; i++){
if(newArr[i] > newArr[i - 1]){
int temp = newArr[i] - newArr[i - 1];
if(temp < min){
min = temp;
}
}
}
return min;
}
/**
* 快速排序
* 1.从数组中选择一个数作为基准数。
* 2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
* 3.再对左右区间重复第2步，直到各区间只有一个数
*
* @param arr
* @param low
* @param high
*/
private static void quickSort(int[] arr,int low,int high){
if(low < high){
int index = partition(arr,low,high);
quickSort(arr,low,index - 1);
quickSort(arr,index + 1,high);
}
}
/**
* 进行第一轮排序获取分割点
*
* @param arr
* @param low
* @param high
* @return
*/
private static int partition(int[] arr,int low,int high){
int pivot = arr[high];
int small = low - 1;
for(int i = low; i < high; i++){
//将比pivot值小的数放到左边
if(arr[i] <= pivot){
small++;
swap(arr,i,small);
}
}
swap(arr,high,small + 1);
return small + 1;
}
3. 求最大子序列乘积。
/**
* 最大子序列乘积
* 方法一：动态规划，每一步只需要记住其前一步的整数最大值和负数的最小值。
* @param arr
* @return
*/
public static int getMaxSeqMulti(int[] arr){
if(arr == null || arr.length < 0){
return 0;
}
int maxMulti = arr[0];
int posMax = arr[0];
int negMin = arr[0];
for(int i = 1; i < arr.length; i++){
int tempPosMax = posMax;
int tempNegMax = negMin;
posMax = Math.max(arr[i],Math.max(tempPosMax * arr[i],tempNegMax * arr[i]));
negMin = Math.min(arr[i],Math.min(tempPosMax * arr[i],tempNegMax * arr[i]));
if(Math.max(posMax,negMin) > maxMulti){
maxMulti = Math.max(posMax,negMin);
}
}
return maxMulti;
}
/**
* 最大子序列乘积
* 方法二：
* @param arr
* @return
*/
public static int getMaxSeqMulti2(int[] arr){
int max = Integer.MIN_VALUE;
for(int i = 0; i < arr.length; i++){
int temp = arr[i];
for(int j = i + 1; j < arr.length; j++){
max = Math.max(max,temp);
temp *= arr[j];
}
max = Math.max(max,temp);
}
return max;
}
习题2.20
编写一个程序来确定正整数N是否是素数。
思路：
如果一个数不是素数，那它除了1和本身一定还有其他的约数。我们假设这个数是num，num=m*n 一定可以分解为两个整数相乘。
设一个命题 ,num可以分解为两个数相乘并且这两个数都大于num的平方根
m>sqrt(num)
n>sqrt(num)
根据数学知识可以知道m*n>num 这与命题相反，所以命题是假的。
所以合数一定至少有一个不大于sqrt(num)约数，只要找到这个数就可以了。
/**
* 方法二：判断是否是素数，运行时间为O(√N)
*
* @param N
* @return
*/
public boolean isPrime(int N){
if(N == 1){
return false;
}
for(int i = 2; i <= Math.sqrt(N); i++){
if(N % i == 0){
return false;
}
}
return true;
}
问题拓展：获取2~N之间的所有素数。
/**
* 方法一：获取2~N之间的所有素数
* 用ArrayList保存
*
* @param N
*/
public void getPrime1(int N){
List<Integer> list = new ArrayList<>();
for(int i = 2; i <= N; i++){
if(isPrime(i)){
list.add(i);
}
}
for(Integer prime : list){
System.out.print(prime + " ");
}
}
/**
* 方法二：双层for循环得出素数
*
* @param N
*/
public void getPrime2(int N){
for(int i = 2; i <= N; i++){
int j;
//测试2至i的数字是否能被i整除，如不能就自加
for(j = 2; j <= i; j++){
if(i % j == 0){
break;
}
}
//当有被整除的数字时，判断它是不是自身，若是，则说明是素数
if(j == i)
System.out.print(j + " ");
}
}
厄拉多塞筛选法
筛选法，是指从小到大筛去一个已知素数的所有倍数。
例如：根据2，我们筛选去4，6，8jiang，....，98，100等数；然后根据3，我们可以筛选9，15，...99等数（注意此时6、12等数早就被筛去了）；
由于4被筛去了，下一个用于筛选的素数是5，以此类推，最后剩余的就是100以内的素数。
public void getPrime3(int N){
//默认isComposite为false
boolean[] isComposite = new boolean[N + 1];
for(int m = 2; m <= Math.sqrt(N); m++){
//筛选 m 的倍数，将isComposite置为true
if(!isComposite[m]){
for(int k = m * m; k <= N; k += m){
isComposite[k] = true;
}
}
}
//剩下所有isComposite为false的数即为素数
for(int m = 2; m <= N; m++){
if(!isComposite[m]){
System.out.print(m + " ");
}
}
}
