可用分押宝游戏火热进行中...	专题改版：Java Web 专题

? 求一个4*4的矩阵,要求所有的行,列,对角线都是可逆索数

楼主tony20020101（tony）2003-08-02 09:54:26 在 C/C++ / C语言提问

索数就是质数.
可逆就是"abcd"是索数,"dcba"也是索数,
请高手帮忙,谢谢! 问题点数：20、回复次数：14Top

1 楼Tangyongkang（匆匆）回复于 2003-08-02 10:38:51 得分 2

最简单的办法，用回溯算法吧。Top

2 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-02 10:53:29 得分 8

先给你几个函数

//-------------------------------------------------
// 功能：检查给定的整数是否为素数
// pn - 指定数组的起始位置
// dwStride - 每两个数组元素之间的间隔
bool CheckPrimeNumber( DWORD dwNum )
{
for ( DWORD i = 0; i < dwNum; i++ )
{
if ( 0 == dwNum % i )
break;
}
return i == dwNum;
}

//-------------------------------------------------
// 功能：将指定的包含四个个位整数合成为四位整数。
// pn - 指定数组的起始位置
// dwStride - 每两个数组元素之间的间隔
DWORD MakeInteger( DWORD *pn, int nStride = 1 )
{
return ( *( pn + 0 ) * 1000 + *( pn + nStride ) * 100 +
*( pn + 2 * nStride ) * 10 + *( pn + 3 * nStride ) );
}

//-------------------------------------------------
// 功能：测试矩阵是否附合要求
// pMatrix - 指定的矩阵
bool CheckMatrix( DWORD *pMatrix )
{
for ( DWORD i = 0; i < 4; i++ )
{
if ( !CheckPrimeNumber( MakeInteger( &pMatrix[ i * 4 ] ) ) ||
!CheckPrimeNumber( MakeInteger( &pMatrix[ i * 4 + 3 ], -1 ) ) ||
!CheckPrimeNumber( MakeInteger( &pMatrix[i], 4 ) ) ||
!CheckPrimeNumber( MakeInteger( &pMatrix[ 12 + i ], -4 ) ) )
{
return false;
}
}
if ( !CheckPrimeNumber( MakeInteger( &pMatrix[0], 5 ) ) ||
!CheckPrimeNumber( MakeInteger( &pMatrix[12], -3 ) ) ||
!CheckPrimeNumber( MakeInteger( &pMatrix[3], 3 ) ) ||
!CheckPrimeNumber( MakeInteger( &pMatrix[15], -5 ) ) )
{
return false;
}
return true;
}
Top

3 楼yakai（日落长河）回复于 2003-08-02 10:56:22 得分 2

列出四位数中所有的素数，然后分拆排列，四位数中的素数应该不是很多的，而且成对可逆就更少了Top

4 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-02 10:59:33 得分 0

第一个函数有点问题，更正一下

//-------------------------------------------------
// 功能：检查给定的整数是否为素数
// dwNum - 指定的整数
bool CheckPrimeNumber( DWORD dwNum )
{
for ( DWORD i = 2; i < dwNum; i++ )
{
if ( 0 == dwNum % i )
break;
}
return i == dwNum;
}
Top

5 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-02 11:13:24 得分 0

再给你两个函数

//-------------------------------------------------
// 功能：将指定的包含四个个位整数合成为四位整数。
// p1...n4 - 指定的四个个位整数
DWORD MakeInteger( DWORD n1, DWORD n2 , DWORD n3 , DWORD n4 )
{
return ( n1 * 1000 + n2 * 100 + n3 * 10 + n4 );
}

//-------------------------------------------------
// 功能：将一个整数反向输出
// dwNumber - 指定的整数
DWORD ReversInteger( DWORD dwNumber )
{
DWORD cur, exp, i, r;
DWORD bit = (DWORD)( log10( dwNumber ) ) + 1;
for ( i = 0, r = 0; i < bit; i++ )
{
cur = dwNumber - ( dwNumber / 10 ) * 10;
exp = (DWORD)( pow( 10, ( bit - i - 1 ) ) );
r += cur * exp;
dwNumber /= 10;
}
return r;
}
Top

