В ящике 4 x 4 лежат груши (16 шт.)Какие 6 груш необходимо убрать, так, чтобы в каждой строке и каждом столбце было чётное число груш.
внимание! комментарии содержат ответ.
10 мар. 2010 г.
Задачка: Груши
В ящике 4 x 4 лежат груши (16 шт.)Какие 6 груш необходимо убрать, так, чтобы в каждой строке и каждом столбце было чётное число груш.
внимание! комментарии содержат ответ.
Подписаться на:
Комментарии к сообщению (Atom)
9 комментариев:
"Какие 6 груш необходимо ..."
1111
1100
1010
1001
:-use_module(library(clpfd)).
solve(GG) :-
GG = [
[A,B,C,D],
[E,F,G,H],
[I,J,K,L],
[M,N,O,P]
],
append(GG, Vars),
Vars ins 0..1,
sum(Vars,#=,10),
( A + B + C + D) mod 2 #= 0,
( E + F + G + H) mod 2 #= 0,
( I + J + K + L) mod 2 #= 0,
( M + N + O + P) mod 2 #= 0,
( A + E + I + M) mod 2 #= 0,
( B + F + J + N) mod 2 #= 0,
( C + G + K + O) mod 2 #= 0,
( D + H + L + P) mod 2 #= 0,
label(Vars).
solve :- forall(solve(GG),format('~n~w~n~w~n~w~n~w~n-------',GG)).
[0, 0, 1, 1]
[0, 1, 0, 1]
[1, 0, 0, 1]
[1, 1, 1, 1]
-------
[0, 0, 1, 1]
[0, 1, 0, 1]
[1, 1, 1, 1]
[1, 0, 0, 1]
-------
[0, 0, 1, 1]
[0, 1, 1, 0]
[1, 0, 1, 0]
[1, 1, 1, 1]
-------
[0, 0, 1, 1]
[0, 1, 1, 0]
[1, 1, 1, 1]
[1, 0, 1, 0]
-------
[0, 0, 1, 1]
[1, 0, 0, 1]
[0, 1, 0, 1]
[1, 1, 1, 1]
-------
[0, 0, 1, 1]
[1, 0, 0, 1]
[1, 1, 1, 1]
[0, 1, 0, 1]
-------
[0, 0, 1, 1]
[1, 0, 1, 0]
[0, 1, 1, 0]
[1, 1, 1, 1]
-------
[0, 0, 1, 1]
[1, 0, 1, 0]
[1, 1, 1, 1]
[0, 1, 1, 0]
-------
[0, 0, 1, 1]
[1, 1, 1, 1]
[0, 1, 0, 1]
[1, 0, 0, 1]
... (и т.д.)
@Andrey:
спасибо за корректировку
@xonix
bravo! физтех :)
@xonix: А что это за язык? Красиво выражает задачу.
У меня тут топорный брут-форс на С, но задачу решает, хотя и не столь изящно.
#include <stdio.h>
#include <stdlib.h>
int b[16];
int f() {
int a;
if (b[0] + b[1] + b[2] + b[3] + b[4] + b[5] + b[6] + b[7] +
b[8] + b[9] + b[10] + b[11] + b[12] + b[13] + b[14] + b[15] != 10)
return 0;
a = b[0] + b[1] + b[2] + b[3]; if (a & 1) return 0;
a = b[4] + b[5] + b[6] + b[7]; if (a & 1) return 0;
a = b[8] + b[9] + b[10] + b[11]; if (a & 1) return 0;
a = b[12] + b[13] + b[14] + b[15]; if (a & 1) return 0;
a = b[0] + b[4] + b[8] + b[12]; if (a & 1) return 0;
a = b[1] + b[5] + b[9] + b[13]; if (a & 1) return 0;
a = b[2] + b[6] + b[10] + b[14]; if (a & 1) return 0;
a = b[3] + b[7] + b[11] + b[15]; if (a & 1) return 0;
return 1;
}
int main() {
int i;
int c = 0;
for (i = 0; i < 16; ++i) b[1];
for (i = 0; i < (1 << 16); ++i) {
int j;
for (j = 0; j < 16; ++j) b[j] = (i & (1 << j)) ? 1 : 0;
if (f()) {
int j;
printf("#%d:\n", ++c);
for (j = 0; j < 16; ++j) {
printf("%d ", b[j]);
if ((j & 0x03) == 0x03) printf("\n");
}
printf("\n");
}
}
return 0;
}
@Александр
судя по блогу xonix'а это пролог - но, могу и ошибаться
@Владимир Долженко
Именно так =)
Отправить комментарий