Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.12.2017, 16:33   #1
Ace_400
 
Регистрация: 08.11.2017
Сообщений: 9
По умолчанию Среди простых чисел, не превосходящих заданного N, найти такое, в двоичной записи которого содержится минимальное число нулей.

Есть какие-то предложения как это делать?
Ace_400 вне форума Ответить с цитированием
Старый 22.12.2017, 16:39   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Нули считать, в цикле. Или пользуясь битовыми операциями, или с преобразованием в строку
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 22.12.2017, 17:14   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Код:
int min_zero_value = 2;
int min_cnt = countZero(i);

цикл i от 2 до N-1 делать
   если isPrime(i) тогда
        int cnt = countZero(i);
        если cnt<min_cnt тогда {
             min_zero_value = i;
             min_cnt = cnt;
        }
}
функция для подсчёта нулей в двоичной записи числа:
Код:
int countZero(int x)
{
	int t=x;
	int cnt=0;
	do{
	  if(t%2==0)
	    cnt++;
	  t/=2;  
	} while (t>0);
	return cnt;
}
что же касается проверки числа простое оно или нет (isPrime) то готовую функцию легко найти на форуме.
например, ТЫЦ
так же можно организовать поиск простых чисел с помощью решета Эратосфена (более эффективно).

Последний раз редактировалось Serge_Bliznykov; 22.12.2017 в 17:52.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 22.12.2017, 20:28   #4
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,536
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
можно организовать поиск простых чисел с помощью решета Эратосфена (более эффективно).
Но, наверно, более затратно по памяти: нужен массив размером N, первоначально заполненный натуральным рядом.
А решение очевидно: 1 . Число несомненно простое, и ни одного нуля в его двоичной записи. Если 1 не годится - тогда 3 . Или 7.

Последний раз редактировалось digitalis; 22.12.2017 в 20:30.
digitalis вне форума Ответить с цитированием
Старый 23.12.2017, 01:02   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от digitalis Посмотреть сообщение
1 . Число несомненно простое
это не простое число.

Цитата:
Сообщение от digitalis Посмотреть сообщение
Если 1 не годится - тогда 3 . Или 7.
ну, в принципе согласен. куда уж меньше нуля то.
ну тут тоже есть подводные камни.
во-первых, могут задать N меньше 3-х
во-вторых, фразу "в двоичной записи которого содержится минимальное число нулей." можно трактовать так: нули в двоичной записи должны быть (раз "содержит"), но их должно быть минимальное число.
(впрочем, тогда всегда ответ 2 )

p.s. а вообще это очередная учебная задача, вся суть в том, чтобы научить программировать.
и тут уже неважно что делать - нули в записи искать или двоичную запись в обратном порядке выводить. Смысл не в результате, а в процессе!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 23.12.2017, 11:52   #6
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,536
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
Смысл не в результате, а в процессе!
Вот это меня всегда и убивает в учебных задачах - зачастую полнейшая высосанность из пальца и оторванность от чего-нибудь хоть минимально конкретного. Мне довелось помогать одному студню решать практикум по Фортрану, так там число в таких тысячных степенях, что если разделить размеры видимой Вселенной на размер атома - все равно оочень много порядков остается в запасе. Зачем нужны числа, которыми нечего описать? Ну научатся они нолики считать, а попадется в жизни банальная FFT - ой, мамочки! ...
"Зачем нужна дорога, если она не ведет к храму ? "
digitalis вне форума Ответить с цитированием
Старый 23.12.2017, 22:01   #7
Ace_400
 
Регистрация: 08.11.2017
Сообщений: 9
По умолчанию

Спасибо вам огромное!
Ace_400 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
С++ Найти сумму всех простых чисел, не превосходящих заданного числа n Defx Помощь студентам 1 23.03.2017 12:50
Для заданного М вывести все квадраты натуральных чисел,не превосходящих М (Язык Си) EnigmaFL Помощь студентам 4 16.02.2017 10:49
В каждой строке вибираеться минимальное число, а затем среди этих чисел вибираеться максимально. Вивести на экран номер строки в котором находится это число. Анастасия3006 Помощь студентам 1 26.12.2016 01:20
Поиск всех простых чисел, не превосходящих заданного N Placebo228 Общие вопросы C/C++ 1 06.11.2012 22:42
Среди чисел найти первое число, большее n Кристина Н Паскаль, Turbo Pascal, PascalABC.NET 5 01.12.2011 20:31