Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.70
Skorpi
0 / 0 / 0
Регистрация: 08.07.2011
Сообщений: 7
#1

Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. - C++

08.07.2011, 20:21. Просмотров 2707. Ответов 22

Помогите пожалуйста!
Среди простых чисел, не превосходящих n, найти такое, в двоичной записи которого максимальное число единиц.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2011, 20:21
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. (C++):

Среди простых чисел, не превосходящих N, найти такое, в десятичной записи которого максимальное число единиц - C++
Пожалуйста, помогите кто может очень срочно нужно((((

Найти число в двоичной записи которого максимальное число единиц - C++
Среди простых чисел ,не превосходящих N ,найти такое ,в двоичной записи которого максимальное число единиц. Уважаемые форумчане помогите...

Найти среди простых чисел, попадающих в этот промежуток, такое число, у которого сумма цифр максимальная - C++
1.В функцию передаются границы числового интревала. Найти среди простых чисел, попадающих в этот промежуток, такое число, у которого сумма...

Определить элемент массива, в двоичной записи которого максимальное число единиц - C++
Здравствуйте, помогите пожалуйста!:scratch: Задан массив целых чисел. Определить элемент этого массива, в двоичной записи которого...

Найти следующее после n число, в двоичной записи которого столько же единиц - C++
Доброго времени суток. Вопрос в названии темы, полное условие тут. Перебор не проходит. Пробовал #include <iostream> int...

Определить элемент этого массива, в двоичной записи которого максимальное число единиц - C++
Задан массив целых чисел. Определить элемент этого массива, в двоичной записи которого максимальное число единиц. С помощью чего можно...

22
silent_1991
Эксперт С++
5005 / 3063 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
08.07.2011, 20:46 #2
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
61
62
#include <iostream>
 
typedef unsigned long long ull_t;
 
bool is_prime(ull_t);
size_t binary_1_number(ull_t);
 
int main()
{
    ull_t num;
 
    std::cout << "Enter n: ";
    std::cin >> num;
 
    size_t last_max_binary_1_number = 1;
    ull_t last_max_binary_1_empty = 2;
 
    for (ull_t n = 3; n <= num; ++n)
    {
        if (is_prime(n))
        {
            size_t current_binary_1_number = binary_1_number(n);
 
            if (last_max_binary_1_number <= current_binary_1_number)
            {
                last_max_binary_1_number = current_binary_1_number;
                last_max_binary_1_empty = n;
            }
        }
    }
 
    std::cout << last_max_binary_1_empty << std::endl;
 
    return 0;
}
 
bool is_prime(ull_t num)
{
    if (num < 2)
        return false;
 
    for (ull_t i = 2; i * i <= num; ++i)
        if (num % i == 0)
            return false;
 
    return true;
}
 
size_t binary_1_number(ull_t num)
{
    size_t count = 0;
 
    while (num != 0)
    {
        if ((num & 1) == 1)
            ++count;
 
        num >>= 1;
    }
 
    return count;
}
1
asics
Freelance
Эксперт С++
2854 / 1789 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
08.07.2011, 20:46 #3
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
 
bool is_prime(int &n){
  for(int i = 2; i <= n / 2; ++i)
    if ( !(n % i) )
      return false;
  return true;
}
 
std::string int_to_str(int one, std::string &r){
  std::ostringstream ost;
  ost << one;
  r = ost.str();
  return r;
}
 
std::string dec_to_bin(int one){
  std::string res;
  const int numb_symb = 2;
  while(one){
    std::string first;
    res += int_to_str(one % 2, first);
    one /= 2;
  }
  std::reverse(res.begin(), res.end());
  return res;
}
 
int main(){
  int n;
  std::cin >> n;
  std::vector<int> v;
  for(int i = 2; i <= n; ++i)
    if(is_prime(i)) v.push_back(i);
  std::cout << *std::max_element(v.begin(), v.end(), [](int &a, int &b) -> bool{
    std::string s_a = dec_to_bin(a), s_b = dec_to_bin(b);
    return std::count(s_a.begin(), s_a.end(), '1') <
           std::count(s_b.begin(), s_b.end(), '1');
  });
  return 0;
}
1
nameless
Эксперт С++
338 / 302 / 14
Регистрация: 16.06.2009
Сообщений: 486
08.07.2011, 20:50 #4
Skorpi,

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
#include <iostream>
#include <bitset>
 
int GetEasyNumber(int MaxNumber)
{
   bool state = false;
   int MaxCount = 0;
   int NumberThisMaxBits;
   for (int num = 2; num <= MaxNumber; num++)
   {
      for (int i = 2; i < num && !state; i++)
         if (num % i == 0)
            state = true;
            
      if (!state)
      {
         std::bitset <32> bin_number(static_cast <unsigned long> (num));
         if (MaxCount < bin_number.count())
            NumberThisMaxBits = num;
         
      }
      state = false;
   }
   
   return NumberThisMaxBits;
}
 
int main()
{
   int number = 1000;
   
   std::cout << GetEasyNumber(number) << std::endl;
   
   return 0;
}
1
Зоти Сергей
229 / 227 / 13
Регистрация: 18.12.2009
Сообщений: 316
08.07.2011, 21:01 #5
Как-то вот так, короче:
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
#include <conio.h>
#include <iostream.h>
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
    int DigitsAmount;
    cout<<"Vvedite kolichestvo chisel N: ";
        cin>>DigitsAmount;
        if(DigitsAmount<=0)
        {
            cout<<"Oshibka!!! N doljno biti > 0";
        }
        int CurrentDigit;
        int BiggestAmountOfTrues=0;
        int Result=0;
 
        for(int i=0;i<DigitsAmount;i++)
        {
            cout<<"Vvedite chislo N "<<i+1<<": ";
            cin>>CurrentDigit;
            int Summ=0;
            for(int j=0;j<32;j++)
                {
                    Summ+=(CurrentDigit>>j)&0x01;
                }
 
                if(Summ>BiggestAmountOfTrues)
                {
                    BiggestAmountOfTrues=Summ;
                        Result=CurrentDigit;
                }
        }
    cout<<"\Chislo v kotorom bolishe vsego edinits = "<<Result;
 
        getch();
    return 0;
}
//---------------------------------------------------------------------------
1
grizlik78
Эксперт С++
1981 / 1474 / 127
Регистрация: 29.05.2011
Сообщений: 3,047
08.07.2011, 21:08 #6
Вариантов-то, вариантов!
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
#include <iostream>
 
int weight(int n); // Вес числа (количество единиц)
 
using namespace std;
 
int main()
{
    int n;
    cout << "Input max number: ";
    cin >> n;
    ++n;
    int *arr = new int[n];
 
    // Получение простых чисел
    // Инициализация
    for (int i = 0; i < n; ++i)
        arr[i] = i;
    // Решето Эратосфена
    for (int i = 2; i*i < n; ++i)
    {
        if (arr[i] > 0);
            for (int j = i*i; j < n; j += i)
                arr[j] = 0;
    }
 
    // Определение числа с максимальным весом (количеством единиц)
    int maxweight = 0;
    int num = 0;
    for (int i = 2; i < n; ++i)
    {
        if (weight(arr[i]) > maxweight)
        {
            maxweight = weight(arr[i]);
            num = arr[i];
        }
    }
    cout << "weight(" << num << ") = " << maxweight << endl;
 
    delete [] arr;
    return 0;
}
 
// Определение веса числа
int weight(int n)
{
    int cnt = 0;
    while (n)
    {
        ++cnt;
        n &= n-1;
    }
    return cnt;
}
1
xAtom
917 / 742 / 60
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
08.07.2011, 21:08 #7
Вот функция выводит бинарно-еденичный максимум из указанного кол-во числа чисел.
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
#include <iostream>
#include <stdarg.h>
using namespace std;
 
// параметр size - указывает на кол-во параметров
int  bin_max(int size, ...) {
   va_list arg;
   va_start(arg, size);
   int a = 0, b = 0, cnt = 0, tmp = 0, n = 0;
   while(size--) {
       cnt = va_arg(arg, unsigned int);
       tmp = cnt;
       for(; cnt; cnt >>= 1) {
          if(cnt & 0x1)
              a++;
       }
       if(a > b) {
          b   = a;
          n   = tmp;
       }
       a = 0;
   }
   va_end(arg);
   return  n;
}
 
 
 
int main(void) {
 
   cout << bin_max(2,   255,16)               << endl;
   cout << bin_max(4,   300,200,128,30)   << endl;
   cout << bin_max(7,   8,1,2,9, 0, 7, 4)   << endl;
   cout << bin_max(3,   24, 32, 64)          << endl;
 
   cin.get();
   return 0;
}
1
Skorpi
0 / 0 / 0
Регистрация: 08.07.2011
Сообщений: 7
08.07.2011, 21:26  [ТС] #8
Зоти Сергей спасибо большое, работает!
0
grizlik78
Эксперт С++
1981 / 1474 / 127
Регистрация: 29.05.2011
Сообщений: 3,047
08.07.2011, 21:36 #9
Skorpi, а где у него простые числа? Простые числа надо самому вводить?
0
silent_1991
08.07.2011, 21:44
  #10

Не по теме:

grizlik78, я вот тоже недопонял...

0
Зоти Сергей
229 / 227 / 13
Регистрация: 18.12.2009
Сообщений: 316
08.07.2011, 22:04 #11
В задаче же не сказано, что числа должны генерироваться. Почему бы их не вводить пользователю?
Иначе, для получения простых чисел, можно было бы использовать Решето Эратосфена, например.
0
silent_1991
Эксперт С++
5005 / 3063 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
08.07.2011, 22:05 #12
Зоти Сергей, задача подразумевает, что надо перебрать все простые числа, не превосходящие N.
0
Зоти Сергей
229 / 227 / 13
Регистрация: 18.12.2009
Сообщений: 316
08.07.2011, 22:17 #13
но не написано же, что не превосходящих 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
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
#include <conio.h>
#include <iostream.h>
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
    int DigitsAmount;
    cout<<"Vvedite kolichestvo chisel N: ";
        cin>>DigitsAmount;
        if(DigitsAmount<=0)
        {
            cout<<"Oshibka!!! N doljno biti > 0";
        }
        int CurrentDigit;
        int BiggestAmountOfTrues=0;
        int Result=0;
        int * SipleDigitsArray = new int [DigitsAmount];
    bool * TestSimpleArray = new bool[DigitsAmount];
        memset(TestSimpleArray, 0x00, sizeof(bool)*DigitsAmount);
    for(int k = 2; k < DigitsAmount; k++)
            TestSimpleArray[k] = true;
    for(int i = 2; i < sqrt(DigitsAmount); i++)
    {
            if(TestSimpleArray[i] == true)
            {
                for(int j = i * 2; j < DigitsAmount; j++)
                {
                        if(!(j % i))
                            TestSimpleArray[j] = false;
                }
                }
        }
        for(int i=0;i<DigitsAmount;i++)
        {
            if(!TestSimpleArray[i])
                    continue;
            CurrentDigit = i;
            cout<<"chislo "<< i+1<< " = :"<<CurrentDigit<<"\n";
 
            int Summ=0;
            for(int j=0;j<32;j++)
                {
                    Summ+=(CurrentDigit>>j)&0x01;
                }
 
                if(Summ>BiggestAmountOfTrues)
                {
                    BiggestAmountOfTrues=Summ;
                        Result=CurrentDigit;
                }
        }
    cout<<"\Chislo v kotorom bolishe vsego edinits = "<<Result;
        getch();
        delete [] TestSimpleArray;
        delete [] SipleDigitsArray;
    return 0;
}
//---------------------------------------------------------------------------
0
silent_1991
Эксперт С++
5005 / 3063 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
08.07.2011, 22:21 #14
Зоти Сергей, ээ... Если одно число не превосходит другое, то автоматически считается, что оно его по значению не превосходит, а не по количеству цифр или любому другому количеству.
0
Зоти Сергей
229 / 227 / 13
Регистрация: 18.12.2009
Сообщений: 316
08.07.2011, 22:28 #15
Согласен.
Добавочный код решает этот вопрос, надеюсь?
0
08.07.2011, 22:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.07.2011, 22:28
Привет! Вот еще темы с ответами:

Найти минимальное число среди положительных чисел и максимальное число среди отрицательных чисел - C++
Никак не могу понять ,как написать эту программу.Помогите пожалуйста. Задан одномерный массив А (10) действительных чисел. Ввести массив...

Среди всех n-битных двоичных чисел указать количество тех, в двоичной записи которых нет k единиц подряд - C++
Помогите пожалуйста понять в чём ошибка! Задание такое: среди всех n-битных двоичных чисел указать количество тех, у которых в двоичной...

Дан одномерный целочисленный массив А из N элементов. Найти в нём максимальное значение среди простых чисел - C++
Здравствуйте,уважаемые программисты!) Помогите решить,пожалуйста, данную задачку в С++: Дан одномерный целочисленный массив А из N...

Найти максимальное число среди чисел, введенных с клавиатуры - C++
Найти максимальное число среди чисел, введенных с клавиатуры. Признак конца ввода-0.Вывести количество введенных чисел. С++ я в тупике


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

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

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