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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.77
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
#1

Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром - C++

06.03.2012, 18:36. Просмотров 2946. Ответов 12
Метки нет (Все метки)

Найти все простые натуральные числа, не превосходящие n, двоичная
запись которых представляет собой палиндром, т.е. читается одинаково слева направо и справа налево.
Простые натуральные числа это 2,3,5,7 да?
Они должны представляться как 2 системе, т.е.
2 - 0010
3 - 0011
5 - 0101(подходит только это, т.к. читается слева на право одинаковое)
7 - 0111
Я правильно понял?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2012, 18:36     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
Посмотрите здесь:
C++ Найти все натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
Найти простые натуральные числа запись которых представляет собой палиндром C++
C++ Найти 4-х значные числа, запись которых в hex представляет собой палиндром
Найти все натуральные числа, не превосходящие заданного и десятичная запись которых последовательность C++
C++ Циклы.Найти все натуральные числа не превосходящие заданного n, десятичная запись которых есть строго убывающая последовательность цифр
Найти все простые числа, не превосходящие заданного числа, сумма цифр которых, также является простым числом C++
Найти все простые числа, не превосходящие N, в десятичном представлении которых, нет совпадающих цифр C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ZiGSuN
27 / 27 / 2
Регистрация: 02.12.2009
Сообщений: 66
06.03.2012, 18:40     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #2
про простые натуральные числа ты понял правильно
а вот палиндром это когда справа-налево читается так же как и слева-направо например 17- 10001
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
06.03.2012, 18:42  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #3
Цитата Сообщение от ZiGSuN Посмотреть сообщение
нет, палиндром это когда справа-налево читается так же как и слева-направо например 17- 10001
А да, но просты натуральные числа это 2,3,5,7 да? в двоичной системе у этих чисел нет такого, чтобы читалось слева на право и наоборот одинаково.
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,444
06.03.2012, 18:44     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #4
Цитата Сообщение от Scaletta Посмотреть сообщение
5 - 0101(подходит только это, т.к. читается слева на право одинаковое)
слева направо — 0101, справа налево — 1010. Где же здесь «одинаково»?

PS. Определение слова «палиндром» можно посмотреть на Википедии.

Добавлено через 43 секунды
Цитата Сообщение от Scaletta Посмотреть сообщение
в двоичной системе у этих чисел нет такого, чтобы читалось слева на право и наоборот одинаково.
а это что тогда?
Цитата Сообщение от ZiGSuN Посмотреть сообщение
а вот палиндром это когда справа-налево читается так же как и слева-направо например 17- 10001
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
06.03.2012, 19:26  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #5
Тогда как мне перести из натуральных чисел в двоичную систему в С++?

Добавлено через 36 минут
Цитата Сообщение от Scaletta Посмотреть сообщение
Тогда как мне перести из натуральных чисел в двоичную систему в С++?
Вот ввести число 55
потом идет цикл
for (i=1;i<=n;i++)
если число натурально=>переводит в 2систему
если нет, ошибка
Как это показать в программе?
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
10.03.2012, 15:52  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #6
Никто не объясни как сделать задачку?
sandye51
программист С++
681 / 583 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
10.03.2012, 16:03     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #7
наверно надо считать только значащие цифры, поэтому 0101 == 101 - полиндром
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,444
10.03.2012, 16:04     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #8
Цитата Сообщение от sandye51 Посмотреть сообщение
наверно надо считать только значащие цифры
я думаю, нужно добавлять и удалять ведущие нули у числа слева от знака сравнения в зависимости от количества значащих разрядов у числа справа от знака сравнения, т.к. 0101 == 1010 — тоже палиндром.
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
10.03.2012, 16:05  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #9
Цитата Сообщение от sandye51 Посмотреть сообщение
наверно надо считать только значащие цифры, поэтому 0101 == 101 - полиндром
Проблема состоит в том, что я могу все это представить, а как написать в программе не знаю, т.к. с этого семестра начали проходить программирование, я себя этим не оправдываю. Как мне избавиться от этой проблемы, знаю, но не пойму как показать в программе?
sandye51
программист С++
681 / 583 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
10.03.2012, 16:18     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #10
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
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <cmath>
 
bool is_simple(unsigned int n)
{
    for (unsigned int i = 2, end = static_cast<unsigned int>(pow(static_cast<double>(n), 0.5)); i <= end; ++i)
        if (n % i == 0)
            return false;
    
    return true;
}
 
bool poly(unsigned int n)
{
    unsigned int size = static_cast<unsigned int>(log2(static_cast<double>(n))) + 1;
    char* number = new char[size];
    for (unsigned int i = 0; i < size; ++i)
    {
        number[i] = n & 1 ? '1' : '0';
        n >>= 1;
    }
    
    for (unsigned int i = 0; i < size / 2; ++i)
        if (number[i] != number[size - i - 1])
            return false;
 
    delete[]number;
    return true;
}
 
int main()
{
    unsigned int n;
    
    std::cout << "Введите n: " << std::endl;
    std::cin >> n;
    
    std::cout << "Ответ: " << std::endl;
    for (unsigned int i = 1; i <= n; ++i)
        if (is_simple(i))
            if (poly(i))
                std::cout << i << " ";
    std::cout << std::endl;
    
    system("Pause");
    return EXIT_SUCCESS;
}
сделал так, как имел ввиду выше
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.03.2012, 10:05     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #11
Более оптимальный перебор:
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
#include <iostream>
#include <vector>
#include <cstdio>
 
bool is_poly( unsigned x )
{
    static char bits[32];
    int i = 0;
    
    for ( ; x != 0; x >>= 1)
            bits[i++] = x & 1;
    
    for (int j = 0; j < (i >> 1); ++j)
        if ( bits[j] != bits[i - j - 1] )
            return false;
            
    return true;;
}
 
int main()
{   
    int n;
    
    if ( !(std::cin >> n) )
    {
        std::cerr << "Incorrect input!" << std::endl;
        return 1;
    }
    
    std::vector< bool > sieve( (n >> 1) + 1);
    
    for (int i = 3; i * i <= n; i += 2)
    {
        if ( !sieve[i >> 1] )
        {
            for (int j = (i << 1); j <= n; j += i)
                if ( j & 1 )
                    sieve[j >> 1] = 1;
        }
    }
    
    for (int i = 3; i <= n; i += 2)
    {
        if ( !sieve[i >> 1] && is_poly(i) )
        {
            std::cout << i << ' ';
        }
    }
}
Для n = 10^8 у меня чуть больше секунды работает. Кушает n / 16 байт памяти.
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
12.03.2012, 22:21  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #12
Цитата Сообщение от sandye51 Посмотреть сообщение
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
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <cmath>
 
bool is_simple(unsigned int n)
{
    for (unsigned int i = 2, end = static_cast<unsigned int>(pow(static_cast<double>(n), 0.5)); i <= end; ++i)
        if (n % i == 0)
            return false;
    
    return true;
}
 
bool poly(unsigned int n)
{
    unsigned int size = static_cast<unsigned int>(log2(static_cast<double>(n))) + 1;
    char* number = new char[size];
    for (unsigned int i = 0; i < size; ++i)
    {
        number[i] = n & 1 ? '1' : '0';
        n >>= 1;
    }
    
    for (unsigned int i = 0; i < size / 2; ++i)
        if (number[i] != number[size - i - 1])
            return false;
 
    delete[]number;
    return true;
}
 
int main()
{
    unsigned int n;
    
    std::cout << "Введите n: " << std::endl;
    std::cin >> n;
    
    std::cout << "Ответ: " << std::endl;
    for (unsigned int i = 1; i <= n; ++i)
        if (is_simple(i))
            if (poly(i))
                std::cout << i << " ";
    std::cout << std::endl;
    
    system("Pause");
    return EXIT_SUCCESS;
}
сделал так, как имел ввиду выше
Спасибо огромное...но я тут вообще толком ничего не пойму...

Добавлено через 4 минуты
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
#include<iostream>
using namespace std;
int main()
{
    setlocale(0,"russian");
    system ("color 70");
    
     int n,i,d;
     d=2;
     aa: cout<<"Введите n=";
     cin>>n;
     for (i=2; i<n ; i++)
     {
      if (n%d==0)
      {
          cout<<"Простое число"<<endl;
      }
      else
      {
          cout<<"Ошибка"<<endl;goto aa;
      }
         system ("pause");
      return 0;
}
почему ответ такой выходит http://i31.***********/big/2012/0312/...5ecf0aa3b.jpeg

Добавлено через 3 минуты
C++
1
2
3
4
5
6
for (int i=3; i>=n; i--)
      {
       int bit = ((n >> i) & 1);
       cout << bit;
      }
      cout<<endl;
В интернете нашел как перевести в двоичную систему, как мне состыковать с выше написанной программой?
Не судите строго, хочу разобраться...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.03.2012, 11:03     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
Еще ссылки по теме:
C++ Найти все такие простые числа, не превосходящие заданного N, в троичной записи которых цифра 2, встречается заданное число раз
a) Найти все натуральные числа, не превосходящие К C++
Найти все натуральные числа, не превосходящие заданного n C++
Найти все натуральные числа не превосходящие заданного C++
Найти все натуральные числа <= n, десятичная запись которых - строго упорядоченная последовательность C++

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

Или воспользуйтесь поиском по форуму:
Scaletta
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 29
18.03.2012, 11:03  [ТС]     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром #13
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
#include<math.h>
#include<stdio.h>
#include<conio.h>
using namespace std;
 bool simple (int n)
{
         for( int i=2; i<=n/2; i++)
         {
             if(n%2==0) 
                 return 0;
             return 1;
         }
     }
int main()
{
    setlocale(0,"russian");
    system ("color 70");
    cout<<"Работу выполнил ст. гр. И-21"<<endl;
    int n,i,c,B,p,b;
    cout<<"Введите n=";
    cin>>n;
    if (simple(n)) 
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
     for (int i=2; n>0; i++)
     {
         c=n%2;
         n/=2;
         B=B*10+c;
         b=b+c*p;
         p*=10;
 
     }
     system ("pause");
     return 0;
}
Особых продвижений в этом нет, но сдвинулся с мертвой точки.
У меня получилось все таки проверить на простоту число, есть даже перевод в двоичную систему и палиндром, помогите все по полочкам разложить. Спасибо

Добавлено через 3 часа 15 минут
Ну что поможет кто?
Yandex
Объявления
18.03.2012, 11:03     Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
Ответ Создать тему
Опции темы

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