差三角问题
在网上看到这样一个题,想了很久,始终没有思路。题目是这样的
仔细观察下面的数字组成的三角形:
3
1 4
5 6 2
看出什么特征吗?
首先,它包含了1~6的连续整数。
重要的是:每个数字都是其下方相邻的两个数字的差(当然是大数减去小数)
满足这样特征的三角形,称为:差三角。
你的任务是找出1~15的整数组成的一个更大的差三角。其形如:
?
4 ?
? ? ?
* ? ? ?
? ? ? ? ?
其中,只给出了一个确定的数字:4
请编程确定出“*” 代表的是哪个一个数字。
我的想法是穷举,但明显行不通。各位大神怎么看?
编程
算法
穷举
------解决方案--------------------#include <iostream>
using namespace std;
int main()
{int r,h,r1,h1;
int j,k,l,m,n;
int b[6];
int c(int i,int j,int b[]);
for(j=1;j<16;j++)
if(j!=4)
for(k=1;k<16;k++)
if(j!=k&&k!=4)
for(l=1;l<16;l++)
if(l!=j&&l!=k&&l!=4)
for(m=1;m<16;m++)
if(m!=j&&m!=k&&m!=l&&m!=4)
for(n=1;n<16;n++)
if(n!=m&&n!=l&&n!=k&&n!=j&&n!=4)
{int a[16]={0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1};
b[1]=j;
b[2]=k;
b[3]=l;
b[4]=m;
b[5]=n;
if(c(4,4,b)==4)
{
for(r=1;r<=5;r++)
{
for(h=1;h<=11;h++)
{if(r%2==1)
{if(h%2==0
------解决方案--------------------r>h
------解决方案--------------------h>9-r+1)
continue;
else if(a[c(r,h,b)]==1)
a[c(r,h,b)]=0;
else continue;
}
if (r%2==0)
{if(r>h
------解决方案--------------------h%2==1
------解决方案--------------------h>9-r+1)
continue;
else if(a[c(r,h,b)]==1)
a[c(r,h,b)]=0;
else continue;
}
}
}
if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0&&a[7]==0&&a[8]==0&&
a[9]==0&&a[10]==0&&a[11]==0&&a[12]==0&&a[13]==0&&a[14]==0&&a[15]==0)
for( r1=1;r1<=5;r1++)
{ for(h1=1;h1<=11;h1++)
{
if(r1%2==1)
{if(h1%2==0
------解决方案--------------------r1>h1
------解决方案--------------------h1>9-r1+1)
cout<<" ";
else
cout<<c(r1,h1,b);
}
if (r1%2==0)
{if(r1>h1
------解决方案--------------------h1%2==1
------解决方案--------------------h1>9-r1+1)
cout<<" ";
else
cout<<c(r1,h1,b);
}
}
cout<<endl;
}
}
}
return 0;
}
int c(int i,int j,int b[])
{
int z;
if(i==1)
{if(j==1)