БлогNot. Адамовы числа

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

Адамовы числа

Числа Адама (не нашёл ссылки на русском вообще, и в английской "Вики" тоже) - это такие натуральные числа, для которых квадрат числа с обратным порядком цифр имеет обратный порядок цифр по отношению к квадрату исходного числа :)

Если проще, то, например, 122=144, а 212=441, значит, 12 - число Адама.

Для небольших чисел, квадрат которых "влазит" в целый тип (например, для 4-байтового беззнакового целого предел - всего лишь корень(INT_MAX)==46341) можно посчитать парой строчек кода, если же числа нужны побольше, подойдёт умножение числа на массив цифр вот отсюда или другой подобный подход.

Приложенная ниже программка выводит в консоль и в текстовый файл numbers.txt все числа Адама до 10000000, впрочем, такая граница поиска была и не нужна, коль скоро они все состоят только из нулей, единиц, двоек и троек. Да и видно из получившегося ряда, что дальше. Проверено в консоли QT 5.X.

Есть мысль, где это пригодится, но, наверное, потом.

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

#define MAX_DIGITS 1000 /*максимально допустимое количество цифр*/

template <typename T>
void reverse_array( T *to_array, T *from_array, size_t N) {
    //Перевернуть массив from_array и записать в to_array
 T temp;
 for( size_t i = 0; i < N / 2; ++i ) {
     temp = from_array[i]; //Если окажется to-array == from_array
     to_array[i] = from_array[N-i-1];
     to_array[N-i-1] = temp;
 }
}

template <typename T>
int compare_array( T *to_array, T *from_array, size_t N) {
    //Сравнить массивы from_array и to_array, вернуть 0, если равны
    for( size_t i = 0; i < N; ++i ) {
        if (from_array[i] != to_array[i]) return from_array[i]-to_array[i];
    }
    return 0;
}

template <typename T>
void print_array( T *array, size_t N) { //Отладочная печать массива цифр
    cout << endl;
    for( size_t i = 0; i < N; ++i ) cout << array[i];
}

size_t multiply(size_t x, size_t res[], size_t res_size) {
 //Умножаем x на число res[], его количество цифр д.б. в res_size
 //Изменит массив res и вернёт новый res_size
 int temp = 0;
 for (size_t i = 0; i < res_size; i++) {
  size_t prod = res[i] * x + temp;
  res[i] = prod % 10;
  temp = prod / 10;
 }
 while (temp) {
  res[res_size] = temp % 10;
  temp = temp / 10;
  res_size++;
 }
 return res_size;
}

size_t reverseDigits(size_t num) {
    //Поменять порядок цифры в числе num без использования строк
    size_t rev = 0;
    while (num > 0) {
        rev = rev * 10 + num % 10;
        num /= 10;
    }
    return rev;
}

template <typename T>
void put_number (size_t num, T *a, size_t &a_size) {
    //Положить число num в массив цифр a, размерность массива будет в a_size,
    //контроля памяти нет
    a_size = 0;
    size_t temp = num;
    while (temp != 0) {
     a[a_size++] = temp % 10;
     temp = temp / 10;
    }
}

bool checkAdamNumber(size_t num) { //Проверить очередное число
    size_t a[MAX_DIGITS],b[MAX_DIGITS];
    size_t a_size,b_size;
    put_number (num,a,a_size);
    a_size = multiply(num, a, a_size); // a = num * num;
    reverse_array(b, a, a_size); // b = reverseDigits(num);
    size_t num2 = reverseDigits(num);
    put_number (num2,b,b_size);
    b_size = multiply(num2, b, b_size); // b = b * b;
    reverse_array(b, b, b_size);
    //print_array (a, a_size); print_array (b, b_size);
    return (compare_array(a,b,a_size)==0 ? true : false);
}

int main() {
 ofstream f("numbers.txt");
 for (int i=0; i<=10000000; i++) {
     if (checkAdamNumber(i)) {
         cout << i << " ";
         f <<  i << endl;
     }
 }
 f.close();
 cin.get(); return 0;
}

 Файл numbers.txt, содержащий все числа Адама до 10000000 (7 Кб)


теги: числа алгоритм c++

19.03.2018, 10:23; рейтинг: 201

  свежие записипоиск по блогукомментариистатистика

Наверх Яндекс.Метрика
© PerS
вход