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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.74
zambaldzr
Сообщений: n/a
26.09.2012, 22:46     В интервале от a до b найти число с наибольшим количеством делителей #1
a и b вводятся с клавиатуры,представить в виде функции
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.09.2012, 22:46     В интервале от a до b найти число с наибольшим количеством делителей
Посмотрите здесь:

C++ Найти столбец матрицы с наибольшим количеством нулей
C++ Найти паралелограмм с наибольшим количеством точек
Определить натуральное число не больше заданного n с наибольшим числом простых делителей C++
C++ Имеется 15 строк, найти строку с наибольшим количеством слов палиндромов
C++ Найти слово с наибольшим количеством гласных букв
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Andrew_Lvov
Эксперт C++
 Аватар для Andrew_Lvov
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 758
Записей в блоге: 1
26.09.2012, 23:06     В интервале от a до b найти число с наибольшим количеством делителей #2
Автор, какие твои идеи по поводу решения ?
Zambal
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 09:23     В интервале от a до b найти число с наибольшим количеством делителей #3
ввести а и б,сделать цикл от а до б,вложить цикл,тело которого нацело делит число а на все от 1 до а,каждый раз когда это происходит к какой-нибудь переменной прибавляется 1,после того как приращение прекращается цикл останавливается и выводятся все числа с наибольшим числом делителей
Andrew_Lvov
Эксперт C++
 Аватар для Andrew_Lvov
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 758
Записей в блоге: 1
27.09.2012, 09:43     В интервале от a до b найти число с наибольшим количеством делителей #4
Ок, как это выглядит в коде ?
Zambal
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 09:58     В интервале от a до b найти число с наибольшим количеством делителей #5
наверное в этом и вся проблема
непонятно как реализовать пользовательскую функцию
и каким образом установить этот самый предел для количества делителей,по которому будут выбираться числа
Andrew_Lvov
Эксперт C++
 Аватар для Andrew_Lvov
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 758
Записей в блоге: 1
27.09.2012, 10:09     В интервале от a до b найти число с наибольшим количеством делителей #6
Всё очень просто. Каждый раз, когда ты встретишь новое число и посчитаешь его кол-во делителей, сравнивай его с максимумом, к-рый ты запомнил. Если у этого числа делителей больше - замени максимум. Запоминать нужно как число, так и кол-во его делителей.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
27.09.2012, 10:44     В интервале от a до b найти число с наибольшим количеством делителей #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;
}
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.09.2012, 10:53     В интервале от a до b найти число с наибольшим количеством делителей #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 и на самого себя)
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 11:07     В интервале от a до b найти число с наибольшим количеством делителей #9
ValeryS, тогда уж еще усовершенствуйте свой алгоритм, рассматривая делители в диапазоне от 2 до http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}. При этом если число n делится на i из этого диапазона, то оно делится и на n/i. Поясню. если n=ab и http://www.cyberforum.ru/cgi-bin/latex.cgi?2\leq a\leq b, то либо http://www.cyberforum.ru/cgi-bin/latex.cgi?a=b=\sqrt{n}, либо
http://www.cyberforum.ru/cgi-bin/latex.cgi?a<\sqrt{n} и http://www.cyberforum.ru/cgi-bin/latex.cgi?b>\sqrt{n}
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.09.2012, 11:14     В интервале от a до b найти число с наибольшим количеством делителей #10
Цитата Сообщение от Thinker Посмотреть сообщение
ValeryS, тогда уж еще усовершенствуйте свой алгоритм, рассматривая делители в диапазоне от 2 до
корень брать много машинного времени а деление на 2 просто сдвиг (1 такт)
и не понятно выиграю я или нет
на малых итерациях точно проиграю,
например от 2 до 9
цикл 2 3 4
на больших может выиграю(надо считать)
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 11:17     В интервале от a до b найти число с наибольшим количеством делителей #11
Цитата Сообщение от ValeryS Посмотреть сообщение
корень брать много машинного времени
Почему же, либо берете один раз корень, либо делаете проверку i*i <= n.
При этом экономите кучу времени, не делая пробных лишних делений, если числа большие.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.09.2012, 11:23     В интервале от a до b найти число с наибольшим количеством делителей #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;
    }
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 11:41     В интервале от a до b найти число с наибольшим количеством делителей #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);
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.09.2012, 11:47     В интервале от a до b найти число с наибольшим количеством делителей #14
Цитата Сообщение от Thinker Посмотреть сообщение
Зачем лишние проверки, лучше уж так
только при d * d == n
у тебя coint увеличится на 3
сначала на 2 в одном условии и еще на 1 во втором
а делитель то один
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 11:48     В интервале от a до b найти число с наибольшим количеством делителей #15
внимательнее на for посмотрите, условие там d*d < n
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.09.2012, 12:42     В интервале от a до b найти число с наибольшим количеством делителей #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);
Вот это круто
вообще нет переходов
но боюсь не все поймут
да и явно привести надо буля к инту а то может не умножится
хотя не проверял верю на слово
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 12:47     В интервале от a до b найти число с наибольшим количеством делителей #17
логические выражения типа (a < b) и т.д. приводятся к 0 или 1 в зависимости от истины, так что здесь все нормально
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.09.2012, 12:53     В интервале от a до b найти число с наибольшим количеством делителей #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 или нет (просто не проверял)
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 12:56     В интервале от a до b найти число с наибольшим количеством делителей #19
Ну, в крайнем случае можно к типу int привести, это уже не страшно. Тоже не проверял еще
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2012, 13:23     В интервале от a до b найти число с наибольшим количеством делителей
Еще ссылки по теме:

Дан одномерный целочисленный массив. Определить элемент с наибольшим количеством делителей C++
C++ Найти слова с наибольшим количеством гласных букв
C++ Число с наибольшим количеством делителей

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
27.09.2012, 13:23     В интервале от a до b найти число с наибольшим количеством делителей #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 минут устал ждать и отрубил программу
Yandex
Объявления
27.09.2012, 13:23     В интервале от a до b найти число с наибольшим количеством делителей
Ответ Создать тему
Опции темы

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