Androidアルゴリズム05-減算法
3837 ワード
アルゴリズム05-減算法
一、紹介
減治法は,一歩一歩一定の問題規模(−1,−k,−n/2など)を縮小し,最後に最小の小さな問題となる.
減治法の一般的な応用:スタックソート、深さ優先検索.
二、スタックの順序付け
1、基本思想
ヒープソート:完全なツリーの昇順ソートに基づいています.
ヒープのソート手順:線形構造(配列など)を完全二叉木として並べ替える:配列中の1つの要素Aの下にkとマークされている場合、下に(k-1)/2とマークされている要素はAの親ノードに相当し、下に2 k+1とマークされている要素はAの左サブノードに相当し、下に2 k+2とマークされている要素はAの右サブノードに相当する. n個の要素を並べ替え、最小値を配列の先頭に置く:まずノードkの左サブツリーの最小値をkの左サブノードに置き、次にノードkの右サブツリーの最小値をkの右サブノードに置き、次にノードkとその左右サブノードの最小値が配列の最小値である.ここでは再帰が必要です. 配列の最小値を取り出し、配列Mを入れる. はn=n-1とし、n=0になるまでステップ2、3を繰り返し、ソートが完了する:Mは拍好順の配列である.
≪適用|Apply|emdw≫:データ・ソースが無秩序またはチェーン構造の場合、二分検索を行います.一般的にソートには使用されず、スペースの複雑さが高すぎます.
2、コード実現
三、深さ優先検索
1、基本思想
深さ優先検索は深さ優先で検索する思想で、一つの方向に沿ってまっすぐ行って、道がなくなったら戻って、それから方向を変えて探して、ゴールを見つけることを知っています.
操作手順:は2次元配列で迷路をシミュレートし、配列の値:0は通じる、1は通じない、2は通る、3は壁を表す.始点と終点を指定します. 始点から左下右上の順に検索し、次の点まで行ける場合はその値を2とマークし、この点を新しい始点として左下右上の順に検索します.次のポイントに移動できない場合は、その値を1としてマークし、前のポイントに戻り、残りの方向から検索します. 手順2を繰り返し、ゴールまで歩いたことを知っています.
応用:迷宮で道を探す
2、コード実現
最後に
コードアドレス:https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/arithmetic/ReduceConquer.java
データ構造とアルゴリズムのテーマ:https://www.jianshu.com/nb/25128590
好きならいいね、ありがとう!
一、紹介
減治法は,一歩一歩一定の問題規模(−1,−k,−n/2など)を縮小し,最後に最小の小さな問題となる.
減治法の一般的な応用:スタックソート、深さ優先検索.
二、スタックの順序付け
1、基本思想
ヒープソート:完全なツリーの昇順ソートに基づいています.
ヒープのソート手順:
≪適用|Apply|emdw≫:データ・ソースが無秩序またはチェーン構造の場合、二分検索を行います.一般的にソートには使用されず、スペースの複雑さが高すぎます.
2、コード実現
public static > E[] heapSort(E[] arr) {
if (Tool.isEmpty(arr)) {
return null;
}
// new , Arrays.copyOf()
E[] result = Arrays.copyOf(arr, arr.length);
// : -1
for (int i = 0; i < arr.length; i++) {
//
int n = arr.length - i;
// : ,
heapSort(arr, n, 0);
//
result[i] = arr[0];
//
arr[0] = arr[n - 1];
}
return result;
}
/**
* :
* @param arr:
* @param n: ,
* @param k:
*/
public static > void heapSort(E[] arr, int n, int k) {
//
int left = 2 * k + 1;
//
int right = 2 * k + 2;
if (left >= n) {
return;
}
//
heapSort(arr, n, left);
//
heapSort(arr, n, right);
E data = arr[k];
E l = arr[left];
// , MAX
E r = right < n ? arr[right] : null;
// ,
if (data.compareTo(l) <= 0 && (r == null || data.compareTo(r) <= 0)) {
return;
}
// ,
if (r == null || l.compareTo(r) < 0) {
arr[left] = data;
arr[k] = l;
// ,
} else {
arr[right] = data;
arr[k] = r;
}
}
三、深さ優先検索
1、基本思想
深さ優先検索は深さ優先で検索する思想で、一つの方向に沿ってまっすぐ行って、道がなくなったら戻って、それから方向を変えて探して、ゴールを見つけることを知っています.
操作手順:
応用:迷宮で道を探す
2、コード実現
/**
* @param arr 。 0 ,1 ,2 ,3 。
* @param startX
* @param startY
* @param endX
* @param endY
*/
public static boolean dfsSort(int[][] arr, int startX, int startY, int endX, int endY) {
if (startX < 0 || startY < 0 || endX < 0 || endY < 0) {
return false;
}
//
if (arr[endX][endY] == 2) {
return true;
}
// ,
if (arr[startX][startY] == 0) {
//
arr[startX][startY] = 2;
//
if (dfsSort(arr, startX - 1, startY, endX, endY)) {
return true;
//
} else if (dfsSort(arr, startX, startY - 1, endX, endY)) {
return true;
//
} else if (dfsSort(arr, startX + 1, startY, endX, endY)) {
return true;
//
} else if (dfsSort(arr, startX, startY + 1, endX, endY)) {
return true;
// , 1,
} else {
arr[startX][startY] = 1;
return false;
}
}
return false;
}
最後に
コードアドレス:https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/arithmetic/ReduceConquer.java
データ構造とアルゴリズムのテーマ:https://www.jianshu.com/nb/25128590
好きならいいね、ありがとう!