算法-5*5矩阵算法 求助

算法-5*5矩阵算法 求助

甜柠檬 发布于 2017-05-28 字数 3501 浏览 1555 回复 6

很久前,遇到一个很有意思的问题:
有一个5*5的表格,将1,2,3,4四个数填入到这25个小格中,其中1可以放在任何小格中,2必须和1相邻,3必须和1,2都相邻,4则要和1,2,3,都相邻,怎样填写这些数字才能够使这个表格里所有数字的和最大。
对于算法我也有些想法。但是所花费的时间太让人呕心了。我想要知道结果。不知道有没有科学的方法解决这个问题。任意语言。求助~

/*
1.当成二维坐标。
2.赋值结构体的时候,我是弄成类似25位的4进制数。每个结构体中的value为每位的数值。
26位为循环用的标志位。每次循环,4进制数,增加一。正好可以遍历所有的数。 */ #include "stdio.h"
#include "conio.h"
#include "dos.h"

typedef struct
{
int x;
int y; //二维坐标
int value; //每4进制位的值
int near_flag;
/*权值,
二进制:000
第1位是1表示已经与0相连
第2位是1表示已经与1相连
第3位是1表示已经与2相连
例:
110 :表示与2和1相连,但是不与0相连
111 :表示与0,1,2都相连
001 :表示与0相连,与1,2不相连
*/
} xy_value;

xy_value num[26];
/* 判断权位,确定相连的数是否符合 */
jdg_flag()
{
int i;
for(i=0;i<25;i++)
switch (num[i].value)
{
case 3: {if(( num[i].near_flag& 7)!= 7) return 0; else break;}
case 2: {if(( num[i].near_flag& 3)!= 3) return 0; else break;}
case 1: {if(( num[i].near_flag& 1)!= 1) return 0; else break;}

}
return 1;

}

flag()//初始化权位
{
int i;
int x,y;
for(i=0;i<25;i++)
{
x=num[i].x;
y=num[i].y;

if((x-1)>=0) //如果越界,则越界的那边不给予权值
num[i].near_flag|=(1<<(num[(x-1)*5+y].value));
if((x+1)<=4)
num[i].near_flag|=(1<<(num[(x+1)*5+y].value));
if((y-1)>=0)
num[i].near_flag|=(1<<(num[(y-1)+x*5].value));
if((y+1)<=4)
num[i].near_flag|=(1<<(num[(y+1)+x*5].value));

}
}
/* 增加1 */
addnum(int i)
{
num[i].value+=1;
if(num[i].value==4)
{
num[i].value=0;
i=addnum(i+1);
}
return i;
}

main()
{

int i,sumbuff=0,sum=0;
int x,y;
for( i= 0; i< 26; i++)//初始化结构体
{
num[i].value= 0;
num[i].x= (int)(i/ 5); //初始化坐标
num[i].y= i% 5;
}

while( num[25].value== 0)
{
addnum(0); //0表示从第一位开始
flag();

if(!jdg_flag())
{

for(i=0;i<25;i++)
num[i].near_flag&=0; /*由于不符合条件,必须消除消权*/
continue;
}
for( i=0; i<25; i++)
sumbuff+=num[i].value; //能运算到这,说明符合条件.求和
if(sumbuff>sum)//输出目前得到的 满足条件的 最大和的 矩阵
{
for(x=0;x<5;x++)
{
for(y=0;y<5;y++)
printf("%d ",num[x*5+y].value);
printf("n");

}
sum=sumbuff;
printf("now sum is:%dn",sum);
printf("n");
}
sumbuff=0;

}
for(x=0;x<5;x++)
{
for(y=0;y<5;y++)
printf("%d ",num[x*5+y].value);
printf("n");

}

}

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

清晨说ぺ晚安 2017-10-25 6 楼

可以将数组简化成3×3寻找规律:发现不管怎么填,只要有最大值4,其他尽量往大的填,最大值都是20。

甜柠檬 2017-10-21 5 楼

这不就是手机上盖大楼的游戏吗?
尽量4最多,1最少,那么就需要把1尽量共用,2和3交替排列,剩下的全都填4.

浮生未歇 2017-09-21 4 楼

