数据结构与算法JavaScript描述练习------第14章高级算法
1. 写一个程序，使用暴力技巧来寻找最长公共子串。
function lcsBruteForce(word1, word2) {
var maxLength = 0;
var longestSubstring = "";
for (var i = 0; i < word1.length; i++) {
for (var j = i + 1; j <= word1.length; j++) {
var substring = word1.substring(i, j);
if (word2.includes(substring) && substring.length > maxLength) {
maxLength = substring.length;
longestSubstring = substring;
}
}
}
return longestSubstring;
}
var word1 = "ABABC";
var word2 = "BABCA";
console.log(lcsBruteForce(word1, word2));2. 写一个程序，允许用户改变背包问题的约束条件，以便于观察条件的变化对结果的影 响。比如，你可以改变背包的容量、物品的价值，或物品的重量。每次最好只改一个约 束条件。
function knapsack(capacity, size, value, n) {
if (n == 0 || capacity == 0) {
return 0;
}
if (size[n - 1] > capacity) {
return knapsack(capacity, size, value, n - 1);
} else {
return max(value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1));
}
}
function dKnapsack(capacity, size, value, n) {
var K = [];
for (var i = 0; i <= capacity + 1; i++) {
K[i] = [];
}
for (var i = 0; i <= n; i++) {
for (var w = 0; w <= capacity; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (size[i - 1] <= w) {
K[i][w] = max(value[i - 1] + K[i-1][w-size[i-1]], K[i-1][w]);
} else {
K[i][w] = K[i - 1][w];
}
console.log(K[i][w] + " ");
}
}
return K[n][capacity];
}3. 使用贪心算法找零钱，不过这次不允许使用 10 美分，假设要找的零钱一共是 30 美分， 请尝试找到一个解。这个解是最优解吗？
function makeChange(origAmt, coins) {
var remainAmt = 0;
if (origAmt % .25 < origAmt) {
coins[3] = parseInt(origAmt / .25);
remainAmt = origAmt % .25;
origAmt = remainAmt;
}
/* if (origAmt % .1 < origAmt) {
coins[2] = parseInt(origAmt / .1);
remainAmt = origAmt % .1;
origAmt = remainAmt;
}
*/ if (origAmt % .05 < origAmt) {
coins[1] = parseInt(origAmt / .05);
remainAmt = origAmt % .05;
origAmt = remainAmt;
}
coins[0] = parseInt(origAmt / .01);
}
function showChange(coins) {
if (coins[3] > 0) {
console.log("25 美分的数量 - " + coins[3] + " - " + coins[3] * .25);
}
/* if (coins[2] > 0) {
console.log("10 美分的数量 - " + coins[2] + " - " + coins[2] * .10);
}
*/ if (coins[1] > 0) {
console.log("5 美分的数量 - " + coins[1] + " - " + coins[1] * .05);
}
if (coins[0] > 0) {
console.log("1 美分的数量 - " + coins[0] + " - " + coins[0] * .01);
}
}
var origAmt = .3;
var coins = [];
makeChange(origAmt, coins);
showChange(coins);本章实验代码：
function recurFib(n) {
if (n < 2) {
return n;
} else {
return recurFib(n-1) + recurFib(n-2);
}
}
function dynFib(n) {
var val = [];
for (var i = 0; i <= n; ++i) {
val[i] = 0;
}
if (n == 1 || n == 2) {
return 1;
} else {
val[1] = 1;
val[2] = 2;
for (var i = 3; i <= n; ++i) {
val[i] = val[i-1] + val[i-2];
}
return val[n-1];
}
}
function iterFib(n) {
var last = 1;
var nextLast = 1;
var result = 1;
for (var i = 2; i < n; ++i) {
result = last + nextLast;
nextLast = last;
last = result;
}
return result;
}
function lcs(word1, word2) {
var max = 0;
var index = 0;
var lcsarr = new Array(word1.length + 1);
for (var i = 0; i < word1.length + 1; ++i) {
lcsarr[i] = new Array(word2.length + 1);
for (var j = 0; j < word2.length + 1; ++j) {
lcsarr[i][j] = 0;
}
}
for (var i = 1; i <= word1.length; ++i) {
for (var j = 1; j <= word2.length; ++j) {
if (word1[i - 1] == word2[j - 1]) {
lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
if (max < lcsarr[i][j]) {
max = lcsarr[i][j];
index = i;
}
}else {
lcsarr[i][j] = 0;
}
}
}
var str = "";
if (max == 0) {
return "";
} else {
for (var i = index - max; i <= max; ++i) {
str += word1[i];
}
return str;
}
}
function lcsBruteForce(word1, word2) {
var maxLength = 0;
var longestSubstring = "";
for (var i = 0; i < word1.length; i++) {
for (var j = i + 1; j <= word1.length; j++) {
var substring = word1.substring(i, j);
if (word2.includes(substring) && substring.length > maxLength) {
maxLength = substring.length;
longestSubstring = substring;
}
}
}
return longestSubstring;
}
function max(a, b) {
return (a > b) ? a : b;
}
function knapsack(capacity, size, value, n) {
if (n == 0 || capacity == 0) {
return 0;
}
if (size[n - 1] > capacity) {
return knapsack(capacity, size, value, n - 1);
} else {
return max(value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1));
}
}
function dKnapsack(capacity, size, value, n) {
var K = [];
for (var i = 0; i <= capacity + 1; i++) {
K[i] = [];
}
for (var i = 0; i <= n; i++) {
for (var w = 0; w <= capacity; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (size[i - 1] <= w) {
K[i][w] = max(value[i - 1] + K[i-1][w-size[i-1]], K[i-1][w]);
} else {
K[i][w] = K[i - 1][w];
}
console.log(K[i][w] + " ");
}
}
return K[n][capacity];
}
function ksack(values, weights, capacity) {
var load = 0;
var i = 0;
var w = 0;
while (load < capacity && i < 4) {
if (weights[i] <= (capacity-load)) {
w += values[i];
load += weights[i];
} else {
var r = (capacity-load)/weights[i];
w += r * values[i];
load += capacity-load;
}
++i;
}
return w;
}
/*
var items = ["A", "B", "C", "D"];
var values = [50, 140, 60, 60];
var weights = [5, 20, 10, 12];
var capacity = 30;
console.log(ksack(values, weights, capacity));
*/
function makeChange(origAmt, coins) {
var remainAmt = 0;
if (origAmt % .25 < origAmt) {
coins[3] = parseInt(origAmt / .25);
remainAmt = origAmt % .25;
origAmt = remainAmt;
}
if (origAmt % .1 < origAmt) {
coins[2] = parseInt(origAmt / .1);
remainAmt = origAmt % .1;
origAmt = remainAmt;
}
if (origAmt % .05 < origAmt) {
coins[1] = parseInt(origAmt / .05);
remainAmt = origAmt % .05;
origAmt = remainAmt;
}
coins[0] = parseInt(origAmt / .01);
}
function showChange(coins) {
if (coins[3] > 0) {
console.log("25 美分的数量 - " + coins[3] + " - " + coins[3] * .25);
}
if (coins[2] > 0) {
console.log("10 美分的数量 - " + coins[2] + " - " + coins[2] * .10);
}
if (coins[1] > 0) {
console.log("5 美分的数量 - " + coins[1] + " - " + coins[1] * .05);
}
if (coins[0] > 0) {
console.log("1 美分的数量 - " + coins[0] + " - " + coins[0] * .01);
}
}
var origAmt = .63;
var coins = [];
makeChange(origAmt, coins);
showChange(coins);