6 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-02 12:46:58 得分 0

不存在，因为矩阵四周的四个整数必须每一位都是素数。符合下列要求的四位数整数：

每一位都是一个个位素数
正序为素数
反序为素数

在1000 - 9999之间，这样的素数只有四个：
3373
3733
7577
7757
但他们并无首尾相连关系，所以这样的矩阵不存在！

Top

7 楼tony20020101（tony）回复于 2003-08-02 15:27:16 得分 0

列出四位数中所有的可逆素数，共有204个.
矩阵四周的四个整数必须每一位好像不一定都要素数.
有一组答案
1 9 1 3
1 0 2 1
9 0 2 9
3 1 9 1Top

8 楼tony20020101（tony）回复于 2003-08-03 06:32:36 得分 0

我用了fireseed的方法,但循环次数太多,算不出来!!!
求助!!!Top

9 楼yakai（日落长河）回复于 2003-08-03 11:21:35 得分 8

我有一个方法，应该花费不了太长时间。

先求出可逆素数，有204个，成对出现，实际上记录102个单向就可以了

然后检查各个位的特点，第一位和最后一位也就1，3，7，9四个，中间两位都霸占了，然后循环即可。计算量可以减少好多

下面是102个素数
1009 1021 1031 1033 1061
1069 1091 1097 1103 1109
1151 1153 1181 1193 1213
1217 1223 1229 1231 1237
1249 1259 1279 1283 1381
1399 1409 1429 1439 1453
1471 1487 1499 1523 1559
1583 1597 1619 1657 1669
1723 1733 1753 1789 1847
1867 1879 1913 1933 1949
1979 3019 3023 3049 3067
3083 3089 3109 3163 3169
3257 3299 3319 3343 3347
3359 3373 3389 3407 3463
3467 3469 3527 3583 3697
3719 3767 3889 3917 3929
7027 7057 7177 7187 7219
7229 7297 7349 7457 7459
7529 7577 7589 7649 7687
7699 7879 7949 9029 9349
9479 9679

Top

10 楼yakai（日落长河）回复于 2003-08-03 11:38:35 得分 0

还是不妥，循环太深了，可以首先从102个数中挑选四个（可以重复），然后分四行排列，四层循环就，然后检测成列和对角线的数是否在102个中，就可以了Top

11 楼tony20020101（tony）回复于 2003-08-03 16:01:21 得分 0

这一题我是算出来了.
但循环次数还是不少,执行要一两秒钟才有结果.
不知还有没有好方法.Top

12 楼yakai（日落长河）回复于 2003-08-03 17:10:06 得分 0

你狠，我算了好久，都用小时计时了，最后没有符合条件的矩阵。

你算出来的话，把结果贴出来看看，我需要肯定是不是我算法错了Top

13 楼tony20020101（tony）回复于 2003-08-03 20:07:05 得分 0

