Нахождение всех совершенных квадратов вида XXYY

Question

Я должен найти 4-значный номер формы XXYY, которые являются идеальными квадратами любого целого числа.Я написал этот код, но он дает квадратный корень всех чисел, когда мне нужно отфильтровать только совершенные целые числа.

Я хочу показать sqrt(z) только тогда, когда это целое число.

#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();
}

Answer 1

Я бы, наверное, проверил это так, потому что моя политика заключается в том, чтобы быть параноиком в отношении точности математических функций:

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 может точно представлять все целые числа, которые нас интересуют (для этогоДело в том, что в большинстве реализаций он может точно представлять все значения int).Он также обладает достаточной точностью, чтобы различать sqrt(x) и sqrt(x+1) для всех целых чисел, которые нас интересуют.sqrt (10000) - sqrt (9999) - 0,005, поэтому нам нужно всего 5 знаков после запятой, чтобы избежать ложных срабатываний, поскольку нецелочисленный квадратный корень не может быть ближе к целому числу.Поэтому хорошая реализация sqrt может быть достаточно точной, чтобы (int)root == root сам по себе справился бы с этой задачей.

Однако в стандарте не указана точность sqrt и других математических функций.В C99 это явно указано в 5.2.4.2.2 / 5: я не уверен, что C89 или C ++ делают это явно.Так что я не хочу исключать, что результат может быть из-за ульпи или около того.int(root) == root даст ложный отрицательный результат, если sqrt(7744) получится как 87.9999999999999-иш

Кроме того, есть гораздо большие числа, где sqrt не может быть точным (в пределах предела того, что может double)представлять точно).Поэтому я думаю, что легче написать дополнительные две строки кода, чем написать комментарий, объясняющий, почему я думаю, что математические функции будут точными в том случае, если я забочусь о: -)

Answer 2

Мы можем заметить, что

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

т.е.. sum(1 + 3 + ... (2N + 1)) для любого N является квадратом. (это довольно легко доказать)

Теперь мы можем сгенерировать все квадраты в [0000, 9999] и проверить каждый квадрат, если это XXYY.

Answer 3

Абсолютно нет необходимости включать математику с плавающей запятой в эту задачу вообще.Вот эффективный фрагмент кода, который сделает эту работу за вас.

Поскольку ваш номер должен быть идеальным квадратом, быстрее проверить только идеальные квадраты, а не все четырехзначные числа, отфильтровываяквадраты (как вы бы это делали в первом наивном решении).

Возможно также безопаснее делать это с целыми числами, а не со значениями с плавающей запятой, так как вам не нужно беспокоиться овсе эти ошибки неточности при выполнении вычисления квадратного корня.

#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;
}

Он основан на том факте, что первый четырехзначный совершенный квадрат равен 32 * 32 или 1024 (31 ² 961).Таким образом, он проверяет 32 ² , 33 ² , 34 ² и т. Д. До тех пор, пока вы не превысите четырехзначный предел (тот, который равен 100 ^2). всего 69 возможностей, тогда как наивное решение проверит около 9000 возможностей.

Затем, при каждой возможности, он проверяет цифры для вашего окончательного требования XXYY, давая вам единственный ответ:

7744

Answer 4

#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

Answer 5

Пока я чувствую запах домашней работы, вот несколько советов. Проблема с этим решением состоит в том, что вы берете квадратный корень, который вводит арифметику с плавающей запятой и проблемы, возникающие в точной математике. Вы можете приблизиться, сделав что-то вроде:

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

Возможно, стоит переписать этот алгоритм, чтобы просто проверить, соответствует ли число этому формату, проверяя квадраты постоянно растущих чисел. Максимальное число, которое вам нужно проверить, не соответствует квадратному корню из наивысшего идеального квадрата, который вы ищете. то есть sqrt (9988) = 99,93 ... так что вам все равно нужно протестировать не более 100 номеров. Думаю, самое низкое число, которое вы можете проверить, - 1122, так что вы можете начать считать с 34.

Есть даже лучшие решения, которые включают факторинг (и использование оператора по модулю) но я думаю, что пока достаточно подсказок. ; -)

Answer 6

Вам не нужно брать квадратные корни. Обратите внимание, что вы можете легко генерировать все целочисленные квадраты и все числа XXYY в порядке возрастания. Так что вам просто нужно сделать один проход через каждую последовательность в поисках совпадений:

 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++ ; }
   }

Answer 7

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" ;

Answer 8

Способ генерации чисел неверный действительно правильный (мой плохой), поэтому все, что вам нужно, это правильный способ найти квадрат. :)

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

см. Здесь, как найти подходящий квадрат Идеальный квадрат и идеальный куб

Answer 9

Чтобы проверить, является ли sqrt(x) целым числом, сравните его с итоговым значением:

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

Однако на самом деле это плохой способ сравнения значений с плавающей запятой из-за проблем с точностью. Вы всегда должны учитывать небольшой компонент ошибки:

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

Даже если вы сделаете это исправление, ваша программа будет по-прежнему выводить sqrt(z), когда звучит так, как будто вы хотите, чтобы вывести z. Вы также должны перебрать все значения y, вместо того, чтобы просто учитывать y=4 (обратите внимание, что y также может быть 0, в отличие от x).