/**
* 文件名：Test8.java
* 时间：2014年11月1日上午9:07:12
* 作者：修维康
*/
package chapter2;
import java.util.Arrays;
import java.util.Random;
/**
* 类名：Test8 说明：生成前N个整数的一个随机置换
*/
public class Test8 {
/**
* 方法名：randInt 说明：生成i-j的随机整数
*/
public static int randInt(int i, int j) {
j++;
Random rand = new Random();
return rand.nextInt(j - i) + i;
}
/**
* 方法名：isExist 说明：x是否存在在数组a中
*/
public static boolean isExist(int[] a, int x) {
for (int i = 0; i < a.length; i++) {
if (x == a[i])
return true;
}
return false;
}
/**
* 方法名：fill1 说明：将数组a填满 算法1
*/
public static void fill1(int[] a, int i, int j) {
int w = 0;
while (w < a.length) {
int num = randInt(i, j);
if (!isExist(a, num)) {
a[w++] = num;
}
}
}
/**
* 方法名：fill2 说明：方法2 借助一个数组
*/
public static void fill2(int[] a, int i, int j) {
boolean[] used = new boolean[j + 1];
int w = 0;
while (w < a.length) {
int num = randInt(i, j);
if (!used[num]) {
a[w] = num;
used[num] = true;
w++;
}
}
}
/**
* 方法名：fill3 说明：利用交换实现 只能实现1-n的
*/
public static int[] fill3(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
for (int i = 1; i < n; i++) {
int rand = randInt(0, i);
int temp = a[i];
a[i] = a[rand];
a[rand] = temp;
}
return a;
}
/**
* 方法名：main 说明：测试
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[10];
fill1(a,1,10);
System.out.println(Arrays.toString(a));
fill2(a,101,110);
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(fill3(5)));
}
}
package chapter2;public class Test16 {/** * 方法名：gcd 说明：求最大公因数 */private static int gcd(int i, int j) {while (j != 0) {int temp = i % j;i = j;j = temp;}return i;}public static int gcd2(int i, int j) {if ((i & 1) == 0 && (j & 1) == 0)return 2 * gcd(i / 2, j / 2);else if ((i & 1) == 0 && (j & 1) == 1)return gcd(i / 2, j);else if ((i & 1) == 1 && (j & 1) == 0)return gcd(i, j / 2);elsereturn gcd((i + j) / 2, (i - j) / 2);}public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(gcd2(50, 15));}}
package chapter2;import java.util.Arrays;public class Test17 {/** * 方法名：minSubSum 说明：求最小子序列和，联机算法，返回位置和最小子序列的和 */public static int[] minSubSum(int[] a) {int[] result = new int[3];// result[0] 开始位置 result[1]结束位置 result[2]为和int min = Integer.MAX_VALUE;int sum = 0;int flag = 0;for (int i = 0; i < a.length; i++) {sum += a[i];if (sum < min) {min = sum;if (flag++ == 0)result[0] = i;result[1] = i;}if (sum > 0) {sum = 0;flag = 0;}}result[2] = min;return result;}/** * 方法名：maxSubMul * 说明：最大子序列乘积 */public static int maxSubMul(int[] a){int[] max = new int[a.length];int[] min = new int[a.length];int maxValue = a[0];max[0] = a[0];min[0] = a[0];for(int i = 1;i < a.length;i++){max[i] = max(max[i-1]*a[i],a[i],min[i-1]*a[i]);//max[i]是以a[i]为结尾的最大子序列乘积min[i] = min(min[i-1]*a[i],a[i],max[i-1]*a[i]);if(max[i] > maxValue)maxValue = max[i];}return maxValue;}public static int max(int x, int y, int z) {return (x > y ? x : y) > z ? (x > y ? x : y) : z;}public static int min(int x, int y, int z) {return (x < y ? x : y) < z ? (x < y ? x : y) : z;}public static void main(String[] args) {// TODO Auto-generated method stubint[] a = new int[] { 2, -5, 3, -4, -6 };System.out.println(Arrays.toString(minSubSum(a)));System.out.println(maxSubMul(a));}}
/**
* 文件名：Test20.java
* 时间：2014年11月2日下午2:53:09
* 作者：修维康
*/
package chapter2;
/**
* 类名：Test20 说明：写一个程序判断是否是素数O(根号N）的算法，只需要判到根号N
*
*/
public class Test20And21 {
public static boolean isPrim(int n) {
if (n == 1)
return true;
else {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
}
return true;
}
/**
* 方法名：printAllPrim 说明：计算小于N的所有素数 厄拉多塞筛法
* 制作 2-N的表，从2开始删除2*i 3*i 当i大于根号N时，算法结束， 留下来的就是素数表
*/
public static void printAllPrim(int n) {
System.out.println("1 ");
int[] a = new int[n + 1];
for (int i = 2; i <= n; i++)
a[i] = 1;
for (int i = 2; i * i <= n; i++) {
if (a[i] != 0){
for (int j = i + i; j <= n; j += i)
a[j] = 0;
}
}
for (int i = 2; i <= n; i++)
if (a[i] == 1)
System.out.println(i + " ");
}
/**
* 方法名：main 说明：测试
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
// for(int i = 1;i <= 100;i++)
// System.out.println(i+" :"+isPrim(i));
printAllPrim(16);
}
}
/**
* 文件名：Test23.java
* 时间：2014年11月2日下午4:13:02
* 作者：修维康
*/
package chapter2;
/**
* 类名：Test23 说明：快速求幂，递归和非递归形式
*/
public class Test23 {
/**
* 方法名：pow 说明：递归形式 复杂度O(logN)
*/
public static long pow(long x, int n) {
if (n == 0)
return 1;
if (n == 1)
return x;
if ((n & 1) == 0)
return pow(x * x, n / 2);
else
return pow(x * x, n / 2) * x;
}
/**
* 方法名：pow2
* 说明：非递归
*/
public static long pow2(long x,int n){
long pw = 1;
while (n > 0) {
if ((n % 2) == 1)
pw *= x;
x *= x;
n /= 2;
}
return pw;
}
/**
* 方法名：main 说明：测试
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(pow2(2, 10));
}
}
/**
* 文件名：Test27.java
* 时间：2014年11月2日下午7:26:08
* 作者：修维康
*/
package chapter2;
import java.util.Arrays;
/**
* 类名：Test27 说明：判断X是否在N*N矩阵中 矩阵从左往右递增，从左往下递增
* 找到右上角的位置，X比右上角大，矩阵去掉上层，比右上角小则去掉最右一层。
* 时间复杂度：O(N)
*/
public class Test27 {
// m n为右上角的位置
private static int[] isExist(int[][] a, int m, int n, int x) {
if (m < 0 || n < 0 || m == a.length || n == a[0].length)
return null;
else {
int top_right = a[m][n];
if (x < top_right)
return isExist(a, m, n - 1, x);
if (x > top_right)
returnisExist(a, m + 1, n, x);
return new int[]{m,n};
}
}
public static int[] isExist(int[][] a, int x) {
return isExist(a, 0, a[0].length - 1, x);
}
/**
* 方法名：main 说明：测试
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] a = new int[][] { { 1, 5,7,9 }, { 4,6,10,15 },
{ 8,11,12,19 }, { 14,16,18,21 } };
System.out.println(Arrays.toString(isExist(a, 21)));
}
}
/**
* 文件名：Test28.java
* 时间：2014年11月2日下午8:25:42
* 作者：修维康
*/
package chapter2;
/**
* 类名：Test28
* 说明：使用正数的数组a设计有效的算法以确定
*
*/
public class Test28 {
/**
* 方法名：maxAdd
* 说明：找到数组里a[i]+a[j]的最大值
*
*/
public static int maxAdd(int[] a){
int max = Integer.MIN_VALUE;
int flag = 0;
for(int i = 0;i < a.length;i++){
if(a[i] > max){
max = a[i];
flag = i;
}
}
a[flag] = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
for(int i = 0;i < a.length;i++)
if(a[i] > max2)
max2 = a[i];
return max + max2;
}
/**
* 方法名：maxSub
* 说明：a[j]-a[i]的最大值 且j >= i
* minLeft记录左端最小的
* a[j]/a[i]最大也如此
*/
public static int maxSub(int[] a){
int i = 0;
int minLeft = a[0];
int maxDiff = a[1] - a[0];
for(i = 2; i < a.length; i++)
{
if(a[i - 1] < minLeft)
{
minLeft = a[i - 1];
}
if(a[i] - minLeft > maxDiff)
{
maxDiff = a[i] - minLeft;
}
}
return maxDiff;
}
/**
* 方法名：main
* 说明：测试
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[]{13,2,1,4,5,6,7,7};
System.out.println(maxSub(a));
}
}
package chapter2;
public class Test32 {
/**
* 方法名：binarySearch
* 说明：实现只有二路比较的二分查找 将判断提到前面，如果与a[mid]相等直接返回，否则执行下去
* 其实执行下面程序时就默认a[mid]！= x
*/
public static int binarySearch(int[] a, int x) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == x)
return mid;
if (a[mid] < x)
low = mid + 1;
else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[] { 1, 2, 3, 4, 5, 6 };
System.out.println(binarySearch(a, 6));
}
}
以上均为我自己所写，不会的也参考了别人的，如果有bug欢迎指出。