найти кратчайшее покрытие
1. Ищется столбец с минимальным числом единиц. Если таковых несколько, то выбирается любой (для определенности, допустим, самый левый).
2. Среди строк, покрывающих этот столбец, ищется строка с максимальным числом единиц и заносится в покрытие (следовательно, удаляется из матрицы); если же таких строк несколько, то выбирается любая из них (для определенности, допустим, самая верхняя). 3. Удаляются все столбцы, которые покрывает полученная строка. Дали такое задание. Может кто подскажет. :cray: |
булевая матрица, метод Закревского
:write: без комментариев...
<!DOCTYPE html>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
</head>
<body>
<script>
function s(a) {
return a.reduce(function(a, b) {
return a + b
}, 0)
}
function c(a) {
return a[0].reduce(function(e, b, g) {
e[g] = [];
for (b = 0; b < a.length; b++) e[g].push(a[b][g]);
return e
}, {})
}
function fn(a, e) {
return Object.keys(a).sort(function(b, g) {
return e ? s(a[g]) - s(a[b]) : s(a[b]) - s(a[g])
})[0]
}
function r(a, e) {
return e.reduce(function(b, e, h) {
e && (b[h] = a[h]);
return b
}, {})
}
function ff(a, e) {
return a.map(function(a) {
return a.filter(function(a, b) {
return 0 == e[b]
})
})
}
function print(a, e, b) {
a = a.reduce(function(a, b) {
return a + "<div>" + JSON.stringify(b) + "</div>"
}, e);
document.body.insertAdjacentHTML("beforeEnd", a + b)
}
var m = [
[1, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0],
[0, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 0]
],
temp = "абвгдежзи".split("");
temp.length = m.length;
for (var res = []; 2 < m.length;) {
print(temp, "", "");
print(m, "", "");
var d = c(m),
n = fn(d),
t = d[n],
f = r(m, t),
k = fn(f, !0);
res.push(temp.splice(k, 1)[0]);
var v = m.splice(k, 1)[0];
m = ff(m, v)
}
print([res.sort()], "<b>", "</b>");
</script>
</body>
</html>
|
А если я сам выбираю размерность матрицы и заполняю, как мне для моей матрицы применить данный метод
<section class="lib" id="oms_blok1">
<h2 style="text-align: center;">матрицы</h2>
<div class="calc" id="frtabl">
Размер матрицы:
<select onchange="oms_mhwA(this.value)">
<option value="2">2×2</option>
<option value="3" selected="selected">3×3</option>
<option value="4">4×4</option>
<option value="5">5×5</option>
<option value="6">6×6</option>
<option value="7">7×7</option>
</select>
<p>Введите значения Матрицы A:</p>
<div class="matrix"></div>
<script>
function oms_mhwA(el) {
var matrix = document.querySelector('.matrix');
matrix.innerHTML = '';
for (var i = 0; i < el; i++) {
for (var k = 0; k < el; k++) {
matrix.innerHTML += '<input type="text" value="0">'
}
matrix.innerHTML += '<br>'
}
}
</script>
<p style="text-align: center;">
<b>A</b>
<input onclick="oms_zakr();" type="button" value="=" title="Найти минимальное покрытие матрицы">
</p>
</div>
|
riddele_for_you,
function foo(xxx) { .... .... var m = xxx, .... } foo(ваша_матрица) |
Я правильно понял?
function oms_zakra(el) {
function s(a) {
return a.reduce(function (a, b) {
return a + b
}, 0)
}
function c(a) {
return a[0].reduce(function (e, b, g) {
e[g] = [];
for (b = 0; b < a.length; b++) e[g].push(a[b][g]);
return e
}, {})
}
function fn(a, e) {
return Object.keys(a).sort(function (b, g) {
return e ? s(a[g]) - s(a[b]) : s(a[b]) - s(a[g])
})[0]
}
function r(a, e) {
return e.reduce(function (b, e, h) {
e && (b[h] = a[h]);
return b
}, {})
}
function ff(a, e) {
return a.map(function (a) {
return a.filter(function (a, b) {
return 0 == e[b]
})
})
}
function print(a, e, b) {
a = a.reduce(function (a, b) {
return a + "<div>" + JSON.stringify(b) + "</div>"
}, e);
document.body.insertAdjacentHTML("beforeEnd", a + b)
}
var m = el,
temp = "абвгдежзи".split("");
temp.length = m.length;
for (var res = []; 2 < m.length;) {
print(temp, "", "");
print(m, "", "");
var d = c(m),
n = fn(d),
t = d[n],
f = r(m, t),
k = fn(f, !0);
res.push(temp.splice(k, 1)[0]);
var v = m.splice(k, 1)[0];
m = ff(m, v)
}
print([res.sort()], "<b>", "</b>");
}
|
riddele_for_you,
да |
Не знаю почему, но программы не работает.
<!DOCTYPE html>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
</head>
<body>
<section class="lib" id="oms_blok1">
<h2 style="text-align: center;">Решение методом Закревского</h2>
<div class="calc" id="frtabl">
Размер матрицы:
<select onchange="oms_mhwA(this.value)">
<option value="2" selected="selected">2×2</option>
<option value="3">3×3</option>
<option value="4">4×4</option>
<option value="5">5×5</option>
<option value="6">6×6</option>
<option value="7">7×7</option>
</select>
<p>Выберете размерность матрицы, после введите значения Матрицы A:</p>
<div class="matrix"></div>
<script>
function oms_mhwA(el) {
var matrix = document.querySelector('.matrix');
matrix.innerHTML = '';
for (var i = 0; i < el; i++) {
for (var k = 0; k < el; k++) {
matrix.innerHTML += '<input type="text" value="0">'
}
matrix.innerHTML += '<br>'
}
}
</script>
<p style="text-align: center;">
<b>A</b>
<input onclick="oms_zakr();" type="button" value="=" title="Найти минимальное покрытие матрицы">
</p>
<script>
function oms_zakr(el) {
function sot(aot) {
return aot.reduce(function (aot, bot) {
return aot + bot
}, 0)
}
function cot(aot) {
return aot[0].reduce(function (eot, bot, got) {
eot[got] = [];
for (bot = 0; bot < aot.length; bot++) eot[got].push(aot[bot][got]);
return eot
}, {})
}
function fnot(aot, eot) {
return Object.keys(aot).sort(function (bot, got) {
return eot ? sot(aot[got]) - sot(aot[bot]) : sot(aot[bot]) - sot(aot[got])
})[0]
}
function rot(aot, eot) {
return eot.reduce(function (bot, eot, hot) {
eot && (bot[hot] = aot[hot]);
return bot
}, {})
}
function ffot(aot, eot) {
return aot.map(function (aot) {
return aot.filter(function (aot, bot) {
return 0 == eot[bot]
})
})
}
function print(aot, eot, bot) {
aot = aot.reduce(function (aot, bot) {
return aot + "<div>" + JSON.stringify(bot) + "</div>"
}, eot);
document.body.insertAdjacentHTML("beforeEnd", aot + bot)
}
var mot = el,
temp = "абвгдежзи".split("");
temp.length = mot.length;
for (var res = []; 2 < mot.length;) {
print(temp, "", "");
print(mot, "", "");
var dot = cot(mot),
not = fnot(dot),
tot = dot[not],
fot = rot(mot, tot),
kot = fnot(fot, !0);
res.push(temp.splice(kot, 1)[0]);
var vot = mot.splice(kot, 1)[0];
mot = ffot(mot, vot)
}
print([res.sort()], "<b>", "</b>");
}
</script>
</div>
</section>
</body>
</html>
|
где создание массива матрицы?
|
Цитата:
var a = new Array() var a = [] |
riddele_for_you,
нужен цикл по всем input |
Цитата:
<script>
function oms_mhwA(el) {
var matrix = document.querySelector('.matrix');
matrix.innerHTML = '';
for (var i = 0; i < el; i++) {
for (var k = 0; k < el; k++) {
matrix.innerHTML += '<input type="text" value="0">'
}
matrix.innerHTML += '<br>'
}
}
</script>
|
riddele_for_you,
нужна функция которая сделает массив из значений полей ввода(input ) |
Цитата:
|
riddele_for_you,
<!DOCTYPE html>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
<style type="text/css">
</style>
</head>
<body>
<div class="matrix" oninput="createMatrix(5)"></div>
<div class="show"></div>
<script>
function print(a, e, b) {
a = a.reduce(function(a, b) {
return a + "<div>" + JSON.stringify(b) + "</div>";
}, e);
document.querySelector(".show").innerHTML = a + b;
}
function oms_mhwA(el) {
var matrix = document.querySelector(".matrix");
matrix.innerHTML = "";
for (var i = 0; i < el; i++) {
for (var k = 0; k < el; k++) {
matrix.innerHTML += '<input type="text" value="1">';
}
matrix.innerHTML += "<br>";
}
}
function createMatrix(el) {
var matrix = [], inp = document.querySelectorAll(".matrix input");
for (var i = 0; i < inp.length; i++) {
if (!(i % el)) {
matrix.push([]);
}
matrix[i / el | 0].push(+inp[i].value);
}
print(matrix, "", "");
return matrix;
}
oms_mhwA(5);
createMatrix(5);
// oms_zakra(createMatrix(5))
</script>
</body>
</html>
|
Цитата:
<h2 style="text-align: center;">Решение методом Закревского</h2> <div class="calc" id="frtabl"> Размер матрицы: <select onchange="oms_mhwA(this.value)"> <option value="2" selected="selected">2×2</option> <option value="3">3×3</option> <option value="4">4×4</option> <option value="5">5×5</option> <option value="6">6×6</option> <option value="7">7×7</option> </select> <p>Выберете размерность матрицы, после введите значения Матрицы A:</p> |
riddele_for_you,
<!DOCTYPE html>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
<style type="text/css">
.matrix input{
width: 20px;
margin: 5px;
}
</style>
</head>
<body>
<h2 style="text-align: center;">Решение методом Закревского</h2>
<div class="calc" id="frtabl">
Размер матрицы:
<select onchange="oms_mhwA(this.value)">
<option value="2" selected="selected">2×2</option>
<option value="3">3×3</option>
<option value="4">4×4</option>
<option value="5">5×5</option>
<option value="6">6×6</option>
<option value="7">7×7</option>
</select>
<p>Выберете размерность матрицы, после введите значения Матрицы A:</p>
</div>
<div class="matrix" oninput="createMatrix()"></div>
<div class="show"></div>
<button onclick="oms_zakra(createMatrix())">calc</button>
<script>
var num = 2;
function print(a, e, b) {
a = a.reduce(function(a, b) {
return a + "<div>" + JSON.stringify(b) + "</div>";
}, e);
document.querySelector(".show").innerHTML = a + b;
}
function oms_mhwA(el) {
num = el;
var matrix = document.querySelector(".matrix");
matrix.innerHTML = "";
for (var i = 0; i < el; i++) {
for (var k = 0; k < el; k++) {
matrix.innerHTML += '<input type="text" value="1">';
}
matrix.innerHTML += "<br>";
}
createMatrix();
}
function createMatrix() {
var el = num;
var matrix = [], inp = document.querySelectorAll(".matrix input");
for (var i = 0; i < inp.length; i++) {
if (!(i % el)) {
matrix.push([]);
}
matrix[i / el | 0].push(+inp[i].value);
}
print(matrix, "", "");
return matrix;
}
oms_mhwA(num)
function oms_zakra(m)
{
alert(JSON.stringify(m));
}
</script>
</body>
</html>
|
Цитата:
|
Цитата:
function oms_zakra(m)
{
alert(JSON.stringify(m));
{
function s(a) {
return a.reduce(function (a, b) {
return a + b
}, 0)
}
function c(a) {
return a[0].reduce(function (e, b, g) {
e[g] = [];
for (b = 0; b < a.length; b++) e[g].push(a[b][g]);
return e
}, {})
}
function fn(a, e) {
return Object.keys(a).sort(function (b, g) {
return e ? s(a[g]) - s(a[b]) : s(a[b]) - s(a[g])
})[0]
}
function r(a, e) {
return e.reduce(function (b, e, h) {
e && (b[h] = a[h]);
return b
}, {})
}
function ff(a, e) {
return a.map(function (a) {
return a.filter(function (a, b) {
return 0 == e[b]
})
})
}
function print(a, e, b) {
a = a.reduce(function (a, b) {
return a + "<div>" + JSON.stringify(b) + "</div>"
}, e);
document.body.insertAdjacentHTML("beforeEnd", a + b)
}
var mat = m,
temp = "абвгдежзи".split("");
temp.length = m.length;
for (var res = []; 2 < m.length;) {
print(temp, "", "");
print(m, "", "");
var d = c(m),
n = fn(d),
t = d[n],
f = r(m, t),
k = fn(f, !0);
res.push(temp.splice(k, 1)[0]);
var v = m.splice(k, 1)[0];
m = ff(m, v)
}
print([res.sort()], "<b>", "</b>");
}
}
|
riddele_for_you,
строки 2,3 и 63 лишние |
riddele_for_you,
<!DOCTYPE html>
<html>
<head>
<title>Untitled</title>
<meta charset="utf-8">
<style type="text/css">
.matrix input{
width: 20px;
margin: 5px;
}
</style>
</head>
<body>
<h2 style="text-align: center;">Решение методом Закревского</h2>
<div class="calc" id="frtabl">
Размер матрицы:
<select onchange="oms_mhwA(this.value)">
<option value="2" selected="selected">2×2</option>
<option value="3">3×3</option>
<option value="4">4×4</option>
<option value="5">5×5</option>
<option value="6">6×6</option>
<option value="7">7×7</option>
</select>
<p>Выберете размерность матрицы, после введите значения Матрицы A:</p>
</div>
<div class="matrix" oninput="createMatrix()"></div>
<div class="show"></div>
<button onclick="oms_zakra(createMatrix())">calc</button>
<script>
var num = 2;
function print(a, e, b) {
a = a.reduce(function(a, b) {
return a + "<div>" + JSON.stringify(b) + "</div>";
}, e);
document.querySelector(".show").innerHTML = a + b;
}
function oms_mhwA(el) {
num = el;
var matrix = document.querySelector(".matrix");
matrix.innerHTML = "";
for (var i = 0; i < el; i++) {
for (var k = 0; k < el; k++) {
matrix.innerHTML += '<input type="text" value="1">';
}
matrix.innerHTML += "<br>";
}
createMatrix();
}
function createMatrix() {
var el = num;
var matrix = [], inp = document.querySelectorAll(".matrix input");
for (var i = 0; i < inp.length; i++) {
if (!(i % el)) {
matrix.push([]);
}
matrix[i / el | 0].push(+inp[i].value);
}
print(matrix, "", "");
return matrix;
}
oms_mhwA(num)
function oms_zakra(m)
{
function s(a) {
return a.reduce(function (a, b) {
return a + b
}, 0)
}
function c(a) {
return a[0].reduce(function (e, b, g) {
e[g] = [];
for (b = 0; b < a.length; b++) e[g].push(a[b][g]);
return e
}, {})
}
function fn(a, e) {
return Object.keys(a).sort(function (b, g) {
return e ? s(a[g]) - s(a[b]) : s(a[b]) - s(a[g])
})[0]
}
function r(a, e) {
return e.reduce(function (b, e, h) {
e && (b[h] = a[h]);
return b
}, {})
}
function ff(a, e) {
return a.map(function (a) {
return a.filter(function (a, b) {
return 0 == e[b]
})
})
}
function print(a, e, b) {
a = a.reduce(function (a, b) {
return a + "<div>" + JSON.stringify(b) + "</div>"
}, e);
document.body.insertAdjacentHTML("beforeEnd", a + b)
}
var mat = m,
temp = "абвгдежзи".split("");
temp.length = m.length;
for (var res = []; m.length && m[0].length;) {
print(temp, "", "");
print(m, "", "");
var d = c(m),
n = fn(d),
t = d[n],
f = r(m, t),
k = fn(f, !0);
res.push(temp.splice(k, 1)[0]);
var v = m.splice(k, 1)[0];
m = ff(m, v)
}
print([res.sort()], "<b>", "</b>");
}
</script>
</body>
</html>
|
riddele_for_you,
на всякий случай, каждая строка или столбец должна содержать хотя бы одну единицу. |
пост №20 исправлено |
| Часовой пояс GMT +3, время: 04:23. |