C/C++

Написать программу на языке Си, которая решит эту задачу:

Написать программу на языке Си, которая решит эту задачу:
Найти квадраты целых чисел, которые можно читать как обычным образом, так и справа налево. Некоторые из них найти очень легко. Например, квадраты чисел 1, 11, 111 и 1111 равны соответственно 1, 121, 12321 и 1 234321.Все получившиеся числа — палиндромы, и данное правило применимо к любому числу единиц, не превосходящему 9. Однако существуют и другие случаи, которые мы могли бы назвать нерегулярными. Например, 2642 = 69 696, а 22852 = 5 221 225. Во всех приведенных выше примерах число цифр было нечетным. Приведите примеры с четным числом цифр.
836^2=698896
На Си обычный перебор лениво писать, сам как-нибудь, а уж проверку числа на "палиндромность" наверняка в гугле можно найти
Тющенко Антон
Тющенко Антон
25 516
Лучший ответ
С обычным перебором на С++:
#include <iostream>
#include <vector>
using namespace std;
bool digits(unsigned long long x)
{
vector <int> d;
while (x)
{
d.push_back(x % 10);
x /= 10;
}
int m, n = d.size(), l = n - 1, k = 1;
for (m = 0; m < n / 2; m++)
{
if (d[m] != d[l - m])
{
k = 0;
break;
}
}
return k;
}
int main()
{
unsigned long long l = 0, m;
for (unsigned n = 1; n < 4294967295; n++)
{
m = n;
m *= n;
if (digits(m))
{
l++;
cout << l << ") " << n << "²=" << m << endl;
}
}
}
На Си:
#include <stdio.h>
int digits(unsigned long long x)
{
int k = 1, l, m, n = 0, d[20];
while (x)
{
d[n] = x % 10;
x /= 10;
n++;
}
l = n - 1;
for (m = 0; m < n / 2; m++)
{
if (d[m] != d[l - m])
{
k = 0;
break;
}
}
return k;
}
int main()
{
unsigned l = 0, n;
unsigned long long m;
for (n = 1; n < 4294967295; n++)
{
m = n;
m *= n;
if (digits(m))
{
l++;
printf("%u) %u²=%llu\n", l, n, m);
}
}
}
Зачем два варианта? А затем, чтобы в случае необходимости проверить, что использование плюсов в такого рода задачах не даёт никаких преимуществ ни по времени написания программы, ни по времени её исполнения. И чистый Си здесь, наверно, даже предпочтительнее.
Теперь по поводу алгоритма. Иногда говорится, о чём я даже на лекциях слышала неоднократно, что хороший алгоритм стоит целого компьютера. Вот тут, по-моему, как раз такой случай и есть. Программа простая и надёжная, работает правильно, но сам алгоритм слишком простой, чтобы быть правильным: у меня разбор каждого нового натурального числа на цифры происходит заново, а ведь это неправильно, так как можно сделать намного быстрее! Интересно, кто здесь возьмётся оптимизировать мой код или написать свой, более оптимальный?
Иван Базылюк
Иван Базылюк
66 572
Garnik Minasyan "кто здесь возьмётся оптимизировать мой код или написать свой"
Писать, повторюсь, лениво, но мыслей могу понакидать.
1. Самое очевидное, так как задача на "примеры с четным числом цифр", то проверять на палиндромы только после проверки количества цифр.
2. Квадрат всегда заканчивается на 14569, пока не придумал можно ли что-то выгадать, откидывая результаты на сравнении старшего разряда вместо младшего с этими значениями, но подумать стоит, наверное.
3. Сам расчет квадратов выгодней сделать по формуле N^2=сумма первых N нечетных натуральных чисел.
4. Попробовать перевернуть задачу - строим палиндромы и проверяем на квадратность. Тут у меня сомнения в эффективности.