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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.74
zambaldzr
Сообщений: n/a
#1

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

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

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

Найти в тексте все слова с наибольшим количеством гласных букв русского алфавита C++
C++ Найти столбец матрицы с наибольшим количеством нулей
C++ Найти паралелограмм с наибольшим количеством точек
Определить натуральное число не больше заданного n с наибольшим числом простых делителей C++
C++ Имеется 15 строк, найти строку с наибольшим количеством слов палиндромов
C++ Найти слово с наибольшим количеством гласных букв
Дан одномерный целочисленный массив. Определить элемент с наибольшим количеством делителей C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 14:41     В интервале от a до b найти число с наибольшим количеством делителей #21
Цитата Сообщение от ValeryS Посмотреть сообщение
fnc и fnc1 менее секунды
fnc2 после 5 минут устал ждать и отрубил программу
Видите как важна оптимизация, если она возможна можете для наглядности еще алгоритм из поста 8 добавить
ValeryS
Модератор
6485 / 4951 / 455
Регистрация: 14.02.2011
Сообщений: 16,400
27.09.2012, 15:56     В интервале от a до b найти число с наибольшим количеством делителей #22
Цитата Сообщение от Thinker Посмотреть сообщение
Видите как важна оптимизация,
Кто бы спорил
я просто прикинул что если даже секунду проходит 100 000 000 итераций цикла (это слишком оптимистично)
то 3 алгоритм (не оптимизированный) будет продолжатся 10 000 секунд а это около 3 часов

Цитата Сообщение от Thinker Посмотреть сообщение
можете для наглядности еще алгоритм из поста 8 добавить
будет 5 000 секунд
слишком долго ждать, жизнь коротка
Zambal
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 16:25     В интервале от a до b найти число с наибольшим количеством делителей #23
ValeryS, спасибо за код
сейчас попробую перебрать все для себя
и с математикой наконец разобраться
ValeryS
Модератор
6485 / 4951 / 455
Регистрация: 14.02.2011
Сообщений: 16,400
27.09.2012, 17:35     В интервале от a до b найти число с наибольшим количеством делителей #24
Zambal,
спасибо то не только мне а и Thinker, самый оптимальный код он предложил в 13 посте (2 листинг)
может можно еще как нибудь оптимизировать. но я не знаю как
Zambal
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 18:11     В интервале от a до b найти число с наибольшим количеством делителей #25
как я понял,мой ход мыслей был правильный,но меня сбивало непонимание функций
теперь мучаюсь с массивом, нужно вывести несколько чисел, если у них одинаковое максимальное число делителей

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
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <windows.h>
int devident(int a, int b, int *pnum)
{
    int max = 0, m=0, d;
    int *num = new int[m];
    for (int n = a; n <= b; n++)
    {
        int count = 2;
        for  (d = 2; d * d < n; d++)
            count += ((n % d == 0) << 1);
                count += (d * d == n);
        if (count > max)
        {
            max = count;
            num[m] = n;
        }
    }
 
    if (pnum != NULL) *pnum = num[m];
 
    return max;
}
 
 
int main()
{
    int a = 0, b = 0, m = 0;
    int *num = new int[m];
    printf("a = "); scanf("%d",&a);
    printf("b = "); scanf("%d",&b);
 
    int max = devident(a,b, &num[m]);
    printf("number = %d devidents = %d\n",num[m], max);
 
    _getch();
    system("pause");
    return 0;
ValeryS
Модератор
6485 / 4951 / 455
Регистрация: 14.02.2011
Сообщений: 16,400
27.09.2012, 18:11     В интервале от a до b найти число с наибольшим количеством делителей #26
Thinker, вот как твою функцию компильнул VS2008
вообще ни одного ветвления
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
text:00401050 loc_401050:                             ; CODE XREF: _main+2Bj
.text:00401050                 mov     eax, 0F4240h
.text:00401055                 cdq
.text:00401056                 idiv    ecx
.text:00401058                 neg     edx
.text:0040105A                 sbb     edx, edx
.text:0040105C                 inc     ecx
.text:0040105D                 mov     eax, ecx
.text:0040105F                 imul    eax, ecx
.text:00401062                 inc     edx
.text:00401063                 cmp     eax, 0F4240h
.text:00401068                 lea     esi, [esi+edx*2]
.text:0040106B                 jl      short loc_401050
.text:0040106D                 mov     edx, ecx
.text:0040106F                 imul    edx, ecx
.text:00401072                 xor     eax, eax
.text:00401074                 cmp     edx, 0F4240h
.text:0040107A                 setz    al
.text:0040107D                 add     eax, esi
.text:0040107F                 mov     edi, eax
.
но это если аргумент int
но если long long
сразу пошли jz jnz....
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 18:30     В интервале от a до b найти число с наибольшим количеством делителей #27
Вот еще быстрее вариант
C++
1
2
3
4
5
6
7
8
9
10
11
unsigned long Count(unsigned long a)
{
   unsigned long i = 2, d = 1, count = 2;
   if (a == 1 || a == 2)
      return a;
   d += (a & 1);
   i += (a & 1);
   for(; i * i < a; i += d)
      count += (a % i == 0) << 1;
   return count + (i * i == a);
}
Такая функция числа от 1 до 1 000 000 обрабатывает за 2 сек.
Andrew_Lvov
Эксперт С++
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 758
Записей в блоге: 1
27.09.2012, 19:48     В интервале от a до b найти число с наибольшим количеством делителей #28
Народ, не могу вьехать в определение кол-ва делителей.
Сколько делителей у числа 12 или 720 ?
ValeryS
Модератор
6485 / 4951 / 455
Регистрация: 14.02.2011
Сообщений: 16,400
27.09.2012, 20:10     В интервале от a до b найти число с наибольшим количеством делителей #29
Цитата Сообщение от Andrew_Lvov Посмотреть сообщение
числа 12
1 2 3 4 6 12 итого 6 делителей
Цитата Сообщение от Andrew_Lvov Посмотреть сообщение
или 720
лень мне сам считай

Добавлено через 1 минуту
прога показала 30 делителей по всем трем алгоритмам
Zambal
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 21:12     В интервале от a до b найти число с наибольшим количеством делителей #30
ValeryS, что требуется изменить в коде,чтобы числа в массив записывались и выводились в строку.если имеют одинаковое кол-во делителей?
ValeryS
Модератор
6485 / 4951 / 455
Регистрация: 14.02.2011
Сообщений: 16,400
27.09.2012, 21:32     В интервале от a до b найти число с наибольшим количеством делителей #31
здесь я вижу такое решение
выделить нахождение общих делителей в отдельную функцию
в первом цикле ты ищешь число с максимальным количеством делителей
во втором цикле сравниваешь и выводишь на экран(без записи в массив)
например так fnc это функция нахождения общих делителей
MaxCount максимальное число общих делителей
C++
1
2
3
for(int i=a;i<=b;i++)
  if(MaxCount==fnc(i))
      printf ("%d %d \n",i MaxCount )
решение не оптимальное "в лоб" но самое простое
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.09.2012, 03:20     В интервале от a до b найти число с наибольшим количеством делителей #32
Вариант (при поиске в большом интервале будет самым быстрым из здесь приведенных):
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
unsigned long f(unsigned long a)
{
    if (a == 1 || a == 2)
      return a;
    unsigned long n=(unsigned long)sqrt((double)a), i, tmp=0, res;  
    while(a%2==0)
    {
        tmp++;
        a/=2;
    }
    res=tmp;
    for(i=3; i<=n && a>1; i+=2)
        if(a%i==0)
        {
            tmp=0;
            while(a%i==0)
            {
                tmp++;
                a/=i;
            }
            res=res+tmp+res*tmp;
        }
    if(a>1)
        res=res*2+1;
    return res+1;
}
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.09.2012, 14:26     В интервале от a до b найти число с наибольшим количеством делителей #33
Сообщение было отмечено автором темы, экспертом или модератором как ответ
valeriikozlov, вот функция, которая работает быстрее, чем все предыдущие функции данного раздела, причем в разы
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
unsigned long Count(unsigned long a)
{
   unsigned long count = 1, k = 0, i;
   if (a == 1 || a == 2)
      return a;
   while ((a & 1) == 0)
   {
      k++;
      a >>= 1;
   }
   if (a == 1)
      return k + 1;
   else
      count = k + 1;
   for(i = 3; i*i <= a; i += 2)
   {
      k = 0;
      while(a % i == 0)
      {
         k++;
         a /= i;
      }
      count *= (k + 1);
   }
   if (a > 1)
      count <<= 1;
   return count;
}
Можно еще быстрее сделать.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.09.2012, 17:53     В интервале от a до b найти число с наибольшим количеством делителей #34
Цитата Сообщение от Thinker Посмотреть сообщение
valeriikozlov, вот функция, которая работает быстрее, чем все предыдущие функции данного раздела
я хотел этот вариант тоже показать, но в следующем посте.

Цитата Сообщение от Thinker Посмотреть сообщение
Можно еще быстрее сделать.
А вот это уже интересно было бы увидеть.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.09.2012, 18:24     В интервале от a до b найти число с наибольшим количеством делителей #35
Вы наверное у же видели вариант с дополнительной памятью
Быстрое нахождение количества делителей натурального числа
пока только в этом направлении вижу ускорение алгоритма. Хотелось бы, чтобы модераторы отнесли ту тему в большую коллекцию решенных задач , так как такая тема актуальна, часто возникает и очень удобно ее найти там будет, но они почему-то не хотят...

valeriikozlov, спасибо Вам за свой алгоритм, он натолкнул меня на мысль, что отбрасывать делители ( n /= i) эффективнее, что так и оказалось, поэтому алгоритм из поста 33 получился быстрым.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.09.2012, 19:14     В интервале от a до b найти число с наибольшим количеством делителей
Еще ссылки по теме:

C++ Найти слова с наибольшим количеством гласных букв
Найти в двумерном массиве строку с наибольшим количеством одинаковых элементов C++
C++ Число с наибольшим количеством делителей
Найти количество и тип домов с наибольшим общим количеством квартир C++
В заданном интервале найти число, с наибольшим количеством делителей C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.09.2012, 19:14     В интервале от a до b найти число с наибольшим количеством делителей #36
Цитата Сообщение от Thinker Посмотреть сообщение
Вы наверное у же видели вариант с дополнительной памятью
быстрое нахождение количества делителей натурального числа
нет не видел, только сейчас посмотрел.

Цитата Сообщение от Thinker Посмотреть сообщение
Хотелось бы, чтобы модераторы отнесли ту тему в большую коллекцию решенных задач , так как такая тема актуальна, часто возникает и очень удобно ее найти там будет, но они почему-то не хотят
Давайте вместе попросим. Я тоже прошу.


Цитата Сообщение от Thinker Посмотреть сообщение
спасибо Вам за свой алгоритм, он натолкнул меня на мысль, что отбрасывать делители ( n /= i) эффективнее, что так и оказалось, поэтому алгоритм из поста 33 получился быстрым.
Не за что.
Yandex
Объявления
28.09.2012, 19:14     В интервале от a до b найти число с наибольшим количеством делителей
Ответ Создать тему
Опции темы

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