Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.69/54: Рейтинг темы: голосов - 54, средняя оценка - 4.69
zambaldzr
1

В интервале от a до b найти число с наибольшим количеством делителей

26.09.2012, 22:46. Показов 10819. Ответов 35
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
a и b вводятся с клавиатуры,представить в виде функции
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.09.2012, 22:46
Ответы с готовыми решениями:

В заданном интервале найти число, с наибольшим количеством делителей
На вход программы подаются положительные числа a и b. Гарантируется, что а <= b. Найти число из...

Найти в диапазоне от M до N число с наибольшим количеством делителей. Функция: количество делителей заданного числа
Найти в диапазоне от M до N число с наибольшим количеством делителей. Функция: количество делителей...

Найти в диапазоне от M до N число с наибольшим количеством делителей.
Найти в диапазоне от M до N число с наибольшим количеством делителей. Функция: количество делителей...

Дано число P, нужно найти число от 1 до Р, с наибольшим количеством делителей
написал проггу, что не правильно уже 3 часа бьюсь... int p; int max=0,a = 0; ...

35
Эксперт С++
261 / 191 / 10
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
26.09.2012, 23:06 2
Автор, какие твои идеи по поводу решения ?
0
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 09:23 3
ввести а и б,сделать цикл от а до б,вложить цикл,тело которого нацело делит число а на все от 1 до а,каждый раз когда это происходит к какой-нибудь переменной прибавляется 1,после того как приращение прекращается цикл останавливается и выводятся все числа с наибольшим числом делителей
0
Эксперт С++
261 / 191 / 10
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
27.09.2012, 09:43 4
Ок, как это выглядит в коде ?
0
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 09:58 5
наверное в этом и вся проблема
непонятно как реализовать пользовательскую функцию
и каким образом установить этот самый предел для количества делителей,по которому будут выбираться числа
0
Эксперт С++
261 / 191 / 10
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
27.09.2012, 10:09 6
Всё очень просто. Каждый раз, когда ты встретишь новое число и посчитаешь его кол-во делителей, сравнивай его с максимумом, к-рый ты запомнил. Если у этого числа делителей больше - замени максимум. Запоминать нужно как число, так и кол-во его делителей.
0
96 / 748 / 279
Регистрация: 11.04.2012
Сообщений: 971
27.09.2012, 10:44 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 <stdio.h>
#include <conio.h>
 
int devident(int a, int b, int* pnum)
{
    int max = 0, num = 0;
    for (int n = a; n <= b; n++)
    {
        int count = 0;
        for (int d = 1; d <= n; d++)
            if ((n % d) == 0) count++;
 
        if (count > max)
        {
            max = count;
            num = n;
        }
    }
 
    if (pnum != NULL) *pnum = num;
 
    return max;
}
 
 
int main()
{
    int a = 0, b = 0, num = 0;
    printf("a = "); scanf("%d",&a);
    printf("b = "); scanf("%d",&b);
 
    int max = devident(a,b, &num);
    printf("number = %d devidents = %d\n",num, max);
 
    _getch();
 
    return 0;
}
1
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 10:53 8
Цитата Сообщение от zitxbit Посмотреть сообщение
for (int d = 1; d <= n; d++)
if ((n % d) == 0) count++;
бесполезные итерации
на 1 делится всегда и делитель больше чем половина числа быть не может
следовательно
C++
1
2
for  (int d = 2; d <= n/2; d++)
 if ((n % d) == 0) count++;
Добавлено через 2 минуты
и count изначально инициализировать 2 (число всегда делится на 1 и на самого себя)
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 11:07 9
ValeryS, тогда уж еще усовершенствуйте свой алгоритм, рассматривая делители в диапазоне от 2 до https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}. При этом если число n делится на i из этого диапазона, то оно делится и на n/i. Поясню. если n=ab и https://www.cyberforum.ru/cgi-bin/latex.cgi?2\leq a\leq b, то либо https://www.cyberforum.ru/cgi-bin/latex.cgi?a=b=\sqrt{n}, либо
https://www.cyberforum.ru/cgi-bin/latex.cgi?a<\sqrt{n} и https://www.cyberforum.ru/cgi-bin/latex.cgi?b>\sqrt{n}
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 11:14 10
Цитата Сообщение от Thinker Посмотреть сообщение
ValeryS, тогда уж еще усовершенствуйте свой алгоритм, рассматривая делители в диапазоне от 2 до
корень брать много машинного времени а деление на 2 просто сдвиг (1 такт)
и не понятно выиграю я или нет
на малых итерациях точно проиграю,
например от 2 до 9
цикл 2 3 4
на больших может выиграю(надо считать)
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 11:17 11
Цитата Сообщение от ValeryS Посмотреть сообщение
корень брать много машинного времени
Почему же, либо берете один раз корень, либо делаете проверку i*i <= n.
При этом экономите кучу времени, не делая пробных лишних делений, если числа большие.
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 11:23 12
хорошо попробую
но учти пишу прямо в посте, не проверял, могут быть алгоритмические ошибки
C++
1
2
3
4
5
6
7
8
for  (int d = 2; d *d<= n; d++)
    {
      if(d *d== n)
        coint++; 
     else  
      if ((n % d) == 0) 
                 count+=2;
    }
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 11:41 13
Лучший ответ Сообщение было отмечено как решение

Решение

Зачем лишние проверки, лучше уж так
C++
1
2
3
4
5
for  (d = 2; d * d < n; d++)
   if (n % d == 0) 
      count += 2;
if(d * d == n)
   count++;
А можно и так
C++
1
2
3
for  (d = 2; d * d < n; d++)
   count += ((n % d == 0) << 1);
count += (d * d == n);
3
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 11:47 14
Цитата Сообщение от Thinker Посмотреть сообщение
Зачем лишние проверки, лучше уж так
только при d * d == n
у тебя coint увеличится на 3
сначала на 2 в одном условии и еще на 1 во втором
а делитель то один
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 11:48 15
внимательнее на for посмотрите, условие там d*d < n
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 12:42 16
Цитата Сообщение от Thinker Посмотреть сообщение
внимательнее на for посмотрите, условие там d*d < n
пардон не заметил
просто на автомате подумал что вторая проверка в теле цикла
но тогда d нужно объявить за пределами цикла
нужно обговорить для начинающих
Цитата Сообщение от Thinker Посмотреть сообщение
C++
1
2
3
for (d = 2; d * d < n; d++)
 count += ((n % d == 0) << 1);
count += (d * d == n);
Вот это круто
вообще нет переходов
но боюсь не все поймут
да и явно привести надо буля к инту а то может не умножится
хотя не проверял верю на слово
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 12:47 17
логические выражения типа (a < b) и т.д. приводятся к 0 или 1 в зависимости от истины, так что здесь все нормально
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 12:53 18
Цитата Сообщение от Thinker Посмотреть сообщение
логические выражения типа (a < b) и т.д. приводятся к 0 или 1
это то я знаю , точнее приводятся false(0) и true (1)
я просто экспериментировал
C++
1
2
3
4
bool t=false;// t=0;
t++; // t= true =1 
t++; // t= true =1 
t++; // t= true =1
и никакой 2 (хотя она тоже true) не возникало
вот и возник вопрос
C++
1
int m=true<<1;
будет m равна 2 или нет (просто не проверял)
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 12:56 19
Ну, в крайнем случае можно к типу int привести, это уже не страшно. Тоже не проверял еще
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 13:23 20
Thinker,
проверил работает
причем сравнил три алгоритма (правда на глаз, точных замеров не делал)
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
#include "stdafx.h"
 int fnc(long long int n)
{
  long long int d; 
   int count=2;
    for (d = 2; d * d < n; d++)
     count += ((n % d == 0) << 1);
    count += (d * d == n);
 return count;
 }
 int fnc1(long long int n)
{
  long long int d; 
   int count=2;
 for (d = 2; d * d <= n; d++)
   {
      if(d *d== n)
        count++; 
     else  
      if ((n % d) == 0) 
            count+=2;
    }
 return count;
 }
int fnc2(long long int n)
{
   long long int d; 
   int count=0;
    for (d = 1; d <= n; d++)
     if(n % d == 0) 
         count++;
    return count;
 }
int _tmain(int argc, _TCHAR* argv[])
{
   int k= fnc(1000000000000);
   int m=fnc1(1000000000000);
   int p=fnc2(1000000000000);
   printf("%d %d %d",k,m,p);
    return 0;
}
fnc и fnc1 менее секунды
fnc2 после 5 минут устал ждать и отрубил программу
1
27.09.2012, 13:23
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.09.2012, 13:23
Помогаю со студенческими работами здесь

Найти число с наибольшим количеством делителей из числового промежутка
Помогите решить задачу, пожалуйста, не понимаю как правильно ее реализовать Задан промежуток от...

Найти в диапазоне от M до N число с наибольшим количеством делителей. PHP
Есть форма, в которую мы вводим значения M и N. Ее я написал: &lt;html&gt; &lt;head&gt; &lt;/head&gt; &lt;body&gt;...

Дано n целых чисел. Найти среди них число с наибольшим количеством делителей
Дано n целых чисел.Найти среди них число с наибольшим количеством делителей.

Найти и вывести первое число в интервале a, b с количеством делителей равным c
Даны три натуральных числа a,b,c. Составить программу,которая находит и выводит первое число в...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru