Странные числа

Question

Вот свойства «странных чисел» в задаче, которую я делаю:

1) У них четное число десятичных цифр (без начальных нулей).

2) Определите левую половину как число, представленное самой старшей половиной цифр исходного числа, а правую половину - той, которая представлена ​​наименее значимой половиной. Правая половина может иметь ведущие нули. Странное число - квадрат суммы его половинок: 81 = (8 + 1) ^ 2

Вот еще несколько примеров: 998001 = (998 + 001) ^ 2, 3025 = (30 + 25) ^ 2

Как мне написать программу, которая перечисляет все странные числа в порядке возрастания, которые имеют не более 18 десятичных цифр?

Я понимаю, как это сделать, рассматривая все возможности (числа с 2 цифрами, 4 цифры, 6 цифр, ..., 18 цифр), но для этого потребуются дни. Есть ли какие-то шаблоны, чтобы я мог вывести все странные числа в считанные секунды? Я бы предпочел ответы на Java, но псевдокод тоже подойдет.

Answer 1

Все эти «странные» числа являются идеальными квадратами. Таким образом, вы можете начать с просмотра всех чисел и возведения их в квадрат (пока в квадрате не будет больше 18 цифр). И для каждого квадрата проверьте, не странно ли это.

Редактировать Я также добавлю, что причина, по которой это так сильно ускоряется, в том, что оно меняет решение с O (n) на O (√n)

Answer 2

Помимо ускорения @ spatulamania, вы можете использовать арифметику по модулю для дальнейшего ускорения проверок.

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

Вместо этого вы можете сначала проверить только последние цифры двух частей (и возвести в квадрат их сумму). Например, для числа 99980001 возьмите цифры 8 и 1, возьмите квадрат (8+1)^2 = 9^2 = 81 и проверьте, что последняя цифра (1 в данном случае) совпадает с последней цифрой 99980001 (Я назову это как «мелкий чек»). Если да, перейдите к полной проверке.

Поскольку таких комбинаций всего 10х10 = 100, это нужно сделать один раз. Вы создадите массив допустимых комбинаций, которые вы можете использовать:

0   0
0   1
8   1
4   4
8   4
0   5
0   6
8   6
4   9
8   9

Используя это, вам нужно будет сделать только "маленькую проверку" для примерно 82% совершенных квадратов (те, которые не проходят проверку маленькой) и обе проверки для остальных 18% (которые проходят маленькую проверку). проверьте, так что "полная проверка" тоже понадобится). Поэтому, если «маленькая проверка» может быть выполнена достаточно быстро, вы получите некоторую скорость.

Вы можете найти еще быстрее расширить эту таблицу для последних 2 цифр двух частей и использовать ее (когда n достаточно велико).

Answer 3

class strange_number
{
    int number(int n)
    {
        int x = n;
        String a = Integer.toString(n);
        int d = a.length();
        if(((int)(Math.pow(((x%(int)(Math.pow(10,d/2)))+(x/(int)(Math.pow(10,d/2)))),2))) == x)
        return 1;
        else
        return 0;
    }
}

можно попробовать таким образом. Это может помочь вам.