[TL][小学数学]如何用简洁的代码实现
Jeff Chen
@@
Jeff Chen
@@
@@
Jiyong Xu
xxmplus
搜索剪枝吧
2009/9/25 @@ <ask...@gmail.com>:
--
Any complex technology which doesn’t come with documentation must be the best
available.
Sent from Sydney, Nsw, Australia
Jeff Chen
Jiyong Xu
@@
Jeff Chen
Jeff Chen
Jiyong Xu
Hongzhang Liu
4行4列中任选出1行和1列，也就是其中的4。按照对称性，只需要考虑三种情况：
1. (1, 1) 第一行与第一列,
2. (1, 2),
3. (2, 2)
对剩下的3行，每行中只能剩下一个1，每个1的列序号都不同，有6组解。
总的解有3*6*4种。
2009/9/25 @@ <ask...@gmail.com>:
Jeff Chen
Bruce Khereid
我换一下词和符号：一个 4x4 的棋盘上放 6 个棋子，使得每个横线（行）和每个竖线（列）上都有 0 个、2 个或 4 个子，问有多少种棋局。
假设某行（列）上有 4 个棋子，那么必然有另一个行（列）上有 2 个，其余两行（列）都是 0 个，这么一来必然有 2 个列（行）有 1 个棋子，不符合题目要求。所以，第一条结论：任何一行和任何一列都不会有 4 个棋子。进而可知，有一行和一列是没有棋子的，其余每行和每列都有 2 个。
如果刨除空行和空列，可以获得 3x3 的子棋盘，要求一样，每行每列 2 个子，共 6 个子。显然是 3 x 2 x 1 种状态。
空行的位置可以区分解（导致不同的解“不同”），所以刨除空行和空列而取得的 3x3 的棋盘中的每个解可以衍生出原问题的 4x4 个解。
总共 96 种。
arri...@gmail.com
--
Arrix
许海斌
是答案了
简洁是够简洁了，就是运算量比较大，呵呵
On 9月25日, 上午11时32分, "arrixz...@gmail.com" <arrixz...@gmail.com> wrote:
> 暴力验证ruby 1.8.7
@@
Jeff Chen
@@
Li Yang
0 1 1 0
0 1 1 0
1 0 0 1
应该也是个解
不过考虑到现在0也终于算是偶数了，所以全0的应该也满足条件
0000
0000
0000
0000
--
While(!success=try())
zong
--
格物，致知；正心，诚意。
Wen YE
int allcount = 0;
// check bits in mask fit or not
int check(int mask) {
for (int i = 0; i < 4; ++i) {
// sh to count i-th row
// sv to count i-th column
int sh = 0;
int sv = 0;
for (int j = 0; j < 4; ++j) {
if (mask & (1 << (i*4+j)))
sh++;
if (mask & (1 << (j*4+i)))
sv++;
}
if ((sh % 2) || (sv % 2))
return 0;
}
// DEBUG INFO, print the matrix
printf(" >> [NO.%d] %d (0x%X) >>\n", allcount++, mask, mask);
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j)
printf("%d", (mask & (1 << (i*4+j)))?1:0);
printf("\n");
}
return 1;
}
int search(int mask, int p, int c) {
if (p == 16) {
if ((c == 0) && (check(mask)))
return 1;
return 0;
}
int count = search(mask, p + 1, c);
if (c > 0)
count += search((mask + (1 << p)), p + 1, c - 1);
return count;
}
int main(int argc, char* argv[]) {
int sum = search(0, 0, 6);
printf("%d\n", sum);
return 0;
}
2009/9/25 Jeff Chen <sheis...@gmail.com>
Wen YE
Little Push
--
Push Chen
SNDA
SDO Project Management Department
Curie Rd. 208
Shanghai, China
Mobile: +8613524446040
Tel: 50504740-1796
Facebook: http://www.facebook.com/littlepush
Twitter: http://twitter.com/littlepush
Little Push
Little Push
--
Push Chen
SNDA
SDO Project Management Department
Curie Rd. 208
Shanghai, China
Mobile: +8613524446040
Tel: 50504740-1796
Facebook: http://www.facebook.com/littlepush
Twitter: http://twitter.com/littlepush
Little Push
在纸上画，参照Jiyong Xu ，给出如下图形1 0 1 01 0 0 10 1 0 10 1 1 0且发现确实是每行（列）都替换两个
Wen YE
Little Push
--
Push Chen
SNDA
SDO Project Management Department
Curie Rd. 208
Shanghai, China
Mobile: +8613524446040
Tel: 50504740-1796
Facebook: http://www.facebook.com/littlepush
Twitter: http://twitter.com/littlepush
Alecs King
> 同事儿子的作业，大概意思是这样:
>
> 1 1 1 1
> 1 1 1 1
>
> 4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种，并打印出来.
>
> 我自己做了下，写得很烦.有没有高人有简洁一点的代码.
>
> --
> My Blog：http://jeffchen.cn
A Haskell brute force:
import Data.Bits
import Data.List
import Data.Char
main = print (length a) >> mapM_ p a
where a = [ m | n <- [0..2^16-1], let m = get n, sum (map sum m) == 10, ok m, ok . transpose $ m]
get n = [[shiftR (n .&. bit b) b :: Int | y <- [0..3], let b = 4*x+y] | x <- [0..3]]
ok = all (even . sum)
p x = putStrLn "----" >> mapM_ (putStrLn . map intToDigit) x
--
Alecs King
Alecs King
> 同事儿子的作业，大概意思是这样:
>
> 1 1 1 11 1 1 1
> 1 1 1 1
> 1 1 1 1
>
> 4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种，并打印出来.
>
> 我自己做了下，写得很烦.有没有高人有简洁一点的代码.
>
> --
> My Blog：http://jeffchen.cn
#!/usr/bin/python
count = 0
for n in xrange(1 << 16):
m = [[(n & (1 << x*4 + y)) >> x*4+y for y in range(4)] for x in
range(4)]
t = zip(*m)
if sum(map(sum, m)) == 10 and all(sum(m[x]) % 2 == 0 and sum(t[x]) %
2 == 0 for x in range(4)):
for x in range(4):
for y in range(4): print m[x][y],
print
print '-------'
count += 1
print count
--
Alecs King
Jeff Chen
@@
Wen YE
Li Yang
Li Yang
Alecs King
> python的没结果...
Alecs King
#!/usr/bin/python
count = 0
ok = lambda m: all(sum(x) % 2 == 0 for x in m)
for n in xrange(1 << 16):
m = [[(n & (1 << x*4 + y)) >> x*4+y for y in range(4)] for x in range(4)]
if sum(map(sum, m)) == 10 and ok(m) and ok(zip(*m)):
for x in m:
for y in x: print y,
Little Push
Lyman
> ruby的代码真简洁啊，我用java写的，同样是暴力求解，复杂多了
暴力法拿 c++ 写起来也不复杂
#include <iostream>
#include <sstream>
int main()
{
char sep[4] = {' ', ' ', ' ', '\n'};
for (int c = 0, i = 0; i < 65535; i++)
{
int zero = 0, x[4] = {0}, y[4] = {0};
std::stringstream ss;
for(int j = 0, t = i; j < 16; ss << (t % 2) << sep[j % 4], j++,
t >>= 1)
if (t % 2)
x[j / 4]++, y[j % 4]++;
else
zero++;
bool b = (zero == 6);
for(int j = 0; j < 4; j++)
b = b && (x[j] % 2 == 0) && (y[j] % 2 == 0);
if (b) std::cout << ++c << ":" << std::endl << ss.str() <<
std::endl;
}
return 0;
}
>
> 2009/9/25 @@ <ask...@gmail.com <mailto:ask...@gmail.com>>
>
> 穷举了下 是96种。。
>
> 2009/9/25 Bruce Khereid <bruce....@gmail.com
> <mailto:bruce....@gmail.com>>
>
> 不是程序求解的，也没遍历验证，用白话说了，没列定义和公理。不知道
> 有没有错误，请大家纠正：
>
> 我换一下词和符号：一个 4x4 的棋盘上放 6 个棋子，使得每个横线
> （行）和每个竖线（列）上都有 0 个、2 个或 4 个子，问有多少种棋局。
>
> 假设某行（列）上有 4 个棋子，那么必然有另一个行（列）上有 2 个，
> 其余两行（列）都是 0 个，这么一来必然有 2 个列（行）有 1 个棋
> 子，不符合题目要求。所以，第一条结论：任何一行和任何一列都不会有
> 4 个棋子。进而可知，有一行和一列是没有棋子的，其余每行和每列都有
> 2 个。
>
> 如果刨除空行和空列，可以获得 3x3 的子棋盘，要求一样，每行每列 2
> 个子，共 6 个子。显然是 3 x 2 x 1 种状态。
>
> 空行的位置可以区分解（导致不同的解“不同”），所以刨除空行和空列而
> 取得的 3x3 的棋盘中的每个解可以衍生出原问题的 4x4 个解。
>
> 总共 96 种。
>
> 2009/9/25 Jeff Chen <sheis...@gmail.com
> <mailto:sheis...@gmail.com>>
>
> 同事儿子的作业，大概意思是这样:
>
> 1 1 1 1
> 1 1 1 1
> 1 1 1 1
> 1 1 1 1
>
> 4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种，并
> 打印出来.
>
> 我自己做了下，写得很烦.有没有高人有简洁一点的代码.
>
> --
> My Blog：http://jeffchen.cn <http://jeffchen.cn/>
Alecs King
>
> 1 1 1 11 1 1 1
> 1 1 1 1
> 1 1 1 1
>
> 4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种，并打印出来.
>
> 我自己做了下，写得很烦.有没有高人有简洁一点的代码.
>
> --
> My Blog：http://jeffchen.cn
Just for fun. A c++ version. This is different from the haskell or the
python version. Since # of 1s is fixed, we can just check those
possible permutations (# of which is 8008) instead of doing no-brainer
2^16 (65536) checkings.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
inline bool ok(vector<int> &a)
{
for (int i = 0; i < 4; i++) {
int r = 0, c = 0;
for (int j = 0; j < 4; j++) {
r += a[i * 4 + j];
c += a[j * 4 + i];
}
if (r & 1 || c & 1)
return false;
}
return true;
}
inline void print(vector<int> &a)
{
for (int i = 0; i < 16; i++)
printf("%d%c", a[i], (i + 1) % 4 == 0 ? '\n' : ' ');
printf("-------\n");
}
int main()
{
vector<int> a(16, 1);
for (int i = 0; i < 6; i++)
a[i] = 0;
int count = 0, all = 0;
do {
all++;
if (ok(a)) {
count++;
print(a);
}
} while (next_permutation(a.begin(), a.end()));
printf("%d ok out of %d\n", count, all);
return 0;
}
--
Alecs King
lostyzd
黑眼猪
raymond
比如
1 1 1 1
1 0 0 1
0 0 1 1
0 1 1 1
异或为1 1 1 1。
2. 现在问题变成了，共有多少种可能的组合呢？就是16个bit中选择6个就行了，配合适当的减枝，速度会很快的。
具体可以使用单一的数据类型，比如short，加上小心的记录位置来实现。
On 9月25日, 上午9时53分, Jeff Chen <sheismyl...@gmail.com> wrote:
> 同事儿子的作业，大概意思是这样:
>
> 1 1 1 11 1 1 1
xiaosuo
On 9月26日, 下午10时48分, raymond <shiqu...@gmail.com> wrote:
> 1.这个可以归纳为异或运算，4个4bit的数字，如果异或结果为1，就满足了你的要求。
> 比如
> 1 1 1 1
> 1 0 0 1
> 0 0 1 1
> 0 1 1 1
> 异或为1 1 1 1。
> 2. 现在问题变成了，共有多少种可能的组合呢？就是16个bit中选择6个就行了，配合适当的减枝，速度会很快的。
>
> 具体可以使用单一的数据类型，比如short，加上小心的记录位置来实现。
void print_row(unsigned char matrix, int colum)
{
int i, ci;
ci = 0;
for (i = 0; i < 4; i++) {
if (i == colum)
printf(" 1");
else
printf(" %d", (matrix >> (ci++)) & 1);
}
printf("\n");
}
void print_instance(unsigned char *matrix, int row, int colum)
{
int i, ri;
static int count = 0;
printf("\nnumber: %d\n", ++count);
ri = 0;
for (i = 0; i < 4; i++) {
if (i == row)
printf(" 1 1 1 1\n");
else
print_row(matrix[ri++], colum);
}
}
void print_matrix(unsigned char *matrix)
{
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++)
print_instance(matrix, i, j);
}
int main(int argc, char *argv[])
{
unsigned char matrix[3];
for (i = 0; i < 3; i++) {
matrix[0] = 1 << i;
for (j = 0; j < 3; j++) {
matrix[1] = 1 << j;
for (k = 0; k < 3; k++) {
matrix[2] = 1 << k;
if ((matrix[0] ^ matrix[1] ^ matrix
[2]) == 7)
print_matrix(matrix);
}
}
}
}
jinhu wang
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
#define IS_EVEN_H(i) (tmp[i*4+0]^tmp[i*4+1]^tmp[i*4+2]^tmp[i*4+3]==0)
#define IS_EVEN_V(i) (tmp[i+0]^tmp[i+4]^tmp[i+8]^tmp[i+12]==0)
#define IS_EVEN() IS_EVEN_H(0)&&IS_EVEN_H(1)&&IS_EVEN_H(2)&&IS_EVEN_H(3)&&IS_EVEN_V(0)&&IS_EVEN_V(1)&&IS_EVEN_V(2)&&IS_EVEN_V(3)
#define PRT_LINE(i) cout<<tmp[i*4+0]<<","<<tmp[i*4+1]<<","<<tmp[i*4+2]<<","<<tmp[i*4+3]<<endl;
#define PRT(i) cout<<"___"<<i++<<"____"<<endl;PRT_LINE(0);PRT_LINE(1);PRT_LINE(2);PRT_LINE(3)
void myapproach()
{
int i=0;
do {
if(IS_EVEN())
{
PRT(i);
}
}while(next_permutation(tmp,tmp+16));
}
int main()
{
myapproach();
return 0;
}
jinhu wang
- 递归
- 利用stl的求组合
- 利用16bit的数字算法
#include <bitset>
#include <algorithm>
using namespace std;
#define IS_EVEN_H(tmp,i) (tmp[i*4+0]^tmp[i*4+1]^tmp[i*4+2]^tmp[i*4+3]==0)
#define IS_EVEN_V(tmp,i) (tmp[i+0]^tmp[i+4]^tmp[i+8]^tmp[i+12]==0)
#define IS_EVEN(tmp) IS_EVEN_H(tmp,0)&&IS_EVEN_H(tmp,1)&&IS_EVEN_H(tmp,2)&&IS_EVEN_H(tmp,3)&&IS_EVEN_V(tmp,0)&&IS_EVEN_V(tmp,1)&&IS_EVEN_V(tmp,2)&&IS_EVEN_V(tmp,3)
#define PRT_LINE(tmp,i) cout<<tmp[i*4+0]<<","<<tmp[i*4+1]<<","<<tmp[i*4+2]<<","<<tmp[i*4+3]<<endl;
#define PRT(tmp,i) cout<<"___"<<i++<<"____"<<endl;PRT_LINE(tmp,0);PRT_LINE(tmp,1);PRT_LINE(tmp,2);PRT_LINE(tmp,3)
//1递归
void recursiveApproach(int n, int m, int *p,int*pb)
{
static int i=0;
if(n==0)
{
for(int j=0;j<m;++j)
{
*(p+j)=1;
}
if(IS_EVEN(pb))
{
PRT(pb,i);
};
return;
}
for(int i=0;i<m-n+1;i+=1)
{
for(int j=0;j<i;++j)
{
*(p+j)=1;
}
*(p+i)=0;
recursiveApproach(n-1,m-1-i,p+1+i, pb);
}
}
//2利用stl的next_permutation
void myapproach(int *p)
{
int i=0;
do {
//++ncount2;
if(IS_EVEN(p))
{
PRT(p,i);
}
}while(next_permutation(p,p+16));
}
//3数字运算
int count_bits(unsigned short n)
{
//0xAAAAAAAA，0x55555555分别是以“1位”为单位提取奇偶位
n = ((n & 0xAAAA) >> 1) + (n & 0x5555);
//0xCCCCCCCC，0x33333333分别是以“2位”为单位提取奇偶位
n = ((n & 0xCCCC) >> 2) + (n & 0x3333);
//0xF0F0F0F0，0x0F0F0F0F分别是以“4位”为单位提取奇偶位
n = ((n & 0xF0F0) >> 4) + (n & 0x0F0F);
//0xFF00FF00，0x00FF00FF分别是以“8位”为单位提取奇偶位
n = ((n & 0xFF00) >> 8) + (n & 0x00FF);
return n;
}
bool is_even_h(unsigned short n)
{
n = ((n & 0xAAAA) >> 1) ^ (n & 0x5555);
n = ((n & 0xCCCC) >> 2) ^(n & 0x3333);
return (n==0);
}
bool is_even_v(unsigned short n)
{
n = ((n & 0xF0F0) >> 4) ^ (n & 0x0F0F);
n = ((n & 0xFF00) >> 8) ^ (n & 0x00FF);
return (n==0);
}
bool is_even(unsigned short n)
{
return is_even_h(n)&&is_even_v(n);
}
void W2Matrix()
{
int i=0;
for(int n=0x3ff;n<=0xff30;++n)
{
if(count_bits(n)==10
&&is_even(n))
{
cout<<"___"<<i++<<"____"<<endl;
cout<<bitset<4>(n>>12)<<endl<<bitset<4>(n>>8)<<endl<<bitset<4>(n>>4)<<endl<<bitset<4>(n)<<endl;
}
}
}
int main()
{
int tmp[16]={0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};
int tmp2[16]={0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};
freopen("recursiveApproach.txt", "w", stdout);
recursiveApproach(6,16,tmp,tmp);
freopen("myapproach.txt", "w", stdout);
myapproach(tmp2);
freopen("countresult.txt", "w", stdout);
W2Matrix();
return 0;
}
jinhu wang
Tongliang Zhu
Wen YE
Tongliang Zhu
jinhu wang
Fei Yan
起码一眼看过去知道大体是怎么来的，细节之处，只需要看宏就可以。
宏的名字起得也算比较清晰
Samuel Ji
1 1 1 11 1 1 11 1 1 14*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种，并打印出来.我自己做了下，写得很烦.有没有高人有简洁一点的代码.
xiaosuo
#include <stdio.h>
void print_row(unsigned char bitpos, int colum)
int i, ci;
ci = 0;
for (i = 0; i < 4; i++) {
printf(" 1");
else
printf(" 0");
}
printf("\n");
}
void print_instance(unsigned char *bitpos, int row, int colum)
int i, ri;
static int count = 0;
printf("\nnumber: %d\n", ++count);
ri = 0;
for (i = 0; i < 4; i++) {
if (i == row)
printf(" 1 1 1 1\n");
else
}
}
void print_matrix(unsigned char *bitpos)
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++)
}
int main(int argc, char *argv[])
{
int i, j, k;
unsigned char bitpos[3];
for (i = 0; i < 3; i++) {
mask = 1 << i;
continue;
bitpos[1] = j;
mask |= 1 << j;
continue;
bitpos[2] = k;
print_matrix(bitpos);
}
mask &= ~(1 << j);
}
}
return 0;
}
jinhu wang
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
void prtbt(unsigned char b)
{
printf("%d ",b);
}
void prtdw(unsigned long dw)
{
unsigned char*pbt =(unsigned char*)&dw;
for_each(pbt,pbt+4,prtbt);
printf("\n");
}
void ByteDwordSolution()
{
int count = 0;
unsigned char v1[16]={0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};
unsigned long *pdw =(unsigned long *)v1;
do {
if((pdw[0]^pdw[1]^pdw[2]^pdw[3]==0)
&(bitset<32>(pdw[0]).count()%2==0)
&(bitset<32>(pdw[1]).count()%2==0)
&(bitset<32>(pdw[2]).count()%2==0)
&(bitset<32>(pdw[0]).count()%2==0))
{
cout<<"......."<<++count<<"...."<<endl;
for_each(pdw,pdw+4,prtdw);
}
}while(next_permutation(v1,v1+16));
}
jinhu wang
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
{
printf("%d ",b);
}
void prtdw(unsigned long dw)
{
unsigned char*pbt =(unsigned char*)&dw;
for_each(pbt,pbt+4,prtbt);
printf("\n");
}
{
n =((n & 0xFF00FF00FF00FF00LL) >> 8) ^ (n & 0x00FF00FF00FF00FFLL);
n =((n & 0xFFFF0000FFFF0000LL) >> 16) ^ (n & 0x0000FFFF0000FFFFLL);
return(0==n);
}
void ByteDwordSolution()
{
int count = 0;
unsigned long *pdw =(unsigned long *)v1;
if(((pdw[0]^pdw[1]^pdw[2]^pdw[3])==0)
#if 1
&&isevenddw(pddw[0])
&&isevenddw(pddw[1])
#else
&&(bitset<32>(pdw[0]).count()%2==0)
&&(bitset<32>(pdw[1]).count()%2==0)
&&(bitset<32>(pdw[2]).count()%2==0)
&&(bitset<32>(pdw[3]).count()%2==0)
#endif
)
{
cout<<"......."<<++count<<"...."<<endl;
for_each(pdw,pdw+4,prtdw);
}
}
xiaosuo
On 9月27日, 下午11时56分, xiaosuo <xiao...@gmail.com> wrote:
> On 9月27日, 上午11时02分, xiaosuo <xiao...@gmail.com> wrote:
>
再更新下，这个不是3皇后，因为皇后还有斜向唯一的要求，这个最终化简的问题，是0，1, 2这三个数的全排列问题：
do { \
x = x ^ y; \
y = x ^ y; \
x = x ^ y; \
} while (0)
int permute(char bitpos[], char bitpos_curr[], int len)
{
int i;
if (len == 1) {
print_matrix(bitpos);
return;
}
for (i = 0; i < len; ++i) {
if (i != 0)
swap(bitpos_curr[0], bitpos_curr[i]);
permute(bitpos, bitpos_curr + 1, len - 1);
if (i != 0)
swap(bitpos_curr[0], bitpos_curr[i]);
}
return;
int main(int argc, char *argv[])
{
permute(bitpos, bitpos, 3);
return 0;
}
Tongliang Zhu
using namespace std;
{
cout << ((i&8)>>3) << " "
<< ((i&4)>>2) << " "
<< ((i&2)>>1) << " "
<< (i&1) << endl;
}
{
cout << "==========" << endl;
printBits(a);
printBits(b);
printBits(c);
printBits(d);
}
{
int count = 0;
int v[6] = {3, 5, 6, 9, 10, 12};
for (int i=0; i<6; ++i)
for (int j=0; j<6; ++j)
for (int k=0; k<6; ++k)
{
if ((v[i]^v[j]^v[k]) == 15)
{
printResult(15, v[i], v[j], v[k]); count++;
printResult(v[i], 15, v[j], v[k]); count++;
printResult(v[i], v[j], 15, v[k]); count++;
printResult(v[i], v[j], v[k], 15); count++;
}
}
cout << "Count: " << count << endl;
}
1 1 1 11 1 1 11 1 1 14*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种，并打印出来.
我自己做了下，写得很烦.有没有高人有简洁一点的代码.