把一个格子按上下左右分成四份,对每一个4、3、2来说,按照规则要求的某个相邻格子中的比它小的数,以及这个数的子树看做是它自己的一部分(平分到其他相邻的格子里)。
先不考虑靠边的问题:
1,占用1个格子,总和为1;有四面可以被使用
2,因为必须和1相邻,占用1 + 1/4个格子,总和为2 + 1/4;有三面可以被使用
3,必须和1、2相邻,占用1 + 1/3 * (1 + 1/4) + 1/4个格子,总和为3 + 1/3 * (2 + 1/4) + 1/4;有两面可以使用
4,必须和1、2、3相邻,占用1 + 1/2 * (1 + 1/3 * (1 + 1/4) + 1/4) + 1/3 * (1 + 1/4) + 1/4个格子,总和为4 + 1/2 * (3 + 1/3 * (2 + 1/4) + 1/4) + 1/3 * (2 + 1/4) + 1/4。4有一面邻接的数字会被“浪费”,可以视作多一个4,就多了一个靠边的格子。

算出结果列成表:
数值 占用格子 总和 平均每格
1 1 1 1
2 5/4 9/4 9/5
3 5/3 4 12/5
4 5/2 7 14/5

靠边的情形:
1,2,3靠边时,分别有1/4、1/3、1/2没有被更大的数使用,这些看成是1/4、1/3、1/2个独立的子树;每个居中的4也会创造一条“边”,如果除了必须的321以外,另一个位置上的1、2、3,这条邻接关系会浪费,等效于靠边。
角落里的格子,等效于靠两次边。

设按以上方法计算,1、2、3、4的独立子树个数和分别为
a1/4, a2/3, a3/2, a4
其中a1,a2,a3,a4为整数

1/4 * a1 + 5/12 * a2 + 5/6 * a3 + 5/2 * a4 = 25
而总和为
1/4 * a1 + 3/4 * a2 + 2 * a3 + 7 * a4

靠边次数:20 + a4 - 2k = a1 + a2 + a3
其中k为1. 两个4相邻 2. 一个4靠边 两种事件发生次数的总和
首先4不能在角落;12个靠边位置中,最多可以有6次靠边(同一侧相邻两格不能同时为4;角落中最接近的两格如果同时为4:
1 4 3 2
4 2 1
3 2
1
或者
1 4 2 1
4 3 2
2 1

至少5格个靠边格内只能有两个4。剩下7个由于相邻格不能同为4,如果有至少5个为4,则左下角最接近两格一定同为4,同上知矛盾)
因此a1 + a2 + a3 >= 20 + 6 + (a4-6) - (6 + (a4-6)/2)*2 = 14
1/4 * a1 + 5/12 * a2 + 5/6 * a3 + 5/2 * a4 = 25 >= 14 / 4 + 5 / 2 * a4
a4 <= 8

1/4 * a1 + 5/12 * a2 + 5/6 * a3 + 20 >= 25
1/4 * a1 + 5/12 * a2 + 5/6 * a3 >= 5

1/4 * a1 + 3/4 * a2 + 2 * a3 + 7 * a4
= 12 / 5 * (1/4 * a1 + 5/12 * a2 + 5/6 * a3 + 5/2 * a4) - 3/5 * a1 - 1/4 * a2 + a4 = 60 - 3/5 * a1 - 1/4 * a2 + a4 <= 68

剩下怎么做就不知道了……

灵芸 2017-09-09 3 楼

5*5的矩阵最多有多少种可能?
4的25次方。
穷举是不现实的,我估计了一下,2.0的cpu,空循环大概要30小时。。。。

想到的思路

符合你要求的有多少呢??
估计可以;
也就是说,一个格一个格的填,保证每次填出来的都符合条件;
然后求和。

另外一种思路,还没想好,就是类似贪心算法,先填大的,然后填小的。

偏爱自由 2017-08-23 2 楼

这道题目贪心点就行 最好就是都是4
但是这是不合理的 然后修改
直到他合法

修改的时候注意

做到尽量少的修改
可能就是最好的答案

归属感 2017-06-30 1 楼

这个有意思,先手工来排列一下 看看怎么样最大吧 希望能看出来什么规律。

1 3 2 1 2
2 4 4 1 4
4 1 3 2 3
3 2 4 4 1
1 3 1 3 2

2 4 3 1 3
3 1 2 1 2
4 1 4 4 3
2 4 3 2 1
1 2 1 4 3

6个4;6个3;6个2;7个1

有更多的跟帖观察。