Finding all perfect squares of the form XXYY_问答_开发者

I have to find 4 digits number of the form XXYY that are perfect squares of开发者_高级运维 any integer. I have written this code, but it gives the square root of all numbers when I have to filter only perfect integer numbers.

I want to show sqrt(z) only when it is an integer.

#include<math.h>
#include<iostream.h>
#include<conio.h>
void main()
{
 int x,y=4,z;
 clrscr();
 for(x=1;x<=9;x++)
 {
  z=11*(100*x+y);
  cout<<"\n"<<sqrt(z);

 }
 getch();
}

I'd probably check it like this, because my policy is to be paranoid about the accuracy of math functions:

double root = sqrt(z);
int introot = floor(root + 0.5); // round to nearby integer
if ((introot * introot) == z) {  // integer arithmetic, so precise
    cout << introot << " == sqrt(" << z << ")\n";
}

double can exactly represent all the integers we care about (for that matter, on most implementations it can exactly represent all the values of int). It also has enough precision to distinguish between sqrt(x) and sqrt(x+1) for all the integers we care about. sqrt(10000) - sqrt(9999) is 0.005, so we only need 5 decimal places of accuracy to avoid false positives, because a non-integer square root can't be any closer than that to an integer. A good sqrt implementation therefore can be accurate enough that (int)root == root on its own would do the job.

However, the standard doesn't specify the accuracy of sqrt and other math functions. In C99 this is explicitly stated in 5.2.4.2.2/5: I'm not sure whether C89 or C++ make it explicit. So I'm reluctant to rule out that the result could be out by a ulp or so. int(root) == root would give a false negative if sqrt(7744) came out as 87.9999999999999-ish

Also, there are much larger numbers where sqrt can't be exact (around the limit of what double can represent exactly). So I think it's easier to write the extra two lines of code than to write the comment explaining why I think math functions will be exact in the case I care about :-)

#include <iostream>
int main(int argc, char** argv) {
    for (int i = 32; i < 100; ++i) { 
        // anything less than 32 or greater than 100 
        // doesn't result in a 4-digit number
        int s = i*i;
        if (s/100%11==0 && s%100%11==0) {
            std::cout << i << '\t' << s << std::endl;
        }
    }
}

http://ideone.com/1Bn77

We can notice that

1 + 3 = 2^2
1 + 3 + 5 = 3^2,
1 + 3 + 5 + 7 = 4^2,

i.e. sum(1 + 3 + ... (2N + 1)) for any N is a square. (it is pretty easy to prove)

Now we can generate all squares in [0000, 9999] and check each square if it is XXYY.

There is absolutely no need to involve floating point math in this task at all. Here's an efficient piece of code that will do this job for you.

Since your number has to be a perfect square, it's quicker to only check perfect squares up front rather than all four digit numbers, filtering out non-squares (as you would do in the first-cut naive solution).

It's also probably safer to do it with integers rather than floating point values since you don't have to worry about all those inaccuracy issues when doing square root calculations.

#include <stdio.h>
int main (void) {
    int d1, d2, d3, d4, sq, i = 32;
    while ((sq = i * i) <= 9999) {
        d1 = sq / 1000;
        d2 = (sq % 1000) / 100;
        d3 = (sq % 100) / 10;
        d4 = (sq % 10);
        if ((d1 == d2) && (d3 == d4))
            printf ("   %d\n", i * i);
        i++;
    }
    return 0;
}

It relies on the fact that the first four-digit perfect square is 32 * 32 or 1024 (31² is 961). So it checks 32², 33², 34², and so on until you exceed the four-digit limit (that one being 100² for a total of 69 possibilities whereas the naive solution would check about 9000 possibilities).

Then, for every possibility, it checks the digits for your final XXYY requirement, giving you the single answer:

While I smell a homework question, here is a bit of guidance. The problem with this solution is you are taking the square root, which introduces floating point arithmetic and the problems that causes in precise mathematics. You can get close by doing something like:

double epsilon = 0.00001;
if ((z % 1.0) < epsilon || (z % 1.0) + epsilon > 1) {
    // it's probably an integer
}

It might be worth your while to rewrite this algorithm to just check if the number conforms to that format by testing the squares of ever increasing numbers. The highest number you'd have to test is short of the square root of the highest perfect square you're looking for. i.e. sqrt(9988) = 99.93... so you'd only have to test at most 100 numbers anyway. The lowest number you might test is 1122 I think, so you can actually start counting from 34.

There are even better solutions that involve factoring (and the use of the modulo operator) but I think those are enough hints for now. ;-)

To check if sqrt(x) is an integer, compare it to its floored value:

sqrt(x) == (int) sqrt(x)

However, this is actually a bad way to compare floating point values due to precision issues. You should always factor in a small error component:

abs(sqrt(x) - ((int) sqrt(x))) < 0.0000001

Even if you make this correction though, your program will still be outputting the sqrt(z) when it sounds like what you want to do is output z. You should also loop through all y values, instead of just considering y=4 (note that y an also be 0, unlike x).

I want to show the sqrt(z) only when it is integer.

double result = sqrt( 25); // Took 25 as an example. Run this in a loop varying sqrt
                           // parameter
int checkResult = result;
if ( checkResult == result )
    std::cout << "perfect Square" ;
else
    std::cout << "not perfect square" ;

The way you are generating numbers is ~~incorrect~~ indeed correct (my bad) so all you need is right way to find square. : )

loop x: 1 to 9
  if(check_for_perfect_square(x*1100 + 44))
         print: x*1100 + 44

see here for how to find appropriate square Perfect square and perfect cube

You don't need to take square roots. Notice that you can easily generate all integer squares, and all numbers XXYY, in increasing order. So you just have to make a single pass through each sequence, looking for matches:

 int n = 0 ;
 int X = 1, Y = 0 ; // Set X=0 here to alow the solution 0000
 while (X < 10) {
   int nSquared = n * n ;
   int XXYY = 1100 * X + 11 * Y ;

   // Output them if they are equal
   if (nSquared == XXYY) cout << XXYY << endl ;

   // Increment the smaller of the two
   if (nSquared <= XXYY) n++ ;
   else if (Y < 9) Y++ ;
   else { Y = 0 ; X++ ; }
   }