The problem is to find the no. of 3x3 matrices of no.s..the rows being perfect squares....like:
121
256
169
whose transpose is same as the original..
The solution I came up with is:
1.Make an array of vectors of the sq nos within the range..(such that..each array contains a vector of the no.s beginning with its(the array's) index...)
2.Iterate over the square nos in the range
--1.Put the current no. as the first row.
--2.Iterate over the set(that array of vectors!) which begins with the middle digit of the first row.
----1.Put the current no. as the 2nd row.
----2..Iterate over the set which begins with the 3rd digit of the first row.
------1.Put the no as the 3rd row.
------2.If the 3rd digit of the 2nd row == 2nd digit of the 3rd row.
----------<You have found one of such a matrix>
------3.Continue.
3.Output ..etc etc..
----
<Though I do not have a rigorous mathematical understanding of algorithms,yet > This works very well.....but seems a bit "bloated"...The 2 nested loops, as below..(which was easy to write...but would be a little difficult to reread later) gives me that idea....
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
for(c=10;c*c<1000;c++)
{
temp.v1=itotr(c*c);
for(VI it1=st[temp.v1[1]].begin();it1!=st[temp.v1[1]].end();it1++)
{
temp.v2=*it1;
for(VI it2=st[temp.v1[2]].begin();it2!=st[temp.v1[2]].end();it2++)
{
temp.v3=*it2;
if(temp.v2[2]==temp.v3[1])
{
mc++;
storage.push_back(temp);
}
}
}
}
|