#include <stdio.h>
#include <math.h>
int su[204][4],su2[22][4];
//su是所有符合的素数(204个),su2是所有符合的由1,3,7,9组成的素数(22个)
int sushu(s0,s1,s2,s3)//输入一个四位数,如果是可逆素数,返回此数,否则返回0.
int s0,s1,s2,s3;
{
int i,ns,nsh;
ns=s0*1000+s1*100+s2*10+s3;//组成此四位数
if((s0+s1+s2+s3)%3==0) return (0);//减少循环,除去被3整除的
if((s3%2==0)||(s0%2==0)||(s3==5)||(s0==5)) return (0);//减少循环,除去被5整除的
for(i=3;i<=sqrt(ns);i=i+2)//偶数排除
if (ns%i==0) return (0);
nsh=s3*1000+s2*100+s1*10+s0;//反向此数
for(i=3;i<=sqrt(nsh);i=i+2)
if (nsh%i==0) return (0);
return (ns);
}
void pri()//求出所有四位的可逆素数
{
int a0,a1,a2,a3,np=0,k=0;
for (a0=0;a0<10;a0++)
for (a1=0;a1<10;a1++)
for (a2=0;a2<10;a2++)
for (a3=0;a3<10;a3++)
{ np=sushu(a0,a1,a2,a3);
if (np!=0)
{ su[k][3]=np%10;
np=np/10;
su[k][2]=np%10;
np=np/10;
su[k][1]=np%10;
np=np/10;
su[k][0]=np%10;
k++;
}
}
}
void pri2()//求出所有由1,3,7,9组成的四位可逆素数
{
int a0,a1,a2,a3,np=0,k=0;
for (a0=1;a0<10;a0=a0+2)
for (a1=1;a1<10;a1=a1+2)
for (a2=1;a2<10;a2=a2+2)
for (a3=1;a3<10;a3=a3+2)
{ np=sushu(a0,a1,a2,a3);
if ( (np!=0)&&(a0!=5)&&(a1!=5)&&(a2!=5)&&(a3!=5) )
{ //printf("%d\t",np);
su2[k][3]=np%10;
np=np/10;
su2[k][2]=np%10;
np=np/10;
su2[k][1]=np%10;
np=np/10;
su2[k][0]=np%10;
k++;
}
}
}
void main()
{ int i0,i1,i2,i3,i4,i5,i6,m[4][4],i,j;
int t=0;//答案个数
pri();
pri2();
//由条件来填数,共有10(4行4列两对角线)条件
for(i0=0;i0<22;i0++){//1 //第一行
{m[0][0]=su2[i0][0];m[0][1]=su2[i0][1];
m[0][2]=su2[i0][2];m[0][3]=su2[i0][3];}//填第一行
for(i1=0;i1<22;i1++){//2 //第四行
{m[3][0]=su2[i1][0];m[3][1]=su2[i1][1];
m[3][2]=su2[i1][2];m[3][3]=su2[i1][3];}//填第四行
for(i2=0;i2<22;i2++){//3 //第一列
if((m[0][0]==su2[i2][0])&&(m[3][0]==su2[i2][3])){//4
{m[1][0]=su2[i2][1];m[2][0]=su2[i2][2];}//填第一列的2,3两个数
for(i3=0;i3<22;i3++){//5 //第四列
if((m[0][3]==su2[i3][0])&&(m[3][3]==su2[i3][3])){//6
{m[1][3]=su2[i3][1];m[2][3]=su2[i3][2];}//填第四列的2,3两个数
//四条边的数已填完.下面填中间四个数,循环次数巨增
for(i4=0;i4<204;i4++) //第二行
if((m[1][0]==su[i4][0])&&(m[1][3]==su[i4][3])){//7
{m[1][1]=su[i4][1];m[1][2]=su[i4][2];}//填第二行2,3两个数
for(i5=0;i5<204;i5++) //第二列
if((m[0][1]==su[i5][0])&&(m[1][1]==su[i5][1])&&(m[3][1]==su[i5][3])){//8
{m[2][1]=su[i5][2];}//填第二列第3个数
for(i6=0;i6<204;i6++) //第三列
if((m[0][2]==su[i6][0])&&(m[1][2]==su[i6][1])&&(m[3][2]==su[i6][3])){//9
{m[2][2]=su[i6][2];}//填第三列第3个数
//所有数填完,剩下3个条件
if(sushu(m[2][0],m[2][1],m[2][2],m[2][3])!=0) //第三行
if(sushu(m[0][0],m[1][1],m[2][2],m[3][3])!=0) //正对角线
if(sushu(m[3][0],m[2][1],m[1][2],m[0][3])!=0) //反对角线
{ t++;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
printf("%d",m[i][j]);
printf("*");//输出结果
}
}}}}}}}}}//共9个
printf("t=%d",t);
}Top

14 楼tony20020101（tony）回复于 2003-08-03 20:09:07 得分 0

一切为了减少循环次数!!!

本人是初学者,编程不太规范,请大家指教.谢谢
Top