На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



Сообщение: 22
ссылка на сообщение  Отправлено: 04.01.22 15:21. Заголовок: P-00 (25) (задача из примера, ошибка в алгоритме)


Здравствуйте! Суть задачи в том, чтобы найти на отрезке числа, которые получаются перемножением двух разных простых чисел (у числа должно быть 4 делителя). Муфаззалов Д.Ф. предлагает решение "без проверки на полный квадрат, так как если число является полным квадратом, то оно имеет нечетное количество делителей" - это все верно, но предложенный алгоритм даст ложные срабатывания, потому что цикл не доходит до корня из числа и счетчик это не учитывает.

Сам алгоритм:


#include <iostream> 
int main()
{
const int divCount =4;
int divs[divCount],i,d;
for( int n = 194455; n <= 194500; n++ )
{
int count = 0;
for( d = 1; d*d < n; d++ )
if( n % d == 0 )
{
divs[count/2] = d;
divs[divCount-count/2-1]=n/d;
count+=2;
if( count > divCount ) break;
}
if (count == divCount)
{
for( i = 0; i < divCount; i++ )
std::cout << divs[ i] << ' ';
std::cout << std::endl;
}
}
}


Если его попробовать на числе 16, то получится закономерный итог "1 2 8 16". Если до корня из числа дойти, то число 16 не учтется, зато теперь число 25 проскочит "1 5 5 25". Так что в любом случае какая-то проверка на квадрат нужна. Проще всего сразу извлекать корень и если окажется, что рассматриваемое число это квадрат другого числа, то дальше не искать делители и переходить к следующему числу

if (pow(int(sqrt(n)), 2) == n) continue;



Алгоритм работает только потому, что попался удачный отрезок. Дальше в объяснении несколько вариаций этого алгоритма с такой же проблемой.

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 13 [только новые]







Сообщение: 1
ссылка на сообщение  Отправлено: 06.01.22 12:48. Заголовок: Можете попробовать н..


Можете попробовать написать решето Эратосфена и циклом идти по простым числам, псевдокод:
for i in range (0, n): 
for j in range (i+1, n):
...

или делать проверку на простоту числа, но тогда i =2;i<sqrt(maxLength), j = i+1;j<sqrt(maxLength).
Примерно так.

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 25
ссылка на сообщение  Отправлено: 06.01.22 13:58. Заголовок: zachto, как решить я..


zachto, как решить я знаю. Я пишу, что в материалах с объяснениями есть ошибка в алгоритме.

Решение с решетом Эратосфена работает существенно дольше, даже если сгенерировать его до квадрата из правой границы. Перебирать его потом не нужно, быстрее с помощью решета искать количество простых делителей.

Спасибо: 0 
ПрофильЦитата Ответить





Сообщение: 3
ссылка на сообщение  Отправлено: 06.01.22 14:24. Заголовок: Решето Эратосфена не..


Решето Эратосфена не нужно писать до квадрата правой границы.

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 27
ссылка на сообщение  Отправлено: 06.01.22 14:31. Заголовок: zachto, и докуда Вы ..


zachto, и докуда Вы предлагаете его генерировать? При переборе придется генерировать до правой границы, деленной пополам. При проверке на простоту, до корня из правой границы.

Спасибо: 0 
ПрофильЦитата Ответить





Сообщение: 5
ссылка на сообщение  Отправлено: 06.01.22 14:41. Заголовок: Ты пишешь решето до ..


Ты пишешь решето до правой границы, пихаешь все найденные числа в вектор или список. Дальше перебираешь уникальные пары простых чисел.

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 29
ссылка на сообщение  Отправлено: 06.01.22 14:52. Заголовок: zachto, зачем правая..


zachto, зачем правая граница, если максимальное по величине простое число, которое теоретически возможно, умножается на 2? В худшем случае end = 2 * primeNumber - куда остальные-то генерировать? Вы границу видели правую? 194500, а можно сгенерировать до 97250 и ничего не потерять. У Вас все такие решения, как эти оба, о которых мы переписываемся?

Спасибо: 0 
ПрофильЦитата Ответить





Сообщение: 7
ссылка на сообщение  Отправлено: 06.01.22 16:20. Заголовок: Справедливое замечан..


Справедливое замечание, однако ваше решение тоже можно ускорить. Например, простоту числа делать не за O(sqrt(n)), а за O(log(n)). Ваши решения все такие долгие?

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 31
ссылка на сообщение  Отправлено: 06.01.22 16:44. Заголовок: однако ваше решение ..



 цитата:
однако ваше решение тоже можно ускорить


А где Вы мое решение увидели? Покажите, пожалуйста, тоже посмотреть на него хочу.

Спасибо: 0 
ПрофильЦитата Ответить





Сообщение: 9
ссылка на сообщение  Отправлено: 06.01.22 17:51. Заголовок: И правда, раз вы ищи..


И правда, раз вы ищите ошибки в авторском решении, своего у вас нет.

 цитата:
Алгоритм работает только потому, что попался удачный отрезок


Опять удача, если меняете входные данные - задача становится другой. Вы хотите общее решение - пишите, присылайте на форум.


Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 32
ссылка на сообщение  Отправлено: 06.01.22 18:14. Заголовок: Ага, так и запишем, ..


Ага, так и запишем, болтнули лишнего.


 цитата:
И правда, раз вы ищите ошибки в авторском решении, своего у вас нет.


А как одно из другого следует расскажите? Что у Вас с логикой?

Теперь давайте еще немного о Вашей логике. Мы говорили о минимальной длине решета, а Вы начали подменять и пытаться говорить о скорости алгоритма на простоту числа. Проверить число по Ферма и я могу, но как это связано с определением минимальной длины решета?


 цитата:
Опять удача, если меняете входные данные - задача становится другой.


И снова проблема с логикой. Вы в алгоритме видите проверку на "удачность отрезка"? И я нет. Автору алгоритма просто повезло, потому что на глаз не определить, попадется ли на таком отрезке число из которого можно извлечь корень четвертой степени и получить простое число.


 цитата:
Вы хотите общее решение - пишите, присылайте на форум.


У Вас снова какие-то проблемы с сооброжалкой. Алгоритм и так является общим решением, а как его пофиксить я тоже указал. Полюбите общие решения и у Вас уменьшатся проблемы с логикой.

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 3162
ссылка на сообщение  Отправлено: 08.01.22 12:50. Заголовок: beep пишет: Муфаззал..


beep пишет:
 цитата:
Муфаззалов Д.Ф. предлагает решение "без проверки на полный квадрат, так как если число является полным квадратом, то оно имеет нечетное количество делителей" - это все верно, но предложенный алгоритм даст ложные срабатывания, потому что цикл не доходит до корня из числа и счетчик это не учитывает.

Спасибо, автор добавил в свои программы проверку на полный квадрат (см. файл ege25.doc).

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Не зарегистрирован
ссылка на сообщение  Отправлено: 08.01.22 12:50. Заголовок: ДФ


Спасибо за обнаруженную ошибку. Исправленное решение выслано Константину Юрьевичу.

Спасибо: 0 
Цитата Ответить



Сообщение: 37
ссылка на сообщение  Отправлено: 11.01.22 12:52. Заголовок: Поляков, ДФ, вам спа..


Поляков, ДФ, вам спасибо за вашу работу и за такие возможности.

Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 5006
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет