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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.70
Skorpi
0 / 0 / 0
Регистрация: 08.07.2011
Сообщений: 7
08.07.2011, 20:21     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #1
Помогите пожалуйста!
Среди простых чисел, не превосходящих n, найти такое, в двоичной записи которого максимальное число единиц.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2011, 20:21     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц.
Посмотрите здесь:

C++ Найти число в двоичной записи которого максимальное число единиц
C++ Найти следующее после n число, в двоичной записи которого столько же единиц
C++ Среди простых чисел, не превосходящих N, найти такое, в десятичной записи которого максимальное число единиц
C++ Найти минимальное число среди положительных чисел и максимальное число среди отрицательных чисел
C++ Найти среди простых чисел, попадающих в этот промежуток, такое число, у которого сумма цифр максимальная
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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;
}
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
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;
}
nameless
Эксперт C++
 Аватар для nameless
289 / 288 / 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;
}
Зоти Сергей
 Аватар для Зоти Сергей
228 / 226 / 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;
}
//---------------------------------------------------------------------------
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
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;
}
xAtom
 Аватар для xAtom
910 / 735 / 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;
}
Skorpi
0 / 0 / 0
Регистрация: 08.07.2011
Сообщений: 7
08.07.2011, 21:26  [ТС]     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #8
Зоти Сергей спасибо большое, работает!
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
08.07.2011, 21:36     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #9
Skorpi, а где у него простые числа? Простые числа надо самому вводить?
silent_1991
08.07.2011, 21:44
  #10

Не по теме:

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

Зоти Сергей
 Аватар для Зоти Сергей
228 / 226 / 13
Регистрация: 18.12.2009
Сообщений: 316
08.07.2011, 22:04     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #11
В задаче же не сказано, что числа должны генерироваться. Почему бы их не вводить пользователю?
Иначе, для получения простых чисел, можно было бы использовать Решето Эратосфена, например.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
08.07.2011, 22:05     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #12
Зоти Сергей, задача подразумевает, что надо перебрать все простые числа, не превосходящие N.
Зоти Сергей
 Аватар для Зоти Сергей
228 / 226 / 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;
}
//---------------------------------------------------------------------------
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
08.07.2011, 22:21     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #14
Зоти Сергей, ээ... Если одно число не превосходит другое, то автоматически считается, что оно его по значению не превосходит, а не по количеству цифр или любому другому количеству.
Зоти Сергей
 Аватар для Зоти Сергей
228 / 226 / 13
Регистрация: 18.12.2009
Сообщений: 316
08.07.2011, 22:28     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #15
Согласен.
Добавочный код решает этот вопрос, надеюсь?
Skorpi
0 / 0 / 0
Регистрация: 08.07.2011
Сообщений: 7
08.07.2011, 22:54  [ТС]     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #16
grizlik78, ага, самому вводить
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
08.07.2011, 22:56     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #17
Skorpi, при чём тогда здесь простые числа, не превышающие n? Эта задача звучала бы тогда примерно так: среди элементов последовательности положительных целых чисел найти такое, в двоичной записи которого максимальное число единиц.
Skorpi
0 / 0 / 0
Регистрация: 08.07.2011
Сообщений: 7
08.07.2011, 23:00  [ТС]     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #18
grizlik78, хм.. я почему то подумал, что их надо самому вводить. Получается они уже должны быть введены в программу?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
08.07.2011, 23:02     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #19
Skorpi, последовательность простых чисел чётко определена. Вы просто вводите ограничитель этой последовательности, остальное программа делает сама.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.07.2011, 23:09     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц.
Еще ссылки по теме:

C++ Определить элемент этого массива, в двоичной записи которого максимальное число единиц
Среди всех n-битных двоичных чисел указать количество тех, в двоичной записи которых нет k единиц подряд C++
C++ Visual Studio. Определить элемент этого массива, в двоичной записи которого максимальное число единиц C++

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

Или воспользуйтесь поиском по форуму:
Skorpi
0 / 0 / 0
Регистрация: 08.07.2011
Сообщений: 7
08.07.2011, 23:09  [ТС]     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц. #20
silent_1991, все понятно.
Yandex
Объявления
08.07.2011, 23:09     Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц.
Ответ Создать тему

Метки
решето эратосфена
Опции темы

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