主题：第45次编程比赛第1题
hotzenplotz [专家分：40] 发布于 2006-10-19 19:21:00
第45次编程比赛第1题
对于一个由0和1填充的n*n方阵，如果它的每一行，每一列都有且仅有两个1，其它地方都是0，则我们称它为满足条件的。
例如，3*3的方阵，以下的情况是满足条件的：
110 110
011 101 . . . . . .
101 011
试求:对于n*n方阵，有几种情况是满足条件的？
以下给出前3个数，供大家参考。
2*2的方阵，明显只有1种。
3*3的方阵，有6种。
4*4的方阵，有90种。
说明：这道题是我在学校时帮一位数理系老师做的，前后写了三个不同的程序。但仍不能保证已经得到最佳的算法。以前的代码已经找不到了。我昨天又做了一遍，可以算到n == 11。希望大家有更好的算法。
提示：搜索的空间相当大,如果对自己的数学水平很有信心的话可以参考第43次编程比赛的第1题。
请编写一包含main的完整程序，当输入n时，输出n*n方阵的结果(共有多少种,不必把每种的具体排列写出来)。
测试环境为VC6或VC2002
截止时间：下个星期一（10月23日）中午12点半
有任何问题，请发帖讨论，或直接通过论坛发短消息给我~~
祝大家好运~~
回复列表 （共10个回复）
板凳
syslwx [专家分：350] 发布于 2006-10-19 17:51:00
#include <stdio.h>
#include <stdlib.h>
static int Num= 0;
static int **ppArray = NULL;
static int count = 0;
int legal_now(int row)
{
int i = 0;
int j = 0;
int col_num = 0;
for(i = 0; i < row; i++)
{
for(j = 0; j < Num; j++)
{
if(ppArray[j][i] == 1)
{
col_num++;
}
if(col_num > 2)
{
return 0;
}
}
col_num = 0;
}
return 1;
}
int legal()
{
int i = 0;
int j = 0;
int col_num = 0;
for(i = 0; i < Num; i++)
{
for(j = 0; j < Num; j++)
{
if(ppArray[j][i] == 1)
{
col_num++;
}
if(col_num > 2)
{
return 0;
}
}
if(col_num != 2)
{
return 0;
}
col_num = 0;
}
return 1;
}
int next(int row)
{
int i = 0;
int first = -1;
int second = -1;
for(i = 0; i < Num; i++)
{
if(ppArray[row][i] == 1)
{
if(first == -1)
{
first = i;
}
else
{
second = i;
break;
}
}
}
if(first == -1 && second == -1)
{
ppArray[row][0] = 1;
ppArray[row][1] = 1;
return 1;
}
if(first == -1 || first == Num -1 || second == -1)
{
return 0;
}
if(second == Num -1)
{
ppArray[row][first] = 0;
ppArray[row][second] = 0;
if(first == Num - 2)
{
return 0;
}
ppArray[row][first+1] = 1;
ppArray[row][first+2] = 1;
return 1;
}
ppArray[row][second] = 0;
ppArray[row][second+1] = 1;
return 1;
}
void trial(int row)
{
#if 0
int i = 0;
int j = 0;
#endif
if(row == Num)
{
if(legal())
{
count++;
printf("\n*********** %d **********\n", count);
#if 0
for(i = 0; i < Num; i++)
{
for(j = 0; j < Num; j++)
{
printf("%5d", ppArray[i][j]);
}
printf("\n");
}
#endif
}
return;
}
if(legal_now(row) == 0)
{
return;
}
while(next(row))
{
trial(row+1);
}
}
int main()
{
int i = 0;
printf("Please input the number:");
scanf("%d", &Num);
if(Num <= 1 || Num > 20)
{
printf("Invalid input value.\n");
return -1;
}
ppArray = malloc(sizeof(int *)*Num);
if(ppArray == NULL)
{
printf("Error: no memory.\n");
return -1;
}
for(i = 0; i < Num; i++)
{
ppArray[i] = malloc(sizeof(int)*Num);
if(ppArray[i] == NULL)
{
printf("Error: no memory.\n");
return -1;
}
}
trial(0);
printf("======== Result: %d\n", count);
return 0;
}
应该还可以优化的，
请多多指教……
(请搂主注意，我的程序有更新)
4 楼
ITER [专家分：680] 发布于 2006-10-19 21:35:00
爷爷的 好歹你还和数理老师讨论过勒 － －
居然出道数理题 晕晕滴 看看吧 呵呵
昏死勒 估计凶多勒
5 楼
syslwx [专家分：350] 发布于 2006-10-20 10:19:00
请搂主注意一下，我的程序更新了，请看三楼。。。
6 楼
goal00001111 [专家分：4030] 发布于 2006-10-21 23:21:00
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long Phalanx(int n);
void Solve(int map[][32], unsigned long max, int pos, int n, long *count);
void GetMap(int map[][32], unsigned long num, int pos, int n);
int JudgeRow(int map[][32], int n, int pos);
int JudgeCol(int map[][32], int n, int pos);
int main(void)
{
int i;
for (i=2; i<10; i++)
printf("n = %d: %ld\n", i, Phalanx(i));
getchar();
return 0;
}
//算法为用一个32位的长整数表示方阵的每一行，该长整数的每一位代表该行的每一个元素
long Phalanx(int n)
{
if (n < 2 || n > 32) //当n大于32时，已超出长整数的范围
return 0;
else if (n == 2)
return 1;
unsigned long max = (~0u) >> (32-n);//max的每一位都是1,是具有n位整数的最大值(二进制数)
int phalanx[32][32] = {0}; //存储方阵
int pos = 0; //行号
long count = 0; //累积结果
Solve(phalanx, max, pos, n, &count); //递归求解每一行数据的可能值
return count;
}
void Solve(int map[][32], unsigned long max, int pos, int n, long *count)
{
if (pos < n)
{
unsigned long i;
for (i=3; i<max; i++)
{
GetMap(map, i, pos, n); //更新方阵的元素
if (JudgeRow(map, n, pos) && JudgeCol(map, n, pos))
Solve(map, max, pos+1, n, count);
}
}
else
{//
// int i, j;
// for (i=0; i<n; i++)
// {
// for (j=0; j<n; j++)
// printf("%d", map[i][j]);
// printf("\n");
// }
// printf("\n");
(*count)++;
}
}
void GetMap(int map[][32], unsigned long num, int pos, int n)
{
int i, j;
for (i=n-1; i>=0; i--) //提取二进制整数每一位的值，存储到方阵中
map[pos][n-i-1] = (num >> i) & 1;
}
int JudgeRow(int map[][32], int n, int pos)//判断每一行的元素是否满足要求
{
int i;
int sum = 0;
for (i=0; i<n; i++)
sum += map[pos][i];
return (sum == 2) ? 1 : 0;
}
int JudgeCol(int map[][32], int n, int pos)//判断每一列的元素是否满足要求
{
int i, j, sum;
for (i=n-1; i>=0; i--)
{
sum = 0;
for (j=0; j<=pos; j++)
sum += map[j][i];
if (sum > 2)
return 0;
}
return 1;
}
7 楼
tiancai007 [专家分：0] 发布于 2006-10-22 20:17:00
#include<stdio.h>
void digui(int now);
struct
{
int one;
int zero;
}
a[100][100];
unsigned long count[100][100][100] = { 0 };
int an[30]={0};
int n;
unsigned long daan;
main()
{
scanf("%d",&n);
an[1] = 1;
count[1][n-2][2] = n*(n-1)/2;
a[1][1].zero = n-2 ;
a[1][1].one = 2;
digui(2);
printf("%ld",count[n][0][0]);
getch();
}
void digui(int now)
{
int i;
int j;
unsigned long linshi;
for( i = 1;i <= an[now -1];i++)
{
for( j = 0;j <= 2; j ++)
if( a[now-1][i].zero - j >= 0 && a[now-1][i].one - 2 + 2*j>=0)
{
if(j == 1 && a[now-1][i].one == 0)
continue;
if(count[now][a[now-1][i].zero - j][a[now-1][i].one - 2 + 2*j] == 0)
{
an[now]++;
a[now][an[now]].zero = a[now-1][i].zero - j;
a[now][an[now]].one = a[now-1][i].one - 2 + 2*j;
}
if( j == 0)
{
linshi = (a[now-1][i].one*(a[now-1][i].one-1))/2;
}
else if( j == 1)
{
linshi = a[now-1][i].one*a[now-1][i].zero;
}
else if( j == 2)
{
linshi = (a[now-1][i].zero * (a[now-1][i].zero -1))/2;
}
count[now][a[now-1][i].zero-j][a[now-1][i].one-2+2*j]+=(count[now-1][a[now-1][i].zero][a[now-1][i].one]*linshi);
}
}
if( now == n)
return;
else
{
digui(now+1);
}
}
不高兴高精度了
8 楼
do熊 [专家分：1250] 发布于 2006-10-22 23:49:00
写着玩，递归的，呵呵～！～！
#include<stdio.h>
#define N 10
int Narray[N][N]={0};
int F(int row, int n)
{
int Nsum[N]={0};
int col1,col2,i,result=0;
for(col1=0; col1<n; col1++)
{
for(i=0; i<row; i++)
{
Nsum[col1] += Narray[i][col1];
}
if(Nsum[col1]>2)
{
return 0;
}
}
if(row == n)
{
return 1;
}
else
{
for(col1=0; col1<n-1; col1++)
{
Narray[row][col1]=1;
for(col2=col1+1; col2<n;col2++)
{
Narray[row][col2]=1;
result += F(row+1,n);
Narray[row][col2]=0;
}
Narray[row][col1]=0;
}
return result;
}
}
int main()
{
int Narray[N][N];
int Nsun[N];
int row,col1,col2,result;
int i,j,n=0;
while(n<2 || n>8)
{
printf("\nPlease enter n(2<=n<=8):");
scanf("%d",&n)? 0: fflush(stdin);
}
result = F(0,n);
printf("%d\n",result);
printf("\n");
system("pause");
return 0;
}
/*自己测了一下(Dev-Cpp 4.9.9.2)，可以算到n=8：187530840*/
9 楼
benen6228 [专家分：0] 发布于 2006-10-23 11:02:00
呵呵 我是菜鸟
10 楼
benen6228 [专家分：0] 发布于 2006-10-23 11:03:00
我回了
我来回复
您所在位置：