Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
dyap
2 / 2 / 0
Регистрация: 20.09.2010
Сообщений: 58
20.09.2010, 20:07     Программа для нахождения автоморфных чисел. #1
Задача такая: Напечатать 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 пар?...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
D@rkD@iver
110 / 110 / 3
Регистрация: 01.10.2008
Сообщений: 876
20.09.2010, 21:17     Программа для нахождения автоморфных чисел. #2
можешь
поменяй в n, не 6 а 2
а увеличить
поменяй все int на int68

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

Не по теме:

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

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. реализацию в коде я не придумал
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 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;
}
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 чисел не выводит...
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 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;
}
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 19:36     Программа для нахождения автоморфных чисел. #13
.....
Миниатюры
Программа для нахождения автоморфных чисел.  
dyap
2 / 2 / 0
Регистрация: 20.09.2010
Сообщений: 58
21.09.2010, 19:38  [ТС]     Программа для нахождения автоморфных чисел. #14
PointsEqual,
Это как раз почти то, что мне нужно. Один момент, можно ли сделать чтобы кол-во чисел можно было выбрать в консоли, а не в самом коде меня значение?
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 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. Парадокс)
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 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;
}

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

492 секунды высчитывал)
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
21.09.2010, 23:41     Программа для нахождения автоморфных чисел. #19
Длинка. Очевидно, что дальнейший поиск втупую будет очень долгим.
Взглянем на последовательность. Заметим закономерность - последовательность (начиная с третьего элемента) состоит из двух подпоследовательностей, в каждой из которых последующий элемент получается приписыванием цифры к предыдущему. Но есть исключения - взглянем на "соседние" числа 9376 и 109376. Если позволить ведущие нули, то число 09376 является полноценным автоморфным числом. Однако ведущие нули обычно запрещают, поэтому подобные числа надо пропускать, но при этом не обрывать последовательность на них.
Особо заинтересовавшимся сюда:
http://acm.timus.ru/problem.aspx?space=1&num=1698
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2010, 23:43     Программа для нахождения автоморфных чисел.
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
21.09.2010, 23:43     Программа для нахождения автоморфных чисел. #20
Цитата Сообщение от Хохол Посмотреть сообщение
Длинка
такой вариант думал - не хочу.

у меня не тупой перебор, тупой перебор был в 10 посте и не высчитывалось даже 10-е число.
Yandex
Объявления
21.09.2010, 23:43     Программа для нахождения автоморфных чисел.
Ответ Создать тему
Опции темы

Текущее время: 22:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru