Форум

alexan0308 · #1 (**permalink**) 18.03.2012, 12:42

Помогите с алгоритмом перебора... Дано s клеточек, m подряд слева закрашены, n подряд справа закрашены, не соприкасаются. Нужно перебрать все возможные варианты.

Вот иллюстрация m=3 n=4 s=10... первый набор всегда должен лежать левее второго.
1110111100
1110011110
1110001111
0111011110
0111001111
0011101111

или более наглядно
***-****--
***--****-
***---****
-***-****-
-***--****
--***-****

В перспективе надо для любого числа наборов клеток... Хотя бы для двух сделать ))

рони · #2 (**permalink**) 18.03.2012, 18:25

alexan0308,
Вариант)))

<!DOCTYPE html>
<html>
<head>
  <title></title>
</head>

<body>
<script type="text/javascript">
var m=3, n=4, s=10;
k = s-(m+n);
for (var arr = [0, 0, 0]; k;) {
    for (var i = k; 0 < i;) arr[2] = --i, arr[1] = k - i, document.write(Array(arr[0] + 1).join("-") + Array(m + 1).join("*") + Array(arr[1] + 1).join("-") + Array(n + 1).join("*") + Array(arr[2] + 1).join("-") + "<br />");
    k--;
    arr[0]++
};
</script>
</body>
</html>

alexan0308 · #3 (**permalink**) 18.03.2012, 19:14

Впечатляюще... правда, не очень понятно... Может пояснишь?
Так то я решил проблему но твое решение интереснее. Я сделал так

for (i1=0; i1<N-p-q+1; i1++) 
	  {
	    for (i2=i1+p+1; i2<N-q+1; i2++) 	    
 		{
		    for (k=0; k<N; k++) {variant[k]=0;}
			for (k=i1; k<i1+p; k++) {variant[k]=1;}
			for (k=i2; k<i2+q; k++) {variant[k]=1;}
                      // что то делаю с выборкой
                       }
               }

тут p,q,N вместо p, q, s.
Можешь очистить алгоритм от вывода, оставить только массив variant?

рони · #4 (**permalink**) 18.03.2012, 19:53

alexan0308,
Длина разделителей равна остатку от общей длины за минусом двух длин занятых участков, стоять эти разделители могут только в трёх местах, осталось распределить))) в распределении есть закономерность согласно этой закономерности и составлен скрипт.
например при к = 4 последний разделитель равен 3,2,1,0 - 2,1,0 - 1,0 - 0 у других разделителей своя закономерность.

alexan0308 · #5 (**permalink**) 18.03.2012, 20:25

понятно... ладно уж я простыми циклами обойдусь =)

nikita.mmf · #6 (**permalink**) 18.03.2012, 22:28

S=10;
M=3;
N=4;
var out = [], i = 1, k, l, j, res;
for ( ; i <= S - M - N; i++ ) {
	k = 0;
	l = (S - M - N) - i;
	for ( ; l > -1; l--, k++ ) {
		res = [];
		for ( j = k; j--; ) res.push('-');
		for ( j = M; j--; ) res.push('*');
		for ( j = i; j--; ) res.push('-')
		for ( j = N; j--; ) res.push('*');
		for ( j = l; j--; ) res.push('-')
		out.push( res.join('') );
	}
}
alert( out.join("\n") )

Форум

Справочник

Discord чат

Курсы javascript