Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.81/16: Рейтинг темы: голосов - 16, средняя оценка - 4.81
dyap
2 / 2 / 0
Регистрация: 20.09.2010
Сообщений: 58
1

Программа для нахождения автоморфных чисел.

20.09.2010, 20:07. Просмотров 3053. Ответов 19
Метки нет (Все метки)

Задача такая: Напечатать N автоморфных чисел (автоморфным называется число, совпадающее с младшими цифрами своего квадрата). ( напр. 25,625; 6,36).
Пока есть такая программа
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
 
void main()
{
    const int N = 6; // Большее число не влезет в int.
    
    int CurrentN = 0;
    int Counter = 0;
 
    while(CurrentN < N)
    {
        char Buffer1[20];
        char Buffer2[20];
        char* StrCounter = itoa(Counter, Buffer1, 10);
        char* StrDoubleCounter = itoa(Counter * Counter, Buffer2, 10);
        if(strcmp(&StrDoubleCounter[strlen(StrCounter)], StrCounter) == 0)
        {
            printf("%s => %s\n", StrDoubleCounter, StrCounter);
            CurrentN++;
        }
        Counter++;
    }
    getchar();
}
Вопрос: можно ли как-нибудь сделать, чтобы программа выдавала определенное кол-во пар, например 2. А не сразу все 6.
И еще вопрос: возможно ли сделать поиск больше, чем 6 пар?...
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.09.2010, 20:07
Ответы с готовыми решениями:

Программа для нахождения простых чисел от 1 до 100
Здравствуйте, в задании требуется написать программу для нахождения простых...

Программа для нахождения всех совершенных чисел до 5000
Мне нужно написать программу 1)которая найдет все числа до числа a, например...

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

Программа для нахождения суммы квадратов всех нечетных чисел
Знаю,что неправильно считает,3 раза подряд выдало 165,хотя вручную совсем...

Программа для нахождения к-ой цифры в ряду подряд идущих натуральных чисел.
Найти k-ую цифру в ряду цифр, составленных из подряд идущих натуральных чисел,...

19
D@rkD@iver
112 / 112 / 13
Регистрация: 01.10.2008
Сообщений: 876
20.09.2010, 21:17 2
можешь
поменяй в n, не 6 а 2
а увеличить
поменяй все int на int68

Добавлено через 54 секунды
й сорри не int68 а __int64
1
asics
Freelance
Эксперт С++
2858 / 1793 / 355
Регистрация: 09.09.2010
Сообщений: 3,841
20.09.2010, 21:20 3
Цитата Сообщение от D@rkD@iver Посмотреть сообщение
__int64
Шо ето ?
0
D@rkD@iver
112 / 112 / 13
Регистрация: 01.10.2008
Сообщений: 876
20.09.2010, 21:26 4
тип 64-битное число
1
asics
Freelance
Эксперт С++
2858 / 1793 / 355
Регистрация: 09.09.2010
Сообщений: 3,841
20.09.2010, 21:28 5
Цитата Сообщение от D@rkD@iver Посмотреть сообщение
тип 64-битное число
хм,незнал про такое.
0
dyap
2 / 2 / 0
Регистрация: 20.09.2010
Сообщений: 58
20.09.2010, 22:00  [ТС] 6
А как сделать, чтобы n можно было выбрать в консоли, а не в самом коде?
И __int64 не помогло, если ввести 10, то чисел будет всего 7, и то 7 уже не корректо отображается, тоесть не полностью и с минусом.
0
D@rkD@iver
112 / 112 / 13
Регистрация: 01.10.2008
Сообщений: 876
20.09.2010, 22:16 7
ну значит ничего не подулаешь, это теоритически невозможно
cin>>n;
0
papochka
20.09.2010, 23:17
  #8

Не по теме:

аж стало интересно - http://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html ...

0
Semapv
0 / 0 / 0
Регистрация: 19.09.2010
Сообщений: 11
20.09.2010, 23:59 9
Как мне кажется алгоритм должен быть другим, вам ведь нужен только младшие разряды, а для поиска старшие не нужны: например при проверке является ли 25 автоморфным, вам вовсе не нужна 6 из числа 625, достаточно узнать что первые два знака 25, а потом уже и вычислять оставшиеся числа и выводить.
можно так, в 25 * 25 = 625, а это 25 * 5 + 25 *20 = 625, нам же будет вообще достаточно 25 * 5 + 05 * 20 = 225, уже сейчас видно что данное число нам подходит, в данном примере не сильно заметна выгода но при больших числах, разница будет велика, и мы лучше сможем использовать емкость int. реализацию в коде я не придумал
0
PointsEqual
ниначмуроФ
842 / 526 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 09:15 10
Цитата Сообщение от dyap Посмотреть сообщение
Напечатать N автоморфных чисел (автоморфным называется число, совпадающее с младшими цифрами своего квадрата)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <iomanip>
 
bool isauthomorf(int x){
    int res = x*x;
    int tmp = x;
 
    while ( tmp ){
        if ((tmp % 10) != (res % 10))
            return false;
        res  /= 10;
        tmp /= 10;
    }
    return true;
}
 
int main()
{
    int cnt = 6; //количество нужных чисел
    int i = 1;
 
    while ( cnt ){
        if (isauthomorf(i) ){
            std::cout << i << std::setw(6);
            --cnt;
        }
        ++i;
    }
 
    return 0;
}
0
dyap
2 / 2 / 0
Регистрация: 20.09.2010
Сообщений: 58
21.09.2010, 17:07  [ТС] 11
Цитата Сообщение от PointsEqual Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <iomanip>
 
bool isauthomorf(int x){
    int res = x*x;
    int tmp = x;
 
    while ( tmp ){
        if ((tmp % 10) != (res % 10))
            return false;
        res  /= 10;
        tmp /= 10;
    }
    return true;
}
 
int main()
{
    int cnt = 6; //количество нужных чисел
    int i = 1;
 
    while ( cnt ){
        if (isauthomorf(i) ){
            std::cout << i << std::setw(6);
            --cnt;
        }
        ++i;
    }
 
    return 0;
}
10 чисел не выводит...
0
PointsEqual
ниначмуроФ
842 / 526 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 19:35 12
Цитата Сообщение от dyap Посмотреть сообщение
10 чисел не выводит...
так пусть выводит минимум 15!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
 
int cnt_digit(int x); // подсчет количества цифр числа
bool isauthomorf(int x);
 
int main(){
 
    int cnt = 15; //количество нужных чисел
    int i = 1;
 
    while ( cnt ){
        if (isauthomorf(i) ){
            std::cout << i << std::endl;
            --cnt;
        }
        ++i;
    }
 
 
    return 0;
}
 
 
 
bool isauthomorf(int x){
    int i = x;
    int tmp = i; //tmp is douplicate i
    int cnt = cnt_digit( i );
    int del = 1; //делитель
    int k = 1; //коэффициент домножения
    int b = 0; //результат умножения i на каждую цифру tmp
    int s = 0;
 
    for (int j = 0; j < cnt; ++j)
        del *= 10;
    int copy_del = del;
 
    while ( tmp ){
        b = i * (tmp % 10);
        tmp /= 10;
        b = ( b % del ) * k;
        del /= 10;
        k *= 10;
        s += b;
    }
 
    return ( (s % copy_del) == i ) ? true : false;
}
 
 
 
int cnt_digit(int x){
    int cnt = 0;
    int tmp = x;
    while (tmp){
        tmp /= 10;
        ++cnt;
    }
    return cnt;
}
1
PointsEqual
ниначмуроФ
842 / 526 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 19:36 13
.....
1
Миниатюры
Программа для нахождения автоморфных чисел.  
dyap
2 / 2 / 0
Регистрация: 20.09.2010
Сообщений: 58
21.09.2010, 19:38  [ТС] 14
PointsEqual,
Это как раз почти то, что мне нужно. Один момент, можно ли сделать чтобы кол-во чисел можно было выбрать в консоли, а не в самом коде меня значение?
0
PointsEqual
ниначмуроФ
842 / 526 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 19:58 15
Цитата Сообщение от dyap Посмотреть сообщение
можно ли сделать чтобы кол-во чисел можно было выбрать в консоли
C++
1
cin >> cnt;
Добавлено через 17 минут
хм, странно на http://ru.wikipedia.org/wiki/Автоморфное_число говорится что последовательность начинается с 1, и там же приведена последовательность A003226, в которой говорится что последовательность начинается с 0. Парадокс)
1
PointsEqual
ниначмуроФ
842 / 526 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 23:12 16
мой алгоритм выводит только 17 Автоморфных чисел , на 18 - получается какое то магическое число



сам алгоритм

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isauthomorf(unsigned int x){
    unsigned int i = x;
    unsigned int tmp = i; //tmp is doublicat i
    unsigned int cnt = cnt_digit( i );
    unsigned int del = 1; //делитель
    unsigned int k = 1; //коэффициент домножения
    unsigned int b = 0; //результат умножения i на каждую цифру tmp
    unsigned int s = 0;
 
    for (unsigned int j = 0; j < cnt; ++j)
        del *= 10;
    unsigned int copy_del = del;
 
    while ( tmp ){
        b = i * (tmp % 10);
        tmp /= 10;
        b = ( b % del ) * k;
        del /= 10;
        k *= 10;
        s += b;
    }
 
    return ( (s % copy_del) == i ) ? true : false;
}

может кто нибудь подскажет как улучшить его?
0
Миниатюры
Программа для нахождения автоморфных чисел.  
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
21.09.2010, 23:23 17
Ну для начала поменять int на long long.
1
PointsEqual
ниначмуроФ
842 / 526 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 23:34 18
Цитата Сообщение от Хохол Посмотреть сообщение
поменять int на long long.
помогло.
Еще.

492 секунды высчитывал)
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
21.09.2010, 23:41 19
Длинка. Очевидно, что дальнейший поиск втупую будет очень долгим.
Взглянем на последовательность. Заметим закономерность - последовательность (начиная с третьего элемента) состоит из двух подпоследовательностей, в каждой из которых последующий элемент получается приписыванием цифры к предыдущему. Но есть исключения - взглянем на "соседние" числа 9376 и 109376. Если позволить ведущие нули, то число 09376 является полноценным автоморфным числом. Однако ведущие нули обычно запрещают, поэтому подобные числа надо пропускать, но при этом не обрывать последовательность на них.
Особо заинтересовавшимся сюда:
http://acm.timus.ru/problem.aspx?space=1&num=1698
0
PointsEqual
ниначмуроФ
842 / 526 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 23:43 20
Цитата Сообщение от Хохол Посмотреть сообщение
Длинка
такой вариант думал - не хочу.

у меня не тупой перебор, тупой перебор был в 10 посте и не высчитывалось даже 10-е число.
0
21.09.2010, 23:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2010, 23:43

Определить количество автоморфных чисел на заданном отрезке
#include &lt;iostream&gt; #include &lt;cmath&gt; using namespace std; int main() { ...

Программа нахождения совершенных чисел
Нужно написать программу которая выводит совершенные числа...

Программа нахождения простых чисел
Я написал программу но в ней ошибка! Не пойму какая! Но мне важно понять